|
Тема
|
Целочислена оптимизация
|
|
Автор | TOPOИД (Нерегистриран) |
Публикувано | 27.10.04 18:06 |
|
Как бихте решили тази задача?
Един цар имал изба с 1000 бъчви отбрано вино. За беда, в един момент от сигурен източник научил, че една от бъчвите е отровена от враговете му. Отровата действа след седмица и е смъртоносна, дори при минимално количество вино.
След 10 дни на царят му идвали гости, които искал да почерпи с вино от избата. Царят е готов да пожертва няколко верноподаника, за да установи преди това коя е отровната бъчва, и да може да точи безопасно от другите. В ролята на велик везир, трябва да го посъветвате как да подходи, така че при "дегустацията" да изложи на риск най-малко на брой хора, да кажем не повече от 10 затворника.
| |
Тема
|
Re: Целочислена оптимизация
[re: TOPOИД]
|
|
Автор | puzzled (Нерегистриран) |
Публикувано | 27.10.04 19: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 бъчви не си е шега работа.
| |
Тема
|
още едно допълнение
[re: Nedev]
|
|
Автор |
Пaлячo () |
Публикувано | 07.11.04 16:22 |
|
Решението е хубаво, но непрактично. Тъй като целта е да не си изтрови гостите и да спести колкото може повече хора, най-добро решение (на проблема-не на задачата) е да нареди колкото хора има дето не му пука за тях-N на първите N бъчви. Ако никой не умре след седмица, поне ще имат достатъчно количество проверено пиене гостите. А пък вполседствие ще си ги допровери по същия начин и след време ще си реши проблема само с една жертва и доста по-малко хамалогия
| |
Тема
|
Re: Нещо по-сходящо.....
[re: TOPOИД]
|
|
Автор |
Reptile (REAPER) |
Публикувано | 11.11.04 10:37 |
|
Предлагам нещо, дето ми се струва по-бързо сходящо....
1. Раздела бъчвите на 10 стотици и ги номерира. Ползва всичките десет затворници за първи тест.
2. Умира един(без да е изложил на риск повече) и фиксира "отровна" стотица.
3. Разпределя на останалите 9 човека стоте бъчви, например 8*11 и една 12-ка - номерира и тества. Остават 8 човека и 11 или 12 бъчви.
4....... с много голяма вероятност ще отрови не повече от 4!! До колкото сметнах, вероятността да тровне 4-ма е 29.4%, иначе казано една радостна преспектива на фона на затриването на 10 човека
| |
Тема
|
Re: Целочислена оптимизация
[re: TOPOИД]
|
|
Автор |
qwe222 () |
Публикувано | 12.11.04 16:30 |
|
а защо все пак не пишеш че си взел задачката от форум програмисти та поне ако някой иска да може да прочете и там...
пп. там има около 100ина мнения по тази задачка
Join the dark side, and get a free cookie.
| |
|
|
|
|