Сформировать и вывести целочисленный массив, содержащий N первых членов последовательности Фибоначчи

@gogo2099 · Регистрация: 20.11.2016

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

Дано целое число N>2. Сформировать и вывести целочисленный массив размера N, содержащий N первых членов элементов последовательности чисел Фибоначчи F_K: F₁=1, F₂=2, F_K=F_K-2+F_K-1, K=3, 4, 5….

@bormant · 14.03.2017, 21:48

См. похожие темы внизу страницы (от правильного названия темы есть плюсы на этом форуме). Пользуйтесь поиском ДО создания темы.

@Darkcat112 · 03.03.2020, 17:38

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var f1,f2,b,i,n: word;
begin
    readln(n);
    f1 := 1;
    f2 := 2;
    write(f1,' ',f2,' ');
    for i:=3 to n do begin
        write(f1+f2, ' ');
        b := f1;
        f1 := f2;
        f2 := b + f1;
    end;
    writeln;
end.

Вот вам уневерсальная прога по Фибоначи(числам)
Выводит то кол-во элементов скок нужно)

@bormant · 03.03.2020, 22:38

Сообщение от Darkcat112

Выводит то кол-во элементов скок нужно)

... особенно, если нужно 1 или 25 и больше ;-)

@markiza-inc · 04.03.2020, 01:08

Сообщение от bormant

... особенно, если нужно 1 или 25 и больше ;-)

Так, Darkcat112 и написал: уневерсальная прога :-)

@Darkcat112 · 04.03.2020, 18:03

ет да)

@Cyborg Drone · 05.03.2020, 22:45

Не по теме:

Darkcat112, пожалуйста, не мусорьте по форуму. Если решили что-то опубликовать в древней теме, то публикуйте что-то не тривиальное.

@Mikstereo · 08.03.2020, 23:35

Сообщение от Cyborg Drone

Если решили что-то опубликовать в древней теме, то публикуйте что-то не тривиальное.

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
#include <bits/stdc++.h> 
using namespace std;
const int MAX=1000000; 
long f[MAX]={0}; 
long fib(int n) 
{ 
    if (n == 0) 
        return 0; 
    if (n == 1 || n == 2) 
        return (f[n] = 1); 
    if (f[n]) 
        return f[n]; 
    long k = (n & 1)? (n+1)/2 : n/2; 
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) 
           : (2*fib(k-1) + fib(k))*fib(k); 
    return f[n]; 
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        if(!f[i])
            fib(i);
    for(int i=1;i<=n;++i)
        cout<<f[i]<<" ";
}

Первые N чисел Фибоначчи за O(N*logn) (большие извинения за то что не на паскале)

@Cyborg Drone · 09.03.2020, 13:57

Mikstereo, ну Вы-то... Вы-то зачем тоже фигню публикуете? На каждой итерации вызов функции с пятью условиями, четырьмя умножениями и двумя делениями, не считая всяких там аддитивных операций... Да ещё и за время O(N*log(N))... Да ещё и "извините за то что не на паскале". Будто бы есть какая-то особенная разница. Что, лень было на паскале написать, что ли? Да ещё и библиотеки не хухёр-мухёр, #include <iostream> уже не вариант... А зачем Вы объявили MAX=1000000, если программа Ваша только до F(92) посчитать может? И в чём нетривиальность? В самодельной 64-битной арифметике? А вот так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main()
{
  int i, n;
  unsigned long long f, g;
  g = 1;
  f = 0;
  cout << "n = ";
  cin >> n;
  for (i = 0; i < n; i++)
    {
      f = f + g;
      g = f - g;
      cout << f << " ";
    }
  return 0;
}

не попроще будет? Никаких лишних вызовов ненужных функций, никаких умножений и делений. За время O(n). И считает до F(93). И не возражайте насчёт unsigned long long, то же самое хоть на Turbo Pascal написать никакая не проблема.

Без ограничения разрядности на Pascal ABC.NET:

Pascal
1
2
3
4
5
6
7
8
9
10
11
var 
  q: text;
begin
  var f, g: BigInteger;
  (f, g) := (0, 1);
  var n := ReadlnInteger('n = ');
  loop n do (f, g) := (g, f + g);
  rewrite(q, 'c:\fib.txt');
  write(q, f);
  close(q)
end.

Вроде так... Проверить сейчас не на чем. Большие извинения за то, что не на C# или Python.

С самодельной длинной арифметикой - тоже запросто. На FPC:

Pascal
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
const
  m = 1000000000;
type
  t = array[boolean] of longword;
var
  q: text;
  f: array of t;
  b: boolean;
  i, j, n, k, c: longint;
