Задача на рекурсию про лесенку из кубиков [закрыт]

#cpp #рекурсия

        
             
                
                    
                        
                            Закрыт. Этот вопрос необходимо уточнить или дополнить
подробностями. Ответы на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Добавьте больше подробностей
и уточните проблему, отредактировав это сообщение.
                        
                        Закрыт 10 месяцев назад.
                                                                                
           
                
        
Эта тема не вопрос, а работающее решение данной задачи в рекурсивном виде и оно ищет
максимальную высоту лесенки, ничего больше.
Как заметили в комментариях можно решить эту задачу через арифметическую прогрессию.
Лесенкой называется набор кубиков, в котором каждый верхний слой содержит кубиков
меньше, чем в предыдущем. Требуется написать программу вычисляющую число лесенок из
N кубиков.
Очень долго искал в интернете какой-то адекватно работающий вариант и все же решил
сделать сам и помочь кому-то со схожей проблемой. Публикую решение ниже.
Для тех, кто хочет разобраться. Сначала самым первым слоем является только один кубик,
в последующих итерациях создаётся слой длины больший на 1, чем предыдущий. И так до
тех пор, пока не достигается результат.

int layersCount = 1;

int Stairs(int n, int previousLayer)
{

    int thisLayer=0;
    while (thisLayer - previousLayer !=1 && n - (thisLayer + previousLayer)>0)
        thisLayer++;

    if (thisLayer - previousLayer == 1) layersCount += 1;
    if (n - thisLayer-previousLayer > 0)
        return Stairs(n - previousLayer, thisLayer);
    else
        return layersCount;

}

int main()
{
    int n;
    std::cin >> n;

    std::cout << Stairs(n,1);
}

    

Ответы

Ответ 1

Округленное вниз положительное решение квадратного уравнения:

(k + 1) * k / 2 = n

k = floor((-1 + sqrt(1 + 8 * n)) / 2)


(Привет от маленького Гаусса.)


Ответ 2

Задачи "ищет максимальную высоту лесенки" и "число лесенок из N кубиков" - разные. 

Отвечу на вторую, т.к. про неё написано "требуется найти", и приведена более-менее
чёткая формулировка:


  Лесенкой называется набор кубиков, в котором каждый верхний слой
  содержит кубиков меньше, чем в предыдущем. Требуется написать
  программу, вычисляющую число лесенок из N кубиков.


Это число разбиений (partitions) N на различные слагаемые  (1, 1, 2, 2, 3, 4, 5,
6, 8, 10, 12, 15, 18, 22..)

import functools
@functools.lru_cache(maxsize=None)   #простейшая мемоизация
def growparts(n, last):
    if n == 0:
        return 1
    result = 0
    for i in range(last + 1, n + 1):
        result += growparts(n - i, i)
    return result

for k in range(15):
    print(k, growparts(k, 0))