115. Две цифры

Сколько n-значных чисел можно составить, используя только цифры 5 и 9, так чтобы никакие три одинаковые цифры не стояли подряд?

Вход. Одно целое число n (n ≤ 30).

Выход. Выведите количество таких n-значных чисел.

Пример входа	Пример выхода
3	6

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Решение задачи начнём с рассмотрения базовых случаев:

· для n = 1 искомых чисел всего два: 5 и 9.

· для n = 2 искомых чисел всего четыре: 55, 59, 95 и 99.

Обозначим через f(n) количество искомых n-значных чисел. Тогда:

· f(1) = 2;

· f(2) = 4;

Далее будем строить n-значные числа, опираясь на уже построенные числа меньшей длины.

· Добавление одной цифры. Возьмем все построенные (n – 1)-значные числа и припишем к каждому из них цифру, отличную от его последней цифры. Таким образом, получим n-значные числа, оканчивающиеся на 559, 595, 959 и 995. Всего таких чисел f(n – 1).

· Добавление двух одинаковых цифр. К n-значным числам также отнесем те, которые можно получить из (n – 2)-значных, приписав к ним две пятёрки или две девятки так, чтобы в конце не оказалось трёх одинаковых цифр подряд. То есть к n-значным числам добавляются также числа, оканчивающиеся на 599 и 955. Таким образом, получаем ещё f(n − 2) допустимых чисел.

Таким образом, получим следующую рекуррентную формулу:

f(n) = f(n – 1) + f(n – 2),

f(1) = 2, f(2) = 4

Пример

Искомых двузначных чисел четыре: 55, 59, 95 и 99.

Искомых трехзначных чисел шесть: 559, 595, 959, 995, 599 и 955. Они получаются:

· из двузначных чисел: 55 → 559, 59 → 595, 95 → 959, 99 → 995

· из однозначных чисел: 5 → 599, 9 → 955

Все искомые четырёхзначные числа получаются:

· из трёхзначных чисел, приписыванием цифры, отличной от последней: 5595, 5959, 9595, 9959, 5995 и 9559.

· из двузначных чисел, приписыванием 55 или 99 так, чтобы не получить три одинаковые цифры подряд: 5599, 5955, 9599 и 9955.

Реализация алгоритма

Значения f(i) будем хранить в ячейках массива m[i].

int m[31];

Читаем входное значение n.

scanf("%d", &n);

Задаём начальные значения f(1) = 2 и f(2) = 4.

m[1] = 2; m[2] = 4;

Вычисляем значения m[i] (3 ≤ i ≤ n) по рекуррентной формуле.

for(i = 3; i <= n; i++)

m[i] = m[i-1] + m[i-2];

Выводим ответ – значение m[n].

printf("%d\n",m[n]);

Java реализация

import java.util.*;

public class Main

{

public static int MAX = 32;

static int m[] = new int[MAX];

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

m[1] = 2; m[2] = 4;

for(int i = 3; i <= n; i++) m[i] = m[i-1] + m[i-2];

System.out.println(m[n]);

}

}

Python реализация

Читаем входное значение n.

n = int(input())

Инициализируем список m.

m = [0] * 31

Задаём начальные значения f(1) = 2 и f(2) = 4.

m[1] = 2

m[2] = 4

Вычисляем значения m[i] (3 ≤ i ≤ n) по рекуррентной формуле.

for i in range(3, n + 1):

m[i] = m[i - 1] + m[i - 2]

Выводим ответ – значение m[n].

print(m[n])