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.
Реализация:
https://gist.github.com/unilecs/78e6bd8cfb827ba91dfc0ca04a23716e
Тест: