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

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

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

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

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

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

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:51  [ТС] #16
Просто с разложением у программы Time-Limit(((
0
soon
2540 / 1305 / 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;
}
Быть может, опираясь на данные из этой программы получится что-либо придумать
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:29  [ТС] #18
Я на Си пишу чуть меньше месяца, и ощущение, что это на каком-то другом языке)))) Можно слегка пояснить?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:32 #19
Bek$, это на плюсах. На си мы бы упирались либо в ограниченный размер строки, либо в ручное выделение памяти. Потребовалось бы чуть больше времени на разработку. Можете тут попробовать проверять. http://liveworkspace.org/code/2ef182...0781cfe4969968
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:35  [ТС] #20
ну да я имел ввиду С++)

Добавлено через 2 минуты
вы, получается, раскладываете число в строку, и далеко не за О(1). Алгоритм проверки через разложение у меня уже есть и он попроще) нужна по-хорошему закономерность
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:37 #21
Что интересно(может пока просто совпадение), в каждом секторе(участке между двумя фиб. числами.) количество чисел с последним битом равно сумме двух предыдущих секторов, т.е. опять возвращаемся к числам фибоначчи. Но, повторюсь, возможно это просто совпадение.

Добавлено через 54 секунды
Bek$, нет, я просто прибавляю к числу единицу. Это не разложение, я просто на основе выдаваемых данных пытаюсь найти закономерность.
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:41  [ТС] #22
soon, нужно постараться придумать обоснование вашему утверждению. Если оно действительно верно, то моя программа сводится к нахождению N-го члена Фибоначчи)
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:42 #23
Bek$, не все так просто. Я говорил про количество, но сами числа отличаются на 2 или 3, причем я пока не могу найти адекватную закономерность.
0
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
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:49 #25
50 мало, вы 500 к примеру рассматривайте. Причем рассматривайте не сами числа, а разность между двумя соседними. Ну, по крайней мере, я так делаю
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:51  [ТС] #26
... 61 64 67 69
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 21:52 #27
Или, как вариант, эти числа в двоичном коде.
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:54  [ТС] #28
их много... Мне кажется, в этой последовательности 2 и 3 есть очевидная закономерность)
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 22:01 #29
Она наверняка очень очевидна, раз мы ее не замечаем

Ладно, все, больше не оффтоплю.
0
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 22:01  [ТС] #30
Мои наблюдения -
1) Никакие 2 двойки рядом не стоят
2) Нет больше 3-х троек идущих подряд
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 22:01
Привет! Вот еще темы с ответами:

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

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

Найти двухзначные числа, равные сумме куба числа единиц и квадрата числа десятков - Turbo Pascal
Найти двухзначные числа, равные сумме куба числа единиц и квадрата числа десятков

Ввести в программу строку (числа, латиница), считать только числа, записать числа в массив - C++
Нужна помощь! Срочно! Нужно ввести в программу строку (числа, латиница), считать только числа, записать числа в массив. Помогите,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.03.2012, 22:01
Ответ Создать тему
Опции темы

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