Domanda Inizio corso di algoritmi e strutture dati

[narakuyama]

Salve a tutti . Sono uno studente di informatica al primo anno e ho un bel po di problemi con le nozioni iniziale di algoritmi e strutture dati .
In particolare ho problemi nel capire il costo e le funzioni ricorsive e il loro relativo costo .
Se qualcuno potrebbe aiutarmi ne sarei molto grato .
Thx Nara

 

[P_1_6]

La ricorsione:
immagina di avere n matriosche non colorate una nell'altra e per colorare la più grande devi colorare quella meno grande quindi se devi colorarle tutte devi prima aprirle tutte per colorare la più piccola per poi colorare quella subito più grande e così via fino ad arrivare alla più grande.
Il costo:
supponiamo che per colorare ogni singola matriosca impieghi m colori allora il costo sarà n*m

comunque aspetta altre spiegazioni io potrei sbagliarmi

 

[P_1_6]

Quello di sopra è un primo approccio ora ti spiego meglio
supponiamo di avere infinite matriosche una nell'altra il meccanismo è lo stesso apri finchè non trovi in una matriosca i colori e le altre matriosche restanti a questo punto fermati e inizia a colorare e a richiudere.
colora e richiudi,...., colora e richiudi fino a colorare e chiudere la più grande

 

[narakuyama]

Quindi il costo sarebbe n^2 ?

 

[P_1_6]

Siccome m(numero colori) è una costante il costo è n (numero delle matriosche da aprire).
Però aspetta altre opinioni.

 

[narakuyama]

emm seguendo il tuo discorso però vengono fatte almeno due operazioni per ogni matriosca quindi penso che il costo dovrebbe essere quello ahahah

 

[St3ve]

In particolare ho problemi nel capire il costo e le funzioni ricorsive e il loro relativo costo .

Questa non è la sezione più adatta, se postavi sotto Informatica o da qualche parte nella sezione Dev probabilmente trovavi più gente. Per la ricorsione dai un'occhiata a queste due guide: 1, 2. Se poi non capisci qualcosa, chiedi pure.

Sei stato un po' troppo generico con le domande, spendi qualche parola in più per farci capire quante cose sai e dove hai problemi. Se porti degli esempi possiamo anche fare il calcolo della complessità.

Quindi il costo sarebbe n^2 ?

Parlare di tempo di calcolo senza mostrare l'algoritmo non ha alcun senso. State tirando i numeri a caso.
Un algoritmo è una serie di istruzioni ben precise e dettagliate, non un discorso fatto in due parole del tipo "massì dai, ci siamo capiti... per colorare la matriosca più grande devi prima colorare la più piccola". Prendi un algoritmo vero, scrivilo e discutiamo su quello.

 

[narakuyama]

int Euclide(int a, int b) // prototipo della funzione Euclide //
{
while(b) //ripetere finché non riduciamo a zero
{
int r = a%b;
a=b;
b=r; //scambiamo il ruolo di a e b
}
return a; //... e quando b è (o è diventato) 0, il risultato è a
}

Lui è quello che mi crea più problemi ho capito cosa vuole ma non ho capito a quanto equivale il costo

 

[St3ve]

Ecco, qui hai ragione ad avere qualche problema. Questo algoritmo non è proprio un bel punto di partenza perché c'è di mezzo un po' di matematica, ma ok... facciamo almeno qualcosa. Prendiamo questo codice, equivalente al tuo:

procedure euclide(a, b) // assumiamo a > b
    if (b == 0)  return a
    else return euclide(b, a mod b)

Vogliamo calcolare il tempo di calcolo nel caso peggiore utilizzando il criterio di costo uniforme. È evidente che il caso peggiore capita quando massimo comun divisore tra i due numeri è 1, ovvero quando a e b sono coprimi. Chiaramente (utilizzando il criterio di costo uniforme) tutte le operazioni fatte in una singola chiamata alla funzione richiedono un tempo costante, chiamiamolo C. Il costo complessivo sarà dato solo dal numero di chiamate ricorsive moltiplicate per questa costante C.

