Máme 12 na pohľad identických guličiek, o ktorých vieme, že 11 z nich má rovnakú hmotnosť a jedna má hmotnosť inú (pričom nevieme, ktorá z nich to je a tiež nevieme, či je ľahšia, alebo ťažšia ako zvyšné guličky). Tiež máme k dispozícii klasickú váhu s dvomi miskami, ktorá vie ukázať len 3 rôzne výsledky: 1) Obsah ľavej misky je ťažší ako obsah pravej misky; 2) Obsah pravej misky je ťažší ako obsah ľavej misky; 3) obsah na oboch miskách je presne rovnako ťažký. Aký je najmenší počet vážení, ktorý nám umožní identifikovať, ktorá gulička je odlišná a aj určiť, či je ťažšia, alebo ľahšia?
Dovolím si tvrdiť, že tento klasický problém by sa podarilo vyriešiť skoro každému, ak by bol dostatočne trpezlivý. Zaujímavé je ale predovšetkým to, či je možné nájsť systematický spôsob hľadania optimálneho, alebo aspoň "dobrého" riešenia podobných úloh, ktorý je schodnejší než vyčerpanie všetkých možností. Máte nejaké návrhy?
1 komentár:
Zdravim,
napadlo mi riesenie pre ulohu s n gulickami , pricom
jedna z nich je tazsia alebo lahsia.
nech 1..n su indexy guliciek. hladam index h ,
ktory najde hladanu gulicku - tazsiu alebo lahsiu ako ostatne.
Vazenie je reprezentavane funkciou odvaz(A,B),
pricom A je mnozina indexov na lavej strane, B na pravej strane vahy.
Tato funkcia moze vratit -1,0,1 ak lava strana je lahsia, rovnaka, tazsia.
napadol mi algoritmus s zlozitostou O(lg(N)) vzhladom na pocet odvazeni:
-zavolam funkciu G({1..n});
//
//G je mnozina indexov od 1 po n, oznacenych g_1 .. g_p, kde p=|G|
//vrati 0, ak sa z danej mnoziny nepodarilo usudit, ktora je hladana gulicka,
//inak vrati index hladanej gulicky
//
//predpokladam, ze |G| >= 2
//
spracuj(G){
p = |G|;
if(p je parne){
ak (p == 2){
x=odvaz(g_1,g_2);
if(x!=0){
nech 1<=t<=n pricom (t != g_1 and t != g_2)
if(odvaz(t,g_1)==0){
return g_2;
}else{
return g_1;
}
}else return 0;
}else{
nech A=g_1 .. g_{p/2};
nech B=g_{p/2+1}..g_p;
x=odvaz(A,B);
if(x!=0){
x=spracuj(A);
if(x=0)return spracuj(B);
else return x;
}else return 0;
}
}else{
nech A = g_1 .. g_{p-1};
x1=spracuj(A);
if(x1>0)return x1;
else{
return spracuj(A - {g_1} +{g_p});
}
}
}
Zverejnenie komentára