Newsgroup: it.comp.lang.pascal
Titolo: problema nella moltiplicazione di due liste

salve, ho questo problema nel risolvere un esercizio di questo tipo:
Si definisca una rappresentazione dei numeri naturali  BigNumber  basata
su sequenze (in linea di principio non limitate) di cifre decimali. Dati
due BigNumber  si scriva una procedura che esegue il prodotto dei due
numeri.
da quello che ho capito devo fare in modo che, ad esempio, se ho due
bignumber del tipo 12345 e 67 devo ottenere 827115.
per fare questo ho utilizzato una struttura dati tipo lista organizzata
in questo modo:
 bignumber=^lista;
 lista= record
         valore: integer;
         next:bignumber;
        end;
mentre per calcolare il prodotto pensavo di usare l'algoritmo detto del
contadino russo, che funziona nella seguente maniera:
dati n e m il prodotto z è uguale a:
se n >= 1 allora
 se n è divisibile per 2 n=n/2, m=2m, ricomincio il ciclo,
 altrimenti (n non è divisibile per 2) z=z+m, n=n-1, ricomincio il
ciclo;
se n<1 allora z è il prodotto dei due numeri.
il mio problema inizia quando devo fare la divisione per due di un
bignuber: come poso realizzarla, sapendo che nel campo valore di ogni
elemento della lista è contenuto un numero naturale (0<=n<10)?
è posibile realizzare il programma secondo la mia impostazione o è più
opportuno seguire un'altra via?
grazie a tutti quelli che mi aiuteranno.

opportuno seguire un'altra via?
Allora, ti do altre 2 soluzioni:
<<1>>
Utilizzare non gli integer ed inserire per ogni numero una sola cifra
(grande spreco di memoria), ma i word... ed utilizzare ogni bit...
In pratica avresti:
1 byte --> 8 bit da 0 a 256
1 word --> 16 bit da 0 a 65535
1 longint --> 32 bit da 0 a non ricordo :-)
1 bignumber --> uno spatasso di bit, da 0 all'infinito!! :-))
Secondo me questa è una soluzione molto vantaggiosa, anche perché ti
permette di usufruire di tutti gli operatori del TP, senza dover rifare
tutti gli algoritmi di somma e prodotto :-)
Unico inconveniente: devi gestirti a mano la conversione bin<-->dec...
soprattutto scrivere sul video un numero in decimale!! :-)
<<2>>
Usa un array, invece di una lista!!
E' molto più comodo da gestire... sprechi meno memoria... e' più facile da
leggere/scrivere... di da ugualmente possibilità di numeri enormi!!
Consiglio migliore: la <<1>> e la <<2>> insieme!! :-)
bye
Emanuele Cesena
d.a.m...@iol.it
ICQ n° #10570672

Emanuele Cesena ha scritto:

intanto ti ringrazio per avermi risposto, ma mi sento in dovere di fare delle
critiche alla tua risposta:
1) è *necessario* utilizzare degli integer, visto che il programma deve
funzionare in standard pascal (e come tu bene saprai nel pascal standard *non*
esistono i byte);
2)non posso utilizzare un array perchè un array è una struttura dati limitata,
mentre una lista, come richiesto dal testo dell'esercizio, no (entro certi
limiti).
per farti un esempio pratico: un array devo dichiaralo e devo dire la
dimesnsione (ad es. array[1..1000] of byte). e se io volessi moltiplicare un
numero di 1001 cifra?. inoltre su uso l'array e moltiplico due numeri di 3 cifre
avrò com risultato un numero preceduto da 996 zero?
grazie ancora per l'aiuto e ciao.


1001 cifre è un numero che occupa metà schermo... un po' improbabile... e
poi quello che importa è il concetto!!
Voglio vedere il tuo programma che fa un bel po' di operazioni su numeri a
1001 cifre!!! :-))) Sarà un po' lentuccio :-)))
Ultima pignoleria: gli zeri iniziali basta non visualizzarli... comunque io
utilizzavo dei char, ed inserivo il numero 123 così:
byte 1: 3
byte 2: 2
byte 3: 1
byte 4: STOP
Era anche più semplice fare alcune operazioni... :-)
Per quanto riguarda poi il tuo problema della divisione... se hai già
risolto, è ora di ottimizzare un po' i tempi:
Se hai un numero lungo (es 10-20 cifre) diviso uno corto (es. 2), continuare
a fare delle sottrazioni diventa molto mooooolto lungo!!! :-)
Allora fai così:
Allunghi il divisore con tanti 0 (Lo moltiplichi per 10^x), finché non ha
lunghezza = al dividendo (o fino ad avere una cifra in meno).
Fai le sottrrazioni, finché il dividendo non risulta minore del "nuovo"
divisore.
Poi levi uno zero... e via ancora sottrazioni
ecc. ecc.
Il tutto si risolve con un while all'interno di un ciclo For...
Se segui questa strada ed hai problemi, non esitare a farti sentire :-)
Ciao...
--


Occhio alla ricorsione, il suo algoritmo deve teoricamente funzionare anche
con n° di 1000 cifre e questo potrebbe mandare in overflow lo stack delle
chiamate.
La soluzione a lista doppiamente concatenata è sicuramente la migliore ma va
tenuto in considerazione che così ogni cifra occupa 12 byte anzichè 8 della
sol. originale.
Secondo me la sol migliore è lista semplice, char al posto di integer, e
algoritmo di inversione lista... mai sentito nominare?
in pratica farebbe questo:
lista originale:
testa -> 1 -> 2 -> 3 -> 4
viene trasformata in
testa -> 4 -> 3 -> 2 -> 1
questo algoritmo ha complessità lineare e non abbisogna di ulteriore spazio
di appoggio (stack delle chiamate per esempio) ma solo tre puntatori di
appoggio.
dopo l'esecuzione si può eseguire la divisione in contemporanea
all'algoritmo che risistema il numero come:
testa -> 1 -> 2 -> 3 -> 4
purtroppo non ho l'algoritmo sotto mano ma non dovrebbe essere difficile
ricavarlo.
Ciao, Matteo
rma...@geocities.com
http://rossini.home.ml.org
 -> 2 chat

 ...
No. comunque e' sicuramente un'ottima soluzione. 
Grazie.