Outil pour définir un algorithme

Version imprimable

07/04/2024, 10h49
scalpel

Outil pour définir un algorithme

Bonjour à tous,

Même si ils ne sont pas hyper complexes, certains exercices du Swinnen nécessitent que je réfléchisse à un algorithme global avant de me lancer dans le codage. Pour ce faire, je dessine sommairement celui-ci sur papier, mais le dessin devient rapidement très très brouillon.

Auriez-vous un outil à me conseiller qui ne soit pas plus compliqué à utiliser que l'exercice que je doit réaliser.
07/04/2024, 10h54
f-leb

Bonjour,

Quel exercice du Swinnen par exemple ?
J'ai du mal à croire qu'un exercice du Swinnen nécessite plus qu'un peu de papier/crayon:koi:
07/04/2024, 11h43
wiztricks

Citation:

Envoyé par scalpel

Pour ce faire, je dessine sommairement celui-ci sur papier, mais le dessin devient rapidement très très brouillon.

Gribouiller est l'intérêt du travail papier/crayon (pour réfléchir). Il n'exclut pas de remettre ce qui émerge "au propre" de temps en temps, voire de papier calque pour superposer/visualiser l'intérêt de certains changements.

Citation:

Envoyé par scalpel

Auriez-vous un outil à me conseiller qui ne soit pas plus compliqué à utiliser que l'exercice que je doit réaliser.

La simplicité du papier/crayon suppose l'élaboration (ou l'apprentissage) d'une méthode (le choix de symboles...) pour arriver à accoucher de... une recherche sur Internet avec le mot clef algorigramme devrait sortir des pistes. Ceci dit pourquoi poser dans un forum python une question sur un sujet qui relève plutôt de la rubrique algorithmique

- W
07/04/2024, 21h28
scalpel

Citation:

Envoyé par f-leb

... Quel exercice du Swinnen par exemple ? ...

Pour exemple : Au paragraphe "12-B-10-A" l'exercice consistant à identifier les nombres premiers dans une liste de 1000 éléments ma donné pas mal "de fil à retordre".

Citation:

Envoyé par wiztricks

... Ceci dit pourquoi poser dans un forum python une question sur un sujet qui relève plutôt de la rubrique algorithmique ...

Parce que je n'avais pas connaissance de cette rubrique. :)
Pas plus que du terme "algorigramme". 8O
07/04/2024, 22h07
f-leb
Oui, mais est-ce que ce ne serait pas plutôt un problème de compréhension de l'énoncé ? Ou de fâcherie avec les maths:aie:?
Car finalement l'algorithme du crible est décrit dans l'énoncé...
Citation:
Envoyé par Swinnen

Un nombre premier est un nombre qui n'est divisible que par un et par lui-même. Écrivez un programme qui établit la liste de tous les nombres premiers compris entre 1 et 1000, en utilisant la méthode du crible d'Eratosthène :

Créez une liste de 1000 éléments, chacun initialisé à la valeur 1.
Parcourez cette liste à partir de l'élément d'indice 2 : si l'élément analysé possède la valeur 1, mettez à zéro tous les autres éléments de la liste, dont les indices sont des multiples entiers de l'indice auquel vous êtes arrivé.

Lorsque vous aurez parcouru ainsi toute la liste, les indices des éléments qui seront restés à 1 seront les nombres premiers recherchés.
En effet : A partir de l'indice 2, vous annulez tous les éléments d'indices pairs : 4, 6, 8, 10, etc. Avec l'indice 3, vous annulez les éléments d'indices 6, 9, 12, 15, etc., et ainsi de suite. Seuls resteront à 1 les éléments dont les indices sont effectivement des nombres premiers.
Citation:

Parcourez cette liste à partir de l'élément d'indice 2...

Une boucle for...

Citation:

si l'élément analysé possède la valeur 1,

Un test if...

Citation:

mettez à zéro tous les autres éléments de la liste, dont les indices sont des multiples entiers de l'indice auquel vous êtes arrivé.[

Une boucle while imbriquée pour calculer les multiples.

C'est une sorte de gymnastique, il faut pratiquer;)
08/04/2024, 09h47
scalpel

Citation:

Envoyé par f-leb

Oui, mais est-ce que ce ne serait pas plutôt un problème de compréhension de l'énoncé ? Ou de fâcherie avec les maths:aie:? ...

