C++ Fibonacci

gotr00t · February 5, 2012

Ca tot a postat pr00f sa se laude...[joke]

Se dau doua numere n si m(n,m apartinand multimii nr naturale). Se cere sa se calculeze cel mare mare divizor comun dintre f(n) si f(m), unde "f()" reprezinta functia de generare a unui termen din sirul lui Fibonacci. De exemplu f(3)=termenul 3 din sirul lui Fibonacci.

Restrictii:

0<n,m<30.000

timp de executie <1 sec

Stiu ca pentru unii e o nimica toata, dar e buna pentru exercitiu si putina gandire. S-a dat la un concurs local de info.

Edited February 6, 2012 by gotr00t

Pugna · February 5, 2012

Daca vreau sa-l scriu in PHP, APC se ia in calcul ? :))

gotr00t · February 5, 2012

de preferat c, dar algoritmul conteaza.

pr00f · February 5, 2012

C++ code - 31 lines - codepad

Patrunjel · February 5, 2012

Poti fie sa le generezi separat, sau ai putea sa incerci niste tweak-uri cu matematica (in caz ca ai numere mari si nu-ti intra in timp). Daca imi vine vreo idee vin cu edit.

Edited February 5, 2012 by Patrunjel

gotr00t · February 5, 2012

pr00f, recursiva aia in ce timpi iti ruleaza la n,m >150?

pr00f · February 5, 2012

pr00f, recursiva aia in ce timpi iti ruleaza la n,m >150?

Citisem pe un site c? la recursiv? de 100 aveam de a?teptat vreo câteva zeci/sute ani. L?s?m recursiva dac? vrem valori mari ?i trecem pe for-uri.

C++ code - 33 lines - codepad

l.e. : numerele sunt foarte mari, e posibil s? crape compilatoarele.

Edited February 5, 2012 by pr00f

shaggi · February 5, 2012

http://challange.tk/pascal/BIN.rar

Tot recursiva facuta-n graba:))

E lenea mare sa opresc filmu' acum:))

Robert1995 · February 5, 2012

presupun ca ideea e sa te bazezi pe array si sa ai ceva de genul

array[0] = 11001000

array[2] = 2000334

si faci cumva output sa iasa 110010002000334 + ca va fi greu la calculat

skull · February 5, 2012

Ca tot a postat pr00f sa se laude...[joke]
Se cere sa se calculeze cel mai mic divizor comun dintre ...

Cred ca ai vrut sa zici cel mai mare divizor comun, cel mai mic ar fi 1.

Al n-lea termen Fibonacci se poate determina in O(log n) cu inmultiri de matrici.

begood · February 5, 2012


#include <stdio.h>
#include <math.h>
#include <conio.h>


