Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
#1

Числа в Фибоначчиевой сс - C++

28.03.2012, 17:52. Просмотров 1866. Ответов 34
Метки нет (Все метки)

Помогите, пожалуйста!!! Как можно за О(1) (ну хотя бы не переводя число в ФСС) узнать есть единичка на конце числа в ФСС. Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2012, 17:52     Числа в Фибоначчиевой сс
Посмотрите здесь:

Реализация фибоначчиевой кучи для оптимизации алгоритма Дейкстры - C (СИ)
Это реализация фибоначивей кучи для оптимизации алгоритма Дейкстры, единственную реализацию нашел на плюсах, помогите перевести на Си,...

Перевод чисел между Фибоначчиевой и десятичной системами счисления - Pascal ABC
Ребят - выручайте) - надо написать программу В понедельник надо курсовую сдавать, а я даже понятия не имею, как такую программу написать:...

Определены ли на множестве: N(натуральные числа), Z(целые числа), Q, 2Z(четные числа), 2Z+1(нечетные) - Логика и множества
4 Определены ли на множестве: N(натуральные числа), Z(целые числа), Q, 2Z(четные числа), 2Z+1(нечетные), R (рациональные),...

Вывести все четные числа, начиная с числа N и до числа M - Pascal
составить программу в паскале,используя оператор WHILE.Вывести все четные числа,начиная с числа N и до числа M.Числа N и M задает...

Вывести все четные числа начиная с числа N и до числа M - Pascal
помогите кто чем может: while вывести все четные числа начиная с числа N и до числа M. числа задает пользователь.

"Запрашиваются 2 числа, вывести нечетные числа с их диапазона и эти числа сложить" - CMD/BAT
Здравствуйте. Не знаю как задать цикл в данной задаче: Запрашиваются 2 числа, вывести нечетные числа с их диапазона и эти числа сложить. ...

Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми - C++
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми. ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 18:13     Числа в Фибоначчиевой сс #2
Последняя цифра повторяется через 60 итераций.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int main()
{
    int arr[2] = { 0, 1 };
    std::cout << arr[0] << ' ' << arr[1] << ' ';
    for(int i = 3; i < 121; ++i)
    {
        int a = (arr[0] + arr[1]) % 10;
        arr[0] = arr[1];
        arr[1] = a;
        std::cout << arr[1] << ' ';
        if(!(i % 30))
            std::cout << std::endl;
    }
    return 0;
}
И единица встречается 8 раз
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
int main()
{
    int arr[2] = { 0, 1 };
    std::cout << 2 << ' ';
    for(int i = 3; i < 61; ++i)
    {
        int a = (arr[0] + arr[1]) % 10;
        arr[0] = arr[1];
        arr[1] = a;
        if(arr[1] == 1)
            std::cout << i << ' ';
    }
    return 0;
}
Дальше сами.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.03.2012, 18:13     Числа в Фибоначчиевой сс #3
Цитата Сообщение от Bek$ Посмотреть сообщение
Как можно за О(1) (ну хотя бы не переводя число в ФСС) узнать есть единичка на конце числа в ФСС. Заранее спасибо!
Вопрос не очень корректный но по-моему Вам нужно вот что:
числа фибоначчи, надеюсь знаете как формируются. Для того чтобы узнать какая цифра у 1000 числа Фибоначчи не обязательно все эти числа вычислять. Достаточно знать последние цифры этих чисел (т.е. к полученным числам применять %10). В общем так:
0, 1, 1, 2, 3, 5, 8, 13 (применяя %10 получаем 3), 11 (применяя %10 получаем 1), 4, 5, и т.д.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 19:41  [ТС]     Числа в Фибоначчиевой сс #4
valeriikozlov, soon, вы не так поняли условия. Дано число в Фибоначчиевой системе счисления. Вот материал о ней. Нужно определить, является ли последний бит единичкой.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 20:07     Числа в Фибоначчиевой сс #5
Все равно не понял. К примеру, дается число 8(порядковый номер 6). Нужно определить последний бит у него? Но это же смешно. Приведите пару примеров вводимых-выводимых данных
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:15  [ТС]     Числа в Фибоначчиевой сс #6
ну да, последний бит, только нужно сделать максимально быстро, и для больших чисел (порядка 10^12). Мне нужна очень эта функция. Например: 2=10(F) последний бит - 0, должна возвращать false. 4=101(f). Последний бит -1, возвращает true
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
28.03.2012, 20:21     Числа в Фибоначчиевой сс #7
Нельзя ли как-нибудь воспользоваться тем, что Fn = ближайшее целое к ((1+sqrt5)/2)n
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:23  [ТС]     Числа в Фибоначчиевой сс #8
Нет, дело не в числах Фибоначчи, а в Фибоначчиевой системе счисления. Это система счисления, подобная двоичной. Ссылка уже была
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 20:25     Числа в Фибоначчиевой сс #9
delete
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:27  [ТС]     Числа в Фибоначчиевой сс #10
В Фибоначчиевой системе счисления???
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
28.03.2012, 20:33     Числа в Фибоначчиевой сс #11
Числа, заканчивающиеся в ФСС на 1:
4 = 3+1
12 = 8+3+1
33 = 21+8+3+1
Мб это F2n-1
Говорю без всякой уверенности, просто направления раскопок

Добавлено через 5 минут
Цитата Сообщение от Bek$ Посмотреть сообщение
Нет, дело не в числах Фибоначчи, а в Фибоначчиевой системе счисления. Это система счисления, подобная двоичной. Ссылка уже была
Это понятно. Я говорю вот о чем.
По этой формуле легко найти максимальное F не превышающее данного. Вычесть его из исходного. И тд.
но это и будет разложение в ФСС.
Bek$
1 / 1 / 0
Регистрация: 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 минуты
А если не раскладывая?
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
28.03.2012, 20:42     Числа в Фибоначчиевой сс #13
Цитата Сообщение от Байт Посмотреть сообщение
4 = 3+1
12 = 8+3+1
33 = 21+8+3+1
Прошу прощения, пропустил 6 = 5+1

Цитата Сообщение от Bek$ Посмотреть сообщение
Короче, как я понял, никто не понял моего вопроса. Любое натуральное число N можно представить в виде последовательности битов а(1)...a(k) так, что, N=a(1)*F(1)+a(2)*F(2)+...+a(k)*F(k), где F(k) - единственный член последовательности Фибоначчи. Доказано, что такое представление единственно. Нужно узнать для заданного N, значение к-го бита.
Да нет, все понятно, вроде. Только искать надо a(1), тк a(k) (старший бит) всегда = 1.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:43  [ТС]     Числа в Фибоначчиевой сс #14
а ну да) просто нужна закономерность, типа if (n=...) return true;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 20:44     Числа в Фибоначчиевой сс
Еще ссылки по теме:

В 2 поля ввести 2 числа и вывести все непарные числа больше первого числа и меньше второго - JavaScript
Нужно в 2 поля ввести 2 числа и вывести все непарные числа больше первого числа и меньше второго;

За 1 просмотр файла вывести сначала числа меньше а, потом числа из промежутка а b, затем, числа больше b - C (СИ)
Дан файл с числами типа float, пользователь вводит 2 числа а и b, за 1 просмотр файла нужно вывести сначала числа меньше а, потом числа из...

Получить из цифр числа четырехзначные числа, у которых цифры исходного числа идут в том же порядке - Pascal
Задано натуральное трехзначное число. Получить из его цифр четырехзначные числа, у которых цифры исходного числа идут в том же порядке, но...

Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел? - C++
Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел?

Определить все натуральные числа m, не превосходящие числа N. Сумма всех цифр числа m-простое число. - Pascal
Уславие Определить все натуральные числа m, не превосходящие числа N. Сумма всех цифр числа m-простое число.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
28.03.2012, 20:44     Числа в Фибоначчиевой сс #15
Цитата Сообщение от Bek$ Посмотреть сообщение
А если не раскладывая?
Понятно, раскладывая - каждый дурак может. И О(1) никак не получится. Но в голову ничего путного не приходит.
Yandex
Объявления
28.03.2012, 20:44     Числа в Фибоначчиевой сс
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru