Inscription / Connexion Nouveau Sujet
Probleme algorithme coloriage carré
Bonjour,
On effectue un coloriage en plusieurs étapes d'un carré de côté de longueur 2 cm
Première étape du coloriage, on partage ce carré en quatre carrés de même aire et on colorie le carré situé en bas à gauche comme indiqué sur la figure ci dessous.
Deuxième étape, on partage chaque carré non encore colorié en quatre carrés de même aire et on colorie dans chacun, le carré situé en bas à gauche.
On poursuit les étapes du coloriage suivant le même procédé
Il faut que j'écrive un algorithme permettant le calcul de l'aire (exprimée en cm2) après n coloriages.
Pouvez vous m'aider, je suis nulle en algorithme ......
Bonjour,
Avant d'écrire un algorithme on étudie (mathématiquement) tout ce qu'on peut étudier.
donc déja : peux tu définir une suite Sn, par récurence, avec S0 = 0, S1 = 1/4 etc qui te donne la surface peinte à l'étape n ?
de toute façon tu auras besoin de cette suite (de sa définition : valeur de départ et formule de récurrence) pour écrire l'algorithme, dont le coeur est bien cette formule
Sn+1 = fonction de Sn et de n éventuellement
si pas d'idée à priori sur cette relation, on peut toujours
1) calculer les premiers termes
2) conjecturer (deviner)
3) démontrer (par récurrence) cette conjecture.
une formule explicite de Sn en fonction de n seul n'est pas nécessaire, mais la formule de récurrence si...
Oui, ça c'est la deuxième étape.
Une fois que tu as défini mathématiquement le problème et seulement alors, tu commences à écrire des choses
commencer directement par écrire quoi que ce soit d'un bout de morceau d'algorithme est une pure perte de temps !!
as tu clairement défini cette suite Sn dont j'ai parlé ???
non !
alors ne mets pas la charrue avant les boeufs !
Au départ rien n'est colorié S0 = 0
à la première étape on colorie 1/4 : S1 = 1/4
à la seconde on colorie en plus le quart de ce qui reste, on a donc colorié en tout 1/4 + (1/4)(3/4) = 7/16, S2 = 7/16
sur ta figure tu as bien 4 + 3 = 7 carreaux colorés sur les 16 en tout indiqués.
Il suffit de poursuivre ce raisonnement pour définir parfaitement notre suite Sn :
à chaque étape on colorie en plus le quart de ce qui reste
la surface coloriée est donc : Sn+1 = Sn + (1/4)(1 - Sn)
on peut laisser comme ça, ou simplifier en : Sn+1 = (3/4)Sn + 1/4
voila pour l'analyse mathématique.
Maintenant on peut effectivement passer à la partie "écriture d'un algorithme" ...
On va avoir besoin de variables
S et n me semblent un bon début : S = l'aire coloriée, à l'étape n
au départ S0 = 0, donc la valeur initiale de ces variables sera S = 0 et n = 0
Notre algorithme va ensuite effectuer de façon répétée le passage au n suivant, en appliquant la formule mathématique précédente.
Mais quand va-t-il s'arrêter ?
Il faut lui dire quand, il ne le devinera pas ...
donc il nous faut une autre variable pour lui dire le nombre de termes qu'on veut calculer. Appelons la nmax.
donc le début de notre algorithme, comme déja dit est de déclarer ces variables et de dire le genre de "chose" qu'elles représentent, des entiers, des réels, du texte ?
le début va donc ressembler à ça :
VARIABLES
Nombre S
Nombre n
Nombre nmax
ensuite on commence à faire des choses avec ça, on le dit :
DEBUT ALGORITHME
et la première chose à faire c'est les valeurs de départ :
S prend la valeur 0
n prend la valeur 0
Lire nmax
l'instruction "Lire nmax" permet d'entrer au clavier la valeur de nmax, c'est à dire le nombre de boucles qu'on veut faire
Ensuite il va falloir "passer au suivant", c'est la matérialisation de notre récurrence
et ce de façon répétée
Pour répéter on a diverses "instructions"
L'une des plus utiles est le "tant que" : on répète tant qu'une condition est vraie
notre algorithme va donc se poursuivre par :
TANT QUE n < nmax
FAIRE
ici tout ce qui doit être répété
FIN TANT QUE
ici on a terminé de boucler
bien entendu il faut que la condition varie sinon on ne sortira jamais de la boucle !
ici ce sera parce que n augmente de 1 à chaque boucle, par une instruction
n prend la valeur n+1, dans la boucle
il faut aussi calculer la nouvelle valeur de S par un
S prend la valeur ....
enfin il faut afficher la valeur de S, selon ce qu'on veut obtenir, on mettra cette instruction dans la boucle (cela affichera toutes les valeurs successives)
ou une fois fini, après la boucle, et on aura juste la derniere valeur : celle de Snmax
cela se fait bien entendu par un
AFFICHER S
et enfin on termine par un FIN ALGORITME
Toutes ces écritures sont :
en langage naturel
ou en un langage spécifique à la machine sur laquelle on fait "tourner" cet algorithme : ALGOBOX, TI-xx etc ...
tu es en principe maintenant prêt à écrire ton premier algorithme !
Je ne comprends pas quand vous dites la surface coloriée est donc Sn + 1 =....
Je ne comprends pas non plus comment faire pour calculer n'max
La surface coloriée à l'étape n+1 (Sn+1) est la surface coloriée à l'étape précédente (Sn) plus le quart de ce qu'il restait non colorié.
Il restait 1 (le tout) moins ce qui était déja colorié (Sn) c'est à dire 1 - Sn
Soit au final et "en formule" :
Sn+1 = Sn + (1/4)(1 - Sn)
Quant à nmax on ne le calcule pas !! c'est la valeur que choisit l'utilisateur qui va lancer l'exécution de l'algorithme
L'algorithme demande donc à l'utilisateur : "quelle valeur voulez vous pour nmax ?" au moment de l'exécution.
par exemple l'éxécution de l'algorithme va donner ça sur l'écran :
il demande "Entrer nmax : " et attend
je lui donne par exemple 5 (ou le nombre de boucles que je veux)
et il enchaine la suite de l'algorithme en calculant et affichant successivement S0, S1, ... S5 puis s'arrête.
J'ai choisi dans mon algorithme d'afficher tous les Sn intermédiaires
J'aurais pu ne faire afficher que le dernier.
Si je lui demandais 100 boucles pour calculer S100, il me mettrait alors 101 lignes (y compris S0) ce qui serait un peu longuet.
Si on envisage ainsi de grandes valeurs de nmax, il vaut mieux ne lui faire afficher que la dernière valeur !!
Donc si je commence c'est
variable
nombre S
nombre n
nombre nmax
Instruction
Début
S prend la valeur 0
n prend la valeur 0
Lire nmax
Tant que n<nmax
Sn prend la valeur Sn+1 = Sn + (1/4)(1-Sn)
Il y a de l'idée...
mais Sn n'est pas une variable de ton algorithme !
c'est S la variable !
donc
S prend la valeur S + (1/4)(1-S)
qui veut dire que la nouvelle valeur de S (Sn+1) est S + (1/4)(1-S) expression dans laquelle S représente l'ancienne valeur (Sn)
c'est vrai que ça surprend un peu cette écriture les premières fois, avec le même "S" des deux côtés du "prend la valeur", mais on s'y fait
"prend la valeur" calcule tout ce qui est à droite avec la valeur actuelle des variables
puis une fois ce calcul fait remplace l'ancienne valeur de la variable S par la nouvelle valeur calculée
on va avoir exactement la même chose quand on va "compter les boucles" dans la variable n :
n prend la valeur n+1
il faut bien sinon, (si on laisse n à sa valeur initiale de 0), la boucle "tant que" ne se terminerait jamais !
l'algorithme ne "devine" pas qu'il lui faudrait augmenter n de 1 automatiquement, peut être bien que dans le "tant que" on ferait diminuer nmax, ou varier les deux, il ne peut pas deviner la signification qu'on donne à nos variables : il fait juste "bêtement" ce qu'on lui dit de faire.
Je ne comprends pas pourquoi on est parti de 0...
Sn+1 représente le deuxième dessin ? Je ne comprends pas car dans le "S" les "1/4" sont déja compris , pourquoi on les rajoute ?
on est parti de 0 c'est à dire d'un carré ou rien n'est colorié S0 = 0
Si tu veux partir de 1 avec S1 = 1/4 ça marchera aussi bien ...
mais alors il faudra écrire l'initialisation :
n prend la valeur 1
S prend la valeur 1/4
S1 représente ton 1er dessin à la 1ère étape de coloriage
S2 ton 2ème dessin à la 2ère étape de coloriage
etc (si tu avais continué à colorier)
On "voit" bien la formule
Sn+1 (coloriage suivant) = Sn + (1/4)(1 - Sn) où Sn est le coloriage (tout compris) de l'étape précédente.
D'accord merci je comprends mieux, du coup pour l'algorithme je préfère rentrer avec S1 = 1/4 etc mais je vois mal comment tout organiser dans la rédaction
Alors ça .. la rédaction ...
tu peux organiser ça sous la forme
1) étude mathématique
sans entrer trop loin dans les détails, maintenant que tu as bien compris le mécanisme de coloriage, tu peux résumer la démarche qui aboutit à la conclusion de cette étape 1 : la fameuse formule
2) rédaction de l'algorithme
tu n'es pas obligé de dire qu'un algorithme en général c'est ci et ça et que dans le S prend la valeur S + (1/4)(1-S) le S de gauche est la nouvelle valeur et le S de droite l'ancienne et que patati patata
C'est directement la traduction de la formule de la partie 1
de même les n prend la valeur n+1 et le pourquoi du tant que ...
tout ça c'est résumé par la fourniture de l'algorithme lui-même, une fois effectivement testé sur Algobox ou la calculette
Il est juste conseillé de dire au préalable la signification de tes variables.
le reste c'est "écrit dedans"
Courage pour mettre tout ça au propre.
Très bonne remarque !
mais ne pas oublier qu'alors "ce qui reste" n'est pas 1 - Sn mais 4 - Sn (l'aire totale du carré étant 4cm²)
Tous les calculs précédents étaient avec comme unité le côté du carré de départ, si on veut obtenir S en cm² plutôt qu'en fraction de ce carré, autant le faire comme tu dis.
mais il faut faire en fonction de l'aire coloriée et c'est ça que j'arrive pas à exprimer dans l'écriture
Rebonsoir,
je ne comprends pas bien ce que tu veux dire. L'aire coloriée est justement ce que tu dois trouver le moyen de calculer.
Tu veux dire l'aire coloriée à une étape en fonction de la précédente?
L'aire colorié a Sn + 1 = Sn + (1/4)(3/4)
j'ai compris, ce que je comprends pas c'est comment écrire l'algorithme :/
L'aire colorié a Sn + 1 = Sn + (1/4)(3/4)
j'ai compris, ...
Non !
D'abord c'est Sn+1 et pas Sn + 1, et puis c'est faux !
Sn+1 = Sn + (1/4)(4 - Sn) (pas (1/4)(3/4) !!!)
Sn l'ancienne surface colorié à l'étape n
Sn+1 la surface totale maintenant coloriée à l'étape n+1
Par exemple à l'étape 15, n = 15, tout ce qui est déja colorié à cette étape n = 15 est S15, il reste 4 - S15 cm²
on colorie le quart de ce qu'il reste (1/4)(4 - S15)
et on obtient :
tout ce qui est maintenant colorié à l'étape n+1 = 15+1 = 16 est
S16 = S15 + (1/4)(4 - S15)
Et la valeur de S15 je la connais pas, et je m'en fiche. Ce qui compte c'est le mécanisme qui permet de passer de l'étape n = 15 à l'étape n+1 = 16,
et ce mécanisme est valable pour n'importe quelle étape.
Mais j'ai l'impression de radoter et qu'on tourne en rond...
La compréhension de ce mécanisme de coloriage est indispensable avant d'écrire quelque algorithme que ce soit.
Quoi qu'il en soit, tous les morceaux de cet algorithme et l'ordre dans lequel ils interviennent est décrit dans mon post du 17 à 0h24
aller plus loin est soit une redite, soit écrire complètement l'algorithme à ta place et le faire tourner sur mon PC ! ce qui ne t'avancera pas à grand chose (qu'il tourne sur mon PC)...
Lances toi !! oses commencer cet algorithme et :
tu prendras confiance au fur et à mesure
et on est là pour corriger !
Tu vas le faire tourner sur quoi cet algorithme ? une calculette ? Algobox ?
ce que je comprends pas c'est que parfois Sn+1 = Sn + (1/4)(1 - Sn) et d'autres fois Sn+1 = Sn + (1/4)(4 - Sn) ...
il n'y a pas une méthode plus simple avec "pour"
Pour I variant de 1 a n ...
S prend la valeur S + (1/4)(3/4)
le 1 - Sn c'est pour l'aire exprimée sur un carré unité, donc S est en pourcentage de l'aire totale
4 - Sn c'est l'aire exprimée en cm² sur notre carré de coté 2 et donc d'aire = 4
ton message suivant :
On peut remplacer une boucle "tant que" avec un n qui s'incrémente explicitement, par une boucle "pour" tout à fait
à condition de corriger e reste en conséquence (ce n'est plus n l'indice maintenat, c'est i, et la valeur du nombre de boucles ce n'est plus nmax c'est n)
mais par contre ton
S prend la valeur S + (1/4)(3/4) est FAUX archifaux je te l'ai déja signalé plusieurs fois !!!!
Tu n'ajoutes pas le 1/4 de ce qu'il restait la première fois
tu dois ajouter le 1/4 de ce qu'il reste maintenant :
S prend la valeur S + (1/4)(4 - S) (pour exprimer S en cm²)
4-S est ce qu'il reste maintenant en cm²
au fur et à mesure que tu colories, ce qu'il reste diminue et n'est pas constamment = 3/4 comme ta formule le prétend
je crois qu'on n'en sortira jamais de ce truc faux, tu le remets à chaque fois sur le tapis !!
Le premier S dans S prend la valeur S + (1/4)(4 - S) est S a l'étape d'avant et le deuxième S c'est celui a l'étape d'après ?
____________ tous ces S là c'est tous à l'étape d'avant, l'ancienne valeur
/ \
S prend la valeur S + (1/4)(4 - S)
\
\ celui là c'est l'étape d'après, la nouvelle valeur
comme mathématiquement S + (1/4)(4 - S) = 3S/4 + 1, tu peux écrire :
S prend la valeur 3S/4 + 1
ça fera exactement pareil
voir mon message du 17 à 0h24 ou je mentionnais deja une telle simplification (mais à l'époque en fraction de la surface totale plutot que en cm², donc formule différente)
Je vais tenter d'écrire l'algorithme :
Variables:
S (surface colorié)
n ( valeur du nombre de boucle, nombre de coloriage)
I (indice)
Début :
Saisir n
Pour I variant de 1 a N
S prend la valeur S + (1/4)(4-S)
Fin Pour
Afficher S
Bien !
il te manque juste la valeur de départ de S, celle "avant de commencer" qui est ici 0 (avant de commencer la boucle "pour", rien n'était colorié)
Variables:
S (surface colorié)
n ( valeur du nombre de boucle, nombre de coloriage)
I (indice)
Début :
Saisir n
S prend la valeur 0
Pour I variant de 1 a N
S prend la valeur S + (1/4)(4-S)
Fin Pour
Afficher S
en l'absence de cette initialisation, au premier passage dans la boucle "pour" (I=1), au moment de calculer la nouvelle valeur à mettre dans S,
il doit bien calculer "S + (1/4)(4-S)"
il prendrait quoi comme valeur pour S lors de ce calcul ???
en d'autres termes il serait incapable de faire le calcul, ou donnerait un résultat fantaisiste selon son humeur.
Annuler
connectez vous