Discussion :

[Erwane]

Bonsoir , quelqu'un aurait il une idée de l'algorithme pour trouver la plus grande valeur dans une liste d'entiers ?

merci

[Erwane]

j'ai trouvé merci .

[Nicolas_75]

Bonjour,

A toutes fins utiles...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
;; une fonction simple donnant le maximum de deux nombres :
(define (max-of-2-numbers a b)
  (if (> a b) a b))

;; version 1 de la fonction : récurrence simple
;; (on suppose que L est une liste non nulle de nombres)
(define (max-of-list-1 L)
  (if (null? (cdr L))
      (car L)
      (max-of-2-numbers (car L) (max-of-list-1 (cdr L)))))

;; version 2 de la fonction : récursion terminale
;; (on suppose que L est une liste non nulle de nombres)
;; fonction auxiliaire :
(define (max-of-list2-aux current-highest rest-of-list)
  (if (null? rest-of-list)
      current-highest
      (if (> (car rest-of-list) current-highest)
          (max-of-list2-aux (car rest-of-list) (cdr rest-of-list))
          (max-of-list2-aux current-highest (cdr rest-of-list)))))
;; fonction proprement dite :
(define (max-of-list-2 L)
  (max-of-list2-aux (car L) (cdr L)))

(max-of-list-1 '(-4 22 5)) ;; donne 22
(max-of-list-2 '(-4 22 5)) ;; donne 22

Cordialement,

Nicolas

[Garulfo]

Bonsoir , quelqu'un aurait il une idée de l'algorithme pour trouver la plus grande valeur dans une liste d'entiers ?

merci

C'est un poste à mettre dans le forum Algorithmie et non Scheme.

[Garulfo]

Bonjour,

A toutes fins utiles...[...]
Cordialement,

Nicolas

Non ! Franchement. Je sais que tu fais ça pour être serviable, mais ce genre de messages fait le contraire. Ainsi un étudiant qui recherche la solution, la prend et l'utilise telle qu'elle, au lieu de le faire réflechir. Il ne faut pas poster de solution en entier juste comme ça. Même quand c'est fait avec un bon esprit.

De plus, le problème ici est que le créateur ne trouvait pas l'algorithme. Le code ne l'aidera en rien. Au mieux ça lui donnera directement une solution de laquelle il va trouver l'algorithme. Au pire, ça va lui donner un morceau de code à utiliser bêtement sans le comprendre. Dans tous les cas, je doute qu'il prenne le temps de vraiment se creuser les méninges pour trouver l'algo seul.

[Nicolas_75]

Bonjour Garulfo,

Il y a plusieurs façons d'aider les gens :
(i) le mode "interactif" permettant progressivement de faire comprendre ;
(ii) le mode "direct" proposant une solution commentée qu'il convient ensuite de disséquer ;
(iii) autre...

Je privilégie souvent (i), même si ici j'ai utilisé (ii). La question est de savoir ce qui est le plus utile aux élèves ou aux personnes qui posent les questions. Après avoir (beaucoup) aidé sur les forums, en particulier en mathématique, il me semble qu'il n'y a pas de réponse évidente.

De plus, dans ce cas précis, Erwane avait déjà trouvé une solution (voir le 2ème message du fil). Mon but était plutôt de lui signaler l'existence d'une seconde solution (au cas où il n'en aurait trouvé qu'une), et de garder trace dans les archives du forum, au cas où quelqu'un se pose la même question.

Cordialement,

Nicolas

[Jedai]

De plus, dans ce cas précis, Erwane avait déjà trouvé une solution (voir le 2ème message du fil). Mon but était plutôt de lui signaler l'existence d'une seconde solution (au cas où il n'en aurait trouvé qu'une), et de garder trace dans les archives du forum, au cas où quelqu'un se pose la même question.

Dans ce cas, peut-être serait-il même plus profitable de signaler l'existence d'une fonction d'ordre supérieur incarnant précisément le schéma de récursion qu'on trouve dans ton "max-of-list2-aux" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(define (maximum L) (foldl max (car L) (cdr L)))

Encore que ce serait plus évident si ton "max-of-list2-aux avait été exprimé plus clairement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
(define (max-of-list2-aux current-highest rest-of-list)
  (if (null? rest-of-list)
      current-highest
      (max-of-list2-aux (max current-highest (car rest-of-list)) 
                        (cdr rest-of-list))))

On peut alors généraliser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
(define (fold-left f current rest-of-list)
  (if (null? rest-of-list)
      current
      (fold-left f (f current (car rest-of-list)) (cdr rest-of-list))))

Mettre des solutions pour la postérité, c'est bien, mettre des solutions claires c'est mieux.

--
Jedaï

[+Guilhem]

Mettre des solutions pour la postérité, c'est bien, mettre des solutions claires c'est mieux.

Mais la solution avec fold est-elle plus claire pour un débutant ? Pas sûr.

Personnellement je pense qu'il vaut mieux bien savoir traiter ce genre de problème avec les opérations de "base" avant de passer à ce genre de fonction d'ordre supérieur.
Ce n'est que mon avis d'étudiant ^^

[Nicolas_75]

Je trouve un peu surprenant de répondre aux questions des débutants avec des fold, et de tirer à boulets rouges sur ceux qui répondent à leurs questions. Je dois probablement être décalé par rapport au style de ce forum...

[Jedai]

Mais la solution avec fold est-elle plus claire pour un débutant ? Pas sûr.

Non, elle ne l'est pas, la solution la plus claire pour un débutant est la solution 1 proposé par Nicolas. Néanmoins quitte à pousser plus loin, autant montrer qu'il y a un schéma de récursivité sous-jacent à la solution 2. De plus il faut éviter de donner une fonction avec des complexités non-nécessaire, le if dans max-of-list-aux de Nicolas n'est pas nécessaire et obscurcit le schéma de récursion.

Personnellement je pense qu'il vaut mieux bien savoir traiter ce genre de problème avec les opérations de "base" avant de passer à ce genre de fonction d'ordre supérieur.
Ce n'est que mon avis d'étudiant ^^

C'est bien beau, mais ce forum n'est pas là que pour les tout débutants avec 4h de cours sous le bras... L'emploi de fonction d'ordre supérieur et en particulier l'encodage de schéma de récursion courant sur des types de données en des fonctions d'ordre supérieur est extrèmement important pour la programmation fonctionnelle. Tant qu'on ne réalise pas cela, on se gâche l'expérience fonctionnelle par de la récursion explicite et répétitive alors que l'un des avantage du fonctionnel est justement de faciliter l'abstraction de ces schémas récurrents.
fold et map sont des fonctions extrêmement courantes dans tous les langages fonctionnels, ils doivent faire partie des premiers cours dans un nouveau langage de ce paradigme.

Je trouve un peu surprenant de répondre aux questions des débutants avec des fold, et de tirer à boulets rouges sur ceux qui répondent à leurs questions. Je dois probablement être décalé par rapport au style de ce forum..

"Tirer à boulets rouges" ? Tu es bien sensible ! C'est parce que j'ai mis :

Mettre des solutions pour la postérité, c'est bien, mettre des solutions claires c'est mieux.

??
Ca ne me semble pas si extrême. Si tu ne cherches pas simplement à résoudre le problème du questionneur (ce qui était le cas ici puisqu'il avait déjà trouvé une réponse), mais à entreposer des réponses pour une future occasion, il faut faire un effort pour qu'elles soient les plus satisfaisantes possibles.

--
Jedaï

[Garulfo]

Je trouve un peu surprenant de répondre aux questions des débutants avec des fold, et de tirer à boulets rouges sur ceux qui répondent à leurs questions. Je dois probablement être décalé par rapport au style de ce forum...

Je ne voulais pas « tirer à boulets rouges » sur toi. Un(e) étudiant(e) n'apprend pas hélas quand il ou elle trouve la solution en ligne ! C'est pourquoi je te disais ça. La version de Jedaï peut provoquer chez l'étudiant(e) une incompréhension qui a) le mène à réflechir b) le mène à copier bêtement le code qui sera probablement non accepté par l'enseignant.

Quand tu dis que cela permettra justement à un(e) étudiant(e) d'avoir la réponse s'il ou elle se pose la même question c'est bien ce que je reproche.

J'ai aussi beaucoup aidé en math, en philo, en français, en histoire et en info. Et j'enseigne en math et en info. L'informatique a une différence sur les trois autres matières: les étudiant(e)s cherchent souvent moins à comprendre quand ils ont une solution. C'est un peu dommage mais c'est ainsi. La matière et l'enseignement font aussi ça puisque d'un autre côté ont leur apprend à réutiliser

Donc voilà pourquoi je suis en accord avec Jedaï. Je suis sûr que tu as fait ça dans un très bon esprit, mais hélas tu n'aiderais pas la personne qui lira ta solution la prochaine fois.

Et en plus, ce n'est pas le bon forum

[Nicolas_75]

Bonjour Garulfo,

J'ai bien lu ton message. Mon avis reste celui que j'ai exposé ci-dessus. Je ne tiens pas à polémiquer. Il est normal que nous ne soyons pas tous du même avis. Merci d'avoir pris le temps de me répondre.

Cordialement,

Nicolas