Фибоначчиева система счисления
Как известно, последовательность Фибоначчи начинается с двух чисел 0 и 1 и каждый последующий член последовательности получается как сумма двух предыдущих. Например, третий член последовательности это 1 ( 1 = 1 + 0 ), четвёртый — 2 ( 2 = 1 + 1 ), пятый — 3 ( 3 = 2 + 1 ) и т.д.
Рисунок 1 — Первые числа последовательности Фибоначчи
Эта последовательность проявляется очень часто и в нашей жизни и в природе и имеет большое значение. А знаете ли Вы, что все положительные целые числа можно представить как сумму чисел из последовательности Фибоначчи? Более того, все натуральные числа можно представить при помощи последовательности Фибоначчи, причём без повторений. Например: 13 может быть представлено из указанного множества как < 13 >, < 5 , 8 >или < 2 , 3 , 8 >а 17 представлено как < 1 , 3 , 13 >или < 1 , 3 , 5 , 8 >. Так как все числа обладают этим свойством (может у Вас есть желание доказать это?), то этот набор является хорошим способом для использования в качестве «базы» (основания системы счисления) для представления чисел. Но, как мы видели выше, некоторые числа могут быть представлены более чем одним способом суммой чисел из последовательности Фибоначчи. Как нам выйти из этой ситуации? Очень просто! Для этого достаточно наложить ограничение, что для предоставления числа нельзя использовать два соседних элемента из последовательности Фибоначчи! Это ограничение объясняется тем, что сумма двух соседних членов последовательности Фибоначчи сама является членом последовательности Фибоначчи.
Теперь, когда мы знаем всё изложенное выше, мы можем предложить хороший способ предоставления любого целого положительного числа. Для этого мы будем использовать двоичную последовательность (только нулей и единиц). Например, 17 = 1 + 3 + 13 (мы должны помнить, что нельзя использовать два последовательных числа Фибоначчи). Будем использовать ноль в записи, если очередное число из последовательности Фибоначчи не используется, и единицу для тех что используются. Тогда, 17 = 100101 (ведущие нули должны быть опущены). На рисунке 2 подробно показано, как получена эта запись и что означают нули и единицы в приведённой выше записи. Для лучшего понимания этой схемы обратим внимание на тот факт, что не использование двух соседних чисел Фибоначчи означает, что двоичная последовательность не будет иметь двух подряд идущих единиц. Используя приведённое представление числа, мы будем говорить, что мы используем Фибоначчиеву систему счисления и записывать его как 17 = 100101 ( fib ).
Рисунок 2 — Объяснение представления числа 17 в Фибоначчиевой системе счисления
Ваша задача состоит в записи заднного десятичного числа в Фибоначчиевой системе счисления.
Входные данные
В первой строке входных данных задано единственное натуральное число N , указывающее на количество примеров в тесте ( 1 ≤ N ≤ 500 ).
Следующие N строк содержат по одному положительному целому числу, не превышающему 100 000 000 . Числа могут быть поданы в произвольном порядке.
Выходные данные
Вы должны вывести по одной строке для каждого из N чисел, полученных во входных данных, в следующем формате: » DEC_BASE = FIB_BASE (fib) «. DEC_BASE это заданное оригинальное число в десятичной системе счисления, а FIB_BASE соответственно — его представление в Фибоначчиевой системе счисления. Образец вывода приведён в примере выходных данных.
Пример
Входные данные #1 content_copy
10 1 2 3 4 5 6 7 8 9 10
Выходные данные #1 content_copy
1 = 1 (fib) 2 = 10 (fib) 3 = 100 (fib) 4 = 101 (fib) 5 = 1000 (fib) 6 = 1001 (fib) 7 = 1010 (fib) 8 = 10000 (fib) 9 = 10001 (fib) 10 = 10010 (fib)
Перевести число 27 из десятичной системы в двоичную
Для того, чтобы перевести число 27 из десятичной системы счисления в двоичную, необходимо осуществить последовательное деление на 2, то тех пор пока остаток не будет меньше чем 2.
| — | 27 | 2 | ||
| 26 | — | 13 | 2 | |
| 1 | 12 | — | 6 | 2 |
| 1 | 6 | — | 3 | 2 |
| 0 | 2 | 1 | ||
| 1 |
Полученные остатки записываем в обратном порядке, таким образом:
Подробнее о том, как переводить числа из десятичной системы в двоичную, смотрите здесь.
Другие переводы числа 27:
- Перевести число 27 из 10-ой в восьмеричную систему
- Перевести число 27 из 8-ой в двоичную систему
- Перевести число 27 из 16-ой в двоичную систему
- Перевести число 27 из 10-ой в троичную систему
- Перевести число 27 из 10-ой в четвертичную систему
- Перевести число 27 из 7 в шестнадцатеричную систему
- Перевести число 27 из 10-ой в шестнадцатеричную систему
- Перевести число 27 из 8-ой в десятичную систему
- Перевести число 27 из 8-ой в шестнадцатеричную систему
- Перевести число 27 из 8-ой в четвертичную систему
- Перевести число 27 из 16-ой в десятичную систему
- Перевести число 27 из 10-ой в пятеричную систему
- Перевести число 27 из 8-ой в пятеричную систему
- Перевести число 27 из 10-ой в десятичную систему
Смотрите также:
- Смотрите также
- Калькуляторы
- Последние переводы
Полезные материалы
- Системы счисления в информатике
- Что такое позиционная система счисления?
- Перевод чисел из десятичной в двоичную систему счисления
Калькуляторы переводов
- Калькулятор из десятичной в двоичную с решением
- Калькулятор из шестнадцатеричной в десятичную с решением
- Калькулятор из восьмеричной в двоичную с решением
- Калькулятор из восьмеричной в шестнадцатеричную с решением
- Калькулятор из шестнадцатеричной в восьмеричную с решением
- Калькулятор из одной системы счисления в другую
Последние примеры переводов из 10-ой в 2-ую систему
- Какое десятичное число соответствует двоичному числу 49.03125?
- Какое десятичное число соответствует двоичному числу 1347?
- Перевод числа 66.76.48.236 из десятичной в двоичную систему
- Перевести 339.393 из десятичной в двоичную систему
- Переведите десятичное число 10110101000 в двоичную систему счисления
- Как перевести 5432.69 из десятичной в двоичную систему счисления?
- Представить десятичное число 01000101 в двоичной системе
- Как представлено число 313.621 в двоичной системе счисления?
- Как перевести 89.09 из десятичной в двоичную систему счисления?
- Как выглядит число 660 в двоичной системе счисления?
Перевод чисел в Фибоначчиеву систему счисления
Представлением натурального числа N в Фибоначчиевой системе счисления называется набор целых значений-цифр (Dn, Dn-1, …, D2), для которого N=DnFn+Dn-1Fn-1+…+D3F3+D2F2, где Di=0 или Di=1, Fi — числа Фибоначчи: F1=F2=1, Fn+2=Fn+Fn+1. К примеру, 20=113+08+15+03+12+01=101010. Во входном файле in.txt содержится последовательность натуральных чисел, например:
20 7 26 17 9
Перевести все заданные целые числа в Фибоначчиевую систему счисления и вывести результат в выходной файл out.txt, например:
101010 1010 1001000 100101 10001
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Перевод чисел из двоичной системы счисления в систему счисления кратной степеням двойки и обратно
Нужно две программы, одна реализует перевод чисел из двоичной системы счисления в систему счисления.
Перевод чисел из 16 системы счисления в 2 систему счисления
Помогите составить программу для перевод чисел из 16 с/c в 2 c/c при условии,что программ может.
Перевод чисел из 10 в 15 систему счисления
Доброго времени суток. Нужно написать программу для перевода введенных с клавиатуры чисел из 10.
Перевод чисел из 10-й в 2-ю систему счисления
Всем привет. Нужна помощь в доработке след.программы: Программа переводит числа из 10-й в 2-ю.
7630 / 6441 / 2937
Регистрация: 14.04.2014
Сообщений: 28,084
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
#include #include #include #include #include #include #include using std::cout; using std::cin; using std::endl; using std::locale; using std::string; int main() { locale::global(locale("")); int n; std::vectorint> F; F.push_back(1); F.push_back(2); string r; std::ofstream ofs("d:\\dataout.txt"); std::ifstream ifs("d:\\data.txt"); if (!ifs) { cout <"Ошибка при открытии файла." ; } else { while (true) { ifs >> n; if (!ifs.good()) break; r.clear(); while (*(F.rbegin()) n) F.push_back(*(F.rbegin()) + *(F.rbegin() + 1)); std::vectorint>::reverse_iterator i = F.rbegin(); while (*i > n) ++i; for (; i != F.rend(); ++i) { int ttt = *i; if (n - *i >= 0) { n -= *i; r += '1'; } else r += '0'; } ofs ; cout ; } } ofs.close(); cout ; system("pause"); return 0; }
Регистрация: 03.12.2020
Сообщений: 16
nmcf, А как написать такой же перевод, но только с немного другими условиями:
Формат входных данных:
В каждой строке входного файла расположено по одному десятичному числу. Строк в файле не более 1000.
Формат выходных данных:
В каждой строке выходного файла должны находиться те же самые числа, то и во входном файле, только записанные в фибоначчиевой системе счисления
И если для некоторого числа имеется несколько представлений в фибоначчиевой системе, то вывести все их, расположив в порядке возрастания (для этого, рассматривая, числа как числа в десятичной системе счисления)? (5 -> 110 -> 1000)
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Перевод чисел из 9 в 10 систему счисления
#include <stdio.h> #include <windows.h> int main(int argc , char * argv) < char s; .
Перевод чисел в двоичную систему счисления
Помогите найти ошибку : #include<iostream> using namespace std; #include<conio.h> void inp(int.
Перевод чисел в восьмеричную систему счисления
Есть программа которая переводит число из 10сс в 8сс(по условию) Не проходит только 1 тест когда.
Перевод чисел из файла в римскую систему счисления
Во входном файле in.txt заданы целые числа в диапазоне от 1 до 3999, например: 112 24 9 3517 438.
Число 27 10 было переведено в систему счисления цекендорфа фиббоначиеву какой из ответов корректный
Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f0 = f1 = 1 , fk = fk — 1 + fk — 2 , где k > 1 .
Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . ( f0 = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11 . Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.
Например, 1110 = 1111fib = 10011fib = 10100fib
Требуется написать программу, которая для натурального числа N будет выводить все его представления в ФСС. Если полученные представления рассматривать как двоичные числа, то выводить их надо в порядке возрастания — от меньшего числа к большему.
Входные данные
Во входном файле записано единственное число N ( 1 ≤ N ≤ 2 × 10 9 ) .
Выходные данные
В выходной файл требуется вывести все представления числа N в ФСС по одному на каждой строке, упорядоченные по возрастанию значений соответствующих этим представлениям двоичных чисел.