long gcd(long a, long  {
    for (long r = a % b; r != 0; a = b, b = r, r = a % ;
    return b;
}

int main (){
    float phi=(sqrt(5)+1)/2;
    long a,b;
    int x,y;

    printf("Primul numar: ");
    scanf("%d",&x);

    printf("\nAl doilea numar: ");
    scanf("%d",&y);

    a=(long)((pow(phi,x) - pow(-phi,-x)) / sqrt(5));
    b=(long)((pow(phi,y) - pow(-phi,-y)) / sqrt(5));

    printf("\nf(%d)=%lu\nf(%d)=%lu",x,a,y,;
    printf("\nCMMDC(f(a),f(= %lu",gcd(a,);
    printf("\nUnde f(a) este numarul din sirul fibonacci de pe pozitia a.");
    getch();
    return 0;
}

Al n-lea termen Fibonacci se poate determina in O(log n) cu inmultiri de matrici.

@skull

ce zici de metoda mea ?

em · February 5, 2012


#include <stdio.h>
#include <math.h>
#include <conio.h>


long gcd(long a, long  {
    for (long r = a % b; r != 0; a = b, b = r, r = a % ;
    return b;
}

int main (){
    float phi=(sqrt(5)+1)/2;
    long a,b;
    int x,y;

    printf("Primul numar: ");
    scanf("%d",&x);

    printf("\nAl doilea numar: ");
    scanf("%d",&y);

    a=(long)((pow(phi,x) - pow(-phi,-x)) / sqrt(5));
    b=(long)((pow(phi,y) - pow(-phi,-y)) / sqrt(5));

    printf("\nf(%d)=%lu\nf(%d)=%lu",x,a,y,;
    printf("\nCMMDC(f(a),f(= %lu",gcd(a,);
    printf("\nUnde f(a) este numarul din sirul fibonacci de pe pozitia a.");
    getch();
    return 0;
}

@skull

ce zici de metoda mea ?

Fib(35) e un contraexemplu. E normal s? se piard? din precizie la numere mari.

begood · February 5, 2012

plm dai un ceil acolo.

true, diferenta e maricica. dar sunt sigur ca se poate optimiza cu putin efort.

Edited February 5, 2012 by begood

em · February 5, 2012

Se dau doua numere n si m(n,m apartinand multimii nr naturale). Se cere sa se calculeze cel mai mic divizor comun dintre [...]


#include <iostream>
using namespace std;
int main()
{
     cout<<1;
     return 0;
}

BEAT THIS! O(1)

begood · February 5, 2012

acum demonstreaza ca-s mereu prime intre ele.

skull · February 5, 2012

@begood Ridicarea la putere nu se face constant, pe caz mediu avand tot O(log N). In plus, dupa cum zicea si em, s-ar putea sa o dea in balarii cand calculeaza, unele zecimale fiind in afara mantisei.

Edited February 5, 2012 by skull

em · February 5, 2012

@begood

Cel mai MIC divizor comun. MIC, nu MARE.

(Da, mi-am dat seama ca a gresit, dar la fel cum a gresit la asta eu cred ca a gresit limita superioara, fib(30.000) mi se pare foarte mare - 6000 de cifre).

Poate doar cu o rezolvare matematic? s? intre în timp.

Edited February 5, 2012 by em

em · February 5, 2012

Sau poate s-a referit la cel mai mic multiplu comun.

begood · February 5, 2012

poate poti prezice divizorii in functie de pozitie.

Andrei · February 5, 2012

@em Cateva puncte la o olimpiada iei cu implementare pe numere mari. Prima varianta ce imi vine in minte e sa faci CMMDC ( FIB ( MAX ( N,M))) in numere mari. Dar asta e varianta naiva. Totusi, implementarea prin matrici pentru FIB ne scoate repejor.

Nu sunt sigur, dar auzisem de o formula ceva de genul : cmmdc(fib(a),fib()=fib(cmmdc(a,). Bafta! :-)

LE: Da, am dreptate. Cititi la "Induc?ie, recursivitate ?i coborâre infinit?

" http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid

Edited February 5, 2012 by Andrei

u0m3 · February 5, 2012

Ca tot a postat pr00f sa se laude...[joke]
Se dau doua numere n si m(n,m apartinand multimii nr naturale). Se cere sa se calculeze cel mai mic divizor comun dintre f(n) si f(m), unde "f()" reprezinta functia de generare a unui termen din sirul lui Fibonacci. De exemplu f(3)=termenul 3 din sirul lui Fibonacci.
Restrictii:
0<n,m<30.000
timp de executie <1 sec
Stiu ca pentru unii e o nimica toata, dar e buna pentru exercitiu si putina gandire. S-a dat la un concurs local de info.

Cam vaga exprimarea: codul executat pe un procesor la 3GHz intr-o secunda va necesita mai mult timp de executie pe un procesor la 133MHz; parerea mea.... Doar daca chiar se cere cel mai mic divizor comun :))

Cazul in care cel mai mare divizor comun, conform wikipedia exista o "teorema": GCD(f(n), f(m)) = f(GCD(n, m)) (GCD - Greatest Common Divisor = Cel Mai Mare Divizor Comun)

Cred ca ai vrut sa zici cel mai mare divizor comun, cel mai mic ar fi 1.
Al n-lea termen Fibonacci se poate determina in O(log n) cu inmultiri de matrici.


#include <stdio.h>
#include <math.h>
#include <conio.h>


long gcd(long a, long  {
    for (long r = a % b; r != 0; a = b, b = r, r = a % ;
    return b;
}

int main (){
    float phi=(sqrt(5)+1)/2;
    long a,b;
    int x,y;

    printf("Primul numar: ");
    scanf("%d",&x);

    printf("\nAl doilea numar: ");
    scanf("%d",&y);

    a=(long)((pow(phi,x) - pow(-phi,-x)) / sqrt(5));
    b=(long)((pow(phi,y) - pow(-phi,-y)) / sqrt(5));

    printf("\nf(%d)=%lu\nf(%d)=%lu",x,a,y,;
    printf("\nCMMDC(f(a),f(= %lu",gcd(a,);
    printf("\nUnde f(a) este numarul din sirul fibonacci de pe pozitia a.");
    getch();
    return 0;
}

@skull

ce zici de metoda mea ?

Tot nu cred ca iti va afisa pentru n=1000 (ma refer la al n-lea termen fibonacii) deoarece acel numar il putem aproxima la 4.35 * 10 ^ 208. Si se cere pentru n si m cuprinse in intervalul [1, 29999]. Si nici varianta cu inmultirea de matrici nu va functiona din aceleasi rationamente (cel putin nu implemnetarea aceasta - daca ar fi in C - Fast Logarithmic Time Fibonacci – AlgoPill)


#include <iostream>
using namespace std;
int main()
{
     cout<<1;
     return 0;
}

BEAT THIS! O(1)

This counts?

; SmallesCommonDivisorFibonacci.as:
; Title: Cel Mai Mic Divizor Comun Intre Doua Numere Fibonacci
.model small

.stack 100h

.data
message db 'Cel mai mic divizor comun este 1.', 13, 10, '$'

.code
start:
mov ax, @data
mov ds, ax
mov dx, offset message	; copy address of message to dx
mov ah, 9h				; string output command
int 21h					; execute command in ah - display string

mov ax, 4c00h			; return to MS-DOS (ah = exit to dos; al=00 return code)
int 21h					; execute command in ah
end start

em · February 5, 2012

@Andrei, formula ta este corect?. Habar nu aveam de ea, bravo.

Ar mai fi de ad?ugat c? dac? ai la intrare (a, cu a<b calculezi mai intai Fib(a), apoi Fib( pornind de la rezultatul precedent. (Nu o mai iei de la capat).

Uita?i cum s-ar face

http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

Ce inteleg eu din ultimul rând este c?

Edited February 5, 2012 by em

begood · February 5, 2012

verfica cineva (bruteforce/demonstratie matematica) daca gcd(fib(a,)==fib(gcd(a,) ?

ar fi bine de stiut sigur.

LE: am gasit-o. nu stiam de ea. bravos !

u0m3 · February 5, 2012

verfica cineva (bruteforce/demonstratie matematica) daca gcd(fib(a,)==fib(gcd(a,) ?
ar fi bine de stiut sigur.
LE: am gasit-o. nu stiam de ea. bravos !

A confirmat Andrei cu un link la un articol.

Andrei · February 5, 2012

Hmm, se rezolva problema numerelor mari aplicand la varianta cu exponentiere rapida cu modulo. :-)

Edited February 5, 2012 by Andrei

Sign In

C++ Fibonacci

Recommended Posts

gotr00t

Pugna

gotr00t

pr00f

Patrunjel

gotr00t

pr00f

shaggi

Robert1995

skull

begood

em

begood

em

begood

skull

em

em

begood

Andrei

u0m3

em

begood

u0m3

Andrei

Join the conversation

Browse

Activity

Pages