#include <iostream>
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int previously[n]={},next[n]={}; //n/4 - nth number will have n/4 digit
int temp[n/4+1]={},i,mx;
previously[n/4]=0;
next[n/4]=1;
int w;
short move=0;
for(int j=0;j<n;j++){
mx=n/4;
for(i=n/4;i>=0;i--) //nast=nast+pop
{
temp[i]=next[i]; //temp=nast
if(mx)
{
w=next[mx]+previously[i]+move;
next[mx]=w%10;
move=w/10;
mx--;
}
else
{
w=next[mx]+move;
next[mx]=w%10;
move=w/10;
}
previously[i]=temp[i]; //pop=temp
}
}
for(int i=0;i<n/4;i++)cout<<next[i];
return 0;
}
Nie kompiluje się w ogóle. Poza tym bardzo skomplikowany ten kod jak na ciąg Fibonacciego. Jeżeli to ma być n-ty wyraz ciągu to wystarczy stworzyć dynamiczną tablicę i w pętli tworzyć kolejne wyrazy ciągu aż do n. Chyba, że to ma działać jakoś inaczej
Skomplikowany bo w zwyklym unsigned long long nie zmiesci sie cala liczba, przy 1000 wyrazie liczba bedzie miala juz 250cyfr.
Przy takim zakresie mozna uzyc dodawania pisemnego na char[]
Tutaj jest na stringach, ale znowu wkradl sie blad. Jakies sugestie?
#include <iostream>
#include <string>
using namespace std;
string fib(int m){
string pop,nast;string wynik;
int temp,przeniesienie=0,min,max,n;
pop=48; //przypisanie 0
nast=49; // przypisanie 1
for(int i=0;i<m;i++){ //ogolna 1petla
/*
* ogolna koncepcja algorytmu:
*
* temp=nast
* nast=pop+nast(2petla)
* pop=nast
*
* */
min = pop.length();
n=min;
max = nast.length();
for(int k = 1; k <= n; k++) //2petla dodajaca 2 liczby
{
temp = (int)(pop[--min]) + (int)(nast[--max]) + przeniesienie - 96;
przeniesienie = temp / 10;
wynik = (char)((temp % 10) + 48) + wynik;
}
while(max) //jesli wyraz 'nast' jest dluzszy od 'min'
{
temp = nast[--max] + przeniesienie - 48;
przeniesienie = temp / 10;
wynik = (char)((temp % 10) + 48) + wynik;
}
if(przeniesienie) wynik = (char)(przeniesienie + 48) + wynik;
pop=nast;
nast=wynik;
}
if(m==2) return "1";
return pop;
}
int main()
{
int x;
cin>>x;
cout << fib(x);
}
100 tysięcy? Wyobrażasz sobie jaka to liczba jest?
Istnieje wzór na n-ty wyraz ciągu i na pewno ułatwi Ci on sprawę. https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego
Jeśli możesz skorzystać z bigintowej biblioteki (np z boost
), to będzie to najsensowniejsze rozwiązanie. I na pewno dużo szybsze niż działanie na stringu.
Mały OT, kod w Pythonie wygląda tak:
def fibo(n):
a,b = 0,1
i = 1
while i<n:
a,b = b,a+b
i+=1
return b
n = input("Ktory wyraz ciagu Fibonacciego obliczyc: ")
print(str(n)+"-ty wyraz ciagu Fibonacciego = "+str(fibo(n)))
Wykonanie dla n=100 000 (łącznie z wypisaniem) trwa sekundę.
Kod w pythonie wyglada całkiem prosto :D
#include <iostream>
#include <string>
using namespace std;
string fib(int m){
string pop,nast;string wynik;
int temp,przeniesienie=0,min,max,n;
pop=48;
nast=49;
for(int i=0;i<m;i++){
wynik="";
min = pop.length();
n=min;
max = nast.length();
for(int k = 1; k <= n; k++)
{
temp = (int)(pop[--min]) + (int)(nast[--max]) + przeniesienie - 96;
przeniesienie = temp / 10;
wynik = (char)((temp % 10) + 48) + wynik;
}
if(przeniesienie == 1 && min==max) wynik = (char)(przeniesienie + 48) + wynik;
else if(przeniesienie == 1&& min!= max) wynik = (char)(nast[0]+1)+wynik;
else if(przeniesienie ==0 && min!=max) wynik=(char)nast[0]+wynik;
pop=nast;
nast=wynik;
przeniesienie =0;
}
if(m==2) return "1";
return pop;
}
int main()
{
int x;
cin>>x;
cout << fib(x);
}
Jak na sprawdzarke idzie to na stringach nie przejdzie.
Po co robisz to +48
i całą resztę?
Nie możesz po ludzku zrobić tego na zasadzie, że ASCII 0
odpowiada cyfrze 0
i tak dalej? :P