Tu a raison de poser la question, c'est probablement les deux. :oops:
08/04/2024, 10h42
Arioch

Moi aussi, je suis fâché avec les maths :mrgreen:

Et tu vois, là c'est typiquement le genre d'exercices dont je me passe allègrement.
08/04/2024, 11h39
wiztricks

Citation:

Envoyé par scalpel

l'exercice consistant à identifier les nombres premiers dans une liste de 1000 éléments ma donné pas mal "de fil à retordre".

Sur la feuille de papier on peut faire un tableau de 2 lignes correspondant aux 20 premiers entiers et regarder comment ça se passe lorsqu'on raye (met à zéro) les multiples de 2, puis les multiples de 3,...
Puis on essaie de traduire ce qu'on fait manuellement en instructions qui ne seront peut être pas encore "python" dans un premier temps...

Au début, difficile de s'en sortir sans tout écrire (ou en écrire trop), puis avec l'habitude, on pourra traduire directement en python dans les cas simples...
L'intérêt des exercices proposé par les tutos pour débutants est qu'ils s'appliquent a des types simples (entiers chaines de caractères,...) qu'on peut représenter facilement sur une feuille de papier. Moins débutant, ça devient plus abstrait mais les constructions sont identiques (juste plus difficile à représenter sur une feuille).

- W
08/04/2024, 12h27
scalpel

Citation:

Envoyé par Arioch

... Et tu vois, là c'est typiquement le genre d'exercices dont je me passe allègrement.

N'ayant aucun autre objectif à court terme que la découverte d'une facette de l'informatique différente de celle que pratique depuis plus de trente ans, malgré de très modestes compétences en mathématique, je m'applique depuis trois mois à ne sauter aucun exercice. Ils ne sont probablement pas résolut dans les "règles de l'art", surtout celui-ci que je n'avais pas résolut avec l'algorithme préconisé par f-leb. Mais je pense que les résultats sont correct. :)

Citation:

Envoyé par wiztricks

... Au début, difficile de s'en sortir sans tout écrire (ou en écrire trop) ...

Je confirme. :?
08/04/2024, 14h13
MPython Alaplancha

Bonjour,

Citation:

Envoyé par scalpel

Ils ne sont probablement pas résolut dans les "règles de l'art", surtout celui-ci que je n'avais pas résolut avec l'algorithme préconisé par f-leb. Mais je pense que les résultats sont correct. :)

N'oublie pas cependant que les exercices ont une visée pédagogique. Le but premier n'est pas de trouver un résultat correct.
Dans le cas présent, si l'algorithme est sous entendu dans l'énoncé (comme dans beaucoup d'exercice scolaire), c'est que l'auteur veut que tu le résolves selon ses consignes pour t'amener à emprunter un certain cheminement (avec les outils/commandes abordé(e)s en cours).

Citation:

Envoyé par MPython Alaplancha

... pour t'amener à emprunter un certain cheminement (avec les outils/commandes abordé(e)s en cours).

Je m'y applique. :)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# création de la liste
liste=[]
for i1 in range(1000):
    liste.append(1)
 
# les indices O et 1 ne correspondent pas à des nombres premiers
liste[0]=liste[1]=0
 
# initialise les valeurs (0 ou 1) liées aux indices premiers
for i2 in range(2,1000):
    if liste[i2]==1:
        for i3 in range(i2+1,1000):
            if i3 % i2 == 0:
                liste[i3]=0
 
# imprime les indices des éléments de valeur 1
for i4 in range(1000):
    if liste[i4] == 1:
        print(i4, end=",")

08/04/2024, 15h44
papajoker

bonjour

Citation:

avec les outils/commandes abordé(e)s en cours

Donc difficile de valider ou non ta réponse (sans relire tout ce qui y avait avant cet exercice).

Petites notes pas directement liées à cet exercice :

Nom de variable
i1, i2, i3 :( NON (c'est important!), tu ne réutilises pas cette variable en dehors de la boucle. Tu dois réutiliser ne même nom de variable i et si boucle dans boucle, on utilise i, j...

Nom de variable
liste :( on n'exprime pas le type mais le contenu ! ici on a une liste de Nombres, donc "nombres" ou "numbers" et un bien meilleur choix. (Au pluriel car nous en avons plusieurs)
ps: généralement on va utiliser l'anglais (plus tard)

i1, ligne 3, tu n'utilises jamais cette variable ! Il n'y a donc aucune raison de la créer et en plus lui assigner 1000 fois une valeur va ralentir ton programme pour rien.
Je suppose que tu as au moins déjà vu dans tes cours au moins 2 meilleures façons d'écrire ce block.

Voir 4 fois 1000 dans si peu de lignes me choque tout de suite...

Citation:
Envoyé par scalpel
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 # création de la liste liste=[] for i1 in range(1000): liste.append(1) # les indices O et 1 ne correspondent pas à des nombres premiers liste[0]=liste[1]=0 # initialise les valeurs (0 ou 1) liées aux indices premiers for i2 in range(2,1000): if liste[i2]==1: for i3 in range(i2+1,1000): if i3 % i2 == 0: liste[i3]=0 # imprime les indices des éléments de valeur 1 for i4 in range(1000): if liste[i4] == 1: print(i4, end=",")
Et finalement, sur le principe cet algorithme fait le boulot. Il n'y a rien de choquant et bon nombre de débutants ont dû écrire un code similaire.

Par contre, cette partie pour déterminer les multiples peut être optimisée :
Code:

1 2 3 for i3 in range(i2+1,1000): if i3 % i2 == 0: # i3 multiple de i2 ...
Pour avoir les multiples de i2, on commence par l'indice 2*i2 et on se déplace avec un pas=i2.
Si i2=2, i3=2*2=4, 6, 8 , 10, ... par pas de 2
Si i2=3, i3=2*3=6, 9, 12, 14, ... par pas de 3
etc.

Dans mon précédent message, j'avais en tête cette version avec un while :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 nbr_premiers = [1]*1000 n = len(nbr_premiers) for i in range(2, n): if nbr_premiers[i]==1: k = 2 multiple_de_i = k * i while multiple_de_i < n: nbr_premiers[multiple_de_i] = 0 k = k + 1 multiple_de_i = k * i # Affichage des nbres premiers for i in range(2, n): if nbr_premiers[i]==1: print(i, end=", ")
Et puis finalement, je suis revenu avec une 2ème boucle for imbriquée qui ne m'est venue qu'après :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 nbr_premiers = [1]*1000 n = len(nbr_premiers) for i in range(2, n): if nbr_premiers[i]==1: for multiple_de_i in range(2*i, n, i): # début=2*i, fin=n non inclus, pas=i nbr_premiers[multiple_de_i] = 0 # Affichage des nbres premiers for i in range(2, n): if nbr_premiers[i]==1: print(i, end=", ")
Bref, voilà un petit exercice pas si simple, et qui donne matière à discuter. J'espère être resté dans les clous du Swinnen au moment de l'exercice, mais c'est un bon exercice pour progresser:ccool:

Tu peux maintenant t'exercer ici ;)

08/04/2024, 22h04
scalpel

Merci à vous tous de me répondre avec autant de précisions et d'exemples. Cela m'est vraiment utile, car je fais encore énormément d'erreurs. :oops:
08/04/2024, 22h19
scalpel

Citation:

Envoyé par papajoker

... ligne 3, tu n'utilises jamais cette variable ! Il n'y a donc aucune raison de la créer et en plus lui assigner 1000 fois une valeur va ralentir ton programme ...

Effectivement :?

Code:

liste=[1]*1000
08/04/2024, 22h28
scalpel

Citation:

Envoyé par f-leb

... J'espère être resté dans les clous du Swinnen au moment de l'exercice ...

Oui, ça correspond exactement à l'avancement du cours. 👌
09/04/2024, 09h36
fred1599

Bonjour,

Je pense qu'au niveau actuel du Swinnen tu peux comprendre l'algorithme du crible d’Ératosthène qui permet de générer l'ensemble des nombres premiers inférieurs à N.

Il est simple, efficace et c'est intéressant de s'appuyer sur des algos connus.
09/04/2024, 11h08
scalpel

Ce n'était pas pour cet exercice en particulier que je me posait la question, c'était surtout pour commencer à apprendre à utiliser un outil que je pensait inévitable pour la suite. Mais au fil de cette discussion, vous m'avez tous persuadé que pour le moment il vaut mieux que je me concentre sur l'apprentissage du langage.

Les exercices deviennent de plus en plus intéressants, en ce moment je suis sur une analyse (par fractionnement) de fonctionnement du générateur de nombres aléatoires. 👌