Problem d algo : ordonner une file en utilisant des fct file (push ..)

Marsh Posté le 26-09-2003 à 10:40:16

je dois decrire l algo en c++ et apres avoir cogiter quelque peu je n avance pas [:dams86]

file q
8, 3, 5, 1, 9, 2

deviens (ordre croissant)
1, 2, 3, 5, 8, 9

je dois utiliser que des operation file
c est a dire push pop front et empty.

une aide serez la bienvenue
(aidez un pauvre n etudiant francais exile en australie)

Message édité par xiluoc le 26-09-2003 à 11:08:57

---------------
jeunes con de la derniere averse, vieux con des neiges d'antant.

Reply

Marsh Posté le 26-09-2003 à 10:40:16

Reply

Marsh Posté le 26-09-2003 à 11:05:01

ben parle français, on capte rien à tes histoires de queue, pop,front,push et après tu nous parle de liste...

Reply

Marsh Posté le 26-09-2003 à 11:07:12

Taz a écrit :

ben parle français, on capte rien à tes histoires de queue, pop,front,push et après tu nous parle de liste...

arf j ai confondu liste et file je corrige tt de suite

---------------
jeunes con de la derniere averse, vieux con des neiges d'antant.

Reply

Marsh Posté le 26-09-2003 à 11:17:23

ben t'es parti pour faire du récursif. commence par faire un algo pour insérer un élément en respectant l'ordre, ensuite, tu n'auras plus qu'a faire des insertions

Reply

Marsh Posté le 26-09-2003 à 11:46:26

Taz a écrit :

ben t'es parti pour faire du récursif. commence par faire un algo pour insérer un élément en respectant l'ordre, ensuite, tu n'auras plus qu'a faire des insertions

insertion ? dans une file ? je peu pas amsi j ai une piste.

exemle :
8, 3, 5, 1, 9, 2

Code :

temp1 = q.front();
q.pop();
temp2 = q.front();

queue temp

8>3 ? oui -> temp.push(3)
q.pop()
temp2=q.front()
8>5 ? oui -> temp.push(5)
..
8>1 ? oui -> temp.push(1)
..
8>9 ? nan -> temp.push(8)
temp1=temp2
q.pop()
temp2=q.front()
9>2 ? oui -> temp.push(2)
q.pop()
is empty ? yes
q.push(9)

et je me retrouve avec 3,5,1,8,2,9
je recommence ce processus jusque ce que ca soit ranger

:sweat:

---------------
jeunes con de la derniere averse, vieux con des neiges d'antant.

Reply

Marsh Posté le 26-09-2003 à 11:50:16

ensuite tu pourras passer en itératif...

si tu lis le fonctionnel (ici Scheme) ...
(car l) -> premier élément
(cdr l) -> l moins le premier élément
(null? l) -> l est vide
(cons e l) -> ajoute e en premiere position
(cons_en_fin l e) -> ajoute e en dernière position (ici le langage me donne cons, j'ai donc créer cons_en_fin, avec une file c'est l'inverse, facile à faire quoi)
(dernier l) -> dernier élément
(ajout l1 l2) -> ajoute les éléments de l2 à la suite de l1

etc...

(define dernier
(lambda (l)
(if (null? (cdr l)) (car l) (dernier (cdr l)))
))

(define cons_en_fin
(lambda (l elem)
(if (null? l) (list elem) (cons (car l) (cons_en_fin (cdr l) elem)))
))

(define ajout
(lambda (l1 l2)
(cond ((null? l1) l2)
((null? l2) l1)
(else (ajout (cons_en_fin l1 (car l2)) (cdr l2)))
)
))

(define insertion_ordonnee
(lambda (l elem)
(letrec ((aux (lambda (l elem debut)
(cond ((null? l) (cons_en_fin debut elem))
((< (car l) elem) (aux (cdr l) elem (cons_en_fin debut (car l))))
(else (ajout (cons_en_fin debut elem) l))
)
)
))
(aux l elem `())
)
))

(define tri
(lambda (l)
(letrec ((aux (lambda (l res)
(if (null? l) res (aux (cdr l) (insertion_ordonnee res (car l))))
)
))
(aux l `())
)))

(display (tri `(1 5 3 -10 4 42 69 1983 0 5 4 3)))
(newline)

Reply

Problem d algo : ordonner une file en utilisant des fct file (push ..)

Sujets relatifs:

Leave a Replay