Страница 1 от 2 12 ПоследноПоследно
Резултати от 1 до 15 от общо 22

Задача 154 ( Изкуплението Шоушенк 23 )

Сподели във Facebook Сподели в Twitter Изпрати на Email Сподели в LinkedIn
  1. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #1

    Задача 154 ( Изкуплението Шоушенк 23 )

    Ако сте чели за този случай, ще се сетите лесно, иначе трябва да помислите.

    <style type='text/css' id='bigchar'> #BIGCHAR {background: black; color: white; font-size: 16pt; } </style><SPAN ID='bigchar'>Н</SPAN id='bigchar'>адзирателят на отделението за осъдените за измами събрал всичките двадесет и трима затворници и им съобщил правилата на играта. Неговите правила на неговата игра.



    <style type='text/css' id='bigchar'> #BIGCHAR {background: black; color: white; font-size: 16pt; } </style><SPAN ID='bigchar'>С</SPAN id='bigchar'>поделил им, че за пръв и последен път ги събира заедно и от този ден нататък всеки отива в единична изолирана килия, без канал за комуникация с другите.

    <style type='text/css' id='bigchar'> #BIGCHAR {background: black; color: white; font-size: 16pt; } </style><SPAN ID='bigchar'>Р</SPAN id='bigchar'>азказал им за така наречената "стая с ключове", където имало два ключa "A" и "B" (стандартни и двата, с позиции on и off), които странно защо не включвали нито една лампа.



    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote"><h5>"От днес насетне, от време на време, когато ми хрумне ще вземам един случайно избран затворник със себе си и ще го водя до "стаята с ключовете", където той <u>трябва</u> да превключи единия от тях(който си избере, ако е на on в off и обратно). После ще го върна в килията му и никой няма да влиза в стаята, докато не реша да заведа следващия от вас. Всеки един ще влизa в стаята прозволен брой пъти, но ви грантирам, че за всяко N, ще е в сила, че всеки един от вас е влизал поне N пъти!"</h5></td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



    <style type='text/css' id='bigchar'> #BIGCHAR {background: black; color: white; font-size: 16pt; } </style><SPAN ID='bigchar'>Н</SPAN id='bigchar'>акрая надзирателят направил драматична пауза, след което с лукава усмивка казал на затворниците, че във всеки един момент някой от тях има право да заяви, че всичките двадест и трима свободолишени са минали през "стаята с ключовете"... разбира се, с условието, че ако това е наистина вярно, ще ги пусне до един. Ако се окаже, че не е - остават заключени завинаги!



    Не забравяйте, че те били събрани за пръв и последен път заедно (а и естествено са невинни до един). Ако сега не измислят стратегия, която да им гарантира свободата, няма кога! ... но как?

  2.  
     
  3. Senior Member
    Тук е от
    Dec 2004
    Мнения
    1,563
    #2

    Задача 154 ( Изкуплението Шоушенк 23 )

    В условието има нещо, което не ми е ясно:

    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">че за всяко N, ще е в сила, че всеки един от вас е влизал поне N пъти</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



    Затова ще предложа следното решение (работещо, но отнемащо много време):

    1. Приемаме, че ключ А е в положение OFF в началото.*

    2. Затворниците избират един от тях за "брояч".

    3. Всеки, с изключение на Брояча, превключва А в ON, когато го види за първи път OFF. При всички останали посещения в стаята си играе с ключ В.

    4. Броячът превключва А в OFF всеки път, когато го види ON. При всяко друго посещение си играе с В.

    5. След като види ключ А 22 пъти в ON, Броячът се сеща, че всички останали затворници са се изредили да го включат по веднъж.



    *Ако ключ А е ON, затворниците го изключват по веднъж, а Броячът го включва на същия принцип.



    Сигурен съм, че има много по-добро решение. Въпрос на оптимизация. Предполагам, че условието за N предназначено за тази цел.


  4. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #3

    Задача 154 ( Изкуплението Шоушенк 23 )

    @Edin_Lud, условието, което те смущава гарантира, че след време всеки един затворник е посетил стаята колкото всеки друг.



    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">следното решение (работещо, но отнемащо много време)</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    отнема врема, да. Но не успеят ли, ще имат цялото време на света да останат насаме с мислите си, къде са сбъркали.




  5. Senior Member Аватара на Bibi
    Тук е от
    Nov 2004
    Мнения
    2,757
    #4

    Задача 154 ( Изкуплението Шоушенк 23 )

    Не виждам нищо смущаващо в решението, предложено от Edin_Lud.

    Освен ако пръвоначалното положение на ключовете е неизвестно на затворниците.

    Тогава може би трябва да модофицираме малко метода.

    Например никой да няма право да пипа "контролния ключ", докато не го намери в състояние, различно от това, в което той е бил при първото му посещение в стаята.

    Броячът ще влиза няколко пъти, без да го пипа. Ако прави това достатъчно дълго, след време ще е сигурен, че всеки поне веднъж е видял (и запомнил) в какво състояние е стартирала задачата. (така аз разбирам условието за N).

    След като се увери, ще го промени, с което ще даде СТАРТ на стратегията.

  6. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #5

    Задача 154 ( Изкуплението Шоушенк 23 )

    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Освен ако пръвоначалното положение на ключовете е неизвестно на затворниците.</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    @Bibi, pазбира се, че никой не го знае, дори и аз, иначе щах да го съобщя.



    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">

    Тогава може би трябва да модифицираме малко метода.

    ...

    Броячът ще влиза няколко пъти, без да го пипа. Ако прави това достатъчно дълго, след време ще е сигурен, че всеки поне веднъж е видял (и запомнил) в какво състояние е стартирала задачата. (така аз разбирам условието за N).

    След като се увери, ще го промени, с което ще даде СТАРТ на стратегията.

    </td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    Дали ще има основания да е сигурен не зная. Може би ще е нетърпеллив. Права си, че ако чака достатъчно дълго, преди да почне да брои (дори и ако е по-дълго от присъдата му [:D]) е вероятно да са минали всичките и с тази страгетия може и да стане. Само, че не знае колко дълго.

    ...трябва да има начин 'Брояча', да знае момента, в който със сигурност всеки е посетил стаята.


  7. Member
    Тук е от
    Sep 2004
    Мнения
    633
    #6

    Задача 154 ( Изкуплението Шоушенк 23 )

    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Не виждам нищо смущаващо в решението, предложено от Edin_Lud.

    Освен ако пръвоначалното положение на ключовете е неизвестно на затворниците.

    Тогава може би трябва да модофицираме малко метода.

    Например никой да няма право да пипа "контролния ключ", докато не го намери в състояние, различно от това, в което той е бил при първото му посещение в стаята.

    Броячът ще влиза няколко пъти, без да го пипа. Ако прави това достатъчно дълго, след време ще е сигурен, че всеки поне веднъж е видял (и запомнил) в какво състояние е стартирала задачата. (така аз разбирам условието за N).

    След като се увери, ще го промени, с което ще даде СТАРТ на стратегията.



    <div align="right">Originally posted by Bibi - 28/01/2005 : 15:00:39</div id="right">

    </td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    Не ми харесва това "достатъчно дълго време". А ако всеки има право три пъти да превключи от оф на он, няма ли "броячът" да е сигурен, че всеки е влизал, след като види 65 пъти он? Т.е. броячът си действа по алгоритъма на Един_луд, но с тройна подсигуровка.

  8.  
     
  9. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #7

    Задача 154 ( Изкуплението Шоушенк 23 )

    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">А ако всеки има право три пъти да превключи от оф на он, няма ли "броячът" да е сигурен, че всеки е влизал, след като види 65 пъти он?</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



    [Wow!]

    Най-накрая някой да ги накара и другите да преброят нещичко. така, де! те до сега само щракаха ключа и чакаха месията да ги изкара навън.

    Само че, не можа да ме убедиш, че няма да изгният по една или друга причина. []

  10. Banned
    Тук е от
    Sep 2003
    Мнения
    1,313
    #8

    Задача 154 ( Изкуплението Шоушенк 23 )

    Не е ли време за жокерче?

  11. Member
    Тук е от
    Sep 2004
    Мнения
    633
    #9

    Задача 154 ( Изкуплението Шоушенк 23 )

    Драги mitkko,

    Вероятно влагаш в това N нещо, което не сме разбрали.

    Значи ли това, че никой няма да влезе в стаята втори път, преди всички да са пребивавали там по един път, трети път, преди всички да са били по два пъти и т.н.

    Ако е така, задачата изглежда много по-лесна от тази, над която се мъчим...

    С уважение чакам отговор.

  12. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #10

    Задача 154 ( Изкуплението Шоушенк 23 )

    добре. Признавам, че е малко мъглива формулировката на въпросното N, но да речем, че това ми е по силите.



    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Значи ли това, че никой няма да влезе в стаята втори път, преди всички да са пребивавали там по един път, трети път, преди всички да са били по два пъти и т.н.</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    не значи. В противен случай не е задача, а броене. Може един човек да влезе пореден брой пъти, но пък след известен период от време време всички ще са влизали поне даден брой пъти. Едва ли успях да го направя по-ясно, dedis, но аз си мислех, че ти специално почти си я разгдал като ги накара всичките да броят. Само да на беше толкова предпазлив в цифрите []

  13. Senior Member
    Тук е от
    Dec 2004
    Мнения
    1,563
    #11

    Задача 154 ( Изкуплението Шоушенк 23 )

    Сега видях, че при първия си отговор съм приел, че затворниците знаят пътрвоначалното положение на ключовете. Щом не го знаят решението не е по-сложно. Просто всички включват точно по два пъти, а Броячът брои до 43. Тогава е сигурен, че всеки е включвал поне по веднъж. Това решение е 100% успешно, но е добре затворниците да са дълголетници или уникални късметлии.



    [EDIT] - докато изкоментирам N и mitkko обяснил горе-долу за какво иде реч.

  14.  
     
  15. Member
    Тук е от
    Sep 2004
    Мнения
    633
    #12

    Задача 154 ( Изкуплението Шоушенк 23 )

    <blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Сега видях, че при първия си отговор съм приел, че затворниците знаят пътрвоначалното положение на ключовете. Щом не го знаят решението не е по-сложно. Просто всички включват точно по два пъти, а Броячът брои до 43. Тогава е сигурен, че всеки е включвал поне по веднъж. Това решение е 100% успешно, но е добре затворниците да са дълголетници или уникални късметлии.



    Не знам какво е вложил mitkko в N. Според мен в условието N не е дефинирано. Ако тълкуваме условието като "при N>1 всички са влизали поне по един път" и приемем, че N е броя влизания в стаята на всеки затворник, излиза супер елементарното решение - първият, който посети стаята за 2ри път, освобождава всички [:D]. Но звучи твърде тъпо. Затова - какво е N ?



    <div align="right">Originally posted by Edin_Lud*-*28/01/2005*:* 19:04:48</div id="right">

    </td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

    И аз опитах с по два пъти /43/ но май не става, затова минах на 3 пъти. Но авторът явно не е доволен - иска още[:D]

  16. Senior Member
    Тук е от
    Dec 2004
    Мнения
    1,563
    #13

    Задача 154 ( Изкуплението Шоушенк 23 )

    С точно 2 пъти включване е 100% сигурно. Авторът иска оптимално решение. А такова е много трудно да се намери.

    Има и решение с произволно превключване на ключа - не само от OFF към ON. Тогава са необходими 3 превключвания (и броене до 65) и пак не е сигурно, че ще се освободят по-бързо.

  17. Member
    Тук е от
    Sep 2004
    Мнения
    633
    #14

    Задача 154 ( Изкуплението Шоушенк 23 )

    Edin_Lud,

    Хипотеза:

    Ключ А е в начално състояние он.

    Първи влиза брояча и преброява 1, без да е влизал никой преди него.

    След това влизат 21 души по два пъти и един изобщо не влиза.

    42+1=43. Ето защо не става с по два пъти.

    Едит// Иначе, без твоята идея за брояч и лев и десен ключ, работата беше умряла.

    Остава финалният напън. Сега ще дойде тежката артилерия и...


  18. Member
    Тук е от
    Dec 2004
    Мнения
    542
    #15

    Задача 154 ( Изкуплението Шоушенк 23 )

    @ Edin_Lud && dedis:

    аз почти бях обявил победител.



    момчета на една стъпка сте отговора, който очаквам, до тук си делите по равно решението, така че който назове точното число в списъка на Брояча (с малка обосновка) мисля, че има право да зададе следващата. Не е 43, не е и 65.



    //Едит: обосновка само ако някой хитрец ви изпревари вас двамата. Вие си я решихте на практика, но много малък детайл ви убягва. Това пусто N ! [:D]

Сподели във Facebook Сподели в Google Plus Сподели в Twitter Изпрати на Email Сподели в LinkedIn
Страница 1 от 2 12 ПоследноПоследно

Подобни теми

  1. Задача 270 (Следваща задача)
    От tricklys във форум Логически задачи
    Отговори: 18
    Последно: 22-06-05, 12:43
  2. Задача №183 (Нелогическа задача)
    От Cko във форум Логически задачи
    Отговори: 17
    Последно: 23-02-05, 17:16
  3. Задача № 64
    От IvO™ във форум Логически задачи
    Отговори: 5
    Последно: 01-11-04, 15:37
  4. Задача №63
    От Star Warrior във форум Логически задачи
    Отговори: 30
    Последно: 01-11-04, 02:00
  5. Задача №62
    От dedis във форум Логически задачи
    Отговори: 3
    Последно: 29-10-04, 13:23

SetCombG.com
SetCombG.com е портален сайт и Форум за битова техника, телевизори, климатици, лаптопи и смартфони, създаден през 1999 година.
Заедно сме над 20 години!
Следвай ни
Горе