Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Pascal - Somma di due numeri di lunghezza arbitraria rappresentati mediante liste simmetriche
Forum - Pascal - Somma di due numeri di lunghezza arbitraria rappresentati mediante liste simmetriche

Avatar
fabioser (Normal User)
Rookie


Messaggi: 59
Iscritto: 12/05/2012

Segnala al moderatore
Postato alle 5:03
Mercoledì, 30/05/2012
Salve amici del Forum! Provo a riaprire una discussione su un tema già trattato in precedenza, con la speranza di risultare più chiaro questa volta. Il problema consiste nel calcolo della somma di due numeri interi di lunghezza qualsiasi. Va precisato che:

1) L'intero è rappresentato da singole cifre, cominciando da destra e procedendo via via verso sinistra, ossia dalle cifre meno significative a quelle più significative (es . : 1 2 5 6 7 rappresenta 12.567):

2) Gli interi sono tutti non negativi ( la lista è cioè composta di singole cifre intere comprese ovviamente fra 0 e 9 e non negative).

3) La singola cifra deve essere rappresentata mediante un intero.

All'atto pratico, faccio solo un esempio, si tratterà cioè di effettuare una somma del tipo:


1 2 5 6 7 +
      2 0 5 =
_________

1 2 7 7 2

ovvero la somma della lista 12567,ossia del numero 12.567, e di quella 205,ovvero del numero 205, deve risultare la lista 12772 corrispondente al numero 12.772.

Per la rappresentazione delle due liste, ho scelto quella simmetrica e per risolvere il problema ho fatto uso di procedure ricorsive, sia per scrivere le due liste , sia per calcolarne la somma. Ecco il codice dell'intero programma:

Codice sorgente - presumibilmente Delphi

  1. program SommaDiDueListe(input,output);
  2. type punt=^elem;
  3.      elem= record
  4.                  val: integer;
  5.                  back : punt;
  6.                  next : punt;
  7.            end;
  8. var p,q,s,t: punt;
  9.     m,n : integer;
  10.  
  11.     procedure LeggiEScriviLista( t : punt; var p : punt; k : integer);
  12.     begin
  13.          if k=0
  14.          then p:=nil
  15.          else begin
  16.                    new(p);
  17.                    read(p^.val);
  18.                    write(p^.val,' ');
  19.                    new(t);
  20.                    read(t^.val);
  21.                    p^.back:=t;
  22.                    write(t^.val,' ');
  23.                    LeggiEScriviLista(t,p^.back,k-1);
  24.               end;
  25.     end;{ Fine procedura LeggiEScriviLista }
  26. procedure CalcoloSommaDiDueListe( var s : punt; p,q : punt; k : integer);
  27. begin
  28.  
  29.      if k=0
  30.      then s:=nil
  31.      else begin
  32.                new(s);
  33.                s^.val:=p^.val+q^.val;
  34.                s^.next^.val:=p^.next^.val+q^.next^.val;
  35.                if s^.next^.val>=10
  36.                then begin
  37.                          s^.next^.val:=(s^.next^.val)mod 10;
  38.                          s^.val:=p^.val+q^.val+(s^.next^.val)div 10;
  39.                     end;
  40.                if s^.val<10
  41.                then write(s^.val,' ')
  42.                else  begin s^.val:=(s^.val)mod 10;
  43.                            write(s^.val,' ');
  44.                      end;
  45.                if k=m
  46.                then if s^.val>=10
  47.                     then begin s^.back^.val:=(s^.val)div 10;
  48.                                write(s^.back^.val,' ');
  49.                          end;
  50.                CalcoloSommaDiDueListe(s^.back,p^.back,q^.back,k-1);
  51.           end;
  52. end;{ Fine procedura CalcoloSommaDiDueListe }
  53.  
  54. { Corpo del programma }
  55. begin
  56.      writeln('------------------------- Dati di ingresso --------------------------');
  57.      writeln;
  58.      write('Fornire la lunghezza della prima lista: ');
  59.      readln(m);
  60.      writeln;
  61.      write('Fornire la lunghezza della seconda lista: ');
  62.      readln(n);
  63.      write('Fornire la prima lista: ');
  64.      LeggiEScriviLista(nil,p,m);
  65.      writeln;
  66.      write('Fornire la seconda lista: ');
  67.      LeggiEScriviLista(nil,q,n);
  68.      writeln;
  69.      writeln('La lista somma e'':');
  70.      writeln;
  71.      CalcoloSommaDiDueListe(s,p,q,m);
  72.      readln;
  73.  
  74. end.



Qualcuno di voi mi sa dire perchè il programma medesimo non funziona? Infatti al momento del calcolo della somma mi da errore. Forse è sbagliata la procedura CalcoloSommaDiDueListe? Vi sarei molto grato se mi segnalaste errori ed eventuali correzioni. Ciao!!! :)

PM Quote
Avatar
Goblin (Member)
Expert


Messaggi: 375
Iscritto: 02/02/2011

Segnala al moderatore
Postato alle 10:18
Mercoledì, 30/05/2012
Adesso creo di aver finalmente capito cosa vuoi fare (spero !!)
Io continuo a preferire le function per un ritorno di valore dunque la prima function che raccoglie i valori diventa (come ti era già stato detto):

Codice sorgente - presumibilmente Delphi

  1. Function LeggiEScriviLista(pNext: punt; k: integer): Punt;
  2. begin
  3.   if k=0 then
  4.     Result := nil
  5.   else
  6.   begin
  7.     new(Result);
  8.     read(Result.val);
  9.     Result.next:=pNext;
  10.     Result.Back := LeggiEScriviLista(Result, k-1);
  11.   end;
  12. end;{ Fine procedura LeggiEScriviLista }



le chiamte sono:
     p := LeggiEScriviLista(Nil, m);
     q := LeggiEScriviLista(Nil, n);
anche qui mi/ci sono/siamo ripetuto/i.

e per stravolgere il tutto io trasformerei CalcoloSommaDiDueListe sempre in una function sulla falsa riga di LeggiEScriviLista e molto semplificata
dunque:
Codice sorgente - presumibilmente Delphi

  1. Function CalcoloSommaDiDueListe(sBack, p, q: punt; k: integer): Punt;
  2. Var nRip : Integer;
  3. begin
  4.   if p = nil then
  5.   begin
  6.     Result := Nil;
  7.     exit;
  8.   end;
  9.  
  10.   new(Result);
  11.   Result.back := sBack;
  12.   if q <> Nil then
  13.     Result.val := k + p.val + q.val
  14.   else
  15.     Result.val := Result.val + p.val;
  16.  
  17.   if Result.val >= 10 then
  18.   begin
  19.     nRip := Result.val;
  20.     Result.val := nRip mod 10;
  21.     k := nRip div 10;
  22.   end
  23.   else
  24.     k := 0;
  25.  
  26.   if q <> Nil then
  27.     Result.next := CalcoloSommaDiDueListe(Result, p.next, q.next, k)
  28.   else
  29.     Result.next := CalcoloSommaDiDueListe(Result, p.next, nil, k);
  30. end;



per comodità ho girato le liste con:

Codice sorgente - presumibilmente Delphi

  1. Function GiraListe(oPunt: Punt; oVerso: SetVerso): punt;
  2. begin
  3.   Result := oPunt;
  4.   case oVerso of
  5.     tvBack: begin
  6.              while Result.back<>nil do
  7.                Result := Result.back;
  8.             end;
  9.     tvNext: begin
  10.              while Result.Next<>nil do
  11.                Result := Result.Next;
  12.             end;
  13.   end;
  14. end;



Con SetVerso definito: Type SetVerso = (tvNext, tvBack);

Per riassumere il tutto:

