3awnou khokom fi sabile lah

Discussion dans 'Forum des étudiants' créé par fsniper, 29 Décembre 2005.

  1. fsniper

    fsniper Guest

    y a quelqu un ki peu m aider pour un projet de programmation en C : [41h]

    voila le sujet :

    Calcul sur les entiers en précision arbitraire
    Projet IAP (B2)



    Introduction

    Le but de ce projet est de mettre au point une librairie travaillant sur de très grands entiers, le nombre de chiffre n'étant limité que par la mémoire de votre machine. La taille des entiers utilisés étant dynamique et donc inconnue à la compilation. L'idée est de représenter un entier donné par la liste de ses chiffres dans une base B. Ainsi l'entier
    n = c0 + c1× B + ... + cn-1× Bn-1 + cn× Bn
    est représenté par la liste
    [ c0 ; c1 ; ... ; cn]
    de ses chiffres qui sont des entiers strictement plus petits que B, avec la convention que le chiffre le plus significatif cn est non nul. En outre, zéro est représenté de manière unique par la liste vide. Remarquez que Le stockage se fait du poids faible (le chiffre le moins significatif) au poids fort (le plus significatif). Pour faciliter l'affichage la base B est multiple de 10. C'est la multiplication qui impose les contraintes les plus strictes sur la base B. En effet, la multiplication de deux chiffres plus un chiffre de retenue vaut au maximum (B-1)× (B-1) + B-1, soit est bornée par B2 qui doit donc être majoré par le plus grand entier positif manipulable. Si on utilise des int codes sur 4 octets pour représenter les chiffres dans la représentation en base B. Le plus grand int étant 231 - 1 la base maximale sera 104 car 108 < 231-1 < 1010. Dans la suite, vous pouvez commencer par prendre la base B=10, les listes de chiffres correspondent alors à l'intuition héritée de l'école primaire. Ensuite, augmentez la base, et voyez si votre code fonctionne encore. Le code final devra fonctionner avec B=10000 c'est dans cette base que sont donnés les exemples.


    Préliminaires sur les listes d'entier

    Définir le type intListe des listes d'entiers (int). Vous aurez besoin au minimum des fonction suivante :
    intListe cons(int n,intListe l) qui ajoute un élément en tête de liste.
    intListe reverse(intListe l) qui inverse les éléments d'une liste.
    int listeLong(intListe l) qui donne la longueur d'une liste
    void afficheList(intList l) qui affiche les éléments de la liste

    Entiers naturels N

    Fonctions de bases

    Définir le type nat des entiers naturel comme un synonyme du type listes d'entiers intListe défini au dessus. Un entier étant represente en base B écrire les fonctions
    nat natOfInt(int n) de conversion (plongement) d'un entier machine (int) vers un grand entier (nat).
    nat natOfString(char * s)de conversion d'un chaîne de caractère (composée uniquement de chiffe) vers un grand entier (nat).
    La seconde est plus dure et pourra être sautée dans une premier temps.

    Opérations

    Addition

    Écrire une fonction d'addition : nat addNat(nat dl1,nat dl2) Telle que nat addNat(a,b) renvoie le grand entier qui représente la somme des grands entiers représentés par a et b. On vous conseille pourra décomposer en plusieurs fonctions auxiliaires, par exemple :

    une fonction calculant la retenue et le résultat de l'addition de deux chiffre (i.e. de deux int des cellules de la représentation chaînée)
    une fonction nat addChiffre(int d, nat dl) calculant le résultat de l'addition d'un chiffre (i.e. d'une cellule de la représentation chaînée) et d'une grand entier (un nat).
    Soustraction :

    Écrire la fonction de soustraction en suivant une démarche analogue au cas de l'addition.

    Multiplication :

    Écrire la fonction de multiplication en suivant une démarche analogue au cas de l'addition. N'essayez pas la division, c'est beaucoup plus compliqué. Notez bien que vous pouvez afficher les listes à tout moment ce qui peut vous aider à mettre au point votre programme, avant même d'avoir écrit la fonction d'affichage.

    Affichage


    Écrire une fonction void printNat(nat n) d'affichage des grands entiers.

    Comparaisons

    Écrire les fonctions de comparaison (==,<,>) sur les grands entiers nat.

    fonctions

    Écrire les fonctions factoriel, puissance et exponentiel sur les grand entiers nat.

    Entiers relatif Z

    Vous devez maintenant passer aux entiers relatifs. Un entier relatif sera vu comme un couple formé d'un signe et d'un entier naturel. Définir un type pour Z et écrire les fonction d'addition,de soustraction, de multiplication, d'affichage et de conversion
    depuis un int et depuis une chaîne de caractère (ne contenant que des entiers potentiellement précédé d'un signe.

    Entiers de Gauss Z

    Les entiers de gauss sont les nombres complexes dont les parties réelles et imaginaires sont des entiers. Définir leur type et écrire les fonctions d'affichage, d'addition et de multiplication.

    Exemple minimaliste


    L'entier 1234567891
    est code par la liste de 3 chiffres:[ 7891 ; 3456 ; 12 ]

    L'entier 1323
    est code par la liste de 1 chiffres :[ 1323 ]

    On peut calculer factoriel 100 qui vaut

    93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

    et est represente par la liste de 40 chiffres :[ 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 6864 ; 1091 ; 1852 ; 8251 ; 2375 ; 8272 ; 7920 ; 5369 ; 2862 ; 6518 ; 7615 ; 4639 ; 8941 ; 1560 ; 2299 ; 9993 ; 1759 ; 8952 ; 2963 ; 6859 ; 6214 ; 4381 ; 6826 ; 7159 ; 490 ; 6670 ; 8562 ; 9238 ; 8169 ; 1526 ; 3944 ; 1544 ; 3262 ; 93 ]

    3awnou khoukom fi sabile lah :-( :(
     
  2. A_mir

    A_mir les causes perdues...

    J'aime reçus:
    103
    Points:
    0
    Re : 3awnou khokom fi sabile lah

    daba bach bghiti n3awnouk? chi 7edd ykherrej lik l projet za3ma? wella nteyybo lik lmakla fach tkoun tatkhdem? wella nd3iw m3ak? wella w7elti f chi l3ba w bghiti lli déblokik?
     

Partager cette page