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

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.81
Lord_Voodoo
Супер-модератор
8577 / 2177 / 61
Регистрация: 07.03.2007
Сообщений: 10,863
Завершенные тесты: 1
#1

злополучные числа фибоначчи - C++

11.10.2008, 16:18. Просмотров 5804. Ответов 7
Метки нет (Все метки)

написал прогу для нахождения очень больших чисел фибоначчи, 1000 - не проблема, но вот бракуют меня, что неверно вычисляют, кто может подсказать, что я не так делаю:
Код
#include <iostream>
using namespace std;
const int N = 100;
int ctrl = 0;
void add(int a[N], int b[N], int c[N]){
  bool isOf = false;
  for(int i = N - 1; i > 0; i--){
    if(isOf){
      c[i]++;
      ctrl = i;
    }
    isOf = (c[i] + a[i] + b[i])/10;
    c[i] = (c[i] + a[i] + b[i])%10;
  }
}
int main()
{
 int fib0[N];int fib1[N];int fib2[N];
 for(int i = 0; i < 100; i++){
   fib0[i] = 0;fib1[i] = 0;fib2[i]=0;
    }
 int n;
 cin>>n;
 fib0[N - 1] = 0;fib1[N - 1] = 1;fib2[N - 1] = 1;
 ctrl = 99;
 if(n>=2){
     for(int i = 0; i < 100; i++) fib2[i]=0;
 }
 for (int i = 2;i<=n;i++)
 {
    add(fib0, fib1, fib2);
    memmove(fib0, fib1, sizeof(int)*N);
    memmove(fib1, fib2, sizeof(int)*N);
    if(i!=n)for(int i = 0; i < 100; i++) fib2[i]=0;
 }
 for(int i = ctrl; i < N; i++) cout<<fib2[i];
 return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2008, 16:18     злополучные числа фибоначчи
Посмотрите здесь:

Числа Фибоначчи C++
числа Фибоначчи- 2 C++
C++ Числа Фибоначчи
Числа Фибоначчи C++ Builder
Числа Фибоначчи! C++
Числа Фибоначчи C++
Числа Фибоначчи C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ABTOP
36 / 36 / 2
Регистрация: 09.06.2008
Сообщений: 324
11.10.2008, 23:39     злополучные числа фибоначчи #2
Больно уж сложный алгоритм, может где-то напутал... Сам проверь 40 елемент больше чем 41 или 42, такого в ряде Фибоначи быть неможет...

Код
40
102334155
 
41
80141
 
42
914296
Lord_Voodoo
Супер-модератор
8577 / 2177 / 61
Регистрация: 07.03.2007
Сообщений: 10,863
Завершенные тесты: 1
13.10.2008, 09:23  [ТС]     злополучные числа фибоначчи #3
ABTOP, да я разобрался, проблема была в поставленной задаче, просто начальные условия слегка экстравагантные, потому что 0-ой и 1-й элемент единицы, хотя принято, что 0 - это 0... а как ты можешь проще сделать, если мне надо вывести именно число, а не выражение с мантиссой - такого целого в си++ нет...а упрощать буду потом, там кое-какие циклы явно лишние... я никак не могу забить массив 0 с помощью memset... ничего не меняется почему-то...
Бартимеус
181 / 33 / 2
Регистрация: 29.10.2008
Сообщений: 283
26.12.2008, 22:33     злополучные числа фибоначчи #4
А чем такой код не устраивает?
Код
#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int _tmain(int argc, _TCHAR* argv[])
{
	int n, sum;
	cout<<"Vvedite chislo: ";
	cin>>n;
	sum=(n-1)+(n-2);
	cout<<"summa ravna "<<sum<<endl;
	return 0;
}
Ensase
Флудер
191 / 29 / 5
Регистрация: 23.03.2007
Сообщений: 335
26.12.2008, 22:46     злополучные числа фибоначчи #5
н-тое число ряда Фибоначчи это количество чисел влезающих в н бит и не имеющих в двоичном разложении 2 и более стоящих подряд нулей (можете проверить если не верите, хотя это легко доказывается) и это можно использовать на практике
Darker
233 / 58 / 2
Регистрация: 04.12.2009
Сообщений: 633
07.12.2009, 13:50     злополучные числа фибоначчи #6
Lord_Voodoo а зачем столько избыточного кода???
Lord_Voodoo
Супер-модератор
8577 / 2177 / 61
Регистрация: 07.03.2007
Сообщений: 10,863
Завершенные тесты: 1
07.12.2009, 14:05  [ТС]     злополучные числа фибоначчи #7
Darker, потому что число фибоначчи надо получить для 1000-ого элемента, поэтому нужна длинная арифметика
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2009, 02:31     злополучные числа фибоначчи
Еще ссылки по теме:

C++ Числа Фибоначчи
Числа Фибоначчи, простые числа и делители C++
C++ Числа Фибоначчи
Числа Фибоначчи C++
C++ Составьте программу, позволяющую найти все числа Фибоначчи, меньшие заданного числа N

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

Или воспользуйтесь поиском по форуму:
Том Ардер
Модератор
Эксперт по математике/физике
3705 / 2318 / 286
Регистрация: 15.06.2009
Сообщений: 4,100
08.12.2009, 02:31     злополучные числа фибоначчи #8
Поправил длинную арифметику.
Код рабочий. Можно, конечно, элегантнее. Например, с динамическими массивами.

файл phib.cpp
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
#include <iostream>
#include <iomanip>
using namespace std;
 
const int N = 250;  // phi(1000) порядка 1.e209
 
typedef unsigned char byte;
 
void add(byte a[N], byte b[N], byte c[N])
{
    byte    over = 0;
 
    for( int i = N - 1; i >= 0; i--)
    {
        c[i] = a[i] + b[i] + over;
 
        if( c[i] >= 10 )
        {
            over = c[i] / 10;
            c[i] = c[i] % 10;
        }
        else
        {
            over = 0;
        }
    }
}
 
void phib(int n)
{
    byte fib0[N];
    byte fib1[N];
    byte fib2[N];
 
    for( int i = 0; i < N; i++)
    {
        fib0[i] = 0;
        fib1[i] = 0;
        fib2[i] = 0;
    }
 
    fib0[N - 1] = 1;
    fib1[N - 1] = 1;
 
    for( i = 2; i < n; i++ )
    {
        add( fib0, fib1, fib2 );
 
        memmove( fib0, fib1, sizeof(byte)*N );
        memmove( fib1, fib2, sizeof(byte)*N );
    }
 
    i = 0;
    while( fib2[i] == 0 ) i++;
    
    for( ; i < N; i++)
    {
        cout << setw(1) << char('0' + fib2[i]);
    }
    cout << endl;
}
файл main.cpp

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <iomanip>
using namespace std;
 
void phib(int n);
 
int main()
{
    int n;
 
    cout << "n = ? ";
    cin >> n;
 
    phib( n );
 
        system("pause");
 
    return 0;
}
Результат: phi(1) = phi(2) = 1 => phi(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Wolfram Mathematica даёт то же самое
Yandex
Объявления
08.12.2009, 02:31     злополучные числа фибоначчи
Ответ Создать тему
Опции темы

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