Algorithmique

[invite71a6d891]

Bonjour,
J'aurais une question concernant l'algorithme d'une figure (nommée Flocon Von Koch) dont les différentes itérations sont jointes dans l'image.
Voici le fameux algorithme sur Python (turtle):

def vonkoch(l,n):
   
  if n==0:
      forward(3)
  else:
            vonkoch(l/3,n-1)
            left(60)
            vonkoch(l/3,n-1)
            right(120)
            vonkoch(l/3,n-1)       Je me demandais : pourquoi écrit-on "n-1" et pas "n+1" étant donné que l'on répète la figure à chaque nouvelle itération ?
            left(60)
            vonkoch(l/3,n-1)

def flocon(l,n):
    vonkoch(l,n)
    right(120)
    vonkoch(l,n)
    right(120)
    vonkoch(l,n)
    mainloop()
    ht()

Voilà donc une question qui va sûrement paraître toute simple pour des calés en algorithmique.
Merci beaucoup d'avance !
-----

[pm42]

Et la question ?

[invite6486d7bd]

Et la question ?

Elle est en commentaire dans le code.

[invite71a6d891]

Pardon, je la pensais plus voyante avant de poster le message.

[A voir en vidéo sur Futura]

[Jack]

Je me demandais : pourquoi écrit-on "n-1" et pas "n+1" étant donné que l'on répète la figure à chaque nouvelle itération ?

Parce que sinon, la fonction étant récursive, tu n'atteindrais pas la condition d'arrêt de la récursion, à savoir n == 0

[invite71a6d891]

Merci beaucoup pour la réponse ��, mais, si je ne me trompe pas, il me semble que dans ce cas on part de n=0
Il s’agit d’une figure fractale, c’est à dire d’une figure dans on «*répète le motif*» à l’infini.
Ai-je tort ?

[pm42]

Merci beaucoup pour la réponse ��, mais, si je ne me trompe pas, il me semble que dans ce cas on part de n=0

Cela ne veut rien dire "partir de n=0" dans le cas présent. On fixe une valeur n et on trace la courbe Fn. Ce qui est fait récursivement comme déjà dit.

Il s’agit d’une figure fractale, c’est à dire d’une figure dans on «*répète le motif*» à l’infini.

La fractale est la limite des Fn. On ne peut pas la tracer puisqu'elle est à l'infini. Sans parler du fait qu'il ne sert à rien de tracer dès que les détails dépassent la résolution de l'écran.

Ai-je tort ?

Oui, tu mélanges un peu tout.

[JPL]

Il s'agit bien d'une structure fractale mais pour dessiner des fractales on ne pousse jamais le calcul à l'infini, et pour cause ! On se fixe toujours une condition d'arrêt en fonction du résultat qu'on veut obtenir. Pour le flocon de von Koch (von étant la particule "de" en français le v est une minuscule) on se limite à très peu d'itérations car en poussant le calcul trop loin le résultat est moins intéressant.

[invite896757ff]

Où est défini n ? how many beers?

[Jack]

Merci beaucoup pour la réponse ��, mais, si je ne me trompe pas, il me semble que dans ce cas on part de n=0

Je rejoins mes petits camarades. On ne vois nulle part où tu donnes une valeur à n, donc comment peux-tu affirmer que n est égal à 0?
Tu ne nous montres que 2 fonctions attendant une valeur de n. Il faudrait nous montrer le programme complet avec son point d'entrée.

[invite71a6d891]

Merci beaucoup pour vos réponses.

Il s'agit bien d'une structure fractale mais pour dessiner des fractales on ne pousse jamais le calcul à l'infini

C'est donc pour cela que l'on a écrit "n-1" ?

Il faudrait nous montrer le programme complet avec son point d'entrée.

Effectivement, je n'ai cité que la partie qui m'intéressait.
Voici le programme complet (même si je ne pense pas qu'il soit indispensable) :

from turtle import*


up()
goto(-600,0)
down()

shape("turtle")
wheel=5
bgcolor("white")
pensize(2)
pencolor("black")

def vonkoch(l,n):
   
  if n==0:
      forward(3)
  else:
            vonkoch(l/3,n-1)
            left(60)
            vonkoch(l/3,n-1)
            right(120)
            vonkoch(l/3,n-1)
            left(60)
            vonkoch(l/3,n-1)

def flocon(l,n):
    vonkoch(l,n)
    right(120)
    vonkoch(l,n)
    right(120)
    vonkoch(l,n)
    mainloop()
    ht()

#main program
from turtle import*
title ("Von Koch Flocon")
e=numinput("Von Koch Flocon","Quelle étape ?", 1, minval=0, maxval=50)
x=300
speed(0)
flocon(x,e)

Concernant le point d'entrée, c'est lorsqu'on lance le programme qu'on nous demande le nombre d'étapes souhaitées (voir image ci-dessous)

En vous remerciant encore !

[pm42]

C'est donc pour cela que l'on a écrit "n-1" ?

Oui. VonKoch est définie récursivement et donc le programme est récursif. Tu as déjà vu le code d'une factorielle récursivement par ex ? C'est la même logique :

def fact(n):
    """fact(n): calcule la factorielle de n (entier >= 0)"""
    if n<2:
        return 1
    else:
        return n*fact(n-1)