Числа Фибоначчи

@VLaDoS_2001a · Регистрация: 14.05.2020

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

https://www.e-olymp.com/ru/con... ems/208360
Не проходит один тест 98/100, где у меня ошибка или нужна другая методика ?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
using namespace std;
 
int main(void){
    uint64_t fib; cin>>fib;
    vector<uint64_t>arr(fib+1);
    arr[0]=1; arr[1] = 1;
    
    for(size_t i = 2 ; i <arr.size(); ++i)
    {
        arr[i] = arr[i-2] + arr[i-1];
    }
    cout<<arr[fib]<<endl;
 
    
    return 0;
 
}

@мама Стифлера · 01.02.2021, 11:04

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
    unsigned fib; cin>>fib;
    vector<unsigned>arr(fib+1);
    arr[0] = 0; arr[1] = 1;
    
    for(size_t i = 2 ; i <arr.size(); ++i)
        arr[i] = arr[i-2] + arr[i-1];
    cout<<arr[fib]<<endl;
return 0;
}

@Folian · 01.02.2021, 11:04

Мой проходит, твой числа те же выдаёт.

Кликните здесь для просмотра всего текста

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
#include <iostream>
 
typedef long long ll;
 
ll fib(int n)
{
    if(n < 2) return 1;
    
    ll a = 1;
    ll b = 1;
    ll temp = 0;
    
    for(int i = 2; i <= n; ++i)
    {
        temp = b;
        b += a;
        a = temp;
    }
    
    return b;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << fib(n);
    
    return 0;   
}

Попробуй в выводе endl убрать чтоль, всякие тесты щепетильны к выводу.

@VLaDoS_2001a · 01.02.2021, 11:20 **[ТС]**

Folian, arr(fib + 2) так тоже проходит

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
using namespace std;
 
int main(void){
    uint64_t fib; cin>>fib;
    vector<uint64_t>arr(fib+2);
    arr[0]=1; arr[1] = 1;
    
    for(size_t i = 2 ; i <arr.size(); ++i)
    {
        arr[i] = arr[i-2] + arr[i-1];
    }
    cout<<arr[fib];
 
    
    return 0;
 
}

Байт · 01.02.2021, 11:25

1. В задаче (Как я ее понимаю) совершенно не нужен ни массив, ни вектор. Может быть вектор лишнюю память жрет?
2. Прикиньте (по формуле Бине, например) какой величины будет требуемое число Не будет ли вылезания за размер данных
В этом случае можно попытаться использовать что-то вроде long long или использовать длинную арифметику
Тип double использовать плохо, так как он дает потерю значащих цифр.

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

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

arr(fib + 2) так тоже проходит

Естественно. size = fib+2 Хотя...

@Folian · 01.02.2021, 11:48

Сообщение от Байт

Прикиньте (по формуле Бине, например) какой величины будет требуемое число Не будет ли вылезания за размер данных
В этом случае можно попытаться использовать что-то вроде long long или использовать длинную арифметику

В тесте n <= 45, т.е. и signed int достаточно

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

arr(fib + 2) так тоже проходит

Кстати да,

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

vector<uint64_t>arr(fib+1);
arr[0]=1; arr[1] = 1;

при n < 2 выход за пределы вектора ж

@повар1 · 01.02.2021, 12:57

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <iomanip>
using namespace std;
 
int main()
{   int k;
    double n =1.0;
 
    cin>>k;
    if(k==1) cout<<'0';
    if(k>1 && k<4)cout<<'1';
    if(k>=4){
       k-=3;
       while(k--){
           n*=1.61803398875;
           n-(int)n<0.5 ? n=(int)n : n=(int)n+1;
       }
       cout<<setprecision(9)<<n<<"\n";
    }
    return 0;
}

@мама Стифлера · 01.02.2021, 13:21

Если честно, то для меня не понятно начало отсчета данной последовательности. В разных местах по разному пишут:

вариант1, где 1 элемент равен 0

1 = 0
2 = 1
3 = 1
4 = 2
5 = 3
6 = 5

вариант2, первый элемент равен 1

1 = 1
2 = 1
3 = 2
4 = 3
5 = 5
6 = 8

Отсюда возникает путаница.

Байт · 01.02.2021, 13:48

Сообщение от мама Стифлера

начало отсчета данной последовательности.

Как зададут начальные условия F(1), F(2) - так и будет. В задании четко сказано Можно начальные условия задать вообще по другому.

@мама Стифлера · 01.02.2021, 14:04

Сообщение от Байт

В задании четко сказано Можно начальные условия задать вообще по другому

В данном задании такого не заметил, но зато есть пример, теперь понятно все.

Байт · 01.02.2021, 14:07

Сообщение от мама Стифлера

В данном задании такого не заметил,

https://www.e-olymp.com/ru/con... ems/208360

F(0) = 1, F(1) = 1, F(n) = F(n - 1) + F(n - 2)

@мама Стифлера · 01.02.2021, 15:27

Байт,

да это я увидел, потом, но это же не означает

Сообщение от Байт

Можно начальные условия задать вообще по другому

Добавлено через 10 минут
Но смысл вашего высказывания мне понятен. То есть в любой задаче

Сообщение от Байт

Можно начальные условия задать вообще по другому

но в данной задаче, начальные условия уже заданы.

@повар1 · 01.02.2021, 15:54

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int main()
{   int k;
    int a =1, b=1,c;
 
    cin>>k;
    if(k==1) cout<<'0';
    if(k>1 && k<4)cout<<'1';
    if(k>=4){
         k-=3;
         while(k--){
             c=a+b;
             a=b;
             b=c;
         }
       cout<<c;
    }
    return 0;
}

@AlexVRud · 01.02.2021, 16:05

VLaDoS_2001a, Если на вход подать 0, то есть выход за пределы массива. Возможно влияние оптимизации или защита в проверяющей системе.

@мама Стифлера · 01.02.2021, 16:37

повар1, в условии задачи указано:

F(0) = 1, F(1) = 1

и пример:

Входные данные #1 = 4
Выходные данные #1 = 5

у вас не верно

@Catstail · 01.02.2021, 16:58

Если что, 45-е число Фибоначчи = 1836311903

@мама Стифлера · 01.02.2021, 17:04

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    int fib, c;
    cin >> fib;
 
    if(fib == 0) {
        cout << 1 << endl;
        return 0;
    }
    if(fib < 2) {
        cout << 1 << endl;
        return 0;
    }
    for(int a=1, b=1, i=2; i<=fib; i++) {
        c = a+b;
        a = b;
        b = c;
    }
    cout << c << endl;

@повар1 · 01.02.2021, 20:09

мама Стифлера, код для классики. А под его условия можно и так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int main()
{   int k;
    int a =1, b=1,c;
 
    cin>>k;
    if(k==0 || k==1) cout<<'1';
 
    if(k>1){
         k-=1;
         while(k--){
             c=a+b;
             a=b;
             b=c;
         }
       cout<<c;
    }
   return 0;
}

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

Сообщение от мама Стифлера

c = a+b;
a = b;
b = c;

где то и у кого то видел уже

@мама Стифлера · 01.02.2021, 20:32

Сообщение от повар1

где то и у кого то видел уже

Знамо где, у самого себя же

И кстати, дурной пример заразителен. Переменная 'с' совсем лишняя в вашем случае. Достаточно 'а' и 'b':

C++
1
2
b = a+b;
a = b-a;

@повар1 · 01.02.2021, 20:38

Сообщение от мама Стифлера

Достаточно 'а' и 'b'

это сложно будет понять заказчику

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@мама Стифлера из племени тумба-юбма 2523 / 1819 / 419 Регистрация: 29.11.2015 Сообщений: 8,852 Записей в блоге: 15
	01.02.2021, 13:21
	Если честно, то для меня не понятно начало отсчета данной последовательности. В разных местах по разному пишут: вариант1, где 1 элемент равен 0 1 = 0 2 = 1 3 = 1 4 = 2 5 = 3 6 = 5 вариант2, первый элемент равен 1 1 = 1 2 = 1 3 = 2 4 = 3 5 = 5 6 = 8 Отсюда возникает путаница. 0

@AlexVRud 694 / 304 / 99 Регистрация: 04.07.2014 Сообщений: 851
	01.02.2021, 16:05
	VLaDoS_2001a, Если на вход подать `0`, то есть выход за пределы массива. Возможно влияние оптимизации или защита в проверяющей системе. 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,679 Записей в блоге: 14
	01.02.2021, 16:58
	Если что, 45-е число Фибоначчи = 1836311903 1

Числа Фибоначчи

Решение