Algorithme factoriel avec boucle while

[invite3a7edcd7]

Bonsoir,

Je dois créer un programme en langage C qui calcul une factorielle à l'aide d'une boucle while! Quelqu'un peut-il m'aider car je me prends la tête dessus depuis 3heures !!
Help!
-----

[Towl]

Peux tu donner ce que tu as déjà obtenu et on t'orientera en fonction, ca fera un peu moins "faites moi mon exo" (meme si ce n'est pas le cas)

[invite3a7edcd7]

#include<stdio.h>
int factoriel(int n);
main(){
int n,;
printf("Entrez une valeur pour n:\n");
scanf("%d", &n);
printf("%d factoriel = %d\n",n,factoriel(n));
return 0;}

int factoriel(int n){
int i,x;
i=1;
while (i<=n){
x=i*++i;
return x;}}

Mon problème se situe au niveau de la couleur rouge, j'ai essayé beaucoup de combinaison possible pour le résultat (appelé "x") mais je ne trouve pas! ++i est l'incrémentation de i.

[le fatumbi]

bhen le souci me semble etre exactement à l'avant-dernier "}"
tu sors trop tot, return est dans le while.. indente un peu, ce sera plus clair (avec encore un peu de bug, mais clair).

[A voir en vidéo sur Futura]

[invitec94d2bbe]

Bonsoir à tous,

je pose :
x = 1 et i qui décrit de 1 à n!

formule : x = x * i
x = 1 pour i = 1 résultat 1 * 1 = 1
x = 1(du résultat) i = 2 1 * 2 = 2
x = 2(du résultat) i = 3 2 * 3 = 6
x = 6 (idem) i = 4 6 * 4 = 24

çà à l'air correct ....

me trompe je ?

[invite765732342432]

int factoriel(int n){
int i,x;
i=1;
while (i<=n){
x=i*++i;
return x;}}

1 ) ton return est à l'intérieur de la boucle while => dès la première itération, la fonction se termine.
2 ) x = i*++i => c'est du code particulièrement complexe pour quelqu'un qui n'arrive pas à coder une factorielle
Il vaut mieux ne pas jouer avec ++i tant qu'on ne maitrise pas le langage (de toute façon, ça ne sert pas à grand chose.
un indice: dans la partie de droite, si tu n'as que des "i", ça ne sert à rien d'avoir une boucle...

[invitec94d2bbe]

re bj,

la mise en page ayant sautée

je pose :
x = 1 et i qui décrit de 1 à n!

formule : x = x * i
x = 1 ---------------------------->pour i = 1----------> résultat 1 * 1 = 1
x = 1(du résultat)------------------> i = 2----------------------> 1 * 2 = 2
x = 2(du résultat)------------------> i = 3----------------------> 2 * 3 = 6
x = 6 (idem)-------------------------> i = 4----------------------> 6 * 4 = 24

[Towl]

Comme dis plus haut tu as mal placer ton accolade de while, tu sors trop tot de ta fonction (dès la premiere itération)
De plus tu calcul mal ton x (tu ne sauvegardes jamais sa valeur)
:

int factoriel(int n)
{
	int i,x;
	i=1;
	while (i<=n)
	{
//		x=i*++i;
		x *=++i;
//		return x;
	}
	return x;
}

Sinon, comme dis au dessus aussi, coder avec des ++i etc n'apporte rien au niveau rapidité (un bon compilateur saura ce qu'il faut faire et comment l'optimiser). Et puis, mettre ca (tentative d'optimisation) avec une variable qui ne sert à rien (n) ca fait bizarre je trouve

La version plus 'je veux tout optimiser' :

int factoriel(int n)
{
	int x=1;
	do
	{
		x *= n--;
	}while (n > 1);
	return x;
}

[invite3a7edcd7]

Comment traduire le faire que i aille de 1 à n! ??
Et malgré le fait qu'il n'y ait que des i à droite je ne sais pas comment rendre compte du factoriel sans passer par une incrémentation...?
n!=(n-3)(n-2)(n-1)n il faudrait une décrémentation alors?
Je ne suis vraiment pas doué =(...

[invite3a7edcd7]

La première programmation ne marche pas chez moi =$... Mais la version optimisée marche même si je n'y comprends pas grand chose !! A quoi correspond le x *?
Et les // permettent de garder en mémoire la valeur de x c'est ça?

[Towl]

L'idée, c'est de découper au maximum ton code et ton raisonnement :
Tu souhaites que i aille de 1 à n ---> comme tu l'as dit, while (i <= n)
Ensuite, il faut décomposer ton algo : le but c'est de ce dire : je suis à l'etat N, quel resultat dois je obtenir à l'état N + 1 --> comment y arriver

Un peu de blabla pour expliciter :
- return quitte la fonction (et non pas la boucle)
- l'initialisation des variables est très importante en C (et partout en fait)

int factoriel(int n)
{
	// initialisation
	int x=1; 
	int i=1;
	// Pour i de 1 à n
	while (i <= n)
	{
		// Passage de l'état N à l'état N + 1
		x = x * i;
		// On passe à l'etat suivant
		i = i + 1;
	} // Fin de la boucle, on a donc finit de calculer
	// On quitte la focntion en renvoyant notre resultat
	return x;
}

Oui la premiere version il manque l'initialisation
Quand au x*= i, c'est une autre forme d'ecriture abrégée (x = x * i), tout aussi moche que ++i (bien que peut avoir un interet sur des ecritures courtes, pour la relecture facile). Le C regorce de truc bizarre comme ca

Et les // c'est des commentaires

[invite3a7edcd7]

Merci beaucoup! C'est vraiment plus clair maintenant, je pourrai allé en TD en ayant compris quelque chose !
Merci encore , bonne soirée à tous!

[le fatumbi]

vi, j'aime bien la dernière version.
Bien lisible, puis j'aime pas toucher directement aux paramètres, même passés par valeur.

Et rapelle-toi du domaine de définition de la fonction: N
fact(-1) est indéfini.

et aussi que fact(0)=0

Limite, le ++i dans la condition while, pour bien montrer ce qui évolue et donc qu'on en sort un jour.

d'ou à peu près:

int factorielle(int n){
  int i,x;
   
  if (n<0) return -1; // erreur: n devrait etre un naturel
  if (n==0) return 1; // par definition, fact(0) vaut 1 et non 0

  // calcul donc pour n Naturel non nul.

  x=n; // resultat, donc multiple de n
  i=n; // copie evolutive de n (j'aime pas bosser en touchant aux paramètres...)

  while (--i>1){
    x=x*i; 
    // voir aussi à traiter le depassement
    // je ne me suis jamais intéressé aux 
    // mécanismes d'exception en C
  }
  return x;
}

[Towl]

Le mécanisme des exceptions est inexistant en C, ce qui résout le problème
Donc dans ce cas, il va nous faire un joli petit modulo.

Et la ca peut devenir délicat à gérer, car sur certaines architecture, on peut avoir fact(x) < fact(x+1) alors que l'on à eut l'effet modulo :

def check(x, y):
	for i in [8, 16, 32, 64, 128]:
		if x < 2**i and y > 2**i and x > y % (2**i):
			print 'Non compatible %d bits' % i
			return False
	return True


def fact(n):
	x = 1
	i = 1
	while i <= n:
		check(x, x*i)
		x *= i
		i += 1
	return x

Cela me donne :

>> fact(40)
Non compatible 16 bits
Non compatible 128 bits
815915283247897734345611269596 115894272000000000L

Bon après, la proba de tomber sur une architecture 16 bits ou 128bits est assez faible, je l'avoue

[Towl]

Tiens marrant en déroulant l'algo dans l'autre sens ( en décrémentant plutot qu'en incrémentant) on obtient pas du tout le même type de résultat :

>>fact(40)
Non compatible 8 bits
Non compatible 16 bits
Non compatible 64 bits
Non compatible 128 bits
815915283247897734345611269596 115894272000000000L

Y a pas a dire, le C est vraiment développeur friendly

[danyvio]

Je vais jouer les rabat-joie : pourquoi n'utilisez-vous pas la récursivité dans des fonctions comme factorielle ?

Syntaxe très approximative, à compléter, corriger conformément au langage C :

n est initialisé à 1 avant l'appel

fonction factorielle(i,n)

si (i == 1)
return (n)
sinon
n:=i*factorielle(i-1,n)
finsi

[invite765732342432]

Je vais jouer les rabat-joie : pourquoi n'utilisez-vous pas la récursivité dans des fonctions comme factorielle ?

Parce que la question demandait l'utilisation d'une boucle while

fonction factorielle(i,n)
si (i == 1)
return (n)
sinon
n:=i*factorielle(i-1,n)
finsi

Euh... c'est bizarre comme algo... pourquoi deux paramètres ?
Plus concis (et marchant pour 0, pas pour les nombres négatifs)

fonction factorielle(n) {
   si (n == 0) return 1;
      return n*factorielle(n-1);
   finsi
}

Enfin, si je ne dis pas de bétise...

[invite765732342432]

Enfin, si je ne dis pas de bétise...

J'en ai dit une: le "finsi" doit être une ligne au dessus.
Désolé.

[polo974]

...
int factoriel(int n){
int i,x;
i=1;
while (i<=n){
x=i*++i;
return x;}}
...

1) x n'est pas initialisé, ce qui peut être dommage => x=1; avec le i=1;
2) x=i*++i; doit être i++; x = x * i; (la pré-incrémentation de i est possible, mais bof)
3) le return après la boucle; c'est mieux
soit:

int factoriel(int n){
int x, i;
x=1; i=1;
while(i<n)
{
     i++;
     x*=i;
}
return x;
}

sinon:
le for(...;...;...) est plus adapté, vu qu'il inclus l'init, le test et l'incrément

 int factoriel(int n){
int x;
for(x=1;n;n--)
    x*=n;
return x;
}

Et pour les fanas de la récursivité, franchement pour de si petites tâches, c'est bien perdre son temps à encombrer la pile pour rien, juste pour le fun...

[invite22bcdbbf]

Bonsoir,

Je dois créer un programme en langage C qui calcul une factorielle à l'aide d'une boucle while! Quelqu'un peut-il m'aider car je me prends la tête dessus depuis 3heures !!
Help!

Voici un lien avec quelques exemples de l'algorithme de factoriel par méthode récursive ou par boucle While ou For:

#############

[invite22bcdbbf]

1) x n'est pas initialisé, ce qui peut être dommage => x=1; avec le i=1;
2) x=i*++i; doit être i++; x = x * i; (la pré-incrémentation de i est possible, mais bof)
3) le return après la boucle; c'est mieux
soit:

int factoriel(int n){
int x, i;
x=1; i=1;
while(i<n)
{
     i++;
     x*=i;
}
return x;
}

sinon:
le for(...;...;...) est plus adapté, vu qu'il inclus l'init, le test et l'incrément

 int factoriel(int n){
int x;
for(x=1;n;n--)
    x*=n;
return x;
}

Et pour les fanas de la récursivité, franchement pour de si petites tâches, c'est bien perdre son temps à encombrer la pile pour rien, juste pour le fun...

Voici un lien avec quelques exemples de l'algorithme de factoriel par méthode récursive ou par boucle While ou For:

################

[invite22bcdbbf]

Bonsoir,

Je dois créer un programme en langage C qui calcul une factorielle à l'aide d'une boucle while! Quelqu'un peut-il m'aider car je me prends la tête dessus depuis 3heures !!
Help!

public static double factoBoucleWhile(double n)

        {

            double res = 1;

            while (n > 1) res *= n--;

            return res;

        }

Il y a d'autres exemples sur:

###############

[invite22bcdbbf]

Bonsoir,

Je dois créer un programme en langage C qui calcul une factorielle à l'aide d'une boucle while! Quelqu'un peut-il m'aider car je me prends la tête dessus depuis 3heures !!
Help!

Fonction factoriel(n)
{
resultat = 1;

tant que n > 1 alors

resultat *=n--;

fin de tant que

retourne n;
}

public static double factoBoucleWhile(double n)

{

double res = 1;

while (n > 1) res *= n--;

return res;

}

Il y a d'autres exemples sur:
##############
Il n'est nul besoin de préciser l'adresse de ton site à chaque message, je te conseille de la mettre dans ton profil.

yoda1234.

[sitalgo]

B'jour,

le for(...;...;...) est plus adapté, vu qu'il inclus l'init, le test et l'incrément

Et pour les fanas de la récursivité, franchement pour de si petites tâches, c'est bien perdre son temps à encombrer la pile pour rien, juste pour le fun...

D'autant que, ayant testé avec du basic compilé mais pas en C, le for est le moyen le plus rapide pour faire des boucles et la récursuvité le moyen le plus lent. Du temps des 8 MHz ça comptait.

[polo974]

oh le beau déterrage
4 messages d'affilée du même auteur...

[invite19415392]

B'jour,

D'autant que, ayant testé avec du basic compilé mais pas en C, le for est le moyen le plus rapide pour faire des boucles et la récursuvité le moyen le plus lent. Du temps des 8 MHz ça comptait.

Faire de la récursivité quand on peut mettre simplement sous la forme d'une boucle, c'est une habitude de matheux ^^ C'est vite écrit, c'est joli, mais c'est pas performant.

[inviteba9bce0d]

En règle générale, le for est plus lent que le while.

[whoami]

Bonjour,

En règle générale, le for est plus lent que le while.

Je ne pense pas qu'on puisse généraliser comme ça, et encore moins avec les compilateurs modernes, qui sont souvent très forts pour optimiser (et une boucle for est plus simple à optimiser ).

[inviteba9bce0d]

Bonjour,

Je ne pense pas qu'on puisse généraliser comme ça, et encore moins avec les compilateurs modernes, qui sont souvent très forts pour optimiser (et une boucle for est plus simple à optimiser ).

C'est ce que j'avais lu. Après tu as surement raison, je ne connais pas encore les principe de compilation ni l'asm ^^

[whoami]

Bonjour,

C'est ce que j'avais lu. Après tu as surement raison, je ne connais pas encore les principe de compilation ni l'asm ^^

En fait, c'est extrêmement dépendant du langage, et, pour un même langage, du compilateur (ou interpréteur) utilisé, et pour un même compilateur, des options choisies, de la qualité du code source, etc.

Il n'est donc pas question de pouvoir généraliser ce genre d'affirmation, qui ne peut concerner qu'une configuration précise.