Система счисления Фибоначчи

wolf41 · Регистрация: 20.04.2014

Author24 — интернет-сервис помощи студентам

Члены классического ряда Фибоначчи вычисляются по следующему правилу .
Любое натуральное число можно представить в виде суммы неповторяющихся чисел Фибоначчи, например: и так далее.
Закодируем натуральное число следующим образом: если в сумме присутствует число Фибоначчи с номером , то в соответствующей позиции, начиная справа, ставится единица; если число Фибоначчи с номером отсутствует в сумме, в соответствующей позиции ставится ноль, например: .
Последовательность четных чисел от 2 до 500 отсортировали по возрастанию количества единиц в представлении числа в коде Фибоначчи. При равном количестве единиц в представлении чисел раньше идет меньшее число. После сортировки на позиции с номером 150 будет находиться число …

Не понимаю. Мне бы ответ хотя бы правильный, чтобы я к нему пришел

@Somebody · 13.11.2014, 11:35

Это получается фибоначчиева система счисления. Тут не может быть двух единиц подряд. Количество n-значных чисел - F_n.
Последовательность получается:
(000)1, (00)10, (0)100, 1000 ... (00)101, (0)1001, (0)1010, 10001 ... 10101 ...
Количество чисел в каждой группе из n цифр, включая ведущие нули, с k единицами - может быть, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{\left( k+1 \right)} ^ {n-2k+1}}{\left(n-2k+1\right)!}$ ... ну, или что-то похожее. Чётные числа от 2 до 500 сводятся ко всем от 1 до 250, но вот 250 - число не круглое, так что с максимальной длиной числа, которое надо включать в эту последовательность, проблемы...

@palva · 13.11.2014, 13:29

Формулы из задачи выброшены, так что задача не очень понятна. Представление чисел не однозначно, например единица может быть представлена двумя способами. Условия, что не допускаются две единицы подряд в задаче нет, что добавляет неоднозначности.

Добавлено через 1 минуту
wolf41, а задачу не на компьютере надо решать?

@Somebody · 13.11.2014, 15:51

Я тоже думал насчёт неоднозначности представления. Не самая чёткая формулировка, может быть, но всё же там написано:

если в сумме присутствует число Фибоначчи с номером , то в соответствующей позиции, начиная справа, ставится единица

@canadamoscow · 05.10.2020, 19:34

Ответ: 100000101001

На PascalABC.NET программа выглядит так:

Pascal

Function FCC(n: integer; F: array of integer): string; //переводим число n в систему счисления Фиб.
begin
  Result := '';
  var Fimax := f.FindLastIndex(t-> t <= n);
  For var j := Fimax downto 1 do 
   if n >= F[j] then 
     begin Result += '1'; n -= F[j] end 
   else Result += '0'; 
end;
 
begin
 var fib := SeqWhile(1,1, (a,b) -> a + b, fib -> fib <= 500).toArray; //ряд Фибоначчи до 500
 Range(2,500,2) //Создаем массив от 2 до 500 с шагом 2
 .Select(t-> FCC(t,fib)) //Переводим числа в систему счисления Фибоначчи (типа String)
 .Select(t-> (t,t.Count(g→g='1'))) //Создаем кортежи (число в ФСС, кол-во единиц в нём)
 .OrderBy(t->t[1]) //Сортируем массив по правому элементу кортежа (т.е. по кол-ву единиц)
 .ToArray[149][0].Print; //Выбираем 150 элемент, индекс его 149, т.к. первый элемент имеет индекс 0
end.

iifat · 06.10.2020, 05:52

Сообщение от palva

Условия, что не допускаются две единицы подряд в задаче нет

На всякий случай: как понимаю, есть. Прямо в теме — система счисления Фибоначчи. Это вполне себе термин.

@palva · 06.10.2020, 14:44

iifat, здесь я скорее пытался спровоцировать топикстартера на общение или хотя бы проверить его на способность отвечать на вопросы. Но увы! Он брезгует с нами общаться.

wolf41 0 / 0 / 0 Регистрация: 20.04.2014 Сообщений: 58
		1
	Система счисления Фибоначчи 13.11.2014, 10:11. Показов 2978. Ответов 6 Метки нет (Все метки) Члены классического ряда Фибоначчи вычисляются по следующему правилу . Любое натуральное число можно представить в виде суммы неповторяющихся чисел Фибоначчи, например: и так далее. Закодируем натуральное число следующим образом: если в сумме присутствует число Фибоначчи с номером , то в соответствующей позиции, начиная справа, ставится единица; если число Фибоначчи с номером отсутствует в сумме, в соответствующей позиции ставится ноль, например: . Последовательность четных чисел от 2 до 500 отсортировали по возрастанию количества единиц в представлении числа в коде Фибоначчи. При равном количестве единиц в представлении чисел раньше идет меньшее число. После сортировки на позиции с номером 150 будет находиться число … Не понимаю. Мне бы ответ хотя бы правильный, чтобы я к нему пришел 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	13.11.2014, 11:35	2
	Это получается фибоначчиева система счисления. Тут не может быть двух единиц подряд. Количество n-значных чисел - F_n. Последовательность получается: (000)1, (00)10, (0)100, 1000 ... (00)101, (0)1001, (0)1010, 10001 ... 10101 ... Количество чисел в каждой группе из n цифр, включая ведущие нули, с k единицами - может быть, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{\left( k+1 \right)} ^ {n-2k+1}}{\left(n-2k+1\right)!}$ ... ну, или что-то похожее. Чётные числа от 2 до 500 сводятся ко всем от 1 до 250, но вот 250 - число не круглое, так что с максимальной длиной числа, которое надо включать в эту последовательность, проблемы... 1

@palva 4240 / 2937 / 687 Регистрация: 08.06.2007 Сообщений: 9,817 Записей в блоге: 4
	13.11.2014, 13:29	3
	Формулы из задачи выброшены, так что задача не очень понятна. Представление чисел не однозначно, например единица может быть представлена двумя способами. Условия, что не допускаются две единицы подряд в задаче нет, что добавляет неоднозначности. Добавлено через 1 минуту wolf41, а задачу не на компьютере надо решать? 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	13.11.2014, 15:51	4
	Я тоже думал насчёт неоднозначности представления. Не самая чёткая формулировка, может быть, но всё же там написано: если в сумме присутствует число Фибоначчи с номером , то в соответствующей позиции, начиная справа, ставится единица 0

iifat 2719 / 1773 / 187 Регистрация: 05.06.2011 Сообщений: 5,132
	06.10.2020, 05:52	6
	Сообщение от palva Условия, что не допускаются две единицы подряд в задаче нет На всякий случай: как понимаю, есть. Прямо в теме — система счисления Фибоначчи. Это вполне себе термин. 1

@palva 4240 / 2937 / 687 Регистрация: 08.06.2007 Сообщений: 9,817 Записей в блоге: 4
	06.10.2020, 14:44	7
	iifat, здесь я скорее пытался спровоцировать топикстартера на общение или хотя бы проверить его на способность отвечать на вопросы. Но увы! Он брезгует с нами общаться. 1

Система счисления Фибоначчи

Решение