Лесенка

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 10 мес. назад.

  • Автор
    Сообщения
  • #4550
    @admin

    Задача взята с acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 55%)

    Очень хорошая задача на понимание рекурсии, рекомендую.

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

    Входные данные:
    Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке.

    Выходные данные:
    В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.

    Пример 1:
    INPUT.TXT: 3
    OUTPUT.TXT : 2

    Пример 2:
    INPUT.TXT: 6
    OUTPUT.TXT : 4

    Для начала, предлагаю попробовать вручную построить лесенки. В частности для второго примера:

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

    Есть у нас лесенка из 7 кубиков, сложенных в ряд. В следующий ряд мы можем положить 1, 2 и 3 кубика. 4 кубика переложить уже нельзя, т.к. тогда в первом будет меньше чем во втором. Дальше аналогичным образом обрабатывается второй ряд, третий, четвертый и т.д. Т.е. налицо рекурсивный алгоритм.

    Первый вариант решения (не пройдет все тесты) мог бы выглядеть так:

    #include <fstream>
    using namespace std;
    
    int get_count(int prev_level, int n) {
      if (0 == n)
        return 1;
      
      int count = 0;
      for (int level = 1; level < prev_level; ++level) {
        count += get_count(level, n - level);
      }
      
      return count;
    }
     
    int main() {
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
    
      int n, count = 0;
      ifst >> n;
    
      for (int level = 1; level <= n; ++level) {
        count += get_count(level, n-level);
      }
    }

    В функции main выполняется генерация кубиков в первом уровне. В нем может быть от 1 до n кубиков. Этот код вынесен в main потому что остальные уровни генерируются чуть-чуть иначе, в них должно учитываться число кубиков на предыдущем уровне (для первого уровня нет предыдущего).

    Функция get_count возвращает единицу (лесенку удалось сгенерировать) если количество кубиков равно нулю — т.е. мы каким то корректным образом строили лесенку и у нас кончились кубики. Для остальных случаев мы запускаем рекурсивную функцию с различными наборами данных, уменьшая количество кубиков на текущем уровне и увеличивая на следующем.

    Этот код будет работать корректно, но долго (не пройдет тесты по времени). Чтобы найти проблемное место можно заставить функцию get_count перед своим завершением выводить входные данные и результат (count) в файл или на экран. Мы увидим, что она много раз вызывается для отрицательных значений количества кубиков на уровне (n). Необходимо добавить проверку, что n - level больше ноля.

    #include <fstream>
    using namespace std;
    
    int get_count(int prev_level, int n) {
      if (0 == n)
        return 1;
      
      int count = 0;
      for (int level = 1; level < prev_level; ++level) {
        if ((n - level) < 0) 
          break;
        count += get_count(level, n - level);
      }
      
      return count;
    }
     
    int main() {
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
    
      int n, count = 0;
      ifst >> n;
    
      ofst << get_count(n+1, n);
    }

    В последнем варианте программы убран также цикл из функции main. В самом деле, можно обобщить генерацию первого и последующих уровней если предположить что перед первым есть «нулевой», на котором находится n+1 кубик (заведомо шире любой лесенки из n кубиков).

Для ответа в этой теме необходимо авторизоваться.