Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Fibonacci ali sa O(n)

[es] :: Art of Programming :: Fibonacci ali sa O(n)

[ Pregleda: 3642 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

bags

Član broj: 10072
Poruke: 715
*.12.15.tuwien.teleweb.at.



+2 Profil

icon Fibonacci ali sa O(n)17.03.2005. u 10:09 - pre 202 meseci
Treba mi pomoc :

Moram uraditi algoritam za fibbonaci niz ali sa vremenom O(n) plus mora biti rekurzivan.
Apsolutno mi ne pada na pamet kako

Fibbonaci niz : f(n) = ( 1 ako je n =< 2
f(n-1)+f(n-2) ako je n > 2 )


Pozdrav
Free advice is seldom cheap.
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 10:31 - pre 202 meseci
Nisam neki stručnjak za složenost, ali da pokušam:
Code:

using System;

namespace ConsoleApplication2
{
    /// <summary>
    /// Summary description for Class1.
    /// </summary>
    class Class1
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main(string[] args)
        {
            //
            // TODO: Add code to start application here
            //

            int a;
            int b;
            fib (7, out a, out b);
        }

        static void fib(int i, out int sa, out int sb) 
        {
            int sc;
            int sd;

            if (i <= 2) 
            {
                sa = 1; sb = 1;
            }
            else 
            {
                fib(i - 2, out sc, out sd);
                sa = sc + sd;
                sb = sd + sa;
            }
            Console.Write(sa.ToString() + " " + sb.ToString() + " ");
        }
    }
}
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1236



+93 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 11:04 - pre 202 meseci
Jel' ovo Java ili C#?

Sećam se da sam u C++ video rešenje koje koristi std::pair kao povratnu vrednost rekurzivne funkcije. To bi stvarno animiralo profesora...

[Ovu poruku je menjao Mihajlo Cvetanović dana 17.03.2005. u 14:20 GMT+1]
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 12:07 - pre 202 meseci
Citat:
Mihajlo Cvetanović: Jel' ovo Java ili C#?

C#. Da, pair bi super bio (vidiš, to mi nije palo na pamet), u .NET-u postoji, ali je smešten u Web namespaceu. U principu, uvek može da se napravi.
 
Odgovor na temu

zi::
Igor Marinović
Manufaktura doo Internet inženjering
Palić

Član broj: 18090
Poruke: 642
*.manufacture.co.yu.

ICQ: 7715569
Sajt: www.marinowski.com


Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 12:21 - pre 202 meseci
Rekurzivni fibonacci se racuna stvarno ako samo moras, za potrebe pokazivanja i rekurzije.

Fibonacci se moze izracunati i sa O(log n) ...
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1236



+93 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 13:45 - pre 202 meseci
Log n? Kako? Znam za računanje Fibonačijevog broja preko stepena zlatnog preseka (što bi bilo O(1)), ali za O(log n) nisam čuo.
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 13:48 - pre 202 meseci
Ček ček jel vi pričate o nalaženju niza ili samo jedne vrednosti f(n)?
 
Odgovor na temu

zi::
Igor Marinović
Manufaktura doo Internet inženjering
Palić

Član broj: 18090
Poruke: 642
*.manufacture.co.yu.

ICQ: 7715569
Sajt: www.marinowski.com


Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 13:55 - pre 202 meseci
Jedne vrednosti ...

Pogledacu kuci algoritam za O(log n), nije bas trivijalan.

Stepen (pa i zlatnog preseka) nije O(1), jer za racunanje stepena treba vise nego konstantno vreme.
 
Odgovor na temu

bags

Član broj: 10072
Poruke: 715
*.12.15.tuwien.teleweb.at.



+2 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 14:37 - pre 202 meseci
Hvala na odgovoru .

Posto mi ne radimo c# nego neki pseudo jezik imam jos jednom pitanje.

Kada incijalizujes sc i sd njihova pocetna vrednost je nula ili ... ?


Free advice is seldom cheap.
 
Odgovor na temu

Damjan S. Vujnovic
London, UK

Član broj: 30444
Poruke: 81
*.ceetel.co.yu.

Jabber: damjan@elitesecurity.org
ICQ: 68189289
Sajt: www.javasvet.net


Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 14:54 - pre 202 meseci
U vezi sa O(log n) algoritmom...

http://en.wikipedia.org/wiki/F...number_program#Matrix_equation

pogledati po "Matrix equation".

Ideja je da se n-ti stepen matrice nadje sukcesivnim kvadriranjima i ocigledno je primenljiva i na onu formulu sa sqrt(5) (zlatni presek, kao sto neko vec rece), ali kada se koristi matrica nema problema sa ne-celim brojevima i tacnosti.

D.

[Ovu poruku je menjao Damjan S. Vujnovic dana 17.03.2005. u 15:57 GMT+1]
I love the smell of copyright violations in the morning. Smells like... freedom!
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 14:55 - pre 202 meseci
Ako malo bolje proučiš kood, videćeš da je nebitna inicijalna vrednost te dve promenljive, pošto se one pune rekurzivnim pozivom funkcije, tj. inicijalizuje ih funkcija, vrativši rezultat u njima.

Pseudokodno, onaj rekurzivni poziv je ustvari (sc, sd) = fib(i - 2). Ok?
 
Odgovor na temu

bags

Član broj: 10072
Poruke: 715
*.12.15.tuwien.teleweb.at.



+2 Profil

icon Re: Fibonacci ali sa O(n)17.03.2005. u 15:12 - pre 202 meseci
Sad je sve jasno. Imas pivo kad navratim do BG-a . ;)
Free advice is seldom cheap.
 
Odgovor na temu

sklitzz

Član broj: 54393
Poruke: 13
*.net.t-com.hr.



Profil

icon Re: Fibonacci ali sa O(n)04.04.2005. u 17:02 - pre 201 meseci
Pa mogla bi se ta složenost uhvatiti sa metodom memoizacije, evo primjera:

Code:

#include <iostream>
using namespace std;

int niz[100] = { 0 };

int fib( int n )
{
    if( n == 0 ) return 0;
    else if( n == 1 ) return 1;
    else if( niz[n] > 0 ) return niz[n];
    else
    {
        //Memoizacija
        niz[n] = fib( n - 1 ) + fib( n - 2 );
        return niz[n];
    }
}

int main()
{
    int n; cin >> n;
    
    niz[0] = 0;
    niz[1] = 1;
    
    cout << fib( n ) << endl;
    return 0;
}

 
Odgovor na temu

zi::
Igor Marinović
Manufaktura doo Internet inženjering
Palić

Član broj: 18090
Poruke: 642
*.tippnet.co.yu.

ICQ: 7715569
Sajt: www.marinowski.com


Profil

icon Re: Fibonacci ali sa O(n)04.04.2005. u 17:27 - pre 201 meseci
Interesantno, ovako ti treba i mesta O(n), sto nije zanemarivo. Doduse, dobijes sve Fibonaccijeve brojeve do n-tog ...
 
Odgovor na temu

sklitzz

Član broj: 54393
Poruke: 13
*.net.t-com.hr.



Profil

icon Re: Fibonacci ali sa O(n)04.04.2005. u 19:03 - pre 201 meseci
Da ali je puno brze i isplativije i jednom kad ih izracunas imas O(1) za dobiti bilo koji
fibonacciev broj.
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.sbb.co.yu.

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Fibonacci ali sa O(n)04.04.2005. u 22:00 - pre 201 meseci
Citat:
bags:
Moram uraditi algoritam za fibbonaci niz ali sa vremenom O(n) plus mora biti rekurzivan.

:) Dakle ceo niz + rekurzivan + O(n), tako da je samo ovo poslenje rešenje ispravno, kako se meni čini

BTW, da nije uslov rekurzija i da ne treba ceo niz, moglo bi na još par načina da se odradi, evo nešto napamet, moguće je i da ne radi tačno, ali bar je ideja tu
Code:
// O(n)
int fibonaci1(int n)
{
    int f2 = 1;    // f(0) = 1
    int f1 = 1;     // f(1) = 1
    int i;
    for(i=2; i<=n; i++)
    {
        f = f2 + f1;
        f2 = f1;
        f1 = f;
    }
    return f;
}
// O(1) - uslovno, ako zanemarimo slozenost funkcije pow
int fibonaci2(int n)
{
    float sqrt5 = pow(5, 0.5) / 0.5;    
    return (int) ((pow(0.5 + sqrt5, n) - pow(0.5 - sqrt5, n)) / (sqrt5 * 2.0));
}

ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

sklitzz

Član broj: 54393
Poruke: 13
*.net.t-com.hr.



Profil

icon Re: Fibonacci ali sa O(n)05.04.2005. u 13:57 - pre 201 meseci
Gdje je tu tebi rekurzija?
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.sbb.co.yu.

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Fibonacci ali sa O(n)06.04.2005. u 01:16 - pre 201 meseci
Pa u tvom rešenju je ima, ko što rekoh:
Citat:
trooper: Dakle ceo niz + rekurzivan + O(n), tako da je samo ovo poslenje rešenje ispravno, kako se meni čini

a ova moja rešenja sam poslao čisto informativno, ko što sam naglasio:
Citat:
trooper: da nije uslov rekurzija i da ne treba ceo niz


damn, mrzim da sam sebe citiram.
ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

[es] :: Art of Programming :: Fibonacci ali sa O(n)

[ Pregleda: 3642 | Odgovora: 17 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.