Se volessimo calcolare l'esatto tempo di calcolo, dovremmo risolvere un equazione di questo tipo:
T(a, b) = C + T(b, a mod b) = C + (C + T(a mod b, b mod (a mod b)) = 2C + T(a mod b, b mod (a mod b)) = ... = kC

Visto che capire cos'è questo k non è proprio banale, iniziamo a dimostrare che k <= b.
Dalla definizione del modulo sappiamo che (a mod b) <= b-1. Possiamo quindi dire che nelle successive chiamata alla procedura avremo il secondo parametro che è qualcosa che è al più b-1.
T(a, b) = C + T(b, r1 <= b-1) = C + (C + T(r1, r2 <= r1-1)) = 2C + T(r1, r2 <= r1-1) = ... = kC

Adesso, non sappiamo quanto valga r1,r2,...,rk ma sappiamo che sono tutti valori strettamente decrescenti. Di conseguenza abbiamo dimostrato che il numero di chiamate (considerando anche la prima) alla funzione euclide sono sicuramente inferiori o uguali a b. Ovvero abbiamo k <= b, che ci porta ad avere T(a, b) = O(bC) = O(b)

Siamo arrivati a dire che il costo di euclide è al massimo lineare sull'input più piccolo, ma abbiamo over-semplificato perché non avevamo una stima migliore per i valori di b. Utilizzando il teorema di Lamé possiamo vedere che non solo è O(b), ma anche ~5*log10(b)

Non so se a ti basta questo o se volevi la dimostrazione seria. Comunque ci può stare che fai fatica a capire i tempi di calcolo di sta roba: la dimostrazione per dire O(b) l'ho fatta sul momento (magari c'è pure qualche errore), ma quella seria non è roba che puoi fare così a caso. Non ci arrivi con l'intuito che c'è una relazione tra i tempi di calcolo dell'algoritmo di Euclide e i numeri di Fibonacci.

 

[Barbossa]

...
È evidente che il caso peggiore capita quando massimo comun divisore tra i due numeri è 1, ovvero quando a e b sono coprimi.
...

In realtà il caso peggiore, ovvero maggior numero di iterazioni con numeri più piccoli possibili, si ha se a e b sono numeri di Fibonacci consecutivi.
sia (a,b) una coppia di numeri tali che a<b e che mcd(a, b) richieda n iterazioni, allora se f(n) è l'n-esimo numero di Fibonacci, a>=f(n) e b>=f(n+1). Per induzione:
<>n=0 banale
<>sia valido per n>=0, e sia (a,b) coppia tale che a<b e mcd(a,b) richieda n+1 iterazioni, esistono q, r tali che b=qa+r con r<a, allora mcd(a,b)=mcd(r,a) ed mcd(r,a) richiede n iterazioni. Per passo induttivo a>=f(n+1) e r>=f(n). Poi q>=1 e b=qa+r>=f(n+1)+f(n)=f(n+2) da cui segue la tesi

Inoltre la formula per calcolare l'n-esimo numero di Fibonacci è esponenziale, da cui segue che il numero di passaggi è O(log a)

NOTA: ho posto f(0)=0 e f(1)=1. Non cambia molto comunque

 

[P_1_6]

qualche tempo fa avevo scritto questo http://www.albericolepore.org/algoritmo-di-lepore-per-il-calcolo-del-mcd/
gentilmente potreste trasformarlo in codice e paragonarlo ad euclide

 

[P_1_6]

Ho provato a scrivere qualcosa dopo 10 anni non ridete di me ,
anzi aiutatemi

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

int main()
{

    int v=1;
    int valMCD=1;
    int a=0;
    int b=0;
    int rip=1;

    printf("Inserisci il primo numero\n");
    scanf("%d",&a);
    printf("Inserisci il secondo numero\n");
    scanf("%d",&b);

    valMCD=MCD(a,b,v,rip);
    printf("valMCD=%d",valMCD);
}

