Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.
Задача
Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.
Вхідні дані
Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.
Вихідні дані
Вивести кількість способів, якими можна заповнити смугу.
Тести
Вхідні дані | Вихідні дані |
---|---|
1 | 1 |
5 | 4 |
12 | 60 |
50 | 122106097 |
Код № 1
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { int n; cin >> n; int F[51] = {0, 1, 1, 2, 3}; for(int i = 5; i <= n; i++) { F[i] = F[i-2] + F[i-3] + F[i-4]; } cout << F[n]; return 0; } |
Рішення 1
Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].
Код № 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; int F[51] = {0, 1, 1, 2, 3}; int numberOfWays(int n) { if(F[n]) { return F[n]; } else { F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4); } return F[n]; } int main() { int n; cin >> n; cout << numberOfWays(n); return 0; } |
Рішення 2
Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.
Посилання
Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone