Discussion :

[Izlane]

bonjour j'aimerai que vous m'aidiez a resoudre la derniere question( celle sur les diviseurs je crois qu'il faut ajouter un autre tableau mais je ne sais pas comment!! et pour les puissance on utilise math.h) de cet algorithme merci d'avance pour toutes vos reponses!!!

Ecrire un algorithme qui permet de
-saisir un entier N>1
-Remplir le tableau facteurs par tous ces facteurs premiers
-remplir a base du tableau facteurs,deus tableaux FD et Puissances: Le tableau FD (facteurs distinct)contiendra les differents facteurs premiers distincts de N
Le tableau Puissances est donne par Puissance[i]=nombre de repetitions du facteur FD[i] dans le tableau Facteurs ex N=720 facteurs=[2,2,2,2,3,3,5] FD=[2,3,5] Puissance=[4,2,1]
-Affiche la liste des diviseurs de N :cette liste doit etre deduite des deux tableaux FD et Puissances cest toutes les combinaisons obtenues en incrementant les exposants des facteurs FD[i] de zero jusqu'au nombre Puissance[i] ex 45=3².5 les diviseurs sont 3°5° ,3°5^1, 3^1.5^1,3².5°,3²*.5^1

[Al_th]

Remplir le tableau facteurs par tous ces facteurs premiers

Selon toi, qu'est ce qui fait que 15 n'a pas "2" dans sa liste ? Sa division par deux n'est pas entière. Et sa division par 3 ?
Tu as là l'élément de base de réponse.

[prgasp77]

Bonjour,

je suppose que tu programmes en C ; dans ce cas tu as à ta disposition les opérateurs / (division euclidienne) et % (modulo, formellement reste de la division euclidienne).

Ces opérateurs assurent qu'étant donné deux entiers positifs a et b,
b * (a / b) + (a % b) = a,
avec a % b < a / b.

Avec ça, il est assez facile de calculer les facteurs premiers d'un entier naturel .

[Izlane]

Merci pour vos réponses pour les diviseurs premiers enfait voici la partie du programme que j'ai faite en langage C

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include<stdio.h>
#include<math.h>
 
int N,i,k,l,m,j,p,puissance;
int Facteurs[100],FD[100],Puissances[100];
 
int main()
{
    printf("                            Affichage des diviseurs d'un entier         ");
    printf("\nEntrer un entier strictement supérieur a 1 : ");
    scanf("%d",&N);
    if(N<=1)
    printf("\nSaisie Incorrecte ");
    else
    {
        i=0;
        while(N!=1)
        { k=2;
          while(N%k!=0)
           { k++;
            Facteurs[i]=k;
            i++;  }
            }
            i=i-1;
            for(j=0;j<=i;j++)
            FD[j]=Facteurs[j];
            for(j=0;j<=i;j++)
              for(l=j+1;l<=i;l++)
                    if(FD[j]=FD[l])
                      { for(m=l;m<=i-1;m++)
                         FD[m]=FD[m+1];  }
 
        j=0;
        p=0;
        while(j<=i)
         {  puissance=1;
          for(l=j+1;l<=i;l++)
              { if(Facteurs[l]=Facteurs[j])
                    puissance=puissance+1; }
            Puissances[p]=puissance;
              p=p+1;
             j=j+puissance; }
 
 
    } 
    getch();
}

Maintenant c'est la derniere question que je n'arrive pas à faire, donner la liste des diviseurs de N ca je sais lefaire mais là ils demandent a partir des deux tableaux FD et Puissances donc si vous aviez ne serait-ce qu'une indication ce serait vraiment sympa . Merci

[Al_th]

Salut,

Alors tout d'abord, je me permet de te donner quelques petits conseils au niveau de ton code.

Premièrement, n'hésite pas à décomposer toute tes "opérations" en fonctions. Ça a l'air débile comme conseil, mais je t'assure que tu y gagneras en lisibilité.
D'autre part, et ça c'est vraiment personnel comme remarque, j'suis ptet bizarre, je te conseille de fermer tes accolades (par exemple une accolade de for) au niveau du début du for. Ça te permettra en un coup d'oeil de voir la fin de ton bloc, sans le chercher.

Ex :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
for(int i = 0 ; i < 10 ; i++)
    {int a = 3;
    int b = 2;}
----------------
for(int i = 0 ; i < 10 ; i++){
    int a = 3;
    int b = 2;
}

Mais ca reste qu'une question de notation, et ca n'est génant que quand l'indentation n'est pas bien réalisée. Mais comme je remarque que dans ton code c'est le cas (exemple ligne 38, le for est en retrait par rapport au reste du bloc), je me suis permis de faire cette remarque

Pour revenir à ton problème, voici une solution. C'est écrit en C++, mais en C, c'est pratiquement similaire. Tu déclares tes tableaux avec des "malloc" au lieux des "new" et les "string" peuvent être changées en char* sans trop de difficulté. Ce qui est important c'est les différents algorithmes.

Pour la première question, on peut penser récursif : on cherche le prochain diviseur dont le résultat donne un nombre entier, et on rappelle la fonction sur notre nombre divisé par le diviseur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Je cherche les diviseurs de 20
*20/2 = 10, j'ajoute 2 dans ma liste et je cherche les diviseurs de 10
*10/2 = 5, j'ajoute 2 dans ma liste et je cherche les diviseurs de 5
*5/5 = 1, j'ajoute 5 dans ma liste et je m'arrête

Pour la seconde question, on compte juste, si le facteur change, on passe à la case suivante de facteur distincts.

Enfin pour la dernière question, on peut penser récursif aussi, comme pour la première question.

Petit exemple pratique :

On a Nb = 20
fd = [2 5]
exp = [2 1]

Imaginons qu'on cherche les diviseurs de 20.
On commence par 1.
Puis, on a 2 comme facteur distinct, avec comme choix d'exposants 0, 1 ou 2;

On a donc (1*2^0), (1*2^1) et (1*2^2)

Je recommence avec mon facteur distinct 5 et comme "base" : (1*2^0), (1*2^1) et (1*2^2)

Le schéma de pensée est le suivant : J'ai le diviseur créé par les facteurs précédents (ici, c'était 1), et je cherche quels diviseurs créer avec mon facteur courant (ici 2), selon les différents exposants que je possède.

