Числа Фибоначчи: иногда выводятся отрицательные значения

@Tengel · Регистрация: 08.10.2008

Студворк — интернет-сервис помощи студентам

У меня вот какая проблема: Числа Фибоначчи определяются рекуррентной формулой:

f0 = 0; f1 = 1; fn = fn-1 + fn-2;

Начало последовательности имеет вид 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... .
Входные данные:
В единственной строке находится число N (0 <= N <= 10000).
Выходные даны:
Выведите N-те число Фибоначчи.
Пример введения
7
Пример выведения
13
я програмку написал, но она мне иногда выводит отрецательные числа...подскажите что мне сделать, что бы ета программа корректно работала.
вот и она:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
using namespace std;
void main()
{
    int n;
    cout << "Введите номер числа :";
    do {cin>>n;} while ((n<0)&&(n>10000));
    long long fib[10000];
    fib[0]=0;
    fib[1]=1;
    for (int i=2;i<9999;i++)
    {
        fib[i] = fib[i-1]+fib[i-2];
    }
    cout<<"Число с номером "<<n<<"ето:";
    cout<<fib[n];
    system("pause");
}

@COKPOWEHEU · 15.02.2019, 11:03

Еще немного экспериментов и исправлений:

фикс моей программы

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
#include <stdio.h>
#include <inttypes.h>
#include <string.h>
#include <stdlib.h>
 
#define LONG_SIZE 10000
 
typedef struct LongNum{
  uint8_t *data;
}LongNum_t;
 
void LongSet( LongNum_t *x, uint8_t val){
  memset( x->data, 0, LONG_SIZE);
  x->data[0] = val;
}
 
void LongSum( LongNum_t *a, LongNum_t *b, LongNum_t *res ){
  uint16_t temp = 0;
  for(unsigned int i=0; i<LONG_SIZE; i++){
    temp += a->data[i] + b->data[i];
    res->data[i] = temp & 0xFF;
    temp >>= 8;
  }
  if(temp != 0)fprintf(stderr, "OVF!!!\n");
}
 
uint8_t LongDivMod10( LongNum_t *a, LongNum_t *res, uint8_t *num){
  uint16_t temp = 0;
  uint8_t zero = 1;
  for(int i=(LONG_SIZE-1); i>=0; i--){
    temp = (temp << 8) | a->data[i];
    res->data[i] = temp / 10;
    temp %= 10;
    if(res->data[i] != 0)zero = 0;
  }
  *num = temp;
  return zero;
}
 
void LongOut(LongNum_t *x){
  char *buf = (char*)malloc(LONG_SIZE*3);
  char *str = &buf[LONG_SIZE*3];
  *(--str) = '\0';
  *(--str) = '\n';
  uint8_t num, res;
  do{
    res = LongDivMod10(x, x, &num);
    *(--str) = num + '0';
  }while(res == 0);
  puts(str);
  free(buf);
}
 
int main(){
  LongNum_t a, b;
  LongNum_t *x=&a, *y=&b, *t;
  a.data = (uint8_t*)malloc(LONG_SIZE * sizeof(uint8_t));
  if(a.data == NULL){return 0;}
  b.data = (uint8_t*)malloc(LONG_SIZE * sizeof(uint8_t));
  if(b.data == NULL){free(a.data); return 0;}
 
  LongSet(x, 0);
  LongSet(y, 1);
  int n;
  scanf("%i", &n);
  for(int i=0; i<n; i++){
    LongSum(x, y, x);
    t=x; x=y; y=t;
  }
 
  printf("%i -> ", n);
  LongOut(x);
  printf("\n");
  
  free(b.data);
  free(a.data);
}

Расчет:

Code
1
2
3
4
5
$ time ./a.out <<< "100000" > /dev/null
 
real    0m2,761s
user    0m2,757s
sys     0m0,004s

фикс программы от Crabintron

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
#include <iostream>
#include <cstdlib>
#include <time.h>
 
#define ARR_SIZE 21000
 
int flag=1;
 
char* sum(char* arr1, char* arr2){
  int tmp=0;
  int i=0;
  
  for(; i<flag;i++){
    tmp+=(arr1[ARR_SIZE-i]+arr2[ARR_SIZE-i]);
    
    arr1[ARR_SIZE-i]=tmp%10;
    tmp/=10;
  }
  if(tmp){
    arr1[ARR_SIZE-i]=tmp;
    flag++;
  }
  
  return arr1;
}
 
int main(){
  char* arr1;
  char* arr2;
  char* arr3;
  unsigned int n;
  
  std::cin >> n;
  if(n==1)
  {
    std::cout <<0;
    return 0;
  }
  else{
    if(n==2)
    {
      std::cout<<1;
      return 0;   
    }   
  }
  arr1=(char*)malloc((ARR_SIZE+1)*sizeof(char));
  arr2=(char*)malloc((ARR_SIZE+1)*sizeof(char));
  arr3 = arr1;
  
  arr1[ARR_SIZE]=1;
  arr2[ARR_SIZE]=1;
  
  for(unsigned int i=2; i<n; i++){
    arr3 = sum(arr1, arr2);   
    arr1=arr2;
    arr2=arr3; 
  }
  
  for(int i=(ARR_SIZE+1-flag); i<ARR_SIZE+1; i++){
    std::cout<<(int)arr3[i];
  }
  std::cout << '\n';
  
  free(arr1);
  free(arr2);
  return 0;
}

Расчет:

Code
1
2
3
4
5
$ time ./b.out <<< "100000" > /dev/null
 
real    0m7,338s
user    0m7,338s
sys     0m0,000s

То есть разница не только в потреблении памяти (даже в исправленном варианте в 2 раза, в теории разница в 2.5 раза), но и в скорости работы (2,75 с против 7,3 с).
Стоит отметить, что мы оба решали задачу "в лоб". Для больших чисел стоило поискать более оптимизированный алгоритм. С другой стороны, наши решения отличаются только представлением длинных целых, так что их можно использовать для сравнения реализаций.

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .