Anccos
15-12-2004, 11:58
Questo è un programma che mi è stato assegnato all'università... Ho qualche problema sia nelle liste (che cmq ho fatto.. non so quanto bene)... Se qualcuno di voi potesse darmi qualche dritta, mi aiuterebbe molto...
Descrizione
Il massimo comun divisore di due numeri e' il più grande divisore comune dei due numeri. Ad esempio, il massimo comun divisore di 24 e 36 è 12. Esiste un antichissimo modo per determinare il Massimo Comun Divisore (MCD) di due numeri interi strettamente positivi, dovuto a Euclide, definito dalle seguenti equazioni ricorsive:
MCD(n,n) = n
MCD(m,n) = MCD(m-n,n) se m>n
MCD(m,n) = MCD(m,n-m) se n>m
Scopo del programma sarà quello di implementare l'algoritmo di Euclide, in modo che funzioni con interi di dimensione arbitraria, quindi con un numero di cifre non previsto a priori. Dovrete implementare gli interi come liste di cifre decimali. Vi suggerisco di implementare almeno tre funzioni: uguale, minore e differenza. uguale dira' se due interi così rappresentati sono uguali. minore dirà se il primo è minore del secondo. differenza restituisce una lista di cifre che rappresenta la differenza di due interi rappresentati come liste di cifre.
Il vostro programma dovrà:
Input
prendere in input una sequenza di cifre decimali. Qualsiasi numero minore di 0 o maggiore di 9 sarà interpretato come un terminatore di un numero. Il primo terminatore dividerà il primo numero dal secondo, mentre il secondo terminatore indicherà la fine dell'input.
Output
produrre in output il Massimo Comun Divisore dei due numeri. Il numero andrà stampato stampando ciascuna cifra con il formato:
%1d
in modo che il numero appaia come una sequenza di cifre senza spazi tra una cifra e l'altra.
IMPORTANTE
non far produrre al programma altri output oltre a quelli richiesti.
Ecco un esempio di input del programma:
1
9
7
2
6
1
0
6
4
-1
5
1
0
7
9
1
8
2
0
10
In questo caso il programma dovrà calcolare l'MCD tra 197261064 e 510791820 e restituire in output il numero 21252. I numeri dell'esempio cadono ancora nel campo intero, ma il vostro programma dovrà funzionare correttamente anche se i numeri in input e output hanno centinaia o migliaia di cifre (certamente finchè c'è memoria...).
Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!
Il codice che ho scritto io per ora è questo...
struct node
{
int info;
struct node *next;
};
struct node *p,*q,*c,*z,*temp;
int n; p=NULL; z=NULL;
scanf("%d",&n);
while ((n>=0)&&(n<=9))
{
q=(struct node *)
malloc(sizeof(struct node));
(*q).info=n;
(*q).next=p;
p=q;
scanf("%d",&n);
}
scanf("%d",&n);
while ((n>=0)&&(n<=9))
{
c=(struct node *)
malloc(sizeof(struct node));
(*c).info=n;
(*c).next=z;
z=c;
scanf("%d",&n);
}
}
Grazie a chiunque mi aiuterà
Descrizione
Il massimo comun divisore di due numeri e' il più grande divisore comune dei due numeri. Ad esempio, il massimo comun divisore di 24 e 36 è 12. Esiste un antichissimo modo per determinare il Massimo Comun Divisore (MCD) di due numeri interi strettamente positivi, dovuto a Euclide, definito dalle seguenti equazioni ricorsive:
MCD(n,n) = n
MCD(m,n) = MCD(m-n,n) se m>n
MCD(m,n) = MCD(m,n-m) se n>m
Scopo del programma sarà quello di implementare l'algoritmo di Euclide, in modo che funzioni con interi di dimensione arbitraria, quindi con un numero di cifre non previsto a priori. Dovrete implementare gli interi come liste di cifre decimali. Vi suggerisco di implementare almeno tre funzioni: uguale, minore e differenza. uguale dira' se due interi così rappresentati sono uguali. minore dirà se il primo è minore del secondo. differenza restituisce una lista di cifre che rappresenta la differenza di due interi rappresentati come liste di cifre.
Il vostro programma dovrà:
Input
prendere in input una sequenza di cifre decimali. Qualsiasi numero minore di 0 o maggiore di 9 sarà interpretato come un terminatore di un numero. Il primo terminatore dividerà il primo numero dal secondo, mentre il secondo terminatore indicherà la fine dell'input.
Output
produrre in output il Massimo Comun Divisore dei due numeri. Il numero andrà stampato stampando ciascuna cifra con il formato:
%1d
in modo che il numero appaia come una sequenza di cifre senza spazi tra una cifra e l'altra.
IMPORTANTE
non far produrre al programma altri output oltre a quelli richiesti.
Ecco un esempio di input del programma:
1
9
7
2
6
1
0
6
4
-1
5
1
0
7
9
1
8
2
0
10
In questo caso il programma dovrà calcolare l'MCD tra 197261064 e 510791820 e restituire in output il numero 21252. I numeri dell'esempio cadono ancora nel campo intero, ma il vostro programma dovrà funzionare correttamente anche se i numeri in input e output hanno centinaia o migliaia di cifre (certamente finchè c'è memoria...).
Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!
Il codice che ho scritto io per ora è questo...
struct node
{
int info;
struct node *next;
};
struct node *p,*q,*c,*z,*temp;
int n; p=NULL; z=NULL;
scanf("%d",&n);
while ((n>=0)&&(n<=9))
{
q=(struct node *)
malloc(sizeof(struct node));
(*q).info=n;
(*q).next=p;
p=q;
scanf("%d",&n);
}
scanf("%d",&n);
while ((n>=0)&&(n<=9))
{
c=(struct node *)
malloc(sizeof(struct node));
(*c).info=n;
(*c).next=z;
z=c;
scanf("%d",&n);
}
}
Grazie a chiunque mi aiuterà