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

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

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

Даны два целых числа A и B (A < B). Вывести в порядке убывания все це-лые числа, расположенные между A и B (не включая числа A и B), а также количеств C++
Дан файл F, компонентами которого являются целые числа. Получить в файле G все нечетные числа, входящие в файл F. Числа в файле G должны следовать C++
C++ От данного числа N вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. до тех пор, пока число положительно
C++ Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел?
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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
 Аватар для soon
2536 / 1301 / 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
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
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
 Аватар для soon
2536 / 1301 / 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
В Фибоначчиевой системе счисления???
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
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 минуты
А если не раскладывая?
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
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;
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
28.03.2012, 20:44     Числа в Фибоначчиевой сс #15
Цитата Сообщение от Bek$ Посмотреть сообщение
А если не раскладывая?
Понятно, раскладывая - каждый дурак может. И О(1) никак не получится. Но в голову ничего путного не приходит.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:51  [ТС]     Числа в Фибоначчиевой сс #16
Просто с разложением у программы Time-Limit(((
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:17     Числа в Фибоначчиевой сс #17
Накидал на скорую руку, возможны баги.
C++
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
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
 
class FibBin
{
    std::string num;
    void addBit()
    {
        std::fill(num.begin(), num.end(), '0');
        num = "1" + num;
    }
 
public:
    FibBin(): num("1")
    {
 
    }
 
    FibBin& operator ++ ()
    {
        for
        (
            auto it = num.rbegin();
            it != num.rend();
            ++it
        )
        {
            if(*it == '1')
            {
                if(it + 1 == num.rend())
                {
                    addBit();
                    return *this;
                }
            }
            else if(*it == '0')
            {
                if(*(it + 1) == '0')
                {
                    std::fill(num.rbegin(), it, '0');
                    *it = '1';
                    return *this;
                }
            }
        }
        std::cerr << "something has happend" << std::endl;
    }
 
    friend std::ostream& operator << (std::ostream& stream, FibBin& fb)
    {
        stream << fb.num;
        return stream;
    }
};
 
void func(int n)
{
    FibBin fb;
    std::cout << 1 << std::setw(16) << fb << std::endl;
    for(int i = 2; i <= n; ++i)
        std::cout << i << std::setw(16) << ++fb << std::endl;
}
 
int main()
{
    func(20);
    return 0;
}
Быть может, опираясь на данные из этой программы получится что-либо придумать
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:29  [ТС]     Числа в Фибоначчиевой сс #18
Я на Си пишу чуть меньше месяца, и ощущение, что это на каком-то другом языке)))) Можно слегка пояснить?
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:32     Числа в Фибоначчиевой сс #19
Bek$, это на плюсах. На си мы бы упирались либо в ограниченный размер строки, либо в ручное выделение памяти. Потребовалось бы чуть больше времени на разработку. Можете тут попробовать проверять. http://liveworkspace.org/code/2ef182...0781cfe4969968
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 21:35     Числа в Фибоначчиевой сс
Еще ссылки по теме:

C++ Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми
Даны два числа. Если квадратный корень из второго числа меньше первого числа, то увличить второе число в пять раз с++ C++
Ввести в программу строку (числа, латиница), считать только числа, записать числа в массив C++

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

Или воспользуйтесь поиском по форуму:
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:35  [ТС]     Числа в Фибоначчиевой сс #20
ну да я имел ввиду С++)

Добавлено через 2 минуты
вы, получается, раскладываете число в строку, и далеко не за О(1). Алгоритм проверки через разложение у меня уже есть и он попроще) нужна по-хорошему закономерность
Yandex
Объявления
28.03.2012, 21:35     Числа в Фибоначчиевой сс
Ответ Создать тему
Опции темы

Текущее время: 05:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru