C++ Fibonacci

u0m3 · February 5, 2012

L.E.: este doar codul de generare a numerelor din sirul fibonacci... cmmdc mi se pare trivial si s-a discutat deja.

Edited February 5, 2012 by u0m3

Andrei · February 6, 2012

@u0m3 Imi place cum e scris dar iti dai seama ca in contextul de fata nu are sens. O varianta si mai eleganta a operatiilor pe numere mari este suprascrierea operatorilor. Ajungi sa faci A+B pe numere mari efectiv scriind A+B. :-)

gotr00t · February 6, 2012

Imi pare rau de greseala cu cel mai mic divizor comun, din neatentie.

Limitele sunt corecte! Multumesc de interes!

kNigHt · February 6, 2012

De ce va complicati?

knight@knight-G31M-ES2L ~/Documents/cpp $ ./fib 30000 2
Calculez fib(30000) de 2 ori...
Elapsed time: 1 milliseconds

knight@localhost ~/Documents/cpp $ ./fib 30000 1000
Calculez fib(30000) de 1000 ori...
Elapsed time: 291 milliseconds

Dual-core de 2.5

shaggi · February 6, 2012

function f(x:integer):integer;

begin

if x=0 then f:=0

else

if x=1 then f:=1

else

f:=a[i-1] + a[i-2];

end;

unde a este un vector in care se memoreaza valorile lui f

prin sintaxa

for i:=1 to 30000 do a:=f(i);

Parerea mea:)

Nu ruleaza instant si nu e in c++ dar e o metoda buna:))

u0m3 · February 6, 2012

@u0m3 Imi place cum e scris dar iti dai seama ca in contextul de fata nu are sens. O varianta si mai eleganta a operatiilor pe numere mari este suprascrierea operatorilor. Ajungi sa faci A+B pe numere mari efectiv scriind A+B.

Nu am mai avut rabdare sa fac clase, etc. Ar fi trebuit sa implementez si adunarea intr-o baza mai mare pentru a reduce numarul de operatii.

Cand voi avea timp il completez.

De ce va complicati?

knight@knight-G31M-ES2L ~/Documents/cpp $ ./fib 30000 2
Calculez fib(30000) de 2 ori...
Elapsed time: 1 milliseconds

knight@localhost ~/Documents/cpp $ ./fib 30000 1000
Calculez fib(30000) de 1000 ori...
Elapsed time: 291 milliseconds

Dual-core de 2.5

Poti arata codul? sunt chiar curios.

Edited February 6, 2012 by u0m3

DiP · February 10, 2012

Am incercat si eu:P.Nu am incercat sa vad ce timp de executie are.


#include<iostream>
using namespace std;

int f(int n)
{
  if((n==1)||(n==2))
      return 1;
  else
      return f(n-1)+f(n-2);
}


