Армянское Радио: Если мы будем поворачивать почти прямую линию вокруг начала координат, то коэффициент корреляции будет меняться от почти единицы (когда линия идёт в направлении (1,1)) до нуля (когда оси координат направлены вдоль осей эллипса инерции) и обратно. Так что при любом пороге она будет оказываться то прямой, то не прямой. Хотя форма меняться не будет.
Так что вам нужно - отличить прямую от ломаной (которая может быть просто шумной прямой), или прямую от дуги? У того, что изображено справа на рисунке, кривизна тоже очень близка к нулю, прямая аппроксимирует эти точки лучше, чем окружность.
AigizK: Не так. Если есть хотя бы одна единица, то надо вообще ни о чём не думать. Ваш вариант сломается на примере "10,5,1, надо получить 11". Он увидит нечётное число и попытается взять пятёрку, что будет ошибкой.
AigizK: Что-то не так. Если считать по моему алгоритму: 1007-5=1002. Следующим шагом, по жадному алгоритму, мы берём 1000. Остаётся 2, и всё решено. Брать 5*2, когда можно брать 1000, алгоритм не рекомендует. Когда мы "объединяем пятачки в пары", то они остаются в кошельке, пока до них не дойдёт очередь.
Вопрос к условию: слово "ровно" в формулировке вопроса не случайно? То есть, требуется ли, чтобы стороны квадратов были параллельны сторонам прямоугольника? В списке требований этого условия нет.
Потому что если квадраты могут располагаться под углом, то приведённые ниже решения неоптимальны. Например, для прямоугольника 120*120 и 5 квадратов они дадут ответ 40, хотя, повернув квадраты на 45 градусов, мы можем увеличить их размер до 42.42 пикселя.
"если нужно запрограммировать как спутник летит - то почитаете книжки по численным методам благо их нынче вагон - с точки зрения программирования - там все гиперпросто."
Вы серьёзно? Спутник летит в несферическом гравитационном поле (Земля - не идеальный шар). На него действует Луна, которая тоже не очень круглая. Скорости достаточно высоки, чтобы начали действовать релятивистские эффекты. В программе всё это придётся задавать и учитывать. Как вы зададите гравитационное поле? Сферическими функциями? Сколько гармоник надо взять, и как они меняются во времени? Или приближением на сетке? Как эту сетку задать (чтобы она уместилась в доступную память), как учитывать в расчётах? Без этих эффектов вы не сможете не то что направить спутник в окно Белого Дома, но даже посадить его на Пентагон. А если вы допустите ошибку в программировании формул - как без понимания математической модели вы будете её искать?
- отличается от старого тем, что массив заполняется с начала, а не с конца. Если учитывать, то надо очень хорошо переписать функцию output: генерировать перестановки придётся в ней. Постановка задачи "плохая" из-за того, что сначала сортировка идёт по наборам, а потом - по перестановкам этого набора. Поэтому программа будет вдвое сложнее.
Про первый порядок - понятно, он лексикографический. Например, для (4,10,1) должно получиться
1,1,1,7
1,1,2,6
1,1,3,5
1,1,4,4
1,2,2,5
1,2,3,4,
1,3,3,3
2,2,2,4
2,2,3,3
Правильно?
Но вот со вторым понять сложно. Ведь перестановки бывают не только циклическими. Уже для примера 1,1,1,1,2,94 их будет 30 штук. В каком порядке их надо вывести?
Алексей: Или я чего-то очень не понимаю, или она будет печатать
10/10/10/10/10/950
20/20/20/20/20/900
...
190/190/190/190/190/50
- и больше ничего (если порядок не важен). То есть, 5 чисел всегда будут одинаковы.
ewb: А что же тогда значит "рассчитать и зафиксировать"? При подсчёте количества способов сами эти способы вы не увидите.
А количество считается так.
Будем считать, что горизонтальная сторона прямоугольника короче вертикальной. Рассмотрим конфигурации, обладающие следующими свойствами:
- нижние k-1 рядов полностью заполнены
- в k-м ряду заполнены клетки b1,b2,..,br (обозначим их множество S)
- в k-м ряду нет ни одной горизонтальной плитки
- все ряды выше k-го пустые.
Нам надо для каждой пары (k,S) посчитать количество допустимых способов P(k,S) заполнения этой фигуры. Для этого для любой пары множеств (S1,S2) считаем число способов R(S1,S2), которыми конфигурацию из (k,S1) можно превратить в (k+1,S2). Это число не зависит от k.
Например, если прямоугольник имеет ширину 3, то
R({},{1})=R({},{3})=R({},{1,2,3}=1
R({1},{})=R({1},{2,3})=1
R({2},{1,3})=1
R({3},{})=R({3},{1,2})=1
R({1,2},{3})=R({1,3},{2})=R({2,3},{1})=1
R({1,2,3},{})=1
Для остальных пар множеств R(S1,S2)=0.
Исходно у нас есть P(1,{})=1. Надо найти P(H+1,{}), где H - высота прямоугольника. Для этого перебираем k от 1 до H, и зная P(k,S) для всех S, находим P(k+1,S) опять же для всех S. Или просто возводим матрицу перехода в степень H.
