Форум программистов, компьютерный форум 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, 21:37     Числа в Фибоначчиевой сс #21
Что интересно(может пока просто совпадение), в каждом секторе(участке между двумя фиб. числами.) количество чисел с последним битом равно сумме двух предыдущих секторов, т.е. опять возвращаемся к числам фибоначчи. Но, повторюсь, возможно это просто совпадение.

Добавлено через 54 секунды
Bek$, нет, я просто прибавляю к числу единицу. Это не разложение, я просто на основе выдаваемых данных пытаюсь найти закономерность.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:41  [ТС]     Числа в Фибоначчиевой сс #22
soon, нужно постараться придумать обоснование вашему утверждению. Если оно действительно верно, то моя программа сводится к нахождению N-го члена Фибоначчи)
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:42     Числа в Фибоначчиевой сс #23
Bek$, не все так просто. Я говорил про количество, но сами числа отличаются на 2 или 3, причем я пока не могу найти адекватную закономерность.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:47  [ТС]     Числа в Фибоначчиевой сс #24
До 50 моя прога выдает так: 1 4 6 9 12 14 17 19 22 25 27 30 33 35 38 40 43 46 48
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:49     Числа в Фибоначчиевой сс #25
50 мало, вы 500 к примеру рассматривайте. Причем рассматривайте не сами числа, а разность между двумя соседними. Ну, по крайней мере, я так делаю
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:51  [ТС]     Числа в Фибоначчиевой сс #26
... 61 64 67 69
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:52     Числа в Фибоначчиевой сс #27
Или, как вариант, эти числа в двоичном коде.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:54  [ТС]     Числа в Фибоначчиевой сс #28
их много... Мне кажется, в этой последовательности 2 и 3 есть очевидная закономерность)
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 22:01     Числа в Фибоначчиевой сс #29
Она наверняка очень очевидна, раз мы ее не замечаем

Ладно, все, больше не оффтоплю.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 22:01  [ТС]     Числа в Фибоначчиевой сс #30
Мои наблюдения -
1) Никакие 2 двойки рядом не стоят
2) Нет больше 3-х троек идущих подряд
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 22:09     Числа в Фибоначчиевой сс #31
Двойка прибавляется к числу, последние биты которого = 0101

Добавлено через 43 секунды
В фибоначчевой, разумеется
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 22:12  [ТС]     Числа в Фибоначчиевой сс #32
хммм... А это мысль! Но это опять в ФСС переводить
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 22:34     Числа в Фибоначчиевой сс #33
Ничего в голову не шло, добавил класс четверичной системы счисления(а вдруг). Подумываю над троичной. Но это завтра. Вот последний вариант, компилился с поддержкой c++11.
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
////////////////////////////////////////////////////////////////////////////////
class Number
{
protected:
    std::string num;
 
public:
    virtual ~Number()
    {
        //std::cerr << "Number~" << std::endl;
    }
    //reference
    friend std::ostream& operator << (std::ostream& stream, Number& n)
    {
        stream << n.num;
        return stream;
    }
    //rvalue reference
    friend std::ostream& operator << (std::ostream& stream, Number&& n)
    {
        stream << n.num;
        return stream;
    }
};
////////////////////////////////////////////////////////////////////////////////
class FibBin: public Number
{
    void addBit()
    {
        std::fill(num.begin(), num.end(), '0');
        num = "1" + num;
    }
 
public:
    FibBin(): Number()
    {
        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;
    }
    //--------------------------------------------------------------------------
    const bool lastBit() const
    {
        return *num.rbegin() == '1';
    }
 
    /*friend std::ostream& operator << (std::ostream& stream, FibBin& fb)
    {
        stream << fb.num;
        return stream;
    }*/
};
////////////////////////////////////////////////////////////////////////////////
class Bin: public Number
{
public:
    Bin(unsigned n): Number()
    {
        num = "";
        while(n)
        {
            num = std::to_string(n & 1) + num;
            n >>= 1;
        }
    }
 
    /*friend std::ostream& operator << (std::ostream& stream, Bin&& b)
    {
        stream << b.num;
        return stream;
    }*/
};
////////////////////////////////////////////////////////////////////////////////
class Quat: public Number
{
public:
    Quat(unsigned n): Number()
    {
        num = "";
        while(n)
        {
            num = std::to_string(n & 3) + num;
            n >>= 2;
        }
    }
 
    /*friend std::ostream& operator << (std::ostream& stream, Quat&& q)
    {
        stream << q.num;
        return stream;
    }*/
};
////////////////////////////////////////////////////////////////////////////////
void func(int n)
{
    FibBin fb;
    std::cout << 1 << std::setw(16) << fb << std::endl;
    int last = 1;
    for(int i = 2; i <= n; ++i)
    {
        ++fb;
        if(fb.lastBit())
        {
            //if(i - last == 3)
            //    std::cout << std::endl;
            std::cout << i << '\t' << Bin(i) << '\t' << Quat(i) << '\t' << fb << ' ' << i - last << std::endl;
            last = i;
        }
    }
}
 
int main()
{
    func(500);
    //std::cout << std::endl;
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.03.2012, 03:14     Числа в Фибоначчиевой сс #34
Bek$, ссылку на задачу можете дать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.03.2012, 18:12     Числа в Фибоначчиевой сс
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.03.2012, 18:12     Числа в Фибоначчиевой сс #35
Нашел. Все они повторяются через 1000. Т.е пока что минимальный алгоритм таков - a % 1000 и проверяете на последний бит.
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
////////////////////////////////////////////////////////////////////////////////
class Number
{
protected:
    std::string num;
 
public:
    Number(): num("")
    {
 
    }
    //--------------------------------------------------------------------------
    virtual ~Number()
    {
        //std::cerr << "Number~" << std::endl;
    }
    //reference
    friend std::ostream& operator << (std::ostream& stream, Number& n)
    {
        stream << n.num;
        return stream;
    }
    //rvalue reference
    /*
    friend std::ostream& operator << (std::ostream& stream, Number&& n)
    {
        stream << n.num;
        return stream;
    }
    */
};
////////////////////////////////////////////////////////////////////////////////
class FibBin: public Number
{
    void addBit()
    {
        std::fill(num.begin(), num.end(), '0');
        num = "1" + num;
    }
 
public:
    FibBin(): Number()
    {
        num = "1";
    }
    //--------------------------------------------------------------------------
    FibBin& operator ++ ()
    {
        for
        (
            std::string::reverse_iterator 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;
    }
    //--------------------------------------------------------------------------
    const bool lastBit() const
    {
        return *num.rbegin() == '1';
    }
};
////////////////////////////////////////////////////////////////////////////////
void func(int n)
{
    FibBin fb;
    std::cout << std::setw(4) << 1;
    for(int i = 2; i <= n; ++i)
    {
        ++fb;
        if(fb.lastBit())
            std::cout << std::setw(5) << i;
        if(!(i % 50))
            std::cout << std::endl;
    }
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
    func(2000);
    return 0;
}
ps/ Убрал auto из кода, теперь можно компилить без с++11(если нет возможности)
Yandex
Объявления
29.03.2012, 18:12     Числа в Фибоначчиевой сс
Ответ Создать тему
Опции темы

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