C++ Fibonacci

[gotr00t]

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]

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

[gotr00t]

de preferat c, dar algoritmul conteaza.

[pr00f]

C++ code - 31 lines - codepad

[Patrunjel]

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]

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

[pr00f]

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]

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

Tot recursiva facuta-n graba:))

E lenea mare sa opresc filmu' acum:))

[Robert1995]

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]

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]

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

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

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]

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]

acum demonstreaza ca-s mereu prime intre ele.

[skull]

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

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

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

[begood]

poate poti prezice divizorii in functie de pozitie.

[Andrei]

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

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]

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

gcd(a,=c <=> gcd(fib(a),fib()=fib© deci nu mai avem un numar asa de mare de calculat.

Edited February 5, 2012 by em

[begood]

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]

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]

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

Edited February 5, 2012 by Andrei