UniLecs #Task. Count and Say
Задача: последовательность Посмотри-и-скажи (Count and Say) — это последовательность целых чисел с первыми пятью слагаемыми:
1, 11, 21, 1211, 111221, …
Каждое последующее число генерируется из предыдущего путём конкатенции цифры, из которой состоит группа одинаковых цифр и количества цифр в этой группе, для каждой группы одинаковых цифр в числе. Например:
- 1 читается как «одна единица», то есть 11
- 11 читается как «две единицы», то есть 21
- 21 читается как «одна двойка, одна единица», то есть 1211
- 1211 читается как «одна единица, одна двойка, две единицы», то есть 111221
- 111221 читается как «три единицы, две двойки, одна единица», то есть 312211
Напишите алгоритм, который определяет n-й член последовательности. Входные данные: n — натуральное число от 1 до 30 включительно.
Вывод: n-й член последовательности.
Пример:
1. n = 1
Output: 1
2. n = 4
Output: 1211
Разбор
Идея простая, для генерации n-го члена мы генерируем предыдущие n-1, зная начальное значение для n=1. Необходимо отслеживать кол-во последовательных символов и ставить это число перед самим символом. Все детали смотрите в реализации.
Реализация
https://gist.github.com/unilecs/5c78be1202647a31c429a1cc8ea83514