Pile et file triées, somme de deux éléments, cible
Le cadre
On dispose d'une pile et d'une file, non vides, d'éléments insérés dans l'ordre croissant.
On cherche à obtenir la somme d'un élément de la pile et d'un élément de la file la plus proche possible d'une cible donnée.
Exemples
la pile : | 10, 11, 13, 16, 20, 25, 31, 38 ↔
la file : ← 50, 60, 71, 82, 93, 104, 115 ←
la cible : 120
Parmi les sommes proches de la cible avec un élément de la pile et de la file, on a :
- \(10 + 115 = 125\) ; écart avec \(120\) : \(5\)
- \(13 + 104 = 117\) ; écart avec \(120\) : \(3\)
- \(16 + 104 = 120\) ; écart avec \(120\) : \(0\)
Ainsi, le plus petit écart entre la somme d'un élément de cette pile et de cette file avec la cible est \(0\).
la pile : | 100, 110, 130, 160, 200, 250, 310, 380 ↔
la file : ← 501, 602, 713, 824, 935, 1046, 1157 ←
la cible : 1200
Parmi les sommes proches de la cible avec un élément de la pile et de la file, on a :
- \(130 + 1057 = 1187\) ; écart avec \(1200\) : \(13\)
- \(160 + 1046 = 1206\) ; écart avec \(1200\) : \(6\)
- \(250 + 935 = 1185\) ; écart avec \(1200\) : \(15\)
- \(380 + 824 = 1204\) ; écart avec \(1200\) : \(4\)
- ... mais pas mieux que \(4\)
Ainsi, le plus petit écart entre la somme d'un élément de cette pile et de cette file avec la cible est \(4\).
Exercice 💥💥💥
Coder une fonction écart_mini_somme
- qui prend en paramètres :
une_pilenon vide de nombres entiers qui ont été insérés dans l'ordre croissant,une_filenon vide de nombres entiers qui ont été insérés dans l'ordre croissant,- une
ciblequi est un nombre entier,
-
et qui renvoie le plus petit écart entre une somme d'un élément de
une_pileet deune_fileavec lacible. -
une_pileest une instance d'une classePiledisponible dans cet exercice ayant les méthodes classiquesest_vide,empileetdépile. -
une_fileest une instance d'une classeFiledisponible dans cet exercice ayant les méthodes classiquesest_vide,enfileetdéfile. 
On attend un algorithme de cout linéaire en la somme des tailles des structures linéaires, et non en leur produit. Pour être simple et direct : on pourra dépiler et défiler tant que c'est possible et faire une opération à cout constant.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)