Diferențe pentru problema/iepurasi1 între reviziile #16 si #17

== include(page="template/taskheader" task_id="iepurasi1") ==

_[*Notă importantă*]: problema este o variantă a unei probleme clasice, numită ["pancake sorting":https://en.wikipedia.org/wiki/Pancake_sorting]. Această problemă este ["NP-hard":https://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html], deci, evident, nu are ce căuta la clasa a cincea, sau, ca idee, la nici o clasă, întrucât omenirea nu cunoaște un algoritm polinomial pentru această problemă. _

_[*Notă importantă*]: problema este o variantă a unei probleme clasice, numită ["pancake sorting":https://en.wikipedia.org/wiki/Pancake_sorting]. Această problemă este ["NP-hard":https://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html], deci, evident, nu are ce căuta la clasa a cincea, sau, ca idee, la nici o clasă, întrucât omenirea nu cunoaște un algoritm polinomial pentru această problemă. Faptul că ea a fost dată la ONI clasa a 5-a arată lipsa de competență a comisiei. În fapt, comisia a fost, la acel moment, prevenită că problema este NP-hard, dar au ales să ignore acest lucru cu mențiunea "noi nu știm ce e aia"._
 
_Dacă aveți îndoieli în legătură cu cele spuse mai sus, să considerăm următorul exemplu:
 
$1 2 5 3 4$
 
Dacă sortăm numerele descrescător conform soluției comisiei, un select sort în care la fiecare pas mutăm maximul la coadă și apoi îl punem pe poziție, vom obține cinci pași (am îngroșat numerele pe care facem operația [*tap*]):
 
$1 2 *5* 3 4$
$*1* 2 4 3 5$
$5 3 *4* 2 1$
$5 *3* 1 2 4$
$5 4 *2* 1 3$
$5 4 3 2 1$
 

!>problema/iepurasi1?problema_iepurasi.png!