1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
1

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

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

Author24 — интернет-сервис помощи студентам
Помогите, пожалуйста!!! Как можно за О(1) (ну хотя бы не переводя число в ФСС) узнать есть единичка на конце числа в ФСС. Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.03.2012, 17:52
Ответы с готовыми решениями:

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

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

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

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

34
2554 / 1319 / 178
Регистрация: 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;
}
Дальше сами.
1
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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, и т.д.
0
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 19:41  [ТС] 4
valeriikozlov, soon, вы не так поняли условия. Дано число в Фибоначчиевой системе счисления. Вот материал о ней. Нужно определить, является ли последний бит единичкой.
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 20:07 5
Все равно не понял. К примеру, дается число 8(порядковый номер 6). Нужно определить последний бит у него? Но это же смешно. Приведите пару примеров вводимых-выводимых данных
1
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
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
28.03.2012, 20:21 7
Нельзя ли как-нибудь воспользоваться тем, что Fn = ближайшее целое к ((1+sqrt5)/2)n
1
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:23  [ТС] 8
Нет, дело не в числах Фибоначчи, а в Фибоначчиевой системе счисления. Это система счисления, подобная двоичной. Ссылка уже была
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
28.03.2012, 20:25 9
delete
0
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:27  [ТС] 10
В Фибоначчиевой системе счисления???
1
Диссидент
Эксперт C
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 минут
Цитата Сообщение от Bek$ Посмотреть сообщение
Нет, дело не в числах Фибоначчи, а в Фибоначчиевой системе счисления. Это система счисления, подобная двоичной. Ссылка уже была
Это понятно. Я говорю вот о чем.
По этой формуле легко найти максимальное 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
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
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.
0
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:43  [ТС] 14
а ну да) просто нужна закономерность, типа if (n=...) return true;
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
28.03.2012, 20:44 15
Цитата Сообщение от Bek$ Посмотреть сообщение
А если не раскладывая?
Понятно, раскладывая - каждый дурак может. И О(1) никак не получится. Но в голову ничего путного не приходит.
0
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 20:51  [ТС] 16
Просто с разложением у программы Time-Limit(((
0
2554 / 1319 / 178
Регистрация: 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
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
28.03.2012, 21:29  [ТС] 18
Я на Си пишу чуть меньше месяца, и ощущение, что это на каком-то другом языке)))) Можно слегка пояснить?
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.03.2012, 21:35
Помогаю со студенческими работами здесь

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

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

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

Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции
Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции

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

Программа вычисления числа простых делителей натурального числа М, не являющихся в то же время делителями числа N
В идеале нужен нужно написать метод: Составьте программу вычисления числа простых делителей...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru