Форум Flasher.ru - Алгоритмы Алгоритм решения задачи "Лестницы"

Идея примерно такая:
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]