Problema de alogritmica

8 Comments

1. 

   mihneasim

   7 October 2009 at 20:44

   Diferita in sensul ca.. stii ca e mai mare sau mai mica?

   Daca stii cum e, intai cantaresti 6 cu 6 si alegi gramada mai grea/mai usoara, in fctie de ipoteza.
   Apoi 3 cu 3 din aia, si iar, alegi gramada mai grea sau mai usoara. Si apoi, cand ramai cu 3, o cantarire este suficienta.

   Daca nu stii daca e mai grea sau mai usoara decat restul, nu cred ca are solutie.
2. 

   necenzurat

   7 October 2009 at 20:49

   nu stii care este, mai grea sau mai usoara doar diferita
3. 

   Auras

   7 October 2009 at 20:51

   Cum a zis Mihneasim mai sus 🙂
4. 

   mihneasim

   7 October 2009 at 20:55

   Problemele astea de cantariri se bazeaza pe cautarea binara, care au solutie in log n. Log 12 este intre 3 si 4, deci sunt suficiente 3 cantariri (pasul al 4-lea reprezinta gasirea solutiei prin eliminare).
   Trebuie sa ai o relatie de ordine intre elemente (adica clasa obiectelor sa implementeze interfata Comparable :D).
5. 

   lore

   7 October 2009 at 20:57

   problema de romano americana
6. 

   Andrei

   7 October 2009 at 21:32

   – Cantaresti 4 cu 4:
   – daca sunt egale, ai redus problema la 4 portocale, 2 cantariri
   – daca NU sunt egale, ai redus problema la 8 portocale, plus 4 portocale “de control” (despre care stii ca sunt bune)
   – scoti 3 de pe al 2-lea brat; scoti 3 de pe primul brat si le muti pe a al 2-lea brat; pe primul brat pui 3 portocale bune:
   – daca balanta inclina la fel, ai redus problema la 2 portocale (cele care au ramas la locul lor, cate una pe fiecare balanta)
   – daca balanta se echilibreaza, ai redus problema la 3 portocale (cele pe care le-ai scos de pe al 2-lea brat) + informatia daca portocala suspecta este mai grea sau mai usoara (de la cantarirea anterioara – functie de cum indica atunci al 2-lea brat)
   – daca balanta isi schimba inclinatia, ai redus problema la cele 3 portocale pe care le-ai mutat de pe primul pe al 2-lea brat + informatia daca portocala suspecta este mai grea sau mai usoara (functie de cum s-a schimbat balanta -/+ sau +/-)

   – Problemele ramase sunt ceva mai intuitive:
   – 4 portocale, 2 cantariri
   – 2 portocale, 1 cantarire
   – 3 portocale, 1 cantarire, informatia daca portocala suspecta este mai grea sau mai usoara

   Don’t shoot if I’m wrong 🙂
7. 

   bruno

   7 October 2009 at 21:40

   Ar trebui sa fie simplu si banal. E derutant ca nu se stie daca este mai grea sau mai usoara.
   Daca as sti daca este mai usoara/grea, as cantari 4 portocale contra 4. Daca sunt egale as continua cu restul, 2 portocale contra 2. As alege portocalele mai grele/usoare pentru ultima cantarire si ar fi o portocala contra una.
   Daca la prima cantarire, 4 portocale contra 4, nu sunt cantitati egale, iau cantitatea mai grea/usoara si o sparg in 2 portocale contra 2 si ajung sa repet a treia cantarire ca mai sus.
   Cu conditia sa stiu daca este mai grea sau mai usoara acea portocala.
8. 

   Tudor Popa

   7 October 2009 at 23:45

   Solutia e urmatoarea:

   Se presupune ca stim dinainte ca portocala respectiva e mai usoara sau mai grea(una din cele doua). Presupunem ca portocala e mai grea decat celelalte.

   Notam cu c = nr cantariri.

   c = 0;

   1) Cantarim 5 si 5. c = 1
   1.1) Daca greutatea e egala raman 2 portocale pe care le cantarim si o gasim pe cea mai grea(=portocala cautata). c = 2

   1.2) Daca greutatea e inegala
   1.2.1) luam cele 5 portocale mai grele
   1.2.2) cantarim 2 si 2 dintre ele. c = 2
   1.2.3) luam cele 2 portocale mai grele
   1.2.3.1) le cantarim si o gasim pe cea mai grea(=portocala cautata) c = 3
   1.2.4) Daca cele 2 grupe de portocale au greutatea egala => portocala cautata e cea ramasa

   Nr maxim de cantariri = 3. Solutie gasita!