Нахождение возможных комбинаций 1 и 2 с постоянной суммой

Question

Это задача, которую нужно выполнить на C. Можете ли вы сказать мне, как к этому подойти?

Поезд имеет длину n метров. Он состоит из отдельных отсеков длиной 1 или 2 метра. Сколько разных комбинаций таких купе существует для поезда заданной длины? Напишите функцию Train (n), которая вычисляет это.

Answer 1

Начните с самых простых случаев и ищите закономерности.

1. Train (1), очевидно, равно 1: (1).
2. Train (2), очевидно, равно 2: (1 1) и (2).
3. Train (3) равно 3: (1 1 1), (1 2) и (2 1). Первые два можно объединить в (1) с (1 1) и (2). Последние являются именно комбинациями Train (2). Итак, Train (3) есть Train (2) + 1.
4. Train (4) равно 5: (1 1 1 1) (1 1 2) (1 2 1) (2 1 1) (2 2). Опять же, мы можем объединить первое как (1) с (1 1 1), (1 2) и (2 1), которые являются комбинациями Train (3). К последним относятся (2), соединенные с (1 1) и (2), которые являются комбинациями Train (2). Итак, Train (4) - это Train (3) + Train (2). Теперь, оглядываясь на Train (3), мы видим, что + 1 равен Train (1).

Теперь ясно, что Train (n) всегда Train (n - 1) + Train (n - 2). Это и есть определение последовательности Фибоначчи.

Теперь давайте посмотрим, как это переводится на C.

1. Скелет функции: Train принимает один целочисленный аргумент и возвращает целое число:

   int Train (int n) {
   }
   

2. Определение, которое мы разработали:

   int Train (int n) {
       return Train (n - 1) + Train (n - 2);
   }
   

3. Это будет повторяться бесконечно, поэтому мы должны остановить его в базовом случае. Один базовый случай ясен: Train (1) равно 1:

   int Train (int n) {
       if (n == 1) {
           return 1;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

4. Этого все еще недостаточно. Представьте себе, что делает Train (2): он вычислит Train (1) + Train (0). Train (1) не проблема, но Train (0) вычислит Train (-1) + Train (-2), что снова повторяется бесконечно. Итак, нам нужен еще один базовый случай: Train (2) равен 2.

   int Train (int n) {
       if (n == 1) {
           return 1;
       } else if (n == 2) {
           return 2;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

5. Это работает, но мы можем упростить базовые случаи:

   int Train (int n) {
       if (n < 3) {
           return n;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

6. Если вы сейчас просто вставите последний фрагмент кода в домашнее задание, не пройдя предварительные задания «слишком долго не читали», я успешно подорву ваше образование, и вы никогда не научитесь программировать. Добро пожаловать.

7. Это не лучший способ для вычисления чисел Фибоначчи. Зачем? Как вы должны изменить код, чтобы избежать дублирования усилий? Можно ли представить разные подходы? Какие?

Answer 2

Полагаю, эта рекурсивная формула отвечает на вопрос

if (n <= 2) вернуть n <br> Поезд (n) = Поезд (n-1) + Поезд (n-2)

Answer 3

Это простая последовательность Фибоначчи .
Для любого поезда длиной n первая тележка может быть длиной 1 или 2. Это приводит нас к формуле f(n) = f(n - 1) + f(n - 2).

Мне, вероятно, не нужно рассказывать, как вычислять числа Фибоначчи.