Модуль: Числа, поиск, сортировки_Обучение


10. TUZ_3-10 Поиск n-го члена последовательности Калкина–Уилфа


TUZ_3-10 Поиск n-го члена последовательности Калкина–Уилфа

TUZ_3-10 Поиск n-го члена последовательности Калкина–Уилфа
3.10 Поиск n-го члена последовательности Калкина–Уилфа
Дерево Калкина–Уилфа – это корневое двоичное дерево, вершины которого находятся во взаимно однозначном соответствии
с положительными рациональными числами. Корню дерева соответствует число 1, и для любого рационального числа a/b
его левый дочерний элемент соответствует числу a/(a+b), а правый дочерний элемент – числу (a+b)/b.
Каждое рациональное число встречается в дереве ровно один раз.
При выполнении обхода дерева Калкина–Уилфа по уровням генерируется последовательность рациональных чисел,
известная как последовательность Калкина–Уилфа.
Ваша задача: определить функцию, которая принимает положительное целое число n и возвращает n-й член последовательности Калкина–Уилфа, который является рациональным числом.
Рассмотрим следующий пример. Если n = 10, то результатом функции должно быть число 3/5.
Процесс поиска ответа описан ниже.
В табл. 3.10 показаны ожидаемые результаты для некоторых входных данных.
Таблица 3.10. Некоторые ожидаемые результаты для задачи поиска первого объекта, предшествующего k меньшим объектам
n Ожидаемый результат 
11 5/2
2022 32/45
1993 59/43
24 2/7
10 3/5

Алгоритм
Для решения задачи используется поиск в ширину (Breadth-First Search, BFS) – алгоритм обхода графа,
генерирующий последовательность Калкина–Уилфа до n-го члена.
Для хранения узлов последовательности используется структура данных, называемая очередью.
Алгоритм генерирует каждый член последовательности, вычисляя левые и правые дочерние узлы текущего узла и добавляя их в очередь.
В конце возвращается n-й член последовательности.
Вот подробное описание шагов алгоритма.
1. Принимается целое положительное число n.
2. Значение n уменьшается на 1.
3. Создается пустая очередь queue.
4. В очередь добавляется корневой узел (1, 1).
5. Затем запускается цикл, выполняющий следующие шаги n раз:
а) из очереди извлекается следующий узел, и его числитель и знаменатель присваиваются переменным
    parent_num и parent_denom соответственно;
б) вычисляется левый дочерний элемент текущего узла установкой его числителя равным parent_num,
    а знаменателя – равным parent_num + parent_denom;
в) вычисляется правый дочерний элемент текущего узла установкой его числителя равным parent_num + parent_denom,
   а знаменателя  – равным parent_num;
г) левый и правый дочерние узлы добавляются в очередь queue.
6. Из очереди извлекается последний элемент, и его числитель и знаменатель присваиваются переменным final_num и final_denom соответственно.
7. Если знаменатель последнего узла равен 1, то возвращается его числитель как целое число.

Для решения задачи можно использовать модуль queue и создавать очередь с помощью метода Queue
import queue'
....
Q=queue.Queue() # создание очереди
Тогда добавление объекта a в очередь можно осуществить как Q.put(a),
а извлечение элемента из начала очереди как b=Q.get() 


time 1000 ms
memory 256 Mb

Комментарий учителя

     

Обсуждения (0)
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Решения (0)

Решения:

Нет доступных решений