Forum de mathématiques - Bibm@th.net

Mopoung Ngnogue Christian

Membre

Inscription : 04-11-2022

Messages : 2

Algorithmique D3 en licence

Bonjour
Soit un vecteur T à n éléments.
a) Écrire un algorithme récursif RENVERSE qui le tableau T ( la 1ère valeur devient la dernière, la 2ème l'avant-dernière,....., la 1ère valeur devient la 1ère). Par exemple si le tableau est trié en ordre croissant au début de la fonction il doit être trié en ordre décroissant par l'algorithme.
b) Ecrire un algorithme itératif REORDRE qui réordonne le vecteur T de la manière suivante: Tous les éléments pairs sont placés en tête et les éléments impairs en queue. Par exemple si T=(5,3,6,1,7,4,2,9) on aura à la fin de l'algorithme T= (6,4,2,5,3,1,7,9)

2) Faire les traces des algorithmes RENVERSE et REORDRE avec le vecteur T =(5,3,6,1,7,4,2,9)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 357

Re : Algorithmique D3 en licence

Re,

Tu avais eu 2 réponses : la mienne et celle de rareStrophe.
Il y a eu ensuite squattage de ta discussion : j'ai fait le "ménage" et je me suis raté.
Ma réponse (via Python) et celle de rareStrophe (via Haskell) ont sauté aussi.
Je vais dans la matinée essayer de réparer ça...
N-B : il n'est pas question qu'on réponde à ces questions à ta place...
Mais t'aider, te guider, oui avec plaisir...

Pour moi, ce sera avec Python. Pour tout autre langage, soit je ne serai pas assez compétent, soit totalement incompétent...
Pour rareStrophe, lui, c'est avec Haskell, d'autres pratiquent Pascal, Maple...
Questions :
1. Toi, qu'as-tu déjà fait ?
2. Langage à utiliser  : C, C++, Pascal, Visual Basic, Python, Haskell ? Autre ?

@+

[EDIT]
Dans mon post, je te disais que, quel que soit le langage (récent), tu allais devoir réinventer la roue parce que les fonctions de tri s y sont incluses nativement...
Exemple en Python et en une seule ligne : tu veux inverser le sens de la liste : [3,1,2,5,4,7,8] :

print([3,1,2,5,4,7,8][::-1])

qui te renvoie :
[8, 7, 4, 5, 2, 1, 3]
Et là, rareStrophe en avait rajouté une couche avec le langage Haskell...

C'est bien ça qui est attendu de la fonction RENVERSE ?
Alors, quel que soit le langage, de toutes façons, il te faudra réfléchir à la façon dont tu t'y prendrais pour RENVERSE, avec papier et stylo et écrire ton procédé en pseudo-code... c'est à dire en décrivant chaque étape (de façon claire et courte) en langage courant...
Une fois trouvé un algorithme, il te restera à le traduire dans le langage choisi.
Là où ça se complique, c'est qu'on te demande un algorithme, fonctionnant de manière récursive (pas évident).
Et celui qui a inventé l'exercice en ajoutant "pour tout $n \in \mathbb N$", si vraiment, on a le choix de n, alors à partir de n=1000, il y a gros à parier qu'on récolterait un beau plantage en ayant saturé la "pile"...

Répondras-tu ?
Peut-être... Quand bien même tu ferais le mort, je ferai ces questions en Python pour le plaisir...
Et je posterai les codes en Python seulement d'ici un mois...

Dernière modification par yoshi (07-11-2022 18:41:46)

---

Arx Tarpeia Capitoli proxima...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 357

Re : Algorithmique D3 en licence

Bien le bonjour évanescent ami...

1. Fonction RENVERSE.
    C'est fait. J'ai commencé par une version itérative, puis je l'ai transformée en récursive.
    Trace : c'était simple et fait aussi...
2. Fonction REORDRE.
    Je vais y réfléchir.

@+

[EDIT]Fonction REORDRE : fait aussi ; pas si simple que ça !

Dernière modification par yoshi (11-11-2022 16:26:41)

---

Arx Tarpeia Capitoli proxima...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 357

Re : Algorithmique D3 en licence

Bonsoir,

Q1a RENVERSE.
Voilà ma solution Itérative (pas demandée), dont je me suis inspiré pour la version récursive.
Je n'ai pas travaillé avec la liste donnée : je l'ai trouvée un peu trop courte...

def RENVERSE(L,n,p):
    #print("Trace :")
    for i in range(n):
        if i<(n-p)//2:
            L[i],L[n-i-1]=L[n-i-1],L[i]
            #print(L)
    #print()
    return L
L=[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]
n,p=len(L),len(L)%2

print("Ma liste d'origine :\n",L)
print()
print("Ma liste renversée :\n",RENVERSE(L,n,p))

Sortie :

Ma liste d'origine :
[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]

Ma liste renversée :
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

Q2a Trace :
Je l'obtiens en supprimant les # dans la fonction (attention à l'indentation ensuite)...
Sortie :

Ma liste d'origine :
[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]

Trace :
[11, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 12]
[11, 8, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 9, 12]
[11, 8, 14, 15, 7, 1, 3, 2, 5, 4, 6, 10, 13, 9, 12]
[11, 8, 14, 10, 7, 1, 3, 2, 5, 4, 6, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 1, 3, 2, 5, 4, 7, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 4, 3, 2, 5, 1, 7, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

Ma liste renversée :
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

En principe, j'aurais dû traiter le cas ou n est pair et le cas où il est impair...
Je m'en suis passé en introduisant la variable p (comme parité) en qui vaut soit 0, soit 1, que je passe aussi en paramètre à la fonction...
Ici, j'ai n= 15 donc p=1.
Le nombre 5 est la médiane de la liste : 7 nombres avant, 7 nombres après : il ne doit pas changer de place
j'échange donc les nombres 2 à 2 symétriques par rapport au nombre 5
Mais 5 est le 8e nombre et son indice est 7 (on commence à 0). donc je fais les échanges tant que l'index i de la position des nombres est strictement inférieure à 7...
Dans certains langages (mais pas en Python), on dispose du mot-clé SWAP :
SWAP a,b échange les valeurs de a et b. En Python, on écrit simplement a,b=b,a...

Cas où n est pair.
Supprimons (par exemple) 11 b: on a donc n=14 et donc p==0.
(n-p)//2 vaut donc 7 correspondant à l'index 6 !

Nombres : 12  9 13 15  7  1  3  2  5  4  6  10 14  8
  Index :  0  1  2  3  4  5  6  7

L'index de la médiane est donc compris entre les index 6 et 7..
Je dois donc bien échanger les nombres 1 et 3 d'indices 6 et 7.
Mon test d'arrêt est donc i=7 c'est à dire (14 -0)//2=7...
Donc (n-p)//2 marche dans les deux cas

Pour avoir la Trace, il fallait opérer le renversement "sur place", en n'utilisant que la liste initiale, ce qui sous peine de voir boucle for perdre le fil de ses indices ...
D'où la solution d'échanger L[0] et L[n-1], L[1] et L[n-2]...
Pourquoi // et non : / ?
Les index doivent être des nombres entiers, or diviser avec / renvoie un "décimal" : 14/2 --> 7.0...
Et là Python n'aime pas ça : erreur assurée.
// renvoie lui, le quotient euclidien (le quotient entier) : 15/2 = 7.5 mais 15//2 =7  et 14//2 = 2 (et non 2.0)

Et la version récursive ?
Bin, je ne vais pas être plus royaliste que le roi : je me suis fait plaisir, les problèmes étaient intéressants (réinventer la roue, ce n'est tout de même pas courant), mais l'ami Chiristian Mopou Ngogue n'est pas pressé de revenir. Il a posté chez developpez.net où on lui a gentiment dit qu'on n'allait pas faire le boulot à sa place...
Et si par hasard il décidait de repasser in extremis, je serais ennuyé de penser que je suis fait avoir à l'usure, qu'il est passé, a vu la solution, fait un copier/coller et sans fatigue  aura pu répondre à ce qui lui avait été demandé : zéro bénéfice pour lui...

Donc, je vais encore patienter...

@+

---

Arx Tarpeia Capitoli proxima...

rareStrophe

Membre

Inscription : 26-06-2022

Messages : 82

Re : Algorithmique D3 en licence

Étant donné que @yoshi ne semble pas avoir été en mesure de remettre ma solution, la revoici, toujours en Haskell

a) Comme déjà indiqué la première fois, cette solution n'est pas optimale mais répond à la question de construire nous même l'algorithme.

reverse' [] = []
reverse' xs = last xs:reverse' (init xs)
 

ghci> reverse' [5,3,6,1,7,4,2,9]
[9,2,4,7,1,6,3,5]
 

b)

import Data.List
import Data.Ord

sortOddFirst xs = sortBy (comparing odd) xs
 

ghci> sortOddFirst [5,3,6,1,7,4,2,9]
[6,4,2,5,3,1,7,9]
 

Dernière modification par rareStrophe (15-11-2022 15:47:03)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 357

Re : Algorithmique D3 en licence

Bonsoir,

@rarestrophe.
Merci.
Questions : - en Haskell, peut-on aussi réinventer la roue et ne pas utiliser les fonctions built-in ?
                 -  quid de la récursivité ?
RENVERSE en console avec 1 ligne de code :

(propriétés des listes)
Sortie:

[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

REORDRE, Tri Pairs d'abord en console en 1 ligne de code :
[code=sorted([12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11],key=lambda e : e%2==1)
[/code]
(option key de la fonction de tri sorted())
Sortie :

[12, 2, 4, 6, 10, 14, 8, 9, 13, 15, 7, 1, 3, 5, 11]

les fonctions anonymes lambda existent-elles aussi en Haskell ?

N-B  : je m'amuse beaucoup...

@+[

---

Arx Tarpeia Capitoli proxima...

rareStrophe

Membre

Inscription : 26-06-2022

Messages : 82

Re : Algorithmique D3 en licence

On peut bien sûr réinventer la roue. Par exemple, pour la fonction reverse', on peut réécrire rapidement (par récursivité) les fonctions init et last.

-- Pour gérer les erreurs dues aux listes vides
import GHC.List

init' []     = errorEmptyList "init'"
init' [x]    = []
init' (x:xs) = x:init' xs

last' []     = errorEmptyList "last'"
last' [x]    = x
last' (_:xs) = last' xs

reverse' [] = []
reverse' xs = last' xs:reverse' (init' xs)
 

edit: j'ai rajouté une petite gestion d'erreurs.

Les fonctions anonymes (lambda functions) existent bien évidement en Haskell. Exemple simple :

(\x -> x*2)
 

Si tu exécutes ce code, par exemple pour 5 tu obtiendras

(\x -> x*2) 5
10
 

10 en sortie.
Si on va plus loin, la comparaison que j'ai utilisé dans sortOddFirst peut s'écrire (de façon simple)

sortOddFirst xs = odds ++ evens
    where odds  = (filter (\x -> x`mod`2==0) xs)
          evens = (filter (\x -> x`mod`2==1) xs)
 

Dernière modification par rareStrophe (15-11-2022 18:58:15)

rareStrophe

Membre

Inscription : 26-06-2022

Messages : 82

Re : Algorithmique D3 en licence

Je viens de me rendre compte que je me suis foiré sur la fin de mon dernier message x'). Je viens donc de le compléter !

rareStrophe

Membre

Inscription : 26-06-2022

Messages : 82

Re : Algorithmique D3 en licence

Petit ajout pour appuyer mes précédents propos. Au cas où quelqu'un d'un peu bizarre voudrait aussi réinventer filter, bien que la fonction paraisse compliquée, c'est bien évidement aussi possible et même très simplement pour pas un sou :

filter' function     [] = []
filter' function (x:xs) = if function x then x:filter' function xs else filter' function xs
 

Si on s'amuse alors à tester cette dernière dans sortOddFirst

sortOddFirst xs = odds ++ evens
    where odds  = (filter' (\x -> x`mod`2==0) xs)
          evens = (filter' (\x -> x`mod`2==1) xs)
 

et qu'on l'exécute

ghci> sortOddFirst [5,3,6,1,7,4,2,9]
[6,4,2,5,3,1,7,9]
 

on obtient bien le résultat souhaité.

Dernière modification par rareStrophe (15-11-2022 20:16:15)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 357

Re : Algorithmique D3 en licence

Bonjour,

3 semaines plus tard, le demandeur n'a pas refait surface, sur aucun forum.
Soit il a capitulé, soit quelqu'un a fait le boulot localement.
Nous arrivons en fin de mois, voici donc mes codes Python...

A) Fonction RENVERSE.
En mode récursif :

def RENVERSE (L,j,n,p):
    if i<(n-p)//2:
        L[i],L[n-j-1]=L[n-1-j],L[j]
        RENVERSE(L,j+1,n,p)
    return L

L=[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]
print("Avant RENVERSE :")
print(L)
print()
L=RENVERSE (L,0,n,p)
print("Après RENVERSE :")
print(L)
 

Sortie

Avant RENVERSE :
[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]

Après RENVERSE :
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

Modification du script pour obtenir la trace :

def RENVERSE (L,j,n,p):
    if j==0:
        print("Trace:")
    if j<(n-p)//2:
        L[j],L[n-j-1]=L[n-1-j],L[j]
        print(L)
        RENVERSE(L,i+1,n,p)
    if j==0:
        print()
    return L

L=[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]
n=len(L)
p=n%2
print("Avant RENVERSE :")
print(L,"\n")
RENVERSE(L,0,n,p)
print("Après RENVERSE :")
print(L)
 

Sortie

Avant RENVERSE :
[12, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 11]

Trace:
[11, 9, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 8, 12]
[11, 8, 13, 15, 7, 1, 3, 2, 5, 4, 6, 10, 14, 9, 12]
[11, 8, 14, 15, 7, 1, 3, 2, 5, 4, 6, 10, 13, 9, 12]
[11, 8, 14, 10, 7, 1, 3, 2, 5, 4, 6, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 1, 3, 2, 5, 4, 7, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 4, 3, 2, 5, 1, 7, 15, 13, 9, 12]
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

Après RENVERSE :
[11, 8, 14, 10, 6, 4, 5, 2, 3, 1, 7, 15, 13, 9, 12]

B) Fonction REORDRE
La méthode de tri est inspirée de celle du "Tri à bulle" à ceci près que je ne teste pas l'ordre (croissant ou décroissant) de deux éléments, mais de leurs restes modulo 2.

def REORDRE(L):
    n = len(L)
    for i in range(n-1):
        for j in range(0, n-i-1):
             if L[j]%2 > L[j+1]%2 :
                L[j], L[j+1] = L[j+1], L[j]
    return L

L = [12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]
print ("Liste non réordonnée :\n" + str(L))
print()
print ("Trace :")
L=REORDRE(L)
print()
print ("Liste réordonnée :\n",L)
 

* Sortie *

Liste non réordonnée :
[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]

[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]

Pour obtenir la trace :

def REORDRE(L):
    n = len(L)
    for i in range(n-1):
        for j in range(0, n-i-1):
             if L[j]%2 > L[j+1]%2 :
                L[j], L[j+1] = L[j+1], L[j]
        print(L)
    return L

L = [12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]
print ("Liste non réordonnée :\n" + str(L))
print()
print ("Trace :")
L=REORDRE(L)
print()
print ("Liste réordonnée :\n",L)
 

* Sortie *

Liste non réordonnée :
[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]

Trace :
[12, 8, 16, 9, 13, 18, 15, 7, 1, 2, 3, 4, 6, 10, 14, 5, 11]
[12, 8, 16, 9, 18, 13, 15, 7, 2, 1, 4, 6, 10, 14, 3, 5, 11]

[12, 8, 16, 18, 9, 13, 15, 2, 7, 4, 6, 10, 14, 1, 3, 5, 11]
[12, 8, 16, 18, 9, 13, 2, 15, 4, 6, 10, 14, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 9, 2, 13, 4, 6, 10, 14, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 9, 4, 6, 10, 14, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]

Liste réordonnée :
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]

- Autres versions sans la fonction REORDRE -
Ce script m'a obligé à gérer deux indices parce qu'il est vivement déconseillé dans une boucle for de supprimer un élément même si c'est pour l'enregistrer en fin de fichier, produisant un fâcheux décalage d'indices...

L,i,j=[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11],0,0
n=len(L)
print("              Liste test :\n",L)
print ("\n************************************************")
while j<n:
    e=L[i]
    if e%2==1:
        del L[i]
        L=L+[e]
    else:
        i+=1
    #print(L)
    j+=1
   
print("              Liste réordonnée :\n",L)
 

* Sortie *

Liste test :
[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]

                         Liste réordonnée
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]

                         --------------------
là, j'utilise l'option facultative  key du tri (natif en Python) par la fonction sorted()

def parite(elem):
    return elem%2

L=[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]
print(sorted(L, key=parite))
 

* Sortie *
[12, 8, 16, 18, 2, 4, 6, 10, 14, 9, 13, 15, 7, 1, 3, 5, 11]
       --------------------
Là, je parcours la liste d'origine L, je stocke dans une liste P ou I, chaque élément rencontré selon qu'il est pair ou impair.
Sorti de la boucle, je concatène les listes P et I...

L=[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]
P,I=[],[]
for e in L:
    if e%2==0:
            P.append(e)
    else:
        I.append(e)
    print(P,I)
L=P+I
print(L)
 

Ce qui m'a donné l'idée de faire plus court en utilisant la technique des list comprehension :

L=[12, 9, 8, 16, 13, 15, 18, 7, 1, 3, 2, 5, 4, 6, 10, 14, 11]
print([i for i in L if i%2==0]+[i for i in L if i%2])
 

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 782

Re : Algorithmique D3 en licence

Petit ajout pour appuyer mes précédents propos..

Et tu as réussi à écrire le programme Ptython en HasKell ?

Dernière modification par LEG (26-11-2022 09:50:03)