Pb d'algorithmie simple [Résolu/Fermé]

Signaler
Messages postés
3
Date d'inscription
mercredi 12 mars 2008
Statut
Membre
Dernière intervention
12 mars 2008
-
 greg -
Bonjour à tous voilà j'ai un petit problème d'algo à résoudre mais je n'y arrive vraiment pas.
J'ai une idée de comment il faut partir mais après...

voici l'énoncé

Nous allons considérer le problème suivant : de combien de manière diérente peut on obtenir une
somme d'argent donnée avec des pièces de 2.00, 1.00, 0.50, 0.20, 0.10 et 0.05. Ce problème admet une
solution récursive dénie par la relation suivante :

Nb de manières d'obtenir une somme S avec n types de pièce
=
Nb de manières d'obtenir S avec n − 1 types de pièce (on enlève le dernier type de pièce)
+
Nb de manières d'obtenir S − v avec n types de pièce, où v est la valeur du dernier type de pièce


Il faut créer une fonction avec 2 paramètres, un qui contient le nombre à décomposer, et un qui contient le nombre de pièces différentes...

Il faut à mon avis aussi créer une autre fonction ou procédure qui affecte à chaque valeur de pièce un numéro pour pouvoir le manipuler...

MERCI de votre aide, j'ai eu mon premier cours d'algo y a 4 semaines, et hier on a commencé la récursivité et j'arrive pas à faire ça. Si une bonne âme voudrait bien me faire une esquisse de la solution, voire carrément la solution entière...

4 réponses

Messages postés
3
Date d'inscription
mercredi 12 mars 2008
Statut
Membre
Dernière intervention
12 mars 2008

Tiens pour ceux qui auront la bonté de m'aider je pense avoir trouvé une bonne piste :


Je veux calculer le nombre de façons de faire un total de N centimes étant donné le nombre de types de pièces qui existent (n) et le nombre que je possède et la valeur en centimes de chaque type (tableaux Nombre et Valeur indicés de 1 à n.)

Calcul de NBFac(Tot,i) le nombre de façons de faire un total de Tot centimes en n'utilisant que les pièces des i premiers types:

t:=0; // sera le nombre souhaite
u:=0; // le nombre de pieces de type i utilisees
repeter
t:=t+NBFac[Tot-u*Valeur[i],i-1];
u:=u+1;
jusqu'a u>Nombre[i] ou u*Valeur[i]>Tot
finrepeter;

sauf les cas i=0 (NBFac[Tot,0]=1 ou 0 selon si Tot=0)


Je pense que c'est ça qu'il faut faire mais maintenant je ne sais pas comment faire le tableaux Nombre et Valeur indicés de 1 à n
TEST de réponse ...
Bonsoir Hellzebuth,
comme je peux répondre sans être membre, je te répond.

Voici le squelette de la fonction que tu recherches.

Déjà il faut avoir un tableau global avec le montant de toutes les pièces (en centimes par exemple)
tab_valeur[1]=5
tab_valeur[2]=10
tab_valeur[3]=20 etc ....


fonction NBFAC(montant, nb_type) retourne le nombre {

/* première chose en récursivité, les critères d'arrêt, j'en vois trois pour simplifier le reste */
si (nb_type <= 0) retourne 0;
si (montant < tab_valeur[nb_type] ) retourne 0; /* car impossible */
si (montant == tab_valeur[nb_type]) retourne 1; /* un seul cas possible */

/* deuxième chose, la récursivité proprement dite */
retourne NBFAC(montant - tab_valeur[nb_type], nb_type) + NBFAC(montant, nb_type - 1);

} /* fin de la fonction */



C'est peut-être pas top mais je pense que ça doit fonctioner, à tester.
Bonne chance.
Messages postés
3
Date d'inscription
mercredi 12 mars 2008
Statut
Membre
Dernière intervention
12 mars 2008

Merci beaucoup greg pour ton aide ! J'avais déjà trouvé des trucs qui ressemblaient, mais maintenant j'ai des critères d'arrêts clairs et je suis sur que c'est ça, merci encore d'avoir pris la peine de m'aider.
Salut,
Jaimerais écrire un algorithme qui affiche et calcul la somme des 10000 premiers nombres paires et impaires.
La somme des N premiers nombre pairs et impaires et donné par cette simple formule : N (N+1) / 2

Par exemple les nombre de 1 à 10 : (10 x 11) / 2 = 55 = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

Pour les 10000 premiers, pas besoin de programme, de tête : 50005000

CQFD
slt tout le monde .voila j'ai un probléme concernant cet exercice surtout la3eme question .sasré vraiment sympas si vous pouvé m'aidé marci.
l'enoncé de l'exo:
un employé est décrit par son nom (25 cractéres ) age(entier) sexe (M\F) et le nombres d'heure assuréespar jour sam,dim;lun;mar,merc,jeu,vend)
1.ecrire un sous programme permettant de saisir un nombre n d'enregistrement employés.
2.ecrire un sous programme permettant de de calculer un salaire hebdomadaire d'un employé dant le nom et prénom sont données par l'utilisateur salaire (1 heure =150 Da)
3.utiliser les deux sous programme pour ecrire un algorithme qui offre un petit menu qui pemet le choix ente 3 actions:
a. saisie d'enregistrement.
b.calcul du salaire hebdomadaire d'un employés.
c.quitter.