[C -code] massimo comune divisore e minimo comune multiplo

[Kashaman]

Salve ragazzi, questo è uno dei miei primi programmi scritti in C. Prende in input due numeri e ne calcola il massimo comune divisore. Vi porto qui il codice, come vi sembra? Notate dei difetti? grazie mille.

#include <stdio.h>
/*calcolo minimo comune multiplo e massimo comune divisore */
main()
{
      printf("Questo programma calcola il massimo comune divisore tra due interi\n");
      long int a,b,mcd,mcm,prod;
      while ( a!=0) { /* valore sentinella */ 
      printf("Inserisci il primo numero\n");
      scanf("%d",&a);
      printf("inserisci il secondo \n");
      scanf("%d",&b);
      prod=a*b;
      while (a!=b) { /* inizio ciclo */
            if (a>b) a=a-b;
            else b=b-a;
            }
            mcd=a; /* associo l'ultimo valore del ciclo alla variabile mcd*/
            printf("il massimo comun divisore e' %d\n", a); /*stampa  massimo comune divisore*/ 
            mcm = prod/mcd; /* formula del minimo comune multiplo*/ 
            printf("mentre il minimo comune multiplo e' %d\n" , mcm); /*stampa minimo comune multiplo*/
            }

}

[Shulz1]

Ciao, dandogli un'occhiata veloce penso che la cosa migliore sia di modularizzare tramite funzioni le varie parti che compongono il programma.

Ad esempio una cosa banale da fare potrebbe essere scrivere le due funzioni mcd(a,b) e mcm(a,b) da chiamare poi all'interno del main.

Per il resto ti consiglio di tener conto della indentazione del codice (se si è sfasata postando allora niente ;D), ma soprattutto occhio quando utilizzi delle variabili non inizializzate... nel tuo codice, quando inizia il ciclio while principale (while (a != 0)), verifichi che 'a' sia diverso da zero quando 'a' non è ancora inizializzato, e quindi contiene potenzialmente memoria sporca.
Ora, magari, non accadrà mai che 'a' assuma valore 0, però è sempre buona norma evitare casi come questi che possono portare a comportamenti inattesi. Una possibile soluzione è assegnare ad 'a' un valore prima del ciclo, oppure come ti ho messo sotto utilizzare un do-while!

Un'ultima cosa riguarda i commenti: probabilemente sei all'inizio e quindi li inserisci su un po' tutto, però non esagere a inserirne troppi (per esempio su ogni printf), altrimenti diminuisci la leggibilità del codice stesso portando più confusione.

Ti metto qui un esempio di come secondo me potresti riscriverlo:

#include <stdio.h>

int mcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a = a - b;
        }
        else { 
            b = b - a;
        }
    }

    return a;
}

int mcm(int a, int b) {
    return (a*b)/mcd(a,b);
}

int main()
{
    long int a, b;

    printf("Questo programma calcola il massimo comune divisore tra due interi\n");
    do {
        printf("Inserisci il primo numero\n");
        scanf("%ld", &a);
        
        printf("inserisci il secondo \n");
        scanf("%ld", &b);

        if (a != 0) {
            printf("il massimo comun divisore e' %d\n", mcd(a,b));
            printf("mentre il minimo comune multiplo e' %d\n" , mcm(a,b)); 
        }
    } while (a != 0);

    return 0;
}

[Kashaman]

Grazie mille, ora il programma funziona meglio. Hai ragione, forse è meglio modulizzare il programma, piuttosto che scriverlo sotto un'unica main, sei stato molto chiaro, ti ringrazio molto.

[Adrianorto]

In questo post parliamo di come far girare meglio il programma, io vorrei dire come in alcuni casi l’algorimto di Euclide ci mette di piu’ dell’algoritmo di Adrianorto. Se i divisori comuni sono piccoli questo nuovo algoritmo del futuro e’ piu’ efficiente.
Consideriamo 153 et 69 : 153=69*2 +15 poi 69=60+9=15*4 +9 poi 15=9+6 poi 9=6+3 poi 6=2*3
abbiamo 5 passi per trovare che il MCD e’ 3. Se invece prendiamo il piu’ piccolo dei due 69 e lo dividiamo iterativamente ad esempio o ricorsivamente per 69/due , 69/tre dato che 23 lo divide dividiamo anche l’altro 153 per 3 .
Forse l’algoritmo euclideo costa di piu’ della radice del minore dei due numeri e quindi meno dell’algoritmo adriaortesco . Chissa' !

typedef
struct razionale{
int num;
int den;
} raz;
///nel main k puo’ partire da 2 o da uno se i due numeri num e den sono divisibili

raz* riduci (raz* p, int k, int c,int numer)///numer dev'essere fissato una volta per tutte perche' se c'e' MCD i potra' altrimenti valere zero
{
int n=0,d=0, i=1;
n= p->num;
d = p->den;
i = part_int(numer/k);
if (c> 0 && d % k==0) { printf("\n Bene c'e un MCD diverso dall'unita' MCD vale :%d, il numero di iterazioni vale :%d \n", k-1;
return p;}
if (c> 0 && d % i==0) { printf("\n Bene c'e un MCD diverso dall'unita' MCD vale :%d, il numero di iterazioni vale :%d \n",part_int(numer/(k-1)),k);
return p;}
if(i*i
if (n<=i*i )
{

if( n % i ==0 && d % i==0 )
{
n = (n /i) ; d= (d/i) ;
p->num = n;
p->den = d;
c++;
}
if( n % i ==0 && d % k==0 )
{
n = (n /k) ; d= (d/k) ;
p->num = n;
p->den = d;
c++;

}

riduci( p, k+1,c,numer );
}

[Adrianorto]

L'esempio che ho fatto non va bene, me ne accorgo solo adesso. Nell'esempio troviamo solo il minimo comun divisore che non e' detto coincida col massimo . Per alcune classi di coppie di numeri si : se il seondo numero e' piu' piccolo della radice quadrata del primo l'algoritmo di Adrianorto potrebbe essere piu' veloce di quello del povero Euclide.

[vict85]

@Adrianorto: L'autore è un principiante e non penso fosse davvero interessato a trovare il miglior algoritmo per risolvere quel problema. Semplicemente ha usato l'algoritmo Euclideo come esempio per allenarsi a programmare in C. Tra l'altro, hai dimenticato una parentesi alla fine di un printf e dimenticato di usare il tag

[code]

[/code] intorno al tuo codice. Inoltre, quando dici che qualcosa è meglio, sarebbe meglio motivarlo, magari con una analisi delle complessità.

@Shulz: Nel tuo codice calcoli due volte il massimo comun divisore.

@Kashaman: Nel tuo codice vedo questi problemi (oltre quello già detto da Shulz):

[*:1ulynnuv] Il tuo codice sembra usare il C89 se non addirittura una versione precedente alla standarizzazione. Non ha secondo me molto senso fermarti a 30 anni fa.[/*:m:1ulynnuv]
[*:1ulynnuv]Manca int prima di main. Il tuo compilatore forse non lo richiede, ma è richiesto dallo standard:


"standard c17(preso da draft)":The function called at program startup is named main. The implementation declares no prototype for this function. It shall be defined with a return type of int and with no parameters:

int main(void) { /* ... */ }

or with two parameters (referred to here as [inline]argc[/inline] and [inline]argv[/inline], though any names may be used, as they
are local to the function in which they are declared):


int main(int argc, char *argv[]) { /* ... */ }


or equivalent; or in some other implementation-defined manner.

[/*:m:1ulynnuv]
[*:1ulynnuv] scrivere [inline]return 0;[/inline] nel main non è strettamente necessario, ma molti lo scrivono. È importante che tu sappia che è opzionale.[/*:m:1ulynnuv]
[*:1ulynnuv]Dovresti dividere esplicitamente calcolo e lettura del codice e, quando esiste un valore per uscire dal programma, quest'ultimo deve essere testato subito. Per esempio:


#include <stdio.h>

void process( int a, int b );

int
main( )
{
    // QUESTO E' UN CICLO INFINITO...
    for ( ;; )
    {
        puts( "#" );
        puts( "# Questo programma fa qualcosa con due interi" );
        puts( "#" );
        printf(
            "Inserisci il due numeri interi separati da uno spazio [scrivere q per uscire dal "
            "programma]:  " );

        int n1, n2;  // puoi definire una variabile ovunque nel codice nei nuovi standard

        int elementi_letti
            = scanf( "%d %d", &n1, &n2 );  // scanf ritorna il numero di elementi letti

        int c;  // variabile per pulizia dell'input
        if ( elementi_letti != 2 )
        {
            c = getchar( );
            if ( elementi_letti == 0 )
            {
                if ( c == 'q' && getchar( ) == '\n' )
                {
                    puts( "Arrivederci a presto" );
                    break;
                }
            }
            puts( "Errore nell'inserimento dei numeri\n" );
            for ( ; c != '\n' && c != EOF; c = getchar( ) )
            {
            }
            continue;  // riinizia da capo il ciclo
        }

        {
            int eliminati = 0;  // questa variabile è definita solo in questo blocco di codice
            for ( ; ( c = getchar( ) ) != '\n' && c != EOF; eliminati++ )
            {
            }
            if ( eliminati > 0 )
            {
                puts( "Inserire solo i due numeri e premere invio\n" );
            }
        }

        process( n1, n2 );
    }
}

void
process( int a, int b )
{
    // funzione vuota perché mi sto concentrando sulla parte di gestione dell'inputaq
    printf( "Sto processando %d e %d...\n\n", a, b );
}

[/*:m:1ulynnuv]
[*:1ulynnuv] Dovresti formattare il tuo codice. Che IDE usi?[/*:m:1ulynnuv][/list:u:1ulynnuv]

[axpgn]

@vict85
Necroposting

[Adrianorto]

@vict85 La parentesi deve stare sopra alla richiamta finale perche' c'e' un doppio if. Non faccio un calcolo doppio dell MCD ma uso il fatto che se a divide b allora anche (b/a) divide a per cui il costo computazionale asintotico non si raddoppia .
Il main non l'ho messo l'ho solo citato, non penso ci sia bisogno di usare breack e contiune , e' piu' bello farlo con la funzione ricorsiva.

[Adrianorto]

* il costo si raddoppia ma questo non cambia il costo asintotico

[Adrianorto]

@vict85 uso codeblocks

[Adrianorto]

Questo dovrebbe andre un po' meglio

#include <stdio.h>

typedef
    struct razionale{
      int num;
      int den;
   } raz;


///k e' inizializzato ad uno numer a num
/// riduci_MCD ,anche se ancora non trova la frazione ridotta ai minimi termini , troverebbe MCD tra due interi : num e den

raz* riduci_MCD (raz* p, int k,int c,int numer)///numer dev'essere fissato una volta per tutte perche' se c'e' MCD i potra' altrimenti valere zero
{
    int n=0,d=0, i=1,fattoreMCD=1;
    n= p->num;
    d = p->den;
    i = part_int(numer/k);
    
    if (c> 0  ) { printf("\n Bene c'e un MCD diverso dall'unita' MCD vale :%d, il numero di iterazioni vale :%d \n",part_int(numer/(k-1)),k);return p;}

   if(i*i<n ){printf("\n Bene MCD vale %d il numero di iterazioni :%d\n",fattoreMCD ,k);return p; }

    if (n<=i*i )
    {

        if( n % i ==0  )

        {
            if( d % i ==0  )

            {
                n = (n /i) ; d= (d/i) ;
                p->num = n;
                p->den = d;
                c++;
                }
            if( d % k ==0  )
            {
                n = (n /k) ; d= (d/k) ;
                p->num = n;
                p->den = d;
                fattoreMCD = k * fattoreMCD ;//Allora opportunament il fattore parta da uno
            }
    }
   // else printf("\nBene proviamo con %d\n",i);
    }
    riduci_MCD ( p, k+1,c,numer );
     return p;
}

[vict85]

"axpgn":@vict85
Necroposting

Hai ragione... non avevo notato...

@Andrianorto. Sarebbe meglio se aprissi una discussione a parte. Insomma, nel caso tu abbia domande. Infatti l'autore della discussione dubito si metterà a leggere questa discussione dopo 8 anni.