Целочислена оптимизация

Как бихте решили тази задача?

Един цар имал изба с 1000 бъчви отбрано вино. За беда, в един момент от сигурен източник научил, че една от бъчвите е отровена от враговете му. Отровата действа след седмица и е смъртоносна, дори при минимално количество вино.

След 10 дни на царят му идвали гости, които искал да почерпи с вино от избата. Царят е готов да пожертва няколко верноподаника, за да установи преди това коя е отровната бъчва, и да може да точи безопасно от другите. В ролята на велик везир, трябва да го посъветвате как да подходи, така че при "дегустацията" да изложи на риск най-малко на брой хора, да кажем не повече от 10 затворника.

Zadachata mozhe da se reshi s ne poveche ot 10 opita (max 10 martvi zatvornici), ako bachvite sa <= 2^10=1024.

Algoritamat e sledniat: Smesvash malko vino ot 500 bachvi i go davash za proba. Ako zatvornikat umre - otrovenoto vino e niakade v tezi 500, a ako otzelee - v ostanalite 500. Sled tova se vzemat 500-te bachvi, koito sadarzhat otrovenata bachva, razdeliat se na dve grupi po 250, smesva se vinoto i t.n. dokato se opredeli tochno koia e otrovenata bachva.

Pozdravi.

Почти си прав, щото както пише в задачката, отровата действа след седмица. Ма решението се адаптира лесно, де. Номерираме бъчвите от 1 до 1000 и има записваме норемцата в двойчен запис. После фащаме 10 затворника и на всеки (да кажем, номер x) му даваме да пие от една бъчва ако и само ако в номера на тая бъчва x-тата цифра е 1. След тва гледаме кой ше овивее след седмица. Така де, ако не умрат сичките още следващия ден, шото да пробваш 500 бъчви не си е шега работа.

Решението е хубаво, но непрактично. Тъй като целта е да не си изтрови гостите и да спести колкото може повече хора, най-добро решение (на проблема-не на задачата) е да нареди колкото хора има дето не му пука за тях-N на първите N бъчви. Ако никой не умре след седмица, поне ще имат достатъчно количество проверено пиене гостите. А пък вполседствие ще си ги допровери по същия начин и след време ще си реши проблема само с една жертва и доста по-малко хамалогия

Предлагам нещо, дето ми се струва по-бързо сходящо....
1. Раздела бъчвите на 10 стотици и ги номерира. Ползва всичките десет затворници за първи тест.
2. Умира един(без да е изложил на риск повече) и фиксира "отровна" стотица.
3. Разпределя на останалите 9 човека стоте бъчви, например 8*11 и една 12-ка - номерира и тества. Остават 8 човека и 11 или 12 бъчви.
4....... с много голяма вероятност ще отрови не повече от 4!! До колкото сметнах, вероятността да тровне 4-ма е 29.4%, иначе казано една радостна преспектива на фона на затриването на 10 човека

а защо все пак не пишеш че си взел задачката от форум програмисти та поне ако някой иска да може да прочете и там...

пп. там има около 100ина мнения по тази задачка

Join the dark side, and get a free cookie.