begin
  k := 0;
  SetLength(f, k + 1);
  b := false;
  f[0, b] := 0;
  f[0, not b] := 1;
  write('n = ');
  readln(n);
  for i := 1 to n do
    begin
      for j := 0 to k do f[j, b] += f[j, not b];
      for j := 0 to k - 1 do
        begin
          f[j + 1, b] += f[j, b] div m;
          f[j, b] := f[j, b] mod m;
        end;
      if f[k, b] >= m then
        begin
          inc(k);
          SetLength(f, k + 1);
          f[k, b] := f[k - 1, b] div m;
          f[k - 1, b] := f[k - 1, b] mod m;
          f[k, not b] := 0
        end;
      b := not b
    end;
  assign(q, 'c:\fib.txt');
  rewrite(q);
  write(q, 'F[', n, '] = ', f[k, b]);
  for i := k - 1 downto 0 do
    begin
      c := m div 10;
      while c > f[i, b] do
        begin
          write(q, 0);
          c := c div 10
        end;
      write(q, f[i, b])
    end;
  close(q)
end.

На самом деле, для FPC есть своя прекрасная длинная арифметика: библиотека GMP. Будем считать, что я здесь изобрёл велосипед чисто для того, чтобы повыпендриваться. Для 64-битных процессоров будет лучше так:

Pascal
1
2
3
4
const
  m: uint64 = 1000000000000000000;
type
  t = array[boolean] of uint64;

Последние две программы выводят не на дисплей, а в текстовый файл, и только n-ное число Фибоначчи, поскольку эти программы реально могут посчитать F(1000000).

@Mikstereo · 13.03.2020, 13:49

Сообщение от Cyborg Drone

Да ещё и за время O(N*log(N))

Про асимптотику: N-е число фибоначчи за O(log(N)), но при этом сохраняем промежуточно использованные значения, так что финальная асимптотика O(N). Кстати, быстрее вашего варианта.

Сообщение от Mikstereo

const int MAX=1000000;

Здесь переборщил, без длинки не было смысла обьявлять MAX больше 92.

Добавлено через 24 секунды

Сообщение от Mikstereo

Первые N чисел Фибоначчи за O(N*logn)

За O(N).
Здесь фишка метода была в том, что все Ваши варианты находят N-е число фибоначчи за O(N), а мой вариант найдет сразу несколько( мемоизация) за O(logN)

Добавлено через 43 минуты

Сообщение от Cyborg Drone

поскольку эти программы реально могут посчитать F(1000000).

F(1000000000) не посчитают. Можно посчитать за O(log(1000000000)) + затраты на длинную арифметику.

@Cyborg Drone · 14.03.2020, 06:23

Сообщение от Mikstereo

F(1000000000) не посчитают.

С чего это Вы взяли? Запросто посчитают.

Посчитаем количество цифр в F(1000000000).

По формуле Бине

$https://www.cyberforum.ru/cgi-bin/latex.cgi? F(n)=\lfloor \varphi ^n/\sqrt{5}\rceil $

где φ = 1.618033988749894848… - золотое сечение.

Количество разрядов в натуральном числе равно целой части десятичного логарифма от этого числа плюс 1. Если избавимся от округления до ближайшего целого в формуле Бине путём добавления дополнительной цифры, то количество цифр в F(n) будет не более

$https://www.cyberforum.ru/cgi-bin/latex.cgi? K\leq \lg \left( \varphi ^n/\sqrt{5}\right)+2=\lg \left( \varphi ^n\right) - \lg \sqrt{5} + 2=n\lg \varphi -\lg \sqrt{5} + 2 $

Получим К ≤ 208987643 десятичных цифр. Будем считать, что все эти цифры - девятки.

В предпоследней моей программе применён тип BigInteger. Для двоичного числа, равного 10^208987643-1, потребуется не более

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \log _2\left(10^{208987643}-1\right)< \log _2\left(10^{208987643}\right)=208987643\log_210=694241923 $

двоичных разрядов. Тогда для двух чисел BigInteger потребуется не более 166 мегабайт.

В последней моей программе в одно число longword помещается 9 цифр результата, и длинных чисел нужно два. Потребуется массив в 23220850 элементов из двух чисел longword, объём массива будет менее 178 Мбайт. Для FPC такой массив - далеко не предел.

Иными словами, любая из моих двух программ успешно посчитает F(1000000000), причём на любом компьютере с объёмом оперативной памяти более 600 Мбайт даже не будет использоваться виртуальная память, если, конечно, не запускать других программ.

Так что, увы, и ах, но Вы не правы...

Правда, любая из двух упомянутых программ будет считать F(1000000000) долго, даже очень долго...

Но всё же посчитает.

