Внимание: Задача на сайте 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 14 15 16 17 18 |
import java.util.Scanner; class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] F = new int[51]; F[0] = 0; F[1] = 1; F[2] = 1; F[3] = 2; F[4] = 3; for(int i = 5; i <= n; i++) { F[i] = F[i-2] + F[i-3] + F[i-4]; } System.out.println(F[n]); } } |
Рішення 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 21 22 23 |
import java.util.Scanner; public class Main { public static int[] F = new int[51]; public static int numberOfWays(int n){ F[0] = 0; F[1] = 1; F[2] = 1; F[3] = 2; F[4] = 3; if(F[n] > 0) { return F[n]; } else { F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4); } return F[n]; } public static void main (String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(numberOfWays(n)); } } |
Рішення 2
Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.