int MCD(a,b,v,rip){
printf("a=%d\nb=%d\n",a,b);
printf("rip=%d\n",rip);
int c=0;
int d=0;
int i=0;
int j=0;
int k=0;
int e=0;

while(a % 2 == 0){ a=a/2; i++;}
while(a % 3 == 0){ a=a/3; j++;}
while(b % 2 == 0){ b=b/2; k++;}
while(b % 3 == 0) {b=b/3; e++;}

if ((i!=0 && k!=0)&&(i>=k)) {
    rip=rip*2*k;
}else if ((i!=0 && k!=0)&&(i<=k)){
    rip=rip*2*i;
}
if ((j!=0 && e!=0)&&(j>=e)) {
    rip=rip*3*e;
}else if ((j!=0 && e!=0)&&(j<=e)){
    rip=rip*3*j;
}

if( (a % b)==0){
        printf("\n\n%d\n%d\n",b,rip);
            return (b*rip);
        }else if ((b % a)==0){
            return (a*rip);
        }


if (((a % 6)==1) && ((b % 6)==5) ){
    return MCD(a,b*5*7,5*7,rip);
    }
else if ((a % 6)==5 && (b % 6)==1 ){
    return MCD(b,a*5*7,5*7,rip);
    }


if(a>b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        MCD(b,c-d,1,rip);
    }else if((a % 6)==5 && (b % 6)==5 ){
        c=(a-5)/6;
        d=(b-5)/6;
        MCD(b,c-d,1,rip);
    }

}else if(a<b){
    if((a % 6)==1 && (b % 6)==1 )
        c=(a-1)/6;
        d=(b-1)/6;
        MCD(a,d-c,1,rip);
    }else if((a % 6)==5 && (b % 6)==5 ){
        c=(a-5)/6;
        d=(b-5)/6;
        MCD(a,d-c,1,rip);
    }
}

 

[Barbossa]

ha un problema con i numeri "grandi", come a=23 e b=25 (mi dà 25), a=145 e b=236 (mi dà 5) e a=1356 e b=2387 (dà 7 invece di 1). Osservando l'algoritmo utilizzi molte più variabili rispetto al metodo di Euclide (tu ne usi almeno 10 contro le 2 di euclide, inclusi i parametri delle funzioni), quindi il tuo algoritmo è peggiore come uso della memoria.

 

[Barbossa]

Ho fatto un test tra l'algoritmo di Euclide (classico) e quello proposto, con numeri casuali fino a mille: ecco i risultati:
a=377 b=935
Lepore MCD=1 iterazioni=12
Classico MCD=1 iterazioni=4

a=796 b=19
Lepore MCD=1 iterazioni=5
Classico MCD=1 iterazioni=4

a=893 b=583
Lepore MCD=1 iterazioni=9
Classico MCD=1 iterazioni=9

a=918 b=143
Lepore MCD=1 iterazioni=3
Classico MCD=1 iterazioni=8

a=606 b=426
Lepore MCD=6 iterazioni=4
Classico MCD=6 iterazioni=7

a=59 b=721
Lepore MCD=7 iterazioni=3
Classico MCD=1 iterazioni=5

a=777 b=984
Lepore MCD=147 iterazioni=5
Classico MCD=3 iterazioni=5

a=809 b=921
Lepore MCD=1 iterazioni=35
Classico MCD=1 iterazioni=5

a=337 b=804
Lepore MCD=1 iterazioni=4
Classico MCD=1 iterazioni=8

a=697 b=628
Lepore MCD=1 iterazioni=4
Classico MCD=1 iterazioni=5

a=761 b=911
Lepore MCD=1 iterazioni=33
Classico MCD=1 iterazioni=7

a=229 b=153
Lepore MCD=1 iterazioni=5
Classico MCD=1 iterazioni=3

a=253 b=239
Lepore MCD=1 iterazioni=5
Classico MCD=1 iterazioni=3

a=810 b=917
Lepore MCD=1 iterazioni=5
Classico MCD=1 iterazioni=6

a=562 b=170
Lepore MCD=10 iterazioni=13
Classico MCD=2 iterazioni=6

a=690 b=291
Lepore MCD=3 iterazioni=2
Classico MCD=3 iterazioni=7

a=457 b=839
Lepore MCD=1 iterazioni=5
Classico MCD=1 iterazioni=7

a=662 b=351
Lepore MCD=1 iterazioni=6
Classico MCD=1 iterazioni=7

a=422 b=580
Lepore MCD=10 iterazioni=4
Classico MCD=2 iterazioni=5

a=846 b=380
Lepore MCD=14 iterazioni=4
Classico MCD=2 iterazioni=7

 

[P_1_6]

si non funziona
cercherò di scriverlo bene nei prossimi giorni
erano 10 anni che non scrivevo codice

 

