1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
1 | |
Числа в Фибоначчиевой сс28.03.2012, 17:52. Показов 3186. Ответов 34
Метки нет (Все метки)
Помогите, пожалуйста!!! Как можно за О(1) (ну хотя бы не переводя число в ФСС) узнать есть единичка на конце числа в ФСС. Заранее спасибо!
0
|
28.03.2012, 17:52 | |
Ответы с готовыми решениями:
34
Реализация фибоначчиевой кучи для оптимизации алгоритма Дейкстры Перевод чисел между Фибоначчиевой и десятичной системами счисления Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми В 2 поля ввести 2 числа и вывести все непарные числа больше первого числа и меньше второго |
28.03.2012, 18:13 | 2 | ||||||||||
Последняя цифра повторяется через 60 итераций.
1
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.03.2012, 18:13 | 3 |
Вопрос не очень корректный но по-моему Вам нужно вот что:
числа фибоначчи, надеюсь знаете как формируются. Для того чтобы узнать какая цифра у 1000 числа Фибоначчи не обязательно все эти числа вычислять. Достаточно знать последние цифры этих чисел (т.е. к полученным числам применять %10). В общем так: 0, 1, 1, 2, 3, 5, 8, 13 (применяя %10 получаем 3), 11 (применяя %10 получаем 1), 4, 5, и т.д.
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 19:41 [ТС] | 4 |
valeriikozlov, soon, вы не так поняли условия. Дано число в Фибоначчиевой системе счисления. Вот материал о ней. Нужно определить, является ли последний бит единичкой.
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:15 [ТС] | 6 |
ну да, последний бит, только нужно сделать максимально быстро, и для больших чисел (порядка 10^12). Мне нужна очень эта функция. Например: 2=10(F) последний бит - 0, должна возвращать false. 4=101(f). Последний бит -1, возвращает true
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:23 [ТС] | 8 |
Нет, дело не в числах Фибоначчи, а в Фибоначчиевой системе счисления. Это система счисления, подобная двоичной. Ссылка уже была
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:27 [ТС] | 10 |
В Фибоначчиевой системе счисления???
1
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
28.03.2012, 20:33 | 11 |
Числа, заканчивающиеся в ФСС на 1:
4 = 3+1 12 = 8+3+1 33 = 21+8+3+1 Мб это F2n-1 Говорю без всякой уверенности, просто направления раскопок Добавлено через 5 минут Это понятно. Я говорю вот о чем. По этой формуле легко найти максимальное F не превышающее данного. Вычесть его из исходного. И тд. но это и будет разложение в ФСС.
1
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:37 [ТС] | 12 |
Короче, как я понял, никто не понял моего вопроса. Любое натуральное число N можно представить в виде последовательности битов а(1)...a(k) так, что, N=a(1)*F(1)+a(2)*F(2)+...+a(k)*F(k), где F(k) - единственный член последовательности Фибоначчи. Доказано, что такое представление единственно. Нужно узнать для заданного N, значение к-го бита.
Добавлено через 3 минуты А если не раскладывая?
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:43 [ТС] | 14 |
а ну да) просто нужна закономерность, типа if (n=...) return true;
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 20:51 [ТС] | 16 |
Просто с разложением у программы Time-Limit(((
0
|
28.03.2012, 21:17 | 17 | |||||
Накидал на скорую руку, возможны баги.
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 21:29 [ТС] | 18 |
Я на Си пишу чуть меньше месяца, и ощущение, что это на каком-то другом языке)))) Можно слегка пояснить?
0
|
28.03.2012, 21:32 | 19 |
Bek$, это на плюсах. На си мы бы упирались либо в ограниченный размер строки, либо в ручное выделение памяти. Потребовалось бы чуть больше времени на разработку. Можете тут попробовать проверять. http://liveworkspace.org/code/... cfe4969968
0
|
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
|
|
28.03.2012, 21:35 [ТС] | 20 |
ну да я имел ввиду С++)
Добавлено через 2 минуты вы, получается, раскладываете число в строку, и далеко не за О(1). Алгоритм проверки через разложение у меня уже есть и он попроще) нужна по-хорошему закономерность
0
|
28.03.2012, 21:35 | |
28.03.2012, 21:35 | |
Помогаю со студенческими работами здесь
20
Получить из цифр числа четырехзначные числа, у которых цифры исходного числа идут в том же порядке Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел? За 1 просмотр файла вывести сначала числа меньше а, потом числа из промежутка а b, затем, числа больше b Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции Определить все натуральные числа m, не превосходящие числа N. Сумма всех цифр числа m-простое число. Программа вычисления числа простых делителей натурального числа М, не являющихся в то же время делителями числа N Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |