|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
Алгоритм решения задачи "Лестницы"
Добрый день!
Задался решением одной задачки. перепробовал тонну вариантов, но никак не могу найти правильное решение. Подскажите, как быть? Какой алгоритм решения? В интернете наверняка есть готовое решение, но я не искал - не хочу. Желание дойти самому или с вашей помощью)) Спасибо!
__________________
Не стыдно спросить, стыдно не знать ! |
|
|||||
Modus ponens
|
Идея примерно такая:
1. Т.как sum(1..n) = n(n+1)/2, то максимальное количество колонок можно рассчитать зная n - floor(sqrt(n*2)). Это число - количество итераций во внешнем цикле. 2. Высота первой колонки задает количество возможных комбинаций для оставшихся колонок - т.е. следующий вложеный цикл можно делать по высоте первой колонки. 3. Дальше, задачу можно описать рекурсивно: отнимаем от общего количества квадратов высоту самой левой колонки и решаем ту же задачу для разности пока не останемся только с одной дополнительной колонкой (основа рекурсии). Решение, к сожалению, получается что-то ипа n^3 по сложности. Возможно есть аналитическое, более простое решение, но что-то не придумывается. Очень наивное решение на Прологе: split(X, Y) :- split(0, X, Y). split(N, X, [X1 | Y]) :- append(X1, X2, X), length(X1, L1), L1 > N, length(X2, L2), L1 < L2, L3 is L1 * 2 + 1, ( L2 > L3 -> split(L1, X2, Y) ; Y = [X2] ). ladder(N, X) :- findall(E, between(1, N, E), L), aggregate_all(count, split(L, _), X1), X is X1 + 1. first_80 :- findall([X, Y], (between(1, 80, X), ladder(X, Y)), Z), print(Z). Ниже: список первых 80 результатов: [1 1] [2 1] [3 2] [4 2] [5 2] [6 3] [7 4] [8 4] [9 5] [10 7] [11 8] [12 10] [13 12] [14 14] [15 18] [16 22] [17 25] [18 31] [19 37] [20 43] [21 52] [22 62] [23 72] [24 85] [25 100] [26 116] [27 136] [28 159] [29 183] [30 213] [31 247] [32 283] [33 327] [34 376] [35 430] [36 494] [37 565] [38 643] [39 734] [40 836] [41 948] [42 1077] [43 1221] [44 1379] [45 1561] [46 1763] [47 1985] [48 2237] [49 2517] [50 2826] [51 3174] [52 3560] [53 3985] [54 4461] [55 4989] [56 5570] [57 6218] [58 6934] [59 7721] [60 8597] [61 9563] [62 10623] [63 11799] [64 13093] [65 14513] [66 16083] [67 17807] [68 19697] [69 21780] [70 24066] [71 26568] [72 29319] [73 32333] [74 35627] [75 39243] [76 43198] [77 47516] [78 52246] [79 57411] [80 63045]
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 17.07.2016 в 18:20. |
Часовой пояс GMT +4, время: 00:41. |
|
« Предыдущая тема | Следующая тема » |
|
|