[P_1_6]

@Barbossa ho fatto un mix di Euclide-Lepore funzionante spero

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

int main()
{


    int valMCD=1;
    int a=0;
    int b=0;
    int rip=1;
    int i=0;
    int j=0;
    int k=0;
    int e=0;

    printf("Inserisci il primo numero\n");
    scanf("%d",&a);
    printf("Inserisci il secondo numero\n");
    scanf("%d",&b);

    while(a % 2 == 0){ a=a/2; i++;}
    while(a % 3 == 0){ a=a/3; j++;}
    while(b % 2 == 0){ b=b/2; k++;}
    while(b % 3 == 0) {b=b/3; e++;}

    if ((i!=0 && k!=0)&&(i>=k)) {
        rip=rip*2*k;
    }else if ((i!=0 && k!=0)&&(i<=k)){
        rip=rip*2*i;
    }
    if ((j!=0 && e!=0)&&(j>=e)) {
        rip=rip*3*e;
    }else if ((j!=0 && e!=0)&&(j<=e)){
        rip=rip*3*j;
    }

    valMCD=(MCD(a,b))*rip;
    printf("valMCD=%d",valMCD);
}

int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;


while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }



if( (a % b)==0){
        return b;
        }else if ((b % a)==0){
            return a;
        }

if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
    if((a>b)&&(a-b<b)){
        return MCD(b,a-b);
    }else if((a>b)&&(a-b>b)){
        return MCD(a-b,b);
    }else if((a<b)&&(b-a>a)){
        return MCD(b-a,a);
    }else if((a<b)&&(b-a<a)){
        return MCD(a,b-a);
    }
}

if(a>b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }else if((a % 6)==5 && (b % 6)==5 ){
        c=(a-5)/6;
        d=(b-5)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }
}else if((a<b)&&((a % 6)==1 && (b % 6)==1 )){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}else if((a<b)&&((a % 6)==5 && (b % 6)==5) ){

        c=(a-5)/6;
        d=(b-5)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}
}

 

[Barbossa]

Per a=1 e b=11 non ha termine

EDIT: errore mio

 

[P_1_6]

@Barbossa potresti fare il paragone come hai fatto ieri gentilmente

 

[Barbossa]

Invece dei cicli di iterazione, ora ho misurato direttamente il tempo di esecuzione (ho dovuto ingrandire l'input):
a=2838009 b=15459363
Classico MCD=3 clock=580
Lepore MCD=3 clock=3336

a=20310935 b=18285582
Classico MCD=1 clock=592
Lepore MCD=1 clock=2312

a=28785569 b=13633184
Classico MCD=1 clock=476
Lepore MCD=1 clock=2360

a=19912641 b=5411583
Classico MCD=3 clock=640
Lepore MCD=3 clock=1916

a=11039785 b=12643424
Classico MCD=1 clock=676
Lepore MCD=1 clock=2172

a=30809622 b=27190424
Classico MCD=2 clock=484
Lepore MCD=2 clock=1644

a=402084 b=21424302
Classico MCD=18 clock=592
Lepore MCD=12 clock=2692

a=12263355 b=13455475
Classico MCD=5 clock=728
Lepore MCD=5 clock=2544

a=15090558 b=3628390
Classico MCD=2 clock=640
Lepore MCD=2 clock=2996

a=1590425 b=15362399
Classico MCD=1 clock=644
Lepore MCD=1 clock=2992

a=18189867 b=20865698
Classico MCD=1 clock=720
Lepore MCD=1 clock=2700

a=25644264 b=18979806
Classico MCD=6 clock=1040
Lepore MCD=6 clock=2640

a=4592105 b=4647266
Classico MCD=1 clock=396
Lepore MCD=1 clock=2848

a=21898493 b=3610780
Classico MCD=1 clock=560
Lepore MCD=1 clock=2228

a=26013909 b=14086503
Classico MCD=3 clock=628
Lepore MCD=3 clock=2316

a=32504643 b=28851918
Classico MCD=3 clock=412
Lepore MCD=3 clock=2124

a=29545866 b=19261146
Classico MCD=6 clock=648
Lepore MCD=6 clock=2276

a=13583069 b=24777004
Classico MCD=1 clock=876
Lepore MCD=1 clock=2420

a=32894330 b=33495710
Classico MCD=10 clock=524
Lepore MCD=10 clock=1848

a=30188587 b=10379683
Classico MCD=41 clock=524
Lepore MCD=41 clock=1600

Insomma: il tuo algoritmo è peggiore sia nell'uso della memoria che nel tempo di esecuzione

NOTA:

a=108 b=198
Classico MCD=18 clock=196
Lepore MCD=12 clock=548

 

[P_1_6]

Ho corretto l'errore potenza pow()
grazie @Barbossa per il tempo che mi stai dedicando
se posso vorrei farti una domanda a livello di iterazioni qual'è migliore?

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

int main()
{


    int valMCD=1;
    int a=0;
    int b=0;
    int rip=1;
    int i=0;
    int j=0;
    int k=0;
    int e=0;

    printf("Inserisci il primo numero\n");
    scanf("%d",&a);
    printf("Inserisci il secondo numero\n");
    scanf("%d",&b);

    while(a % 2 == 0){ a=a/2; i++;}
    while(a % 3 == 0){ a=a/3; j++;}
    while(b % 2 == 0){ b=b/2; k++;}
    while(b % 3 == 0) {b=b/3; e++;}

    if ((i!=0 && k!=0)&&(i>=k)) {
        rip=rip*pow(2,k);
    }else if ((i!=0 && k!=0)&&(i<=k)){
        rip=rip*pow(2,i);
    }
    if ((j!=0 && e!=0)&&(j>=e)) {
        rip=rip*pow(3,e);
    }else if ((j!=0 && e!=0)&&(j<=e)){
        rip=rip*pow(3,j);
    }

    valMCD=(MCD(a,b))*rip;
    printf("valMCD=%d",valMCD);
}

int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;


while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }



if( (a % b)==0){
        return b;
        }else if ((b % a)==0){
            return a;
        }

if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
    if((a>b)&&(a-b<b)){
        return MCD(b,a-b);
    }else if((a>b)&&(a-b>b)){
        return MCD(a-b,b);
    }else if((a<b)&&(b-a>a)){
        return MCD(b-a,a);
    }else if((a<b)&&(b-a<a)){
        return MCD(a,b-a);
    }
}

if(a>b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }else if((a % 6)==5 && (b % 6)==5 ){
        c=(a-5)/6;
        d=(b-5)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }
}else if((a<b)&&((a % 6)==1 && (b % 6)==1 )){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}else if((a<b)&&((a % 6)==5 && (b % 6)==5) ){

        c=(a-5)/6;
        d=(b-5)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}
}

 

[P_1_6]

Ho aumentato i cicli e diminuito i tempi di calcolo

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

int main()
{


    int valMCD=1;
    int a=0;
    int b=0;
    int rip=1;
    int i=0;
    int j=0;
    int k=0;
    int e=0;

    printf("Inserisci il primo numero\n");
    scanf("%d",&a);
    printf("Inserisci il secondo numero\n");
    scanf("%d",&b);

    while(a % 2 == 0){ a=a/2; i++;}
    while(a % 3 == 0){ a=a/3; j++;}
    while(b % 2 == 0){ b=b/2; k++;}
    while(b % 3 == 0) {b=b/3; e++;}

    if ((i!=0 && k!=0)&&(i>=k)) {
        rip=rip*pow(2,k);
    }else if ((i!=0 && k!=0)&&(i<=k)){
        rip=rip*pow(2,i);
    }
    if ((j!=0 && e!=0)&&(j>=e)) {
        rip=rip*pow(3,e);
    }else if ((j!=0 && e!=0)&&(j<=e)){
        rip=rip*pow(3,j);
    }

    valMCD=(MCD(a,b))*rip;
    printf("valMCD=%d",valMCD);
}

int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;


while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }



if( (a % b)==0){
        return b;
        }else if ((b % a)==0){
            return a;
        }

if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
    if(a>b){ return MCD(a,a-b);}
    else {return MCD(b,b-a);}
}

if(a>b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        return MCD(a,c-d);
    }else{
        c=(a-5)/6;
        d=(b-5)/6;
        return MCD(a,c-d);
    }
}else if(a<b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        return MCD(b,d-c);
        }
    }else{
        c=(a-5)/6;
        d=(b-5)/6;
        return MCD(b,d-c);
    }
}

 

[Barbossa]

non funziona per a=2704 e b=2331. Inoltre utilizza troppa memoria

EDIT: penso che siamo andati un po'

 

[P_1_6]

@Barbossa qual'è la complessità computazionale di

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

int main()
{


    int valMCD=1;
    int a=0;
    int b=0;
    int rip=1;
    int i=0;
    int j=0;
    int k=0;
    int e=0;

    printf("Inserisci il primo numero\n");
    scanf("%d",&a);
    printf("Inserisci il secondo numero\n");
    scanf("%d",&b);

    while(a % 2 == 0){ a=a/2; i++;}
    while(a % 3 == 0){ a=a/3; j++;}
    while(b % 2 == 0){ b=b/2; k++;}
    while(b % 3 == 0) {b=b/3; e++;}

    if ((i!=0 && k!=0)&&(i>=k)) {
        rip=rip*pow(2,k);
    }else if ((i!=0 && k!=0)&&(i<=k)){
        rip=rip*pow(2,i);
    }
    if ((j!=0 && e!=0)&&(j>=e)) {
        rip=rip*pow(3,e);
    }else if ((j!=0 && e!=0)&&(j<=e)){
        rip=rip*pow(3,j);
    }

    valMCD=(MCD(a,b))*rip;
    printf("valMCD=%d",valMCD);
}

int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;


while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }



if( (a % b)==0){
        return b;
        }else if ((b % a)==0){
            return a;
        }

if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
    if((a>b)&&(a-b<b)){
        return MCD(b,a-b);
    }else if((a>b)&&(a-b>b)){
        return MCD(a-b,b);
    }else if((a<b)&&(b-a>a)){
        return MCD(b-a,a);
    }else if((a<b)&&(b-a<a)){
        return MCD(a,b-a);
    }
}

if(a>b){
    if((a % 6)==1 && (b % 6)==1 ){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }else if((a % 6)==5 && (b % 6)==5 ){
        c=(a-5)/6;
        d=(b-5)/6;
        if(((c-d)>b)&&((c-d-b)<(a-c-d))){
            return MCD(c-d,b);
        }else if((c-d)<b){
            return MCD(b,c-d);
        }else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
            return MCD(a,c-d);
        }
    }
}else if((a<b)&&((a % 6)==1 && (b % 6)==1 )){
        c=(a-1)/6;
        d=(b-1)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}else if((a<b)&&((a % 6)==5 && (b % 6)==5) ){

        c=(a-5)/6;
        d=(b-5)/6;
        if(((d-c)>a)&&((d-c-a)<(b-d-c))){
            return MCD(d-c,a);
        }else if((d-c)<a){
            return MCD(a,d-c);
        }else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
            return MCD(b,d-c);
        }
}
}

GRAZIE
per il tempo che mi stai dedicando

 

[P_1_6]

Ho capito il caso peggiore è quando a e b sono composti esclusivamente da potenze di 2 e di 3 quindi ho pensato di migliorarlo così:

While(a%b!=0 && ((a%2==0 && b%2==0 ) || (a%3==0 &&  b%3==0))) {
     if(a % 2 == 0){ a=a/2; i++;}
    if(a % 3 == 0){ a=a/3; j++;}
    if(b % 2 == 0){ b=b/2; k++;}
    if(b % 3 == 0) {b=b/3; e++;}

}

 

[P_1_6]

Ora dovrebbe essere più veloce di euclide

int MCD(a,b){//supponendo che siano stati divisi già per le potenze di 2 e di 3 e che  inizialmente a >b
    printf("a=%d\nb=%d\n",a,b);

   while(a % 2 == 0){ a=a/2; }
   while(a % 3 == 0){ a=a/3; }
   while(b % 2 == 0){ b=b/2; }
   while(b % 3 == 0) {b=b/3; }

    if( (a % b)==0){
        return b;
    }
    if ((((a % 6)==1) && ((b % 6)==1) )|| ((a % 6)==5 && (b % 6)==5 )){
        if(b>(a-b)/6){
            return MCD(b,b%((a-b)/6));
        }else{
            return MCD(a,a%((a-b)/6));
        }
    }
    else{
        return MCD(b,(a%b));
    }

}