Nty wyraz ciagu, sumowanie komorek dwoch tablic

0
#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;
}
1

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

0

Skomplikowany bo w zwyklym unsigned long long nie zmiesci sie cala liczba, przy 1000 wyrazie liczba bedzie miala juz 250cyfr.

1

Przy takim zakresie mozna uzyc dodawania pisemnego na char[]

0

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);
}
1

100 tysięcy? Wyobrażasz sobie jaka to liczba jest?

1

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

1

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.

1

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ę.

0

Kod w pythonie wyglada całkiem prosto :D

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0