problème exercice algorithmique

Version imprimable

14/02/2009, 14h53
chicabonux

problème exercice algorithmique
Bonjour

ça fait quelque moments que je bute sur ce problème et je me décide à venir vous poser la question

Je dois convertir un algorithme en programme C pour la décomposition d'un nombre entier en facteurs premiers
J'ai l'algorithme mais je comprends pas bien

ça me dit:
Code:

1 2 3 4 5 6 7 k<___3 tant que n=1 si (n modulo k = 0) alors k<- -k+2 sinon debut ecrire k n<___n/k
avec n et k 2 entiers

Je comprends pas la signification de ce passage ?
14/02/2009, 15h02
ram-0000

tu as sûr de ce que tu nous a donné parce que moi aussi, je sèche.
J'ai l'impression que n est le nombre à décomposer mais j'ai l'impression que cet algorithme est incapable de décomposer 8 car le diviseur commence à 3
14/02/2009, 15h07
chicabonux

Tu veux l'algo complet ?
14/02/2009, 15h14
ram-0000

Citation:

Envoyé par chicabonux

Tu veux l'algo complet ?

ben oui, cela m'évitera de chercher ma boule de cristal, je l'ai oubliée au boulot :P

(tu pourras me la prêter ta boule de cristal stp ? )

Code:

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
/*
entier n
entier k
 
début
  écrire << Décomposition d'un nombre en facteurs premiers>>
  écrire<< Introduire un nombre>0>>
  lire n
  tant que n>0 faire
  début
          écrire<<Facteurs premiers>>
          tant n modulo 2=0 faire
          début
                 écrire <<2>>
                 n<---n/2
          fin
           k<___3
           tant que n=1 
           si(n modulo k =0) alors k<- -k+2
           sinon
           début
                 écrire k
                 n<___n/k
           fin    
           écrire<<Introduire un nombre>0>>
           lire n
   fin
fin
*/

C'est plus facile quant on a tout

La première partie:

Code:

1
2
3
4
5
          tant n modulo 2=0 faire
          début
                 écrire <<2>>
                 n<---n/2
          fin

gère les facteurs 2
ensuite la partie suivante gère les facteurs impairs par contre, elle est bizarre:

Code:

1
2
3
4
5
6
7
           tant que n=1 
           si(n modulo k =0) alors k<- -k+2
           sinon
           début
                 écrire k
                 n<___n/k
           fin

J'écrirai plutôt :

Code:

1
2
3
4
5
6
7
           tant que n <> 1 
           si(n modulo k <> 0) alors k<- -k+2
           sinon
           début
                 écrire k
                 n<___n/k
           fin

Tu pourrais me montrer le programme que tu pourrais faire avec cet algo ?

Je te montre celui que j'ai voulu faire mais qui ne fonctionne pas avec visual

Code:

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
#include<stdio.h>
 
int main (void)
{
long n,k;
 
printf("Decomposition d'un nombre entier en facteurs premiers\n");
printf("introduire un nombre>0:\n");
scanf("%ld",&n);
 
while(n>0)
{
	printf("Facteurs premiers");
	while(0=n%2)
	{
 
	printf("ecrire 2\n");
	n=n/2;
	}
 
	long k=3;
	while(n=1)
	{
		if(0=n%k)
			k=-k+2;
		else
		{
			printf("ecrire k\n");
			n=n/k;
		}
	}
}

14/02/2009, 17h47
ram-0000
les tests en C, c'est avec ==
Code:

1 2 while(n == 1) if(0 == n%k)
19/02/2009, 18h20
chicabonux

J'ai changé pour les tests et ça fonctionne bien merci

par contre il me met un warning à la compilation sur le premier scanf et me met une erreur de syntaxe sur la ligne 21 en me disant "absence de ';' avant 'type' "

Je comprends pas pourquoi à nouveau ?
19/02/2009, 18h55
ram-0000

Le nouveau code s'il te plait et le message de warning complet

excuse moi encore pour mes imprécisions mais j'ai vraiment beaucoup de mal avec le langage et j'ai vraiment l'impression de patauger

le code:
Code:

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 #include<stdio.h> int main () { long n=0,k; printf("Decomposition d'un nombre entier en facteurs premiers\n"); printf("introduire un nombre>0:"); scanf("%d",&n); while(n>0) { printf("Facteurs premiers"); while(0==n%2) { printf("ecrire 2\n"); n=n/2; } long k=3; while(n==1) { if(0==n%k) k=-k+2; else { printf("ecrire k\n"); n=n/k; } } } return 0; }
les messages d'erreurs:

Avertissement 1 warning C4996: 'scanf' a été déclaré désapprouvé c:\documents and settings\yannick\mes documents\visual studio 2005\projects\devoir1\devoir1\main.c 9

Erreur 2 error C2143: erreur de syntaxe*: absence de ';' avant 'type' c:\documents and settings\yannick\mes documents\visual studio 2005\projects\devoir1\devoir1\main.c 21

19/02/2009, 20h40
ram-0000

En fait, tu as 2 choses,

la 1ere, c'est un warning au sujet de scanf qui est désapprouvé. Probablement que Microsoft juge que la fonction n'est pas assez sûre. I; préférerait que tu utilises autre chose que scanf mais ce n'est qu'un warning, donc laisse tomber pour l'instant (il faudra y revenir quand même plus tard)

Le 2eme est lié à la définition "long k=3;". Tu n'a pas le droit en C de définir une variable au milieu d'un bloc d'instructions. il faut remonter "long k;" avec les autres variables locales à ta fonction (en plus, je viens de voir que c'est déjà fait) et ensuite, tu peux faire "k = 3;"
20/02/2009, 09h32
Médinoc
Bonjour,
Pour compléter ce que dit ram-0000:
- Tu devrais installer le SP1 de Visual, si c'est possible. Ça ne supprimera pas directement le Warning, mais ça le modifiera légèrement et surtout, ça modifie la commande nécessaire pour le désactiver. Les versions récentes de Visual utilisent la même commande que le SP1, la commande d'avant étant désormais obsolète.
  - La nouvelle commande consiste à définie _CRT_SECURE_NO_WARNINGS pour ta compilation, soit au début du fichier source (avec #define), soit dans les options du projet, section préprocesseur.
  - L'utilisation que tu fais de scanf() ne présente aucun problème de sécurité. Les avertissements de Microsoft concernent l'utilisation de scanf() pour la saisie de chaînes de caractères. Et surtout, l'alternative proposée est non-standard.
- La déclaration une variable en milieu de bloc est interdite par les normes C89 et C90 du langage C, mais la nouvelle norme C99 l'autorise. Par contre, elle nécessite un compilateur qui supporte cette norme (à savoir: pas Visual Studio) et le choix de cette norme dans les options dudit compilo.

Je le télécharge où le SP1 de Visual ?

Par contre pour en revenir au programme j'ai effectué les modifications mais là le programme ne s'arrête plus et ne donne aucun résultat.En fait il tourne en boucle
Code:

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 #include<stdio.h> int main () { long n=0,k; printf("Decomposition d'un nombre entier en facteurs premiers\n"); printf("introduire un nombre>0:"); scanf("%d",&n); while(n>0) { printf("Facteurs premiers"); while(0==n%2) { printf("ecrire 2\n"); n=n/2; } } k=3; while(n==1) { if(0==n%k) k=-k+2; else { printf("ecrire k\n"); n=n/k; } } system("PAUSE"); return 0; }

21/02/2009, 10h04
ram-0000

Citation:

Envoyé par chicabonux

Je le télécharge où le SP1 de Visual ?

:google:
ici http://msdn.microsoft.com/fr-fr/vstudio/bb265237.aspx
ou
ici http://www.microsoft.com/downloads/d...displaylang=fr
suivant la version que tu as
21/02/2009, 10h54
chicabonux

Merci je suis en train de le télécharger :yaisse2:

Et sinon pour le programme ?
21/02/2009, 11h40
Médinoc

Le problème, c'est que je ne pige pas l'algo...
21/02/2009, 11h46
chicabonux

ben je crois que c'est mon problème aussi

C'est une question sur un devoir sur le langage C pour educatel

Je crois que je vais finir par demander des explications au prof :(

Tu aurais une idée d'algo sinon pour la décomposition en facteurs premiers ?
21/02/2009, 11h54
ram-0000

Si on reprend ton algo (et uniquement lui, j'ai pas regardé le code), cela prend un nombre, cela le divise par 2 tant qu'il est divisible par 2 et cela affiche les facteurs 2.

Quand il n'est plus divisible par 2, cela tente de diviser par 3 puis par 5 puis par les autres nombres impair tant que le reste n'est pas 0.

Ceci dit, ce n'est pas très optimisé puisque cela va tenter de diviser par 9 et par 15 (et d'autres nombres impais mais non premiers) alors que c'est inutile, les facteur 3 et 5 ont été déjà testés.

Autre chose, il n'est pas utile de tester plus loins que la racine carée du nombre. Un nombre quelconque n'a pas de facteurs premiers plus grands que sa racine.
21/02/2009, 12h14
chicabonux

ok

Mais tu peux m'expliquer sinon purquoi mon programme ne fonctionne pas ?

Il me semble qu'avec ce programme ça fonctionne bien

Code:

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
#include<stdio.h>
 
int main (int argc,char *argv[])
{
int n,k;
 
	printf("Facteurs premiers\n");
	printf("Introduire un nombre entier >1:  ");
	scanf("%d",&n);
	while(0==n%2)
	{
 
	printf("2 ");
	n=n/2;
	}
 
 
	 k=3;
	while(n!=2)
	{
		if(0!=n%k)
		{
			k=k+2;
		}
		else
		{
			printf("%d ",k);
			n=n/k;
		}
	}
 
			printf("\n");
 
 
system("PAUSE");
return 0;
}

Nouvelle question sur un programme calculant la factorielle d'un nombre .
Pourquoi j'obtiens une valeur négative avec 100 ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include<stdio.h> /* la fonction*/ double fact(double x) { return(x>1)?(x*fact(x-1)):1; } /*la fonction appelante*/ int main() { double x; printf("Introduire x:"); scanf("%f",&x); printf("la factorielle de %f est %f\n",x,fact(x)); system("pause"); return 0; }

23/02/2009, 17h58
diogene

ram-0000 :

Citation:

Un nombre quelconque n'a pas de facteurs premiers plus grands que sa racine

????
6 = 2x3 et 3 > Racine(6)
23/02/2009, 18h32
ram-0000

Citation:

Envoyé par ram-0000

Autre chose, il n'est pas utile de tester plus loins que la racine carée du nombre. Un nombre quelconque n'a pas de facteurs premiers plus grands que sa racine.

Citation:

Envoyé par diogene

ram-0000 : ????
6 = 2x3 et 3 > Racine(6)

Heu oui, là, j'ai honte :oops:, c'est très mal dit.

Extrait de wiki : Soit un entier composé à factoriser, les essais de divisions consistent à essayer de diviser ce nombre par chaque nombre premier inférieur ou égal à la racine de ce nombre.
23/02/2009, 18h36
chicabonux

et en ce qui concerne le programme sur la factorielle ?
24/02/2009, 15h09
3DArchi

Citation:

Envoyé par chicabonux

et en ce qui concerne le programme sur la factorielle ?

C'est quoi fact(3.14) ?
Ou en d'autres termes, pourquoi utiliser un double ? ;)

[edit] : autre question : %f c'est pourquoi déjà :fessee:

[edit 2] : tu n'as pas un debugger avec visual :?? T'as essayé de voir quelle était la valeur prise par ta variable après la saisie ?

J'ai modifié mon code

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
 
/* la fonction*/
unsigned long fact(unsigned long x)
{
	return(x>1)?(x*fact(x-1)):1;
}
 
/*la fonction appelante*/
 
int main()
{
unsigned long x;
 
	printf("Introduire x:");
	scanf("%lu",&x);
 
	printf("la factorielle de %lu est %lu\n",x,fact(x));
system("pause");
return 0;
}

quand je veux connnaître la factorielle de 100 ça me donne 0
Comment ça se fait ?

25/02/2009, 15h12
diogene

Le résultat de 100! ne tient pas, et de beaucoup s'en faut, dans un unsigned long
25/02/2009, 15h17
3DArchi

Au delà, as-tu compris pourquoi ta première version ne fonctionnait pas (pour apprendre le langage, il faut aussi comprendre les erreurs, le codage n'est pas de la 'pensée magique')
25/02/2009, 15h21
chicabonux

J'ai changé le type de la fonction en double et là effectivement ça fonctionne

Pour répondre à 3Darchi je crois que j'ai des soucis avec la ddésignation des types et ça doit être là mon problème principal :(:(:(:(
25/02/2009, 15h34
diogene

Lors d'un scanf, il est IMPERATIF que le format corresponde à l'argument correspondant.
Celui-ci n'est qu'une adresse et le format indique comment (et sur combien de bytes) scanf doit écrire le résultat. Il ne peut y avoir de conversion implicite d'un type à l'autre.

Pour un double, la lettre de format est celle d'un float précédée de l (el) (comme signifiant long float) :
Si on veut lire un double, le format est %lf, %f est utilisé pour un float.

Si mes souvenirs mathématiques ne sont pas trop lointains, factoriel n'est défini que pour des entiers (positifs?) et pas pour autre chose. Donc ta fonction doit prendre en paramètre un entier et retourner un entier.
Maintenant, quels sont les choix en C pour un entier (respectivement positif) :
-> char ou unsigned char
-> short ou unsigned short
-> int ou unsigned int
-> long ou unsigned long
-> (non standard, je crois) : long long et unsigned long long

float et double permettent de représenter des nombres 'réels'.
Donc ta fonction ne peut pas prendre float ou double comme argument !

Après comment choisir entre les autres. Ben, la seule chose que te garantie la norme est que chacun des types que j'ai mentionné ci-dessus représente au moins autant que celui qui le précède ( Au moins autant, ne veut pas forcément dire plus). Ensuite si tu veux calculer factoriel pour des nombres plus grand que puissent en contenir un unsigned long long (ou un unsigned long), alors il te faut construire toi même une représentation d'entiers plus grands (ou d'utiliser une bibliothèque qui le fait).
Utiliser un double pour pouvoir accéder à de plus grandes représentations est une erreur de conception au regard des spécifications de factoriel.

Après, pourquoi ton exemple précédent ne fonctionnait pas :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include<stdio.h> /* la fonction*/ double fact(double x) { return(x>1)?(x*fact(x-1)):1; } /*la fonction appelante*/ int main() { double x; printf("Introduire x:"); scanf("%f",&x); printf("la factorielle de %f est %f\n",x,fact(x)); system("pause"); return 0; }
x est double et tu fais scanf("%f",&x); Or %f c'est pour les float. Donc tu essais de mettre un float dans un double -> ça ne marche pas. Il faut que tu dises à scanf que tu veux un double et pas un float.

ok va falloir que je sois plus rigoureux dans la désignation de mes variables alors :?

J'ai un autre soucis avec un nouvel exercice
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include<stdio.h> #include<conio.h> main () { double x,y,delta; printf("Introduire x="); scanf("%lf",&x); y=(2*x*x+(2*(3/4)*x-2))/5-1; printf("le resultat est %lf\n",y); puts("pour continuer frapper une touche..."); getch(); }
Quand je veux vérifier ce programme manuellement:

pour une valeur de x=4 je trouve manuellement 5.80 et avec le programme 4.60 ?
Et il y a une différence avec toutes les valeurs que j'ai essayées.

Je fais encore une erreur de désignation de variable ?

25/02/2009, 15h47
3DArchi

:faq:
(par exemple, ici)
25/02/2009, 15h52
chicabonux

Citation:

# Si au moins l'une des deux opérandes est de type flottant (float, double, long double) alors la division effectuée sera réelle, donnant un résultat décimal.
# Le type du résultat de la division est celui de l'opérande réelle (si au moins l'une des deux l'est) possédant la plus grande capacité.

eh bien ?

Je ne comprends pas ?
J'ai bien désigné mes variables comme étant des réels ? ça ne devrait pas poser de problème quant au résultat ?

Essaies ça :

Code:

1
2
3
4
5
6
7
8
9
 
y=(2*x*x+(2*(3/4)*x-2))/5-1;
printf("2*x*x = %lf\n",2*x*x);
printf("2*(3/4)*x-2 = %lf\n",2*(3/4)*x-2);
printf("1+2 = %lf\n",(2*x*x+(2*(3/4)*x-2)));
printf("/5 = %lf\n",(2*x*x+(2*(3/4)*x-2))/5);
printf("-1 = %lf\n",(2*x*x+(2*(3/4)*x-2))/5-1);
 
printf("le resultat est %lf\n",y);

(Perso, je ne trouve ni 5.8 ni 4.6 avec x=4)

25/02/2009, 16h24
chicabonux

Citation:

printf("2*(3/4)*x-2 = %lf\n",2*(3/4)*x-2);

c'est cette ligne là que je trouve erronée
Pour x=1 ça me donne 2*3/4*1-2 ce qui fait 3/2-2 =>-1/2 ?

alors que dans le programme ça me donne -2 comme résultat ?

Je fais une erreur de calcul quelque part ?
25/02/2009, 16h55
3DArchi

2*(3/4) = 0 :mrgreen:
2*(3./4.) = 1.5
En fait, prend l'habitude de toujours préciser le type réel pour tes constantes sans rien présumer de ce que peut faire le compilateur de ton expression.