Rezolvarea problemelor
Ok, a trecut ceva timp, haideți să vin și cu un răspuns în privința întrebărilor de algoritmică pe care le-am postat zilele trecute.
Portocalele
Aveam 12 portocale și din 3 cântăriri trebuie să aflu care este cea mai ușoară.
În primul rând trebuie să împart portocalele în 3 grupe formate din 4 portocale fiecare.
Grup 1: 1 2 3 4
Grup 2: 5 6 7 8
Grup 3: 9 10 11 12
Cântăresc primele două grupe, notez înclinarea balanței și o să am două cazuri:
1. Grupele sunt egale, acesta este cazul favorabil, urmând să iau grupul 3 și să cântăresc 9 10 și 11 12. Notez care a atârnat mai grea sau mai ușor și fac o rocadă, cântăresc 9 11 și 10 12. Dacă balanța a atârnat în jos la 11 12 și după a atârnat în jos la 9 11, știu sigur că 11 e portocala diferită. Aceeași deducție și pentru restul cazurilor.
2. Grupele sunt inegale, știu sigur că pot să renunț la grupa 3 astfel că rămân cu portocalele 1 2 3 4 și 5 6 7 8. De dragul exemplului hai să zicem că 1 2 3 4 este cea care a atârnat mai greu.
Împart portocalele în următoarea sub grupă: 1 2 3 și 4 5 6 și le cântăresc:
1. Grupele sunt egale este clar că portocala 7 sau 8 este diferită și o pot afla prin a treia cântărire între o portocală de test și 7. Dacă acestea sunt egale 8 era portocala mea diferită, dacă sunt inegale atunci 7 e portocala diferită și pot să aflu dacă este și mai grea sau mai ușoară.
2. Grupele sunt inegale:
A. Dacă am balanța înclinată în aceeași direcția ca la prima cântărire știu sigur că în grupul 1 2 3 este portocala diferită și urmează cântărirea cu numărul 3: între 1 și 2. Dacă acestea sunt egale 3 este portocala mea și dacă 1 sau 2 înclină în jos aceea este aleasa.
B. Dacă am balanța înclinată diferit față de prima cântărire știu sigur că portocala diferită este cea care a ajuns în alt grup, adică portocala 4. Nemaiavând nevoie de o a 3-a cântărire.
Pălăriile lui Molly, Polly și Curly
Întrebarea aia în care am 3 pălării negre, 2 albe, Molly vede ce pălărie are Polly și Curly, Polly vede ce pălărie are Curly și Curly nu vede nimic. Întrebarea completă dând click aici.
Răspunsul:
Dacă Polly și Curly ar fi avut pălării albe, Molly ar fi știut răspunsul. Anume că are pălăria neagră, dar cum nu știut răspunsul există două posibilități: Polly și Curly fie au pălării negre și fie o pălărie albă și una neagră.
Curly dacă ar fi văzut în fața lui pălăria albă și știind că Molly nu a dat un răspuns concret putea să deducă că el are în cap pălăria neagră, dar cum nici acesta nu a știut răspunsul rezultă că Dl Curly avea o pălărie neagră de toată frumusețea 🙂
Cutiile poștale
Problema în care Ion era pus pe șotii, avea multă energie și a făcut 100 drumuri prin cartier să închidă și să deschidă cutiile poștale. Problema o găsiți aici.
Răspunsul:
Am aplicat un for și o metodă recursivă:
class cutia
{
int open;
int poz;
}
cutia[] cutie=new cutia[100];
void main()
{
RunIonRon(0);
foreach (cutia c in cutia)
{
if (c.open==1) open++ else close++;
}
Console.WriteLine(“Am {0} cutii deschise și {1} cutii închise”, open, close);
}
//Realizez că puteam afla nr de cutii închise scăzând din 100 nr cutii deschise, dar nu mi-am dat seama în momentul rezolvării.
RunIonRun(int j)
{
if (j<100)
{
for (int i=0+j;i<n-1;i+1+j)
{
if (cutia[i].open==1) cutia[i].open=0 else cutia[i].open=1;
}
RunIonRun(j+1);
}
}
By: Adrian Coman
