Bonjour à tous!

En 1ère année de cycle préparatoire aux grandes écoles, je dois réaliser un algorithme permettant de multiplier 2 nombres par jalousie (technique de multiplication par jalousie : https://fr.wikipedia.org/wiki/Technique_de_la_multiplication_par_jalousies), puis le retranscrire sous le langage C. Cependant, j'ai déjà beaucoup de mal a écrire mon algorithme, rien ne marche, et encore moins en C...

J'espère que vous pourrez m'aider, Merci d'avance!

Salut formuler comme ça pour t'aider il faudrait te donner le code :/

Déjà commence par faire une matrice et stocker dans la ligne 0 et la colonne 0 ton nombre grâce a des modulo10

Après on passe à la suite

Ecrire ("entrer le nombre numéro 1"!)

Lire (Clavier! nb1)

Ecrire ("entrer le nombre numéro 2"!)

Lire (Clavier! nb2)

Déjà ici j'ai un problème. En effet, je sais prendre pour un nombre donné son chiffre des dizaines, ou encore son chiffres des milliers, et etc (par exemple, pour 238, 238mod10=8, (238mod100-238mod10)mod10=3, (238-238mod100)=2). Mais la, on connait pas le nombre de chiffre dans les nombres à l'avance... Donc déjà là, je vois pas comment prendre les chiffres qu'il me faut :/

En gros, a chaque fois j'ai une ou plusieurs idées mais je sais en mettre 0 en place...

Merci de prendre le temps de me répondre Golgoo

-
Edité par Theoucs 19 mai 2018 à 19:32:29

Alors d'abord il faut que tu récpère le nombre de décimale d'un nombre quelconque, il tu faut une fonction pour ça ;

tu peux par exemple faire une boucle avec un compteur, chaque tour de boucle incrément ce compteur, et chaque fois tu divise le nombre par 10 puis 100, etc.. jusqu'à ce que cette division te donne un chiffre < 1 ; alors tu retourne la valeur du compteur comme résultat de la fonction, il s'agit du nombre de décimale.

Une fois cette étape opérationnelle faite on va devoir créer un matrice via l'allocation dynamique

Erf... Désolé Golgoo mais je suis pas sur de tout bien comprendre... Déjà rien que la boucle j'ai pas bien compris, et ensuite je ne sais pas ce qu'est l'allocation dynamique, et je n'ai jamais utilisé de matrices en algo et encore moins en C. :/

Ok ben on fera sans l'allocation dynamique, mais nous en sommes pas encore la.

Tu dois faire une fonction :

int nbr_decimale( int nombre ) ; 

qui te retourne le nombre de décimale(s) d'un nombre.

Avant de passer à la suite faut être capable de faire ça, poste ce que tu as essayé

-
Edité par Golgoo 19 mai 2018 à 20:18:07

Oh, désolé mais je crois que j'ai oublié de préciser que les chiffres saisis étaient des entiers et non des décimales...

Du coup pas besoin de ca si? sauf si j'ai vraiment rien compris

-
Edité par Theoucs 19 mai 2018 à 20:34:33

Peut être que c'est moi qui est pas compris ce que tu voulais

Pour récupérer les entiers tu fait scanf(%d",&nombre); ?

Oui la fonction int nbre_décimale (int nombre ) te retourne le nombre de chiffre ( décimales ) dans le nombre int ( entier ) passer en arguments, faut just la faire avant de passer à la suite

Oh je crois que j'avais pas la bonne notion de "décimales". Pour moi c'était les nombres après la virgule, mais la je crois comprendre que c'est juste le nombre de chiffres, par exemple 238 comporte 3 décimales.

Sinon oui je fais bien "scanf(%d",&nombre);" !

Du coup l'algo commencerait comme ça?

int nombre1;

int nombre2;

printf ("Entrer le nombre numéro 1");

scanf ("%d", &nombre1);

printf ("Entrer le nombre numéro 2");

scanf ("%d", &nombre2);

int nombre_decimales1( int nombre1);

int nombre_decimales2( int nombre2);

Voila voila!

-
Edité par Theoucs 19 mai 2018 à 21:18:55

Ha non j'ai vérifier je me planter c'étais bien nombre de chiffres, d'après ce que j'ai compris.

Oui il commence comme ça, après tu fais une matrice de structure qui contient 2 int genre entier_up entier_down;

Tu créer 2 tableaux ( un par nombre ), genre t1[0]=2 t1[1]=3 avec int nbr_decimale_nombre1 = 2 ; pour 23.

tu remplis ta matrice de structure en faisant les multiplication :

pour l'entier de la matrice M[0][0].entier_down=(t1[0]*t2[0]) % 10 ; entier_up = (t1[0]*t2[0]) / 10 ;

Une fois que tu as fais ça tu as juste a interpréter la matrice.

Mais on en est pas encore la fais voir ou t'en ais dans ton code

Le truc c'est que j'ai jamais fais de matrices en algo... Et en maths ca remonte l'année derniere en terminale, vite fait grace a la spé maths.

Et j'ai du mal a bien comprendre les fonctions que tu utilises... Ca m'énerve d'être aussi nul erf :/

Je viens de lire l'algorithme, il n'y a pas besoin de matrices, juste de tableaux. Peut-être que Golgoo emploie le mot « matrice » dans le sens de « tableau » ? A priori, la méthode doit pouvoir se faire en parcourant un tableau (c'est juste qu'il faut le parcourir en diagonale − et qu'il faut d'abord le créer).

-
Edité par robun 19 mai 2018 à 23:48:58

Exact j'entends par "matrice" ensemble de tableaux identiques , enfin je trouvais plus simple de remplir une matrice qu'un tableau à remplir en diagonale, mais peut être que c'est plus compliquer, il y a certainement plusieurs façons de le faire, certaines meilleurs et d'autres moins, dans tous les cas je te propose une méthode qui marchera et qui est accessible en regardant le cours sur le site en langage C

Tu peux regarder dans le cours comment créer une matrice si ça t'intéresse.

Pour rendre le problème plus simple essaye de stocker les nombres dans des tableaux,

Une fois que tu auras fais ces deux étapes, on devra remplir la matrice avec les tableaux.

-
Edité par Golgoo 20 mai 2018 à 0:41:42

D'acc, je vais essayer de regarder le cours sur les matrices.

Mais je comprends pas bien avec quels nombres je dois remplir les tableaux :/

Tu peux remplir les tableaux avec les nombres que tu souhaite multiplier :

253 :

case 0 => 1er chiffre => 3

case 1 => 2eme => 5

case 2 => 3eme => 2

Ok, je pense que j'ai reussi a faire ca : 

J'ai pas utilisé ta fonction pour le nombre de décimale parce que je comprenais vraiment pas comment elle marchait... Mais je pense que comme ca ca marche? 

-
Edité par Theoucs 20 mai 2018 à 13:29:29

Je ne savais pas qu'on pouvait les récupérer comme ça, enfin quand je le lance ça me donne pas un bon résultat :/ peut être un truc similaire log10(nbr) ; aucune idée

Il existe peut être déjà des fonctions pour trouver rapidement sinon j'utilise celle-ci :

int nombre_chiffre(int nombre, int base){
  int i = 0 ;
  while(nombre>0){
    i++;
    nombre/=base;
  }
  return i ;
}

Sinon ton compilateur a du te dire qu'il y a une erreur pour int tab1[nbdec1] ;

Sans allocation dynamique tu dois créer un tableau suffisamment grand avec un constante a l'intérieur du genre : int tab1[100] ;

Lorsqu'on le lira, on saura qu'il ne faudra pas aller plus loin que nbdec1,

tu peux encore combiner les étapes mais c'est pas très important.

L'algo marche

maintenant pour créer une matrice tu fais pareil que pour les tableaux :

int matrice[100][100]

tu remarque que la case [0][0] de la matrice doit correspondre à la multiplication de la case 0 du tableau 1 et 0 du tableau2

                                    [0][1] <=> la case 0 du tableau 1 multiplié par la case 1 du tableau 2.

Pour parcourir toute les case d'une matrice tu dois faire 2 boucle for l'une dans l'autre

-
Edité par Golgoo 20 mai 2018 à 14:03:40

Voila comme ca c'est bon?

Et j'ai rectifié oui, je pensais que log correspondait au log10 mais il faut donc taper log10? (Et sinon oui normalement ca marche, il faut juste un nombre positif comme ici )

Oui ça à l'air bon., l.28 nombre1 = nombre2 / 10 => nombre2 = nombre2 / 10

Et je dirait qu'il faut des < au lieu de <= l.25 et l.30 regarde le cours pour parcourir des tableaux si tu comprend pas pourquoi

Maintenant il faut créer un tableau ou tu puisse stocker le résultat en ayant lu la matrice en diagonale.

Ce tableaux aura comme taille nb_dec_result = nb_dec_1 + nb_dec_2 ;

Et donc tu le créera avec la taille maximale que tu puisse avoir : int tableau[100+100]

Ensuite on a plus qu'à appliquer l'algo pour stocker les additions des bonnes case + les retenues

-
Edité par Golgoo 20 mai 2018 à 14:33:53

Oups oui l.28 erreur d'inattention.

En effet, j'avais pas pensé mais comme on commence a 0 et pas a 1, i faut des <, j'ai compris!

Ok je vois pour le tableau, c'est bon je l'ai créé. ( int tab3[200] )

Par contre j'ai vraiment du mal a comprendre de quelle façon je dois le remplir : en multipliant certaines cases de la matrice entre elles je pense, mais comme j'ai déjà du mal a voir quelles cases, et que je ne maîtrise pas les matrices, c'est chaud

En tout cas merci de m'aider c'est génial de ta part

Derien

En effet en ayant jamais fait de matrices pas évidents. Une matrice c'est ça :

           colonnes:  [0]       [1]

lignes:

  [0]         case : [0][0]  [1][0]

  [1]                   [0][1]  [1][1]

  [2]                   [0][2]  [1][2]

Dans l'exemple multiplié 92 * 81

On a :

[1]   [0]

9      2

72   16     8  [1]

1      2      1  [0]

Ici [1][1] = 72 ; [1][0] = 1 ; [0][0]  = 2

----------------------------------------------

Ce qu'il reste à faire c'est un algo du genre :

on initialise retenu à  0.

Pour n = 0 jusqu'à n < nb_dec_result

---- tab3[n] = LaSomme des cases de la matrice[i][j]%10 tq i+j = n

                   + LaSomme des cases de la matrice[i][j]/10 tq i+j = n - 1

                   + la retenu.

-----retenu = tab3[n] / 10

-----tab3[n] = tab3[n] % 10

Fin du pour

La chaque chiffre de ton résultat est stockés dans le tableau tab3.

PS: Si je peux aider pour répondre au post de quelqu'un je le fais en espérant que d'autre personne m'aide lorsque je post un problème, mais malheureusement c'est pas trop vrai

-
Edité par Golgoo 20 mai 2018 à 15:12:42

Alors, je pense avoir compris l'algo que tu a écris

Le truc c'est que j'ai aucune idée de comment retranscrire le "tel que i+j=n" en langage C, je savais même pas que c'était possible... Ou alors c'est pas possible et je vais devoir utiliser des boucles ou je sais pas quoi? Sinon le reste de l'algo je peux le retranscrire en C sans problème je pense.

Je vais essayer de chercher comment faire tel que sur internet en attendant que tu me répondes, je poste un autre message si je trouve.

Sinon je suis désolé mais étant donné que c'est toi qui m'aide, j'aurais du mal a t'aider je pense Bonne chance

EDIT : Enfaites apparemment on peut pas poster 2 msg a la suite, donc voila :

Bon, j'ai rien trouvé sur les tels que alors j'ai essayé de faire avec des outils que je connais, des boucles. Je suis loin d'être sur que ca fonctionne, ou que c'est optimisé, mais j'ai tenté :

Voila voila :/

-
Edité par Theoucs 20 mai 2018 à 15:51:54

Tu peux parcourir toutes les case à chaque fois et tu rajoute une condition if(i+j == n) { }

Ou bien je croix, pas sûr je vérifierai plus tard si tu veux:

int retenue = 0 ;
for(int n = 0 ; n < nbdec_tot ; n++){
  int a = retenue;
  for(int i=0, j=n ; j>=0 ; i++, j--){
    a+= matrice[i][j]%10;
  }
  for(int i=0, j=n-1 ; j >= 0 ; i++, j--){
    a+= matrice[i][j]/10;
  }
  tab3[n] = a %10;
  retenue = a / 10 ;
}

C'est plus simple de parcourir toute les cases et de rajouter des if (condition ) { quelque chose } je te conseille de voir si ça marche en parcourant tout avant d'essayer d'optimiser. :

int retenue = 0 ;
for(int n = 0 ; n < nbdec_tot ; n ++){
  int a = retenue ;
  for(int i = 0 ; i < nbdec1 ; i ++){
    for(int j = 0 ; j < nbdec2 ; j ++){
      if(i+j == n){
        a+= matrice[i][j]%10;
      }
      else if(i+j == n - 1){
        a+= matrice[i][j]/10;
      }
    }
  }
  //Fin du parcours de la matrice :
  tab3[n] = a % 10;
  retenue = a / 10 ;
}

Je n'ai rien fait tourner encore, je ne te garanti pas que c'est bon à 100 % je testerai plus tard. Bonne chance.

Sinon, le faire directement sur un tableau, et sans passer par matrice. Mais je ne voix pas comment le faire simplement à première vue.

Ah ça y est, j'ai compris !

Golgoo : ce que tu appelles un tableau, c'est un tableau à 1 dimension, et ce que tu appelles une matrice, c'est un tableau à 2 dimension. C'est bien ça ?

Je reviens sur ce sujet pour éviter que Theoucs perde son temps à lire un cours sur les matrices (qui sont plus que juste des tableaux à 2 dimensions).

> Le truc c'est que j'ai aucune idée de comment retranscrire le "tel que i+j=n" en langage C

Ça se fait à l'intérieur de la boucle « for (i = 0 ; i < n ; i++) { ... } ». i+j=n est équivalent à j=n-i, donc il suffit d'écrire « j = n - i ; ».

-
Edité par robun 20 mai 2018 à 18:26:39

Merci de vos réponses!

Oui robun, j'ai compris après que la "matrice" était un tableau a 2 dimensions

Du coup golgoo, la j'ai bien mon tab3 avec dans chaque case un des chiffres du resultat final? D'après ce que j'ai compris oui, donc je vais essayer de coder la derniere partie pour avoir le nombre, ca doit pas etre trop dur je pense?

Au fait la première méthode que je t'ai donné pour remplir tab3 est fausse ; la deuxième marche et je te la conseille toujours ;

sinon la première méthode corrigé donnerai un truc comme ça :

int retenue = 0 ;
  for(int k = 0 ; k < nb_dec_3 ; k ++){
    int a = retenue ;
    for(int i = max(0,k - nb_dec_2 + 1) ; i <= min(k,nb_dec_1 - 1) ; i ++){
      int j = k - i ;
      a+= matrice[i][j]%10;
    }
    for(int i = max(0,k - nb_dec_2) ; i <= min(k - 1, nb_dec_1 -1) ; i++){
      int j = k - 1 - i ;
      a+= matrice[i][j]/10;
    }
    tab3[k] = a % 10 ;
    retenue = a / 10 ;
  }

 Ici le nombre est stocké dans tab3 ;

Ca te permet de réduire le temps d'exécution mais je pense qu'il vaut mieux parcourir toute les cases de la matrices, c'est plus accessible.

GL

Oui mais en soit une dimension de ta matrice peut très bien aussi être une matrice ou autre mais sinon le larousse dit :

Mathématiques
Famille (α_ij) d'éléments d'un corps K, (i, j) ∈ { 1, …, n } × { 1, …, p}, n et p étant deux naturels, habituellement présentée sous la forme d'un tableau rectangulaire à n lignes et p colonnes [matrice de type (n, p)].

-
Edité par Golgoo 20 mai 2018 à 22:44:00

Okay parfait je vais voir ca alors! Par contre la je viens d'installer codeblocks hier enfaites, (j'avais déja codé mais sur des ordis de mon école) et j'viens de me rendre compte qu'il y avait un pb de compilateur ou jsp quoi donc je vais regarder d'ou ca vient (je peux pas lancer de programmes, juste les écrire). Quand ca marche je te dit si l'ensemble fonctionne!

Et du coup pour écrire le nombre sous sa forme normale, ca ca marcherait? :

ça a l'air d'être correct oui :), tu peux toujours poster sur le forum, je ne pourrais pas t'aider pour code block

Yeeeees c'est bon tout marche, milles merci a toi! Sinon pour codeblocks j'avais simplement installé la version sans compilateur x)

Une derniere chose, je dois aussi afficher le tableau de la multiplication par jalousie (en gros la "matrice")

Je peux toujours faire une boucle pour et afficher chaque cellule une a une, mais je suis pas sur que ca soit ca le truc demandé, et si c'est des gros nombres... juste horrible a lire.

Y'a une meilleure facon d'afficher un tableau? genre sous forme de vrai tableau?

Tu voudrais afficher comme le lien que tu as donné dans le post ?

-
Edité par Golgoo 21 mai 2018 à 1:19:03