TUZ_7-05 Определение позиции числа в массиве Витхофа
7.5. Определение позиции числа в массиве Витхофа
Массив Витхофа – это двумерная таблица, которая характеризуется первой строкой, содержащей последовательность Фибоначчи (1, 2, 3, 5, …). Массив можно определить следующим образом:
- пусть pr обозначает предыдущую строку, cr обозначает текущую строку,
а a и b – первый и второй элементы pr соответственно.
- Первый элемент следующей строки (исключая первую строку) определяется как наименьшее число,
которое не встречается ни в одной из предыдущих строк, и обозначается как c.
- Второй элемент следующей строки определяется на основе следующих двух условий:
- Значение каждого следующего элемента определяется подобно числам в последовательности Фибоначчи
– как сумма двух предыдущих элементов.
Например, пусть x1, x2 и x3 обозначают первую, вторую и третью строки массива Витхоффа.
х1 = 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
х2 = 4, 7, 11, 18, 29, 47, 76, 123, 199, ...
х3 = 6, 10, 16, 26, 42, 68, 110, 178, 288. ...
Согласно правилам, первый элемент x2 равен 4 – наименьшему числу, которого нет в x1.
Чтобы определить второй элемент в x2, используем a = 1 и b = 2 из x1 и c = 4 из x2.
Вычисляем c – a: 4–1 = 3. Поскольку 3 ≠ 2, используем формулу b + 5 и
получаем 7 – значение для второго элемента в x2.
После получения первых двух элементов в x2 мы можем продолжить эту последовательность,
используя алгоритм Фибоначчи. Так, третий элемент получается сложением 7 и 4
– двух предыдущих элементов, в результате получается 11.
Используя аналогичный подход, можно полу- чить x3 из x2.
Цель этой задачи – найти позицию (индекс) заданного числа
n в виде кортежа (строка, столбец).
Ваша задача: написать функцию, которая принимает положительное целое число
n
и возвращает его позицию в виде кортежа (строка, столбец) в массиве Витхофа.
В табл. 7.5 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 7.5. Некоторые ожидаемые результаты для задачи поиска позиции числа в массиве Витхофа |
| n |
Ожидаемый результат |
| 1042 |
(8, 8) |
| 13 |
(0, 5) |
| 127 |
(48, 0) |
| 20022 |
(4726, 1) |
Примечание: нумерация строк и столбцов начинается с нуля