C++ Fibonacci

[u0m3]

Ce parere aveti de #3324297 - Pastie?

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]

@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]

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

Limitele sunt corecte! Multumesc de interes!

[kNigHt]

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]

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]

@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]

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]

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]

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]

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]

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.