Codice sorgente - presumibilmente Delphi

  1. program SommaDiDueListe(input,output);
  2.  
  3. uses
  4.    SysUtils;
  5.  
  6.     const bell=07;
  7.     Type SetVerso = (tvNext, tvBack);
  8.     type punt=^elem;
  9.          elem= record
  10.                  val: integer;
  11.                  back : punt;
  12.                  next : punt;
  13.                end;
  14.     var p,q,s, oDummy: punt;
  15.         m,n : integer;
  16.         st: String;
  17.  
  18. Function LeggiEScriviLista(pNext: punt; k: integer): Punt;
  19. begin
  20.   if k=0 then
  21.     Result := nil
  22.   else
  23.   begin
  24.     new(Result);
  25.     read(Result.val);
  26.     Result.next:=pNext;
  27.     Result.Back := LeggiEScriviLista(Result, k-1);
  28.   end;
  29. end;{ Fine procedura LeggiEScriviLista }
  30.  
  31. Function CalcoloSommaDiDueListe(sBack, p, q: punt; k: integer): Punt;
  32. Var nRip : Integer;
  33. begin
  34.   if p = nil then
  35.   begin
  36.     Result := Nil;
  37.     exit;
  38.   end;
  39.  
  40.   new(Result);
  41.   Result.back := sBack;
  42.   if q <> Nil then
  43.     Result.val := k + p.val + q.val
  44.   else
  45.     Result.val := Result.val + p.val;
  46.  
  47.   if Result.val >= 10 then
  48.   begin
  49.     nRip := Result.val;
  50.     Result.val := nRip mod 10;
  51.     k := nRip div 10;
  52.   end
  53.   else
  54.     k := 0;
  55.  
  56.   if q <> Nil then
  57.     Result.next := CalcoloSommaDiDueListe(Result, p.next, q.next, k)
  58.   else
  59.     Result.next := CalcoloSommaDiDueListe(Result, p.next, nil, k);
  60. end;{ Fine procedura CalcoloSommaDiDueListe }
  61. { Corpo del programma }
  62.  
  63. Function GiraListe(oPunt: Punt; oVerso: SetVerso): punt;
  64. begin
  65.   Result := oPunt;
  66.   case oVerso of
  67.     tvBack: begin
  68.              while Result.back<>nil do
  69.                Result := Result.back;
  70.             end;
  71.     tvNext: begin
  72.              while Result.Next<>nil do
  73.                Result := Result.Next;
  74.             end;
  75.   end;
  76. end;
  77.  
  78. begin
  79.   try
  80.     writeln('------------------------- Dati di ingresso --------------------------');
  81.     writeln;
  82.     write('Fornire la lunghezza della prima lista: ');
  83.     readln(m);
  84.     writeln;
  85.     write('Fornire la lunghezza della seconda lista: ');
  86.     readln(n);
  87.     writeln;
  88.     if m<n then
  89.     begin
  90.       writeln(chr(bell),'Errore nei dati di ingresso!- STOP -');
  91.       exit;
  92.     end
  93.     else
  94.     begin
  95.      write('Fornire la prima lista: ');
  96.      writeln;
  97.      p := LeggiEScriviLista(Nil, m);
  98.      writeln;
  99.      write('Fornire la seconda lista: ');
  100.      writeln;
  101.      q := LeggiEScriviLista(Nil, n);
  102.      writeln;
  103.      writeln('La lista somma e'':');
  104.      writeln;
  105.  
  106.      p := GiraListe(p, tvBack );
  107.      q := GiraListe(q, tvBack);
  108.      s := CalcoloSommaDiDueListe(nil, p, q, 0);
  109.      s := GiraListe(s, tvNext);
  110.  
  111.      oDummy := s;
  112.      repeat
  113.        Write(oDummy.val);
  114.        oDummy := oDummy.back;
  115.      until oDummy.back=nil;
  116.      Write(oDummy.val);
  117.     end;
  118.     readln(st);
  119. end.



Non credo sia un codice molto ortodosso, si può limare e perfezionare ancora, ma dovrebbe essere un buon punto di partenza.
Non l'ho commentato ma la semplicità credo parli da sola..

G.


Ibis redibis non morieris in bello
PM Quote
Avatar
fabioser (Normal User)
Rookie


Messaggi: 59
Iscritto: 12/05/2012

Segnala al moderatore
Postato alle 16:27
Mercoledì, 30/05/2012
Grazie mille Goblin per i preziosi suggerimenti. Proverò a metterli in pratica. Ciao!!!:)

PM Quote
Avatar
fabioser (Normal User)
Rookie


Messaggi: 59
Iscritto: 12/05/2012

Segnala al moderatore
Postato alle 17:50
Giovedì, 31/05/2012
Ci sono due cose che non riesco a capire nella tua soluzione e riguardano il calcolo del generico valore Result^.val. Tu scrivi:

Codice sorgente - presumibilmente Delphi

  1. ...
  2.  
  3.   if q <> Nil then
  4.     Result.val := k + p.val + q.val
  5.   else
  6.     Result.val := Result.val + p.val;
  7.  
  8.   if Result.val >= 10 then
  9.   begin
  10.     nRip := Result.val;
  11.     Result.val := nRip mod 10;
  12.     k := nRip div 10;
  13.   end
  14.   else
  15.     k := 0;
  16.  
  17. ...



ma non assegni un valore al riporto k prima di usarlo e inoltre fai un confronto
Codice sorgente - presumibilmente Pascal

  1. if Result.val >= 10 then



ancora prima di avere assegnato a k un valore....

PM Quote
Avatar
Goblin (Member)
Expert


Messaggi: 375
Iscritto: 02/02/2011

Segnala al moderatore
Postato alle 20:57
Giovedì, 31/05/2012
a rivederlo direi che ho commesso un errore :om: nella somma del riporto K, dunque il codice giusto dovrebbe essere:
Codice sorgente - presumibilmente Delphi

  1. if q <> Nil then
  2.     Result.val := k + p.val + q.val
  3.   else
  4.     Result.val := k + p.val;



K viene valorizzato a 0 al primo giro
Codice sorgente - presumibilmente Plain Text

  1. s := CalcoloSommaDiDueListe(nil, p, q, 0);



Ho effettuato un minigiro di debug, cosa che prima non avevo fatto, e mi sono accorto di alcune inesattezze nel codice, per
esempio se sommo 999 e 44 il risultato deve essere 1043 dunque la lista risultante deve essere dinamica.
Devo dire che il codice scritto così è abbastanza orribile... vediamo di fare un refactoring "parlante e più mantenibile", e di dare un commento al codice.

