Task 68. Две цифры

Task 68. Две цифры

UniLecs

Задача: сколько n-значных чисел можно составить, используя цифры 4 и 7, в которых три одинаковые цифры не стоят рядом ?

Входные данные: Одно число n, где n <= 30.

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

Пример: 3

447, 474, 747, 774, 477, 744

Вывод: 6.

Идея: искомых однозначных чисел всегда два: 4 и 7.

Искомых двухзначных чисел четыре: 44, 47, 74 и 77.

Искомые n-значные числа будем строить следующим образом. Возьмем все построенные (n – 1)-значные числа и припишем к ним цифру, которая не совпадает с их последней. 

Таким образом получим n-значные числа, которые заканчиваются на 447, 474, 747 и 774. К n-значным числам также отнесем те, которые можно получить из (n – 2)-значных приписыванием двух 4-к или двух 7-к так, чтобы не получилось три последних одинаковых цифры. То есть к n-значным числам добавятся те, которые заканчиваются на 477 и 744.

Если через f(n) обозначить количество искомых n-значных чисел, то получим рекуррентность:

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

Для наглядности рассмотрим пример:

Искомых двузначных чисел четыре: 44, 47, 74, 77

Искомых трехзначных чисел шесть: 447, 474, 747, 774, 477, 744. 

Получаются 

- от двухзначных: 44 - 447, 47 - 474, 74 - 747, 77 - 774

- от однозначных: 4 - 477, 7 - 744

Множество четырехзначных чисел получим из:

- трехзначных чисел, приписав к ним цифру, отличную от последней: 4474, 4747, 7474, 7747, 4774, 7447

- двухзначных чисел, приписав к ним 44 или 77 так чтобы не получить три одинаковые цифры: 4477, 4744, 7477, 7744.

пример

Реализация:

реализация на C#

https://gist.github.com/unilecs/78e6bd8cfb827ba91dfc0ca04a23716e


Тест:

https://dotnetfiddle.net/mKHlYO

Report Page