Solution du TD d'informatique No. 4 :
les listes

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 4 décembre 2000

1   Arithmétique en précision infinie

import java.io.* ;
import java.lang.* ;
import java.util.* ;

public class Liste {
    // Elements constitutifs des Listes
    int elt ;
    Liste suivant ;

    Liste(int i, Liste l) {
 elt = i ;
 suivant = l ;
    }

    // Creation d'une liste a partir d'une chaine de caracteres
    ///////////////////////////////////////////////////////////
    static Liste Faire_Liste_Iteratif(String chaine) {
 Liste l = null ;
 for (int i = 0 ; i < chaine.length() ; i++) {
     l = new Liste(Integer.parseInt(chaine.substring(i, i+ 1)), l) ;
 }
 return l ;
    }

    static Liste Faire_Liste_Recursif(String chaine) {
 if (chaine.length() == 0)
     return null ;
 return new Liste(Integer.parseInt(chaine.substring(chaine.length() - 1, chaine.length())),
    Faire_Liste_Recursif(chaine.substring(0, chaine.length() - 1))) ;
    }
    
    // Affichage d'une liste
    ////////////////////////
    static void Afficher_Liste(Liste l) {
 if (l != null) {
     Afficher_Liste(l.suivant) ;
     System.out.print(l.elt) ;
 }
    }
    
    // Copie d'une liste
    ////////////////////
    static Liste Copie_Liste(Liste l) {
 if (l == null)
     return null ;
 return  new Liste(l.elt, Copie_Liste(l.suivant)) ;
    }
    
    // Addition de deux listes
    //////////////////////////
    static Liste Addition_Liste(Liste l1, Liste l2) {
 return Addition_Liste_Aux(l1, l2, 0) ;
    }
    
    static Liste Addition_Liste_Aux(Liste l1, Liste l2, int retenue) {
 if (l1 == null && l2 == null && retenue == 0)
     return null ;
 if (l1 == null && l2 == null && retenue != 0)
     return new Liste(retenue, null) ;
 if (l1 == null && retenue == 0)
     return Copie_Liste(l2) ;
 if (l1 == null && retenue != 0) {
     int n = l2.elt + retenue ;
     return new Liste(n % 10, Addition_Liste_Aux(null, l2.suivant, n / 10)) ;
 }      
 if (l2 == null && retenue == 0)
     return Copie_Liste(l1) ;
 if (l2 == null && retenue != 0) {
     int n = l1.elt + retenue ;
     return new Liste(n % 10, Addition_Liste_Aux(l1.suivant, null, n / 10)) ;
 }
 int n = l1.elt + l2.elt + retenue ;
 return new Liste(n % 10, Addition_Liste_Aux(l1.suivant, l2.suivant, n / 10)) ;
    }
    
    // Multiplication de deux listes
    ////////////////////////////////
    // Calcul le produit de l par n en ajoutant la retenue.
    static Liste Mult_Liste(Liste l, int n, int retenue) {
 if (l == null) {
     if (retenue == 0)
  return null ;
     return new Liste(retenue, null) ;
 }
 int i = l.elt * n + retenue ;
 return new Liste(i % 10, Mult_Liste(l.suivant, n, i / 10)) ;
    }
    
    static Liste Multiplication_Liste(Liste l1, Liste l2) {
 if (l1 == null || l2 == null) {
     System.out.println("Multiplication impossible !") ;
     System.exit(0) ;
 }
 if (l2.suivant != null)
     return Addition_Liste(Mult_Liste(l1, l2.elt, 0), Mult_Liste(Multiplication_Liste(l1, l2.suivant), 10, 0)) ;
 else
     return Mult_Liste(l1, l2.elt, 0) ;
    }
    
    // Programme principal
    //////////////////////
    public static void main(String[] arg) {
 // Verification des arguments
 if (arg.length != 2) {
     System.out.println("Utilisation : java grands_nombres n1 n2") ;
     System.exit(0) ;
 }
 
 Liste l1 = Faire_Liste_Iteratif(arg[0]) ;
 Liste l2 = Faire_Liste_Recursif(arg[1]) ;
 System.out.print("Premier nombre : ") ;
 Afficher_Liste(l1) ;
 System.out.print("\nDeuxieme nombre : ") ;
 Afficher_Liste(l2) ;
 System.out.print("\nSomme : ") ;
 Afficher_Liste(Addition_Liste(l1, l2)) ;
 System.out.print("\nProduit : ") ;
 Afficher_Liste(Multiplication_Liste(l1, l2)) ;
 System.out.println() ;
    }
}

This document was translated from L^AT_EX by H^EV^EA.