Codice sorgente - presumibilmente Delphi

  1. program SommaDiDueListe;
  2.  
  3. uses
  4.   SysUtils;
  5.     const bell=07;
  6.     Type SetVerso = (tvNext, tvBack);
  7.     type TpuntElemento = ^Telem;
  8.          Telem= record
  9.                  val: integer;
  10.                  back : TpuntElemento;
  11.                  next : TpuntElemento;
  12.                end;
  13.     var Lista_1, Lista_2, Risultato, oDummy: TpuntElemento;
  14.         nLungLista_1, nLungLista_2: integer;
  15.         nDomanda: Integer;
  16.  
  17. Function LeggiEScriviLista(pNext: TpuntElemento; nLung: integer): TpuntElemento;
  18. {******************************************************************
  19.  * Funzione che riempe le liste con i valori in input da tastiera *
  20.  * Ritorna una lista di tipo TpuntElemento con i valori immessi   *
  21.  ******************************************************************
  22. }
  23. begin
  24.   if nLung = 0 then
  25.     Result := nil
  26.   else
  27.   begin
  28.     new(Result);
  29.     read(Result.val);
  30.     Result.next := pNext;  // dato che scrivo da Dx vs Sx mi salvo il valore precedente
  31.     Result.Back := LeggiEScriviLista(Result, nLung-1); // chiedo il valore successivo
  32.   end;
  33. end;{ Fine procedura LeggiEScriviLista }
  34.  
  35. Function CalcoloSommaDiDueListe(sBack, oLista_1, oLista_2: TpuntElemento; nRiporto: integer): TpuntElemento;
  36. {******************************************************************
  37.  * Funzione che somma le due liste in entrata                     *
  38.  * Ritorna una lista di tipo TpuntElemento con i valori sommati   *
  39.  ******************************************************************
  40. }
  41.  
  42. Var nRip_temp : Integer;
  43. begin
  44.   if (oLista_1 = nil) and (nRiporto = 0) then  // se sono nell'ultimo elemento
  45.   begin                                        // e non c'e' riporto vuol dire che ho finito
  46.     Result := Nil;
  47.     exit;
  48.   end
  49.   else if (oLista_1 = nil) and (nRiporto > 0) then // se sono nell'ultimo elemento
  50.   begin                                            // e ho un riporto aggiungo il valore
  51.     new(Result);                                   // del riporto ad un nuovo elemento
  52.     Result.Val := nRiporto;                        // della lista
  53.     Result.back := sBack;
  54.     Exit;
  55.   end;
  56.  
  57.   new(Result);
  58.   Result.back := sBack;
  59.   if oLista_2 <> Nil then                          // Se la lista_2 ha finito i valori
  60.     Result.val := nRiporto + oLista_1.val + oLista_2.val
  61.   else
  62.     Result.val := nRiporto + oLista_1.val;         // sommo solo il riporto e la lista_1
  63.  
  64.   if Result.val >= 10 then             // se c'e' un possibile riporto
  65.   begin
  66.     nRip_Temp := Result.val;           // lo calcolo
  67.     Result.val := nRip_Temp mod 10;    // il modulo lo metto nella lista
  68.     nRiporto := nRip_Temp div 10;      // il resto lo scrivo nel riporto
  69.   end
  70.   else
  71.     nRiporto := 0;
  72.  
  73.   if oLista_2 <> Nil then              // chiamata ricorsiva
  74.     Result.next := CalcoloSommaDiDueListe(Result, oLista_1.next, oLista_2.next, nRiporto)
  75.   else
  76.     Result.next := CalcoloSommaDiDueListe(Result, oLista_1.next, nil, nRiporto);
  77. end;{ Fine procedura CalcoloSommaDiDueListe }
  78. { Corpo del programma }
  79.  
  80. Function GiraListe(oPunt: TpuntElemento; oVerso: SetVerso): TpuntElemento;
  81. { mi serve per girare le liste e leggerle da sx vs dx
  82. }
  83. begin
  84.   Result := oPunt;
  85.   case oVerso of
  86.     tvBack: begin
  87.              while Result.back<>nil do
  88.                Result := Result.back;
  89.             end;
  90.     tvNext: begin
  91.              while Result.Next<>nil do
  92.                Result := Result.Next;
  93.             end;
  94.   end;
  95. end;
  96.  
  97. begin
  98.   repeat
  99.     writeln('------------------------- Dati di ingresso --------------------------');
  100.     writeln;
  101.     write('Fornire la lunghezza della prima lista: ');
  102.     readln(nLungLista_1);
  103.     writeln;
  104.     write('Fornire la lunghezza della seconda lista: ');
  105.     readln(nLungLista_2);
  106.     writeln;
  107.     if nLungLista_2 > nLungLista_1 then
  108.     begin
  109.       writeln(chr(bell),'Errore nei dati di ingresso!- STOP -');
  110.       exit;
  111.     end
  112.     else
  113.     begin
  114.      write('Fornire la prima lista: ');
  115.      writeln;
  116.      Lista_1 := LeggiEScriviLista(Nil, nLungLista_1);
  117.      writeln;
  118.      write('Fornire la seconda lista: ');
  119.      writeln;
  120.      Lista_2 := LeggiEScriviLista(Nil, nLungLista_2);
  121.      writeln;
  122.      writeln('La lista somma e'':');
  123.      writeln;
  124.  
  125.      Lista_1 := GiraListe(Lista_1, tvBack );
  126.      Lista_2 := GiraListe(Lista_2, tvBack);
  127.      Risultato := CalcoloSommaDiDueListe(nil, Lista_1, Lista_2, 0);
  128.      Risultato := GiraListe(Risultato, tvNext);
  129.  
  130.    // giro di stampa
  131.      oDummy := Risultato;
  132.      repeat
  133.        Write(oDummy.val);
  134.        oDummy := oDummy.back;
  135.      until oDummy.back=nil;
  136.      Write(oDummy.val);
  137.     end;
  138.     writeln;
  139.     writeln;
  140.     writeln('1) Per finire 2) per ripetere');
  141.     readln(nDomanda);
  142.   until nDomanda=1;
  143. end.




Ibis redibis non morieris in bello
PM Quote
Avatar
fabioser (Normal User)
Rookie


Messaggi: 59
Iscritto: 12/05/2012

Segnala al moderatore
Postato alle 7:05
Venerdì, 01/06/2012
Grazie mille per la disponibilità!

PM Quote