int cmmdc(int a,int 
{
  if(a>
     {int aux=a;a=b;b=aux;}
  if(b%a==0) return a;
  else return cmmdc(a,b-a);
}

int main()
{
  int n,m;
  cin>>n;
  cin>>m;
  cout<<cmmdc(f(n),f(m));
return 0;
}

Edited February 10, 2012 by DiP

kNigHt · February 10, 2012

Am incercat si eu:P.Nu am incercat sa vad ce timp de executie are.


#include<iostream>
using namespace std;

int f(int n)
{
  if((n==1)||(n==2))
      return 1;
  else
      return f(n-1)+f(n-2);
}


int cmmd(int a,int 
{
  if(a>
     {int aux=a;a=b;b=aux;}
  if(b%a==0) return a;
  else return cmmdc(a,b-a);
}

int main()
{
  int n,m;
  cin>>n;
  cin>>m;
  cout >>cmmd(f(n),f(m));
return 0;
}

Nu cred ca-ti incape fib(30k) intr-un integer.

@u0m3 nu mai am codul, il rescriu si revin mai pe seara cu el.

DiP · February 10, 2012

Nu cred ca-ti incape fib(30k) intr-un integer.

int-ul signed este aproximativ 4bytes si tine de la -2147483648 pana la 2147483647 (depinde de sistemul pe care il compilezi).Dar totusi e mai bine sa il declaram unsigned integer pentru ca asa ai acces si la numere mai mari si rezolvi si problema cu numerele negative,deci mersi pentru idee.Si mai am o gresala acolo la cout(trebuia sa pun<< scuze )

maftrunk · February 10, 2012

Vin si eu cu varianta pascal dar individualizat, poate prinde bine la unii.

1.Algoritm_Fibonacci{varianta recursiva}

2.Algoritm_cmmdc{prin scaderi repetate, varianta recursiva}


program algoritm_fibonacci;
 var n:integer;
    function fibo(k:integer):integer;
       begin
        if (k=1) or (k=2) then fibo:=1
                               else fibo:=(fibo(k-1)+fibo(k-2);
       end;
 begin
  write('n=');readln(n);
  writeln('termenul este= ',fibo(n));
  readln;
 end.

======================================================================


program algoritm_cmmdc;
 var m,n:integer;
   function cmmdc(m,n:integer):integer;
    begin
      if m=n then cmmdc:=m else
      if m>n then cmmdc:=cmmdc(m-n,n)
               else  cmmdc:=cmmdc(m,n-m);
    end;
 begin
  write('m,n=');readln(m,n);
  writeln('cmmdc este= ',cmmdc(m,n));
  readln;
 end.

Precizari

Aici la cele doua exemple pe care le-am scris in varianta recursiva nu sunt indicate pentru valori mari deoarece consuma foarte multa memorie din stiva prin urmare viteza de compilare va fi mica.
Am ales sa fac recursiv deoarece este mult mai simplificat si mai usor.
La cmmdc se poate face si cu Euclid.
Am facut particularizat nu la cerintele problemei.
Pentru cei care intra in theard si nu au habar ce este sirul lui Fibonacci :
Sirul lui Fibonacci este o secventa de numere in care fiecare numar se obtine prin adunarea precedentului la anteprecedentul lui si primele doua numere logic vor fi 1.

Nu am facut si in c++ pentru ca am vazut ca ati postat inainte destul de multe variante.

Edited February 10, 2012 by maftrunk

cmiN · February 10, 2012

Bitch please ... 0.85 secunde (worst case):

Ideone.com | Online Python Interpreter & Debugging Tool


#! /usr/bin/env python
# C++ Fibonacci challenge
# 10.02.2012 cmiN
# exponentiere a matricei Q fibonacci
# in timp logaritmic folosind numere mari


from decimal import getcontext, Decimal as D


class CFib:
    """
    Clasa pentru a calcula CMMDCul a 2 numere din seria Fibonacci.
    Se stie ca cmmdc(fib(a), fib() e acelasi lucru cu fib(cmmdc(a, )
    unde fib(x) este al x-lea numar din serie. Acesta poate fi calculat
    foarte rapid cu ridicarea unei matrice 2x2 specifice folosind
    ridicare la putere in logN.
    Totusi avem nevoie si de numere mari (decimal) ;].
    """

    def __init__(self, a, :
        # setam precizia in zecimale
        getcontext().prec = 7000 # nici al 30k-lea nu depaseste
        self.a = a
        self.b = b
        self.qmat = ((1, 1),
                     (1, 0))
        self.res = ((D(1), D(0)), # I2
                    (D(0), D(1)))

    def cmmdc(self, a, :
        """ Euclid cu impartiri. """
        while b != 0:
            t = a
            a = b
            b = t % b
        return a

    def multiply(self, op=False):
        if op: # op e True cand inmultim noua matrice Q cu rezultatul
            mat = self.res # doar o referinta / un sinonim catre un obiect
        else: # si False cand ridicam la patrat si retinem matricea Q
            mat = self.qmat
        # prea lenes sa bag 3 foruri
        e1 = mat[0][0] * self.qmat[0][0] + mat[0][1] * self.qmat[1][0]
        e2 = mat[0][0] * self.qmat[0][1] + mat[0][1] * self.qmat[1][1]
        e3 = mat[1][0] * self.qmat[0][0] + mat[1][1] * self.qmat[1][0]
        e4 = mat[1][0] * self.qmat[0][1] + mat[1][1] * self.qmat[1][1]
        # modificam rezultatul cu noile valori
        mat = ((e1, e2),
               (e3, e4))
        if op:
            self.res = mat
        else:
            self.qmat = mat

    def process(self):
        """ Functia principala. """
        nr = self.cmmdc(self.a, self.
        #print nr # debug
        # acum ridicam pe res la nr
        while nr > 0:
            if nr % 2: # putere impara
                self.multiply(True) # inmultim cu rezultatul
            self.multiply() # multiplicam qmat
            nr /= 2

    def get(self):
        return str(self.res[0][1]) # (Q^n)[0][1] == F(n)


def main():
    (a,  = raw_input("Introdu 2 numere: ").split()
    obj = CFib(int(a), int()
    obj.process()
    print obj.get()


if __name__ == "__main__":
    main()

Codul e comentat nu mai e nevoie de explicatii, implementati asta in C/C++ si veti obtine un timp mult mai bun. O biblioteca light pentru numere mari gasiti aici.

Sign In

C++ Fibonacci

Recommended Posts

u0m3

Andrei

gotr00t

kNigHt

shaggi

u0m3

DiP

kNigHt

DiP

maftrunk

cmiN

Join the conversation

Browse

Activity

Pages