Pascal - Somma di due numeri di lunghezza arbitraria rappresentati mediante liste simmetriche

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:

program SommaDiDueListe(input,output);
type punt=^elem;
     elem= record
                 val: integer;
                 back : punt;
                 next : punt;
           end;
var p,q,s,t: punt;
    m,n : integer;

    procedure LeggiEScriviLista( t : punt; var p : punt; k : integer);
    begin
         if k=0
         then p:=nil
         else begin
                   new(p);
                   read(p^.val);
                   write(p^.val,' ');
                   new(t);
                   read(t^.val);
                   p^.back:=t;
                   write(t^.val,' ');
                   LeggiEScriviLista(t,p^.back,k-1);
              end;
    end;{ Fine procedura LeggiEScriviLista }
procedure CalcoloSommaDiDueListe( var s : punt; p,q : punt; k : integer);
begin

     if k=0
     then s:=nil
     else begin
               new(s);
               s^.val:=p^.val+q^.val;
               s^.next^.val:=p^.next^.val+q^.next^.val;
               if s^.next^.val>=10
               then begin
                         s^.next^.val:=(s^.next^.val)mod 10;
                         s^.val:=p^.val+q^.val+(s^.next^.val)div 10;
                    end;
               if s^.val<10
               then write(s^.val,' ')
               else  begin s^.val:=(s^.val)mod 10;
                           write(s^.val,' ');
                     end;
               if k=m
               then if s^.val>=10
                    then begin s^.back^.val:=(s^.val)div 10;
                               write(s^.back^.val,' ');
                         end;
               CalcoloSommaDiDueListe(s^.back,p^.back,q^.back,k-1);
          end;
end;{ Fine procedura CalcoloSommaDiDueListe }

{ Corpo del programma }
begin
     writeln('------------------------- Dati di ingresso --------------------------');
     writeln;
     write('Fornire la lunghezza della prima lista: ');
     readln(m);
     writeln;
     write('Fornire la lunghezza della seconda lista: ');
     readln(n);
     write('Fornire la prima lista: ');
     LeggiEScriviLista(nil,p,m);
     writeln;
     write('Fornire la seconda lista: ');
     LeggiEScriviLista(nil,q,n);
     writeln;
     writeln('La lista somma e'':');
     writeln;
     CalcoloSommaDiDueListe(s,p,q,m);
     readln;

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!!!

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):

Function LeggiEScriviLista(pNext: punt; k: integer): Punt;
begin
  if k=0 then
    Result := nil
  else
  begin
    new(Result);
    read(Result.val);
    Result.next:=pNext;
    Result.Back := LeggiEScriviLista(Result, k-1);
  end;
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:

Function CalcoloSommaDiDueListe(sBack, p, q: punt; k: integer): Punt;
Var nRip : Integer;
begin
  if p = nil then
  begin
    Result := Nil;
    exit;
  end;

  new(Result);
  Result.back := sBack;
  if q <> Nil then
    Result.val := k + p.val + q.val
  else
    Result.val := Result.val + p.val;

  if Result.val >= 10 then
  begin
    nRip := Result.val;
    Result.val := nRip mod 10;
    k := nRip div 10;
  end
  else
    k := 0;

  if q <> Nil then
    Result.next := CalcoloSommaDiDueListe(Result, p.next, q.next, k)
  else
    Result.next := CalcoloSommaDiDueListe(Result, p.next, nil, k);
end;

per comodità ho girato le liste con:

Function GiraListe(oPunt: Punt; oVerso: SetVerso): punt;
begin
  Result := oPunt;
  case oVerso of
    tvBack: begin
             while Result.back<>nil do
               Result := Result.back;
            end;
    tvNext: begin
             while Result.Next<>nil do
               Result := Result.Next;
            end;
  end;
end;

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

Per riassumere il tutto:

program SommaDiDueListe(input,output);

uses
   SysUtils;

    const bell=07;
    Type SetVerso = (tvNext, tvBack);
    type punt=^elem;
         elem= record
                 val: integer;
                 back : punt;
                 next : punt;
               end;
    var p,q,s, oDummy: punt;
        m,n : integer;
        st: String;

Function LeggiEScriviLista(pNext: punt; k: integer): Punt;
begin
  if k=0 then
    Result := nil
  else
  begin
    new(Result);
    read(Result.val);
    Result.next:=pNext;
    Result.Back := LeggiEScriviLista(Result, k-1);
  end;
end;{ Fine procedura LeggiEScriviLista }

Function CalcoloSommaDiDueListe(sBack, p, q: punt; k: integer): Punt;
Var nRip : Integer;
begin
  if p = nil then
  begin
    Result := Nil;
    exit;
  end;

  new(Result);
  Result.back := sBack;
  if q <> Nil then
    Result.val := k + p.val + q.val
  else
    Result.val := Result.val + p.val;

  if Result.val >= 10 then
  begin
    nRip := Result.val;
    Result.val := nRip mod 10;
    k := nRip div 10;
  end
  else
    k := 0;

  if q <> Nil then
    Result.next := CalcoloSommaDiDueListe(Result, p.next, q.next, k)
  else
    Result.next := CalcoloSommaDiDueListe(Result, p.next, nil, k);
end;{ Fine procedura CalcoloSommaDiDueListe }
{ Corpo del programma }

Function GiraListe(oPunt: Punt; oVerso: SetVerso): punt;
begin
  Result := oPunt;
  case oVerso of
    tvBack: begin
             while Result.back<>nil do
               Result := Result.back;
            end;
    tvNext: begin
             while Result.Next<>nil do
               Result := Result.Next;
            end;
  end;
end;

begin
  try
    writeln('------------------------- Dati di ingresso --------------------------');
    writeln;
    write('Fornire la lunghezza della prima lista: ');
    readln(m);
    writeln;
    write('Fornire la lunghezza della seconda lista: ');
    readln(n);
    writeln;
    if m<n then
    begin
      writeln(chr(bell),'Errore nei dati di ingresso!- STOP -');
      exit;
    end
    else
    begin
     write('Fornire la prima lista: ');
     writeln;
     p := LeggiEScriviLista(Nil, m);
     writeln;
     write('Fornire la seconda lista: ');
     writeln;
     q := LeggiEScriviLista(Nil, n);
     writeln;
     writeln('La lista somma e'':');
     writeln;

     p := GiraListe(p, tvBack );
     q := GiraListe(q, tvBack);
     s := CalcoloSommaDiDueListe(nil, p, q, 0);
     s := GiraListe(s, tvNext);

     oDummy := s;
     repeat
       Write(oDummy.val);
       oDummy := oDummy.back;
     until oDummy.back=nil;
     Write(oDummy.val);
    end;
    readln(st);
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.

Grazie mille Goblin per i preziosi suggerimenti. Proverò a metterli in pratica. Ciao!!!

Ci sono due cose che non riesco a capire nella tua soluzione e riguardano il calcolo del generico valore Result^.val. Tu scrivi:

...

  if q <> Nil then
    Result.val := k + p.val + q.val
  else
    Result.val := Result.val + p.val;
 
  if Result.val >= 10 then
  begin
    nRip := Result.val;
    Result.val := nRip mod 10;
    k := nRip div 10;
  end
  else
    k := 0;

...

ma non assegni un valore al riporto k prima di usarlo e inoltre fai un confronto

if Result.val >= 10 then

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

a rivederlo direi che ho commesso un errore nella somma del riporto K, dunque il codice giusto dovrebbe essere:

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

K viene valorizzato a 0 al primo giro

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.

program SommaDiDueListe;

uses
  SysUtils;
    const bell=07;
    Type SetVerso = (tvNext, tvBack);
    type TpuntElemento = ^Telem;
         Telem= record
                 val: integer;
                 back : TpuntElemento;
                 next : TpuntElemento;
               end;
    var Lista_1, Lista_2, Risultato, oDummy: TpuntElemento;
        nLungLista_1, nLungLista_2: integer;
        nDomanda: Integer;

Function LeggiEScriviLista(pNext: TpuntElemento; nLung: integer): TpuntElemento;
{******************************************************************
 * Funzione che riempe le liste con i valori in input da tastiera *
 * Ritorna una lista di tipo TpuntElemento con i valori immessi   *
 ******************************************************************
}
begin
  if nLung = 0 then
    Result := nil
  else
  begin
    new(Result);
    read(Result.val);
    Result.next := pNext;  // dato che scrivo da Dx vs Sx mi salvo il valore precedente
    Result.Back := LeggiEScriviLista(Result, nLung-1); // chiedo il valore successivo
  end;
end;{ Fine procedura LeggiEScriviLista }

Function CalcoloSommaDiDueListe(sBack, oLista_1, oLista_2: TpuntElemento; nRiporto: integer): TpuntElemento;
{******************************************************************
 * Funzione che somma le due liste in entrata                     *
 * Ritorna una lista di tipo TpuntElemento con i valori sommati   *
 ******************************************************************
}

Var nRip_temp : Integer;
begin
  if (oLista_1 = nil) and (nRiporto = 0) then  // se sono nell'ultimo elemento
  begin                                        // e non c'e' riporto vuol dire che ho finito
    Result := Nil;
    exit;
  end
  else if (oLista_1 = nil) and (nRiporto > 0) then // se sono nell'ultimo elemento
  begin                                            // e ho un riporto aggiungo il valore
    new(Result);                                   // del riporto ad un nuovo elemento
    Result.Val := nRiporto;                        // della lista
    Result.back := sBack;
    Exit;
  end;

  new(Result);
  Result.back := sBack;
  if oLista_2 <> Nil then                          // Se la lista_2 ha finito i valori
    Result.val := nRiporto + oLista_1.val + oLista_2.val
  else
    Result.val := nRiporto + oLista_1.val;         // sommo solo il riporto e la lista_1

  if Result.val >= 10 then             // se c'e' un possibile riporto
  begin
    nRip_Temp := Result.val;           // lo calcolo
    Result.val := nRip_Temp mod 10;    // il modulo lo metto nella lista
    nRiporto := nRip_Temp div 10;      // il resto lo scrivo nel riporto
  end
  else
    nRiporto := 0;

  if oLista_2 <> Nil then              // chiamata ricorsiva
    Result.next := CalcoloSommaDiDueListe(Result, oLista_1.next, oLista_2.next, nRiporto)
  else
    Result.next := CalcoloSommaDiDueListe(Result, oLista_1.next, nil, nRiporto);
end;{ Fine procedura CalcoloSommaDiDueListe }
{ Corpo del programma }

Function GiraListe(oPunt: TpuntElemento; oVerso: SetVerso): TpuntElemento;
{ mi serve per girare le liste e leggerle da sx vs dx
}
begin
  Result := oPunt;
  case oVerso of
    tvBack: begin
             while Result.back<>nil do
               Result := Result.back;
            end;
    tvNext: begin
             while Result.Next<>nil do
               Result := Result.Next;
            end;
  end;
end;

begin
  repeat
    writeln('------------------------- Dati di ingresso --------------------------');
    writeln;
    write('Fornire la lunghezza della prima lista: ');
    readln(nLungLista_1);
    writeln;
    write('Fornire la lunghezza della seconda lista: ');
    readln(nLungLista_2);
    writeln;
    if nLungLista_2 > nLungLista_1 then
    begin
      writeln(chr(bell),'Errore nei dati di ingresso!- STOP -');
      exit;
    end
    else
    begin
     write('Fornire la prima lista: ');
     writeln;
     Lista_1 := LeggiEScriviLista(Nil, nLungLista_1);
     writeln;
     write('Fornire la seconda lista: ');
     writeln;
     Lista_2 := LeggiEScriviLista(Nil, nLungLista_2);
     writeln;
     writeln('La lista somma e'':');
     writeln;

     Lista_1 := GiraListe(Lista_1, tvBack );
     Lista_2 := GiraListe(Lista_2, tvBack);
     Risultato := CalcoloSommaDiDueListe(nil, Lista_1, Lista_2, 0);
     Risultato := GiraListe(Risultato, tvNext);

   // giro di stampa
     oDummy := Risultato;
     repeat
       Write(oDummy.val);
       oDummy := oDummy.back;
     until oDummy.back=nil;
     Write(oDummy.val);
    end;
    writeln;
    writeln;
    writeln('1) Per finire 2) per ripetere');
    readln(nDomanda);
  until nDomanda=1;
end.

Grazie mille per la disponibilità!