Le code ci-dessous regroupe les 3 questions, en C++ (petites adaptations à faire pour le C, mais le but est que tu comprennes la méthode de raisonnement pour résoudre des problêmes différents dans le futur !)

Cdt,

Al_th

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <sstream>
 
using namespace std;
 
 
// Q1. Fonction récursive pour trouver le prochain diviseur donc la division donne un résultat entier
int findNextDiv(int nb,int* facteurs,int iteration){
    for(int i = 2; i<=nb ;i++){
        if ((nb/i)*i==nb){
            facteurs[iteration]=i;
            return findNextDiv(nb/i,facteurs,iteration+1);;
        }
    }
    return iteration;
}
 
 
// Q2. Fonction qui crée le tableau de facteurs distincs et de leurs exposants
int assignPower(int* factors, int* distinctFactors, int* exponents, int lastIndex){
    int distinctFactorsIndex = 0;
    distinctFactors[0] = factors[0];
    exponents[0] = 1;
    for(int i = 1 ; i < lastIndex ;i++){
        if(factors[i]!=distinctFactors[distinctFactorsIndex]){
            distinctFactorsIndex++;
            distinctFactors[distinctFactorsIndex]=factors[i];
            exponents[distinctFactorsIndex]=1;
        }
        else{
            exponents[distinctFactorsIndex]+=1;
        }
    }
    return distinctFactorsIndex;
}
 
// Q3. Conversion int -> string
string toString(int i){
    ostringstream oss;
    oss << i;
    return oss.str();
}
 
 
 
 
 
// Q3. Procédure récursive créant les diviseurs à partir des tableaux de facteurs distincts et d'exposants
void recursiveDiv(int index, int* distinctFactors, int* exponents, int lastDistinctIndex, int baseDiv){
    for(int i = 0 ; i <= exponents[index];i++){
        int div = baseDiv;
        for(int j = 0; j<i;j++){
            div *= distinctFactors[index];
        }
        if(index<lastDistinctIndex){
            recursiveDiv(index+1, distinctFactors,exponents,lastDistinctIndex, div);
        }
        else{
            cout << div << "\n";
        }
    }
}
 
// Q3. Procédure chapeau lancant la procédure de recherche de diviseur
void findDiv(int* distinctFactors, int* exponents, int lastDistinctIndex){
    recursiveDiv(0, distinctFactors, exponents, lastDistinctIndex, 1);
}
 
 
int main()
{
    int a;
    int* factors = new int[100];
    int* distinctFactors = new int[100];
    int* exponents = new int[100];
 
    scanf("%i",&a);
    int lastIndex =  findNextDiv(a,factors,0);
    int lastDistinctIndex = assignPower(factors, distinctFactors,exponents,lastIndex);
    findDiv(distinctFactors, exponents, lastDistinctIndex);
    return 0;
}