На моём стареньком ноутбуке примерно за 8 лет. А на современном навороченном числогрызе и за полгода, может быть, справится, а то и ещё быстрее.

С длинной арифметикой, конечно же, ни о каком O(n) даже и речи не идёт... В моей второй программе оценка сверху будет O(n²), поскольку количество итераций будет пропорционально n-ному треугольному числу. Точнее, для F(1000000000) будет сделано всё же не квинтиллион итераций, а примерно 12 квадриллионов. Это миллиардное треугольное число, умноженное на десятичный логарифм золотого сечения, и поделённое на количество десятичных цифр, которое я поместил в longword. Может быть, даже ещё меньше, где-то на десяток миллиардов, из-за моего не вполне корректного допущения, что количество элементов массива "f" растёт пропорционально количеству десятичных цифр в F(n).

Добавлено через 3 часа 44 минуты

Сообщение от Mikstereo

N-е число фибоначчи за O(log(N))

Не совсем так. Зависит от степени заполнения массива и номера числа.

При последовательном вычислении n чисел Фибоначчи (это как раз Вы и делаете) "Ваша" функция fib никакого выигрыша не даёт. У Вас будет примерно 4.5n вызовов функции fib, причём примерно половина из этих вызовов - с одним и тем же аргументом. Хорошо хоть, что только в одном из 4.5 вызовов будет вычисление частного, двух произведений, от 3 до 5 сложений или вычитаний, и четыре чтения из массива, а в остальных - только чтение из массива, ну, может быть, ещё присвоение 1. На каждом вызове при n>2 у Вас также проверяются 5 условий в функции, плюс, ещё одно условие (в данном случае ненужное) в программе (проверка на 0 в строке 22). Да ещё и время на каждый вызов тратится. Так что, в программе у Вас, пусть и очень-очень-очень-очень и очень плохое, но всё же O(n). И программа Ваша значительно медленнее, чем у меня, поскольку у меня на каждой итерации всего лишь одно сложение, одно вычитание, инкремент и проверка одного условия.

Всё отличие Вашей программы при последовательном вычислении чисел от стандартного варианта - в вычислении не по обычной формуле, а с помощью известных тождеств, требующих возводить числа в квадрат. Это позволяет несколько выровнять время вычисления чисел до заполнения массива, и замедляет программу. Можно заменить это дело на обычную формулу, будет в конечном счёте значительно быстрее.

Если бы "Ваша" функция fib вызывалась для случайных чисел, то вот тогда мемоизация работала бы, и однократный вызов функции из основной программы порождал бы рекурсивные вызовы с вычислением нескольких других чисел. Если число было однажды помещено в массив, то всё будет сводиться к проверке трёх уже не нужных условий, и чтению числа из массива, то есть, будет вычисление числа за плохонькое O(1). Преимущество? Не скажите.

Если без всяких премудростей сразу заполнить массив, то после этого числа можно просто читать из массива, без проверки каких бы то ни было условий.

Сообщение от Mikstereo

мой вариант найдет сразу несколько( мемоизация) за O(logN)

Ну да. Точнее, F(n) и ещё n-1 чисел будет вычисляться не более чем за log₂(n-1) итераций при почти пустом массиве, и по мере заполнения массива количество вычисляемых чисел будет уменьшаться до 0, а количество итераций до 1. Но при вычислении всех чисел от F(1) до F(n) всё равно нужно вычислить все эти n чисел, неважно, с рекурсией или без, с мемоизацией или без. Чудес не бывает.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@gogo2099 1 / 1 / 0 Регистрация: 20.11.2016 Сообщений: 85

	Сформировать и вывести целочисленный массив, содержащий N первых членов последовательности Фибоначчи 14.03.2017, 21:34. Показов 2116. Ответов 10 Метки нет (Все метки) Дано целое число N>2. Сформировать и вывести целочисленный массив размера N, содержащий N первых членов элементов последовательности чисел Фибоначчи F_K: F₁=1, F₂=2, F_K=F_K-2+F_K-1, K=3, 4, 5…. 1

@bormant Модератор 7816 / 4635 / 2837 Регистрация: 22.11.2013 Сообщений: 13,158 Записей в блоге: 1
	14.03.2017, 21:48
	См. похожие темы внизу страницы (от правильного названия темы есть плюсы на этом форуме). Пользуйтесь поиском ДО создания темы. 1

@Darkcat112 Кот форума 9 / 9 / 5 Регистрация: 02.03.2020 Сообщений: 183
	04.03.2020, 18:03
	ет да) 0

@Cyborg Drone
	05.03.2020, 22:45
	Не по теме: Darkcat112, пожалуйста, не мусорьте по форуму. Если решили что-то опубликовать в древней теме, то публикуйте что-то не тривиальное. 0