Статья Автор: Лебедев Дмитрий

TUZ_2-25 Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа

TUZ_2-25 Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа

TUZ_2-25 Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа
2.25 Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа
Согласно теореме Цекендорфа, любое произвольное положительное целое можно выразить
как сумму (необязательно последовательных) чисел Фибоначчи.
Напишите функцию, которая принимает положительное целое число n и возвращает
список непоследовательных чисел Фибоначчи, сумма которых равна n.
Числа в списке должны следовать в порядке убывания.
В табл. 2.25 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.25. Некоторые ожидаемые результаты для задачи поиска суммы чисел Фибоначчи
n Ожидаемый результат
53  34, 13, 5, 1
25  21, 3,1
31 21, 8, 2
3009  2584, 377, 34, 13, 1

Представление числа в виде суммы различных чисел Фибоначчи может быть неоднозначным (например, 6=5+1=3+2+1). 
Теорема Цекендорфа гарантирует наличие разложения. Любое такое разложение, по аналогии с двоичной системой счисления,
можно записать в виде последовательности из 1 и 0, где вместо степеней числа 2 будут числа Фибоначчи. 
Если наложить на "максимальность представления", то можно получить "фибоначчивая систему счисления Фибоначчи" (ФСС) 
В данной задаче требуется получить такое "максимальное представление":
  • длина списка минимальна
  • числа в списке "максимально убывают"

Алгоритм
.Алгоритм генерирует последовательность чисел Фибоначчи, сортирует ее в порядке убывания
с использованием алгоритма сортировки вставками и выбирает элементы из отсортированной последовательности,
руководствуясь определенными критериями.
Ниже перечислены шаги, выполняемые алгоритмом.
1. Принимается целое положительное число n.
2. Инициализируются переменные:
    previous_fibonacci_number – значением 0,
    current_fibonacci_number – значением 1,
    fibonacci_numbers – списком, содержащим previous_fibonacci_number и current_fibonacci_number,
    selected_fibonacci_numbers – пустым списком, 
    current_sum – суммой previous_fibonacci_number + current_fibonacci_number.
3. Используется цикл while, чтобы сгенерировать числа Фибоначчи до n:
1) добавить current_sum в fibonacci_numbers;
2) обновить previous_fibonacci_number значением current_fibonacci_number;
3) обновить current_fibonacci_number значением current_fibonacci_ number + previous_fibonacci_number;
4) обновить current_sum значением previous_fibonacci_number + current_ fibonacci_number;
5) продолжать выполнять цикл, пока current_sum не станет больше n;
6) отсортировать fibonacci_numbers в порядке убывания.
4. Используется цикл for для выбора чисел Фибоначчи, сумма которых дает в результате n, выполняющий следующие действия:
1) переменная sum_of_fibonacci_numbers инициализируется значением 0;
2) для каждого числа в fibonacci_numbers выполняются следующие действия:
а) если sum_of_fibonacci_numbers + number меньше или равно n, то number добавляется в selected_fibonacci_numbers и переменная sum_of_fibonacci_numbers обновляется значением sum_of_ fibonacci_numbers + number;
б) если sum_of_fibonacci_numbers равна n, то возвращается selected_fibonacci_numbers.
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать