Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.3k comentarii

2.5k utilizatori

2 plusuri 0 minusuri
270 vizualizari
Sunt in Dubai, in Burj Khalifa. Finlandezii ma plac, deci am primit doua telefoane Nokia identice, despre care stim cu totii cat de rezistente sunt. Stiu ca exista un etaj k intre 0 si 100 inclusiv, de unde daca arunc un telefon se sparge. De la toate etajele de sub k, telefoanele nu se sparg, de la toate etajele de peste k, telefoanele se sparg. Precizez ca pot arunca cu telefoanele de cate ori am chef, de la orice etaj intre 1 si 100, atat timp cat nu sunt sparte.

Care este algoritmul optim(cel care presupune un numar minim de aruncari) pentru a determina numarul k?
Novice (339 puncte) in categoria Matematica
editat de
0 0
După ce criteriu un algoritm e mai bun decît altul?
0 0
Algoritmul optim este cel care presupune un numar minim de aruncari. Am editat acum

1 Raspuns

3 plusuri 0 minusuri
 
Cel mai bun raspuns

Se aruncă primul telefon de la un etaj, să-i spun j. Dacă se sparge atunci pentru a determina etajul k, cel de-al doilea telefon ar trebui aruncat de j-1 ori de la etajele inferioare. Dacă nu se sparge , urcăm şi aruncăm primul telefon de la etajul j + (j-1) şi remarcăm starea lui. Tot aşa se ajunge la : 1+ .....+ j = 100 => j ~= 14. Deci testarea telefoanelor trebuie începută de la etajul 14 şi numărul maxim de încercări pentru a-l detecta pe k  este tot 14. 

Experimentat (4.8k puncte)
selectat de
0 0
Felicitari, Gheorghita! Solutia ta e cea optima, ar mai putea fi detaliata un pic, dar merge. Trebuie sa recunosc, sunt extrem de placut surprins. Eu am gasit greu algoritmul asta, mult timp am crezut ca un alt algoritm cu numar maxim de aruncari 19 este cel mai bun posibil. Daca site-ul asta era mai activ un pic, m-as fi asteptat la multe incercari nereusite pana la un raspuns corect, ma mira ca primul raspuns este cel bun. Spune-mi, stiai cumva problema?
0 0

Mi-a luat ceva timp, nu am găsit soluţia hop-ţop. Iniţial, eram convinsă că sînt 19, ba chiar şi 20 de încercări, dar am remarcat că insistaţi pe un algoritm optim, aşa că am insistat şi eu.

...