ważenie różnych przedmiotów...

dagoth · Post autor: **dagoth** » 22 maja 2005, o 06:54

Mając do dyspozycji wagę szalkową bez odważników należy ustawić w kolejności od najlżejszego do najcięższego cztery przedmioty. Ile ważeń trzeba będzie wykonać?

A jeśli mamy pięć przedmiotów?

kaarol · Post autor: **kaarol** » 22 maja 2005, o 11:49

Co do tych 4 roznych worków to wystarczy wykonac 3 odwazania podpowiedz najpierw kładziemy dwa pierwsze worki na jedna szalke potem kładziemy 2 ostatnie worki na druga szalkę i w zaleznosci od wyniku biezemy odpowiedznie worki. Jak bede miał czas toto moge rozrysowac.

dagoth · Post autor: **dagoth** » 22 maja 2005, o 12:37

hmmm...nawet nie wiedzialem ze te przedmioty to worki
co do wazen to chodzi o najmniejsza liczbe wazen w najgorszym przypadku...

Post autor: **DEXiu** » 22 maja 2005, o 13:02

Strzelam: dla 4 przedmiotów 6 ważeń a dla 5 - 10 ważeń. Zgadza się?

dagoth · Post autor: **dagoth** » 22 maja 2005, o 14:26

DEXiu pisze:Strzelam: dla 4 przedmiotów 6 ważeń a dla 5 - 10 ważeń. Zgadza się?

strzelasz?...mozna mniej...

droopy · Post autor: **droopy** » 22 maja 2005, o 15:44

to jest typowe zagadnienie z algorytmiki
ustawianie elementów tablicy w porządku, z tego co pamiętam jakiś algorytm miał złożoność obliczeniową równą n log n
czyli dla 4 przedmiotów wychodzi: 3
a dla 5: 4

dagoth · Post autor: **dagoth** » 22 maja 2005, o 16:01

droopy:tyle wazen otrzymasz tylko przy wielkim szczesciu...chodzi o "pewna na 100% liczbe wazen" ale najmniejsza....

droopy · Post autor: **droopy** » 22 maja 2005, o 16:49

rzeczywiście, pomyliłem się, taką złożoność osiągaja przy "odrobinie" szczęścia algorytm "dziel i zwyciężaj", a jego pesymistyczna złożoność wynoci trochę ponad 2n*log(n), więc dla 4: 5 a dla 5: 8

opis metody
mamy 4 elementy, dzielimy je na 2 ciągi po 2
te dwie ciągi ustawiamy w kolejności - (2 porównania)
i teraz porównujemy pierwsze elementy z obu grup i lżejszy stawiamy w nowym ciągu - (1)
znowu porównujemy pierwsze elementy (ale jeden ciąg ma już tylko jeden element) - (1)
i ten krok ni zawsze będzie: znowu porównanie na tej samej zasadzie - (1)
czyli łącznie 5 porównań

analogicznie dla 5 elementów wyjdzie 8 porównań

jest jeakiś prostszy sposób??

dagoth · Post autor: **dagoth** » 22 maja 2005, o 17:17

gratz...
a sposób prostrzy?...hmmm:
4 przedmioty:
1. 1 z 2
2. ciezszy z 3
3. jesli ciezszy jest 3 to z 4 a jesli lzejszy to z najlzejszym z pierwszego wazenia
4. 4 z tym co ma srednia wage
5. jesli czwarty byl lzejszy to wazymy z najlzejszym a jesli ciezszy to z najciezszym...
z piecioma przedmiotami dodatkowo:
6. 5 z 2 co do wagi
7. jezeli 5 byl lzejszy to z najlzejszym a jak byl ciezszy to z najciezszym
8. jesli 5 byl ciezszy od najciezszego to ok a jak lzejszy to 3 co do wagi, jesli byl lzejszy od najlzejszego to ok a jak ciezszy do z 3 co do wagi....
czy prostrzy sposob to nie wiem ...ja tak robilem...