C/C++

Задача "Числа Фибоначчи"

Последовательность Фибоначчи определена следующим образом: φ0=1, φ1=1, φn=φn−1+φn−2 при n>1. Начало ряда Фибоначчи выглядит следующим образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Напишите функцию vector phi(int n), которая по данному натуральному n возвращает последовательность Фибоначчи до n-го члена включительно.
Примеры
Ввод
5
Вывод
1 1 2 3 5 8
Необходимо дополнить код ниже








#include <iostream>
#include <vector>
using namespace std;
vector<int> phi(int n)


int main()
{
int n;
cin >> n;
vector<int> res = phi(n);
for (int i = 0; i < res.size(); ++i){
cout << res[i] << " ";
}
return 0;
}
Айдар Адильбеков
Айдар Адильбеков
348 
 

 

#include 

 

#include 

 

using namespace std;

 

vector phi(int n)

 



 



 

int main()

 

{

 

int n;

 

cin >> n;

 

vector res = phi(n);

 

for (int i = 0; i < res.size(); ++i){

 

cout
Денис Минин
Денис Минин
793
Лучший ответ 
 #include  

#include  

using namespace std; 

vector phi(const size_t n) { 

    vector res(n); 

    if (n > 0) res[0] = 1; 

    if (n > 1) res[1] = 1; 

    for (int i = 2; i < n; ++i) res[i] = res[i - 2] + res[i - 1]; 

    return res; 

} 

int main() { 

    size_t n; 

    cin >> n; 

    auto fib = phi(n); 

    for (auto x : fib) cout
Евгений Попцев
Евгений Попцев
67 998
Rus : ) Автор капитально всё запутал, сместив номера элементов! Ряд ведь на самом деле такой: φ₀=0, φ₁=1, φ₂=1, φ₃=2 -так ведь всегда было, не так ли? Вот и у Вас при n=10 вычисляется и выдаётся вектор из первых десяти натуральных номеров ряда Фибоначчи от 1 до 55, как, собственно, и должно быть. Только Автору то ведь надо выдать на одно число больше, то есть последним должно быть не 55, а 89, которое у него десятый номер в ряду, хотя на самом деле одиннадцатый... :-)
Вы же сами написали, что φ₀=1, φ₁=1 и т.д., поэтому начало ряда Фибоначчи выглядит так: 0 1 1 2 3 5 8 13 21 34 55 ... Но даже если ноль в ряд не включать, то при n=5 вывода 1 1 2 3 5 8 никак получится не должно! Так что сначала лучше-ка уточните свой вопрос, потому что если с самого начала в спецификации задача такая ерунда, то и всё остальное автоматически ставится под очень большое сомнение...
А вообще для больших натуральных n (хоть до нескольких тысяч, а то и больше !) можно сделать, например, так (цикл while можно убрать, если в нём нет нужды):
#include <vector>
#include <gmpxx.h>
#include <iostream>
using namespace std;
vector <mpz_class> pfi(int n)
{ vector <mpz_class> f = { 0 };
if (n == 0) return f; f.push_back(1);
if (n == 1) return f; for (int i = 1; i < n; i++)
f.push_back(f[i] + f[i - 1]); return f; }
int main()
{ vector <mpz_class> res; int i, n; while (true)
{ cout << "n: "; cin >> n; res = pfi(n);
for (i = 0; i <= n; i++) cout << res[i] << ' ';
cout << endl; res.clear(); } }
А если надо всё таки использовать (четырёхбайтный знаковый) тип int, тогда лучше так:
#include <vector>
#include <iostream>
using namespace std;
vector <int> pfi(int n)
{ vector <int> f = { 0 }; if (n == 0) return f;
f.push_back(1); if (n == 1) return f;
for (int i = 1; i < n; i++) f.push_back(f[i] + f[i - 1]);
return f; }
int main()
{ vector <int> res; int i, n; while (true)
{ cout << "n: "; cin >> n; res = pfi(n);
for (i = 0; i <= n; i++) cout << res[i] << ' ';
cout << endl; res.clear(); } }
Только так будет правильно работать только до n=46 включительно, так как числа Фибоначчи с номерами больше сорока шести числами типа int не выразить. Смотрите:
СА
Сабухи Абдуллаев
66 572
Сабухи Абдуллаев И ещё одна пикантная деталь: между прочим, ISO (эта Международная Организации Стандартизации, в которой состоит и РФ, а значит и в РФ должны действовать стандарты ISO) включает ноль в число натуральных чисел ℕ. Поэтому у меня обе программы сделаны как раз с учётом этого обстоятельства...
Сабухи Абдуллаев А, вот в чём ошибка: φ₀=0 должно быть в начале -такова традиция! Иначе -да, всё правильно: при n=5 вывод должен быть 1 1 2 3 5 8. Что-то я тогда как-то не разобралась... :-) 
 vector phi(int i)

 

{

	vector vec{ 1 };

	vec.reserve(i + 1);

	int prev = 0;

	while (i--)

	{

		vec.push_back(vec.back() + prev);

		prev = *( & vec.back() - 1);

	}

	return vec;

}
Muradil Kazmatov
Muradil Kazmatov
51 416 
 vector phi(int k) {

    vector prev;

    if (k < 2) {

        (k == 1) ? prev = {1, 1} : prev = {1};

        return prev;

    }

    prev = phi(k - 1);

    prev.push_back(prev[prev.size() - 1] + prev[prev.size() - 2]);

    return prev;

}
Вот тебе функция phi(k), как ее использовать, думаю, сам разберешься
Resul Aras
Resul Aras
12 614

Похожие вопросы