Sign in to follow this  
Followers 0
Veidali

Задача про басмачей и товарища Сухова.

36 posts in this topic

Поймал как-то товарищ Сухов в песках Каракумов банду басмачей. И стал перед ними речь держать:

Так мол и так, сидеть вам товарищи басмачи предстоит долго. Сегодня вечером вас разведут по зинданам и общаться вы друг с другом больше не будете. (Для одаренных поясню - общаться нельзя никакими способами - перестукиваться, дрессированых мышей с записками отправлять и т.д.)

Но! Как завещал товарищ Ленин - учиться, учиться и еще раз учиться. Петруха будет водить басмачей в библиотеку, в которой всего 2 книги (например синяя и вторая :) ). Обе лежат на столе. Каждый басмач за время посещения должен взять со стола одну книгу и, уходя, перевернуть ее (т.е. если до его прихода титульный лист был наверху, то после ухода он будет внизу и наоборот)

При этом графика посещений нет - Петруха водит басмачей в случайном порядке и нерегулярно. Может за один день 10 человек по очереди отвести, а может неделю никого не водить.

Но при этом каждый басмач может быть уверен, что никакое его посещение не станет последним - рано или поздно он еще раз придет в библиотеку.

За порчу имущества библиотеки - смертная казнь (книги нельзя рвать, пачкать и т.д.)

В любой день любой из басмачей может сказать - "мы уже все побывали в библиотеке". Если он будет прав - их отпустят, если нет - всех расстреляют.

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

 

Вопрос - как они должны действовать, чтобы гарантированно выйти на свободу?

Число бандитов не принципиально. Допустим их 10 (но решение должно работать и для 20 человек)

0

Share this post


Link to post
Share on other sites

Это на сообразительность... Это не для меня(я тугодум). :)

0

Share this post


Link to post
Share on other sites

Подобные задачи на ТРИЗе решать дают. Ну и некоторые айтишные конторы любят на собеседованиях задачи на логику давать.

0

Share this post


Link to post
Share on other sites

Да, есть такое - куча таких задач, там Роберт, Джозеф и пр.

белые сидят в затылок друг другу, им перо показывают и пр.

бинарная логика + еще всякие умные слова.

0

Share this post


Link to post
Share on other sites

Есть такая идея:

Каждый басмач проделывает следующее: при первом посещении берет синию книгу и переворачивает ее. При следующем посещении переворачивает ее обратно.

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

Таким образом они смогут подсчитать, сколько раз в обе стороны перевернули синию книгу. И когда количество раз будет равно количеству басмачей (минус 1), последний придет и скажет, что все уже тут побывали.

Каждый басмач, кроме первого басмача, должен перевернуть синию книгу, когда второй раз увидит, что она не перевернута.

Пример для трех:

Заходит первый басмач и переворачивает синию книгу. Все остальные басмачи при посещении переворачивают другие книги. Потом, когда первый басмач появляется в библиотеке еще раз, то переворачивает синию книгу обратно.

Теперь второй басмач пришел и видит, что книга уже опять лицевой стороной вверх. Но он ее не переворачивает, т.к. может быть третий басмач еще не видел, что первый басмач перевернул ее обратно. Вот когда второй басмач придет и увидит еще раз, что синяя книга лицевой стороной вверх, то только тогда он ее перевернет.

После этого, когда уже посетит третий басмач, он увидит, что книга лежит тыльной стороной вверх второй раз, значит, что уже двое тут побывали. Он скажет, что они все трое тут побывали ;)

Не совсем верное решение, т.к. есть вероятность, что третий басмач посетит библиотеку через год, а до этого каждый день ее будут посещать только первые два басмача или вообще только один басмач ;) но все же :)

 

А еще есть вариант разбить стол на клетки и оставлять одну из книг по клеткам. Т.е. если басмач ни разу не был в библиотеке, то он кладет книгу на следующую клетку. Если этот вариант допускается условием, то берем этот вариант. Если максимально возможное количество клеток на столе будет Н, то количество басмачей, для которых это сработает, должно быть Н*Н, т.к. у нас две книги. А если еще учесть, что книги можно переворачивать, то это возможное количество будет еще больше.

Edited by Stan
0

Share this post


Link to post
Share on other sites

Ничерта не понял, что вы имели в виду с вашей идеей.

 

Пример для трех:

Заходит первый басмач и переворачивает синию книгу. Все остальные басмачи при посещении переворачивают другие книги. Потом, когда первый басмач появляется в библиотеке еще раз, то переворачивает синию книгу обратно.

Откуда все остальные узнают что первый перевернул книгу? Они же не знают лежала она титульным листом вверх или вниз?

В условии задачи про начальное положение книг ничего не сказано.

 

Не совсем верное решение, т.к. есть вероятность, что третий басмач посетит библиотеку через год, а до этого каждый день ее будут посещать только первые два басмача или вообще только один басмач ;) но все же ;)

Сами понимаете, что условие неверное, зачем его предлагаете?

Хотя дельные мысли там есть, но вы ушли в неправильном направлении.

 

А еще есть вариант разбить стол на клетки и оставлять одну из книг по клеткам. Т.е. если басмач ни разу не был в библиотеке, то он кладет книгу на следующую клетку. Если этот вариант допускается условием, то берем этот вариант. Если максимально возможное количество клеток на столе будет Н, то количество басмачей, для которых это сработает, должно быть Н*Н. А если еще учесть, что книги можно переворачивать, то это возможное количество будет еще больше.

А если стол круглый? Или треугольный? Число басмачей ничем неограничено. А если стол размером 30х30 см? По миллиметрам будут книгу двигать?

 

В общем оба ваши варианта не подходят.

0

Share this post


Link to post
Share on other sites

Да я так, после обеда морально отдыхаю ;) А то от работы голова кругом идет ;)

 

Тогда есть еще одна идея:

Есть синяя книга и другая.

Каждый басмач, который заходит и видит, что синяя книга лежит лицевой стороной кверху, берет и переворачивает ее, если он ее до этого никогда еще не переворачивал. Если синяя книга лежит тыльной стороной кверху, то басмачи переворачиют другую книгу.

И есть только один басмач-считальщик, только он имеет право переворачивать синюю книгу лицевой стороной кверху.

Теперь нужно разобраться с начальным положением книг и кто будет считальщиком.

Считальщиком может быть любой из них.

А вот как он просигнализирует о том, что побывал уже там и может начинать отсчет, пока в голову не пришло.

0

Share this post


Link to post
Share on other sites

К тому же переворачивать с лицевой стороны на тыльную можно разными способами: переплет справа-налево, переплет всегда с одной стороны, по часовой стрелке, против и т.д.

Т.е. они должны договориться, в каком положении должна лежать книга, после того как ее прочтет последний басмач, обговорив цепочку всех положений книг, соблюдая условие "лицевая-тыльная сторона".

0

Share this post


Link to post
Share on other sites

Ага. Только вот по условию мы не знаем начального положения книги.

Но мыслишь верно.

0

Share this post


Link to post
Share on other sites
Ага. Только вот по условию мы не знаем начального положения книги.

Но мыслишь верно.

Да, вот в этом пока и загвоздка, что начальное положение книг может быть любым и они его не знают ;)

0

Share this post


Link to post
Share on other sites
К тому же переворачивать с лицевой стороны на тыльную можно разными способами: переплет справа-налево, переплет всегда с одной стороны, по часовой стрелке, против и т.д.

Т.е. они должны договориться, в каком положении должна лежать книга, после того как ее прочтет последний басмач, обговорив цепочку всех положений книг, соблюдая условие "лицевая-тыльная сторона".

Нужен четкий алгоритм, а не "они как-нибудь обговорят".

А если их 100 человек? 100 положений книги будете придумывать?

0

Share this post


Link to post
Share on other sites
Нужен четкий алгоритм, а не "они как-нибудь обговорят".

А если их 100 человек? 100 положений книги будете придумывать?

 

Каков привет - таков ответ!

Задавай тогда конкретные условия задачи, а не "допустим 10, а может быть и 20".

0

Share this post


Link to post
Share on other sites
Каков привет - таков ответ!

Задавай тогда конкретные условия задачи, а не "допустим 10, а может быть и 20".

Тут ты не прав ;) Это называется найти решение для общего случая

0

Share this post


Link to post
Share on other sites

Шторм, условие задачи читай внимательно - "Число бандитов не принципиально".

 

Стэн на полпути к решению уже.

Edited by Veidali
0

Share this post


Link to post
Share on other sites
Тут ты не прав ;) Это называется найти решение для общего случая

 

Согласен ;)

0

Share this post


Link to post
Share on other sites

Решение этой задачки в случае, если их водят по одному в день, и водят каждый день - проще, чем в заданных условиях. Если бы их водили раз в день и каждый день, строго по одному, тогда алгоритм такой: басмачи договариваются, что тот из них, который попал в зиндан в первый день, становится "учетчиком", и действует так: он, в первое свое посещение, обязательно оставит синюю книгу лицом вверх. Если она уже лицом вверх, он ее не трогает. Затем, все остальные басмачи, действуют так: каждый из них, ТОЛЬКО ОДИН РАЗ ЗА ВСЕ ВРЕМЯ ПРЕБЫВАНИЯ В ПЛЕНУ, увидев синюю книгу лицом вверх, переворачивает ее лицом вниз. И делает это ТОЛЬКО ОДИН РАЗ. Все остальные разы он тупо читает вторую книгу и делает с ней что хочет. Книга так и пролежит лицом вниз до следующего появления учетчика. Учетчик же, каждый раз возвращаясь в зиндан, когда-нибудь увидит синюю книгу перевернутой лицом вниз. Это означает, что один из ранее не переворачивавших книгу басмачей побывал в библиотеке. Он снова переворачивает книгу лицом вверх и уходит. И так до тех пор, пока учетчик не перевернет книгу 9 раз, не считая самого первого раза. После этого он смело может заявить, что каждый из его товарищей успел побывать в библиотеке.

 

В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

 

Вот как-то так.

Edited by cduz
0

Share this post


Link to post
Share on other sites
В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

хехехе

точно :unsure:

по два раза :)

когда в 18 раз увидит, то все, конец :)

0

Share this post


Link to post
Share on other sites

При чем тут ШТОРМ ?

я что такого сказал , что мне надо внимательно читать ?

Да и до стена мне нет дела вовсе, на полпути он, или заблудился.

решал такие задачи уже, посему неинтересно, типичные они все.

0

Share this post


Link to post
Share on other sites
хехехе

точно :)

по два раза :)

когда в 18 раз увидит, то все, конец :)

 

В том-то и дело, что 18-го раза может и не быть. Если первым вошел не учетчик, и синяя книга была лицевой стороной вверх, он перевернет ее лицом вниз, то учетчик так и не узнает, переворачивали книги до него или нет. И "восемнадцатого" раза для него так и не наступит, потому что все уже по два раза перевернули и больше не трогают. Потому и нужно договариваться на по два раза, что ответ можно дать на 17-м переворачивании (которое на самом деле может оказаться 18-м, но это уже не важно).

Edited by cduz
0

Share this post


Link to post
Share on other sites
В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

 

Вот как-то так.

Дец как мало.

Маладец!

 

Именно поэтому, когда Стэн предложил переворачивать 1 раз я сказал что он на полпути.

:-)

 

В том-то и дело, что 18-го раза может и не быть. Если первым вошел не учетчик, и синяя книга была лицевой стороной вверх, он перевернет ее лицом вниз, то учетчик так и не узнает, переворачивали книги до него или нет. И "восемнадцатого" раза для него так и не наступит, потому что все уже по два раза перевернули и больше не трогают. Потому и нужно договариваться на по два раза, что ответ можно дать на 17-м переворачивании (которое на самом деле может оказаться 18-м, но это уже не важно).

Нет. Он обязательно должен дождаться 18-го раза

Возможная ситуация:

1 раз книга лежала неправильно - он ее посчитал.

Потом 8 зеков зашли по 2 раза и он их постчитал, всего получится 17 раз.

Поэтому ему надо дождаться 18-го, раза чтобы гарантировать результат

 

При чем тут ШТОРМ ?

я что такого сказал , что мне надо внимательно читать ?

Ты сказал что тебе непонятно из условия сколько там басмачей, то ли 10, то ли 20.

Я тебе показал, что в условии сказано о том, что басмачей может быть сколько угодно, алгоритм от этого не должен зависеть.

 

Да и до стена мне нет дела вовсе, на полпути он, или заблудился.

решал такие задачи уже, посему неинтересно, типичные они все.

Интересная позиция. То пытаешься решать, какие-то ответы предлагаешь, а то вдруг в кусты, "мне, мол, не интересно". ;)

0

Share this post


Link to post
Share on other sites

Никто ничего не двигает, каждый запоминает изначальное расположение книги, скажем синяя книга лежит обратной стороной,так как все басмачи скажут одну и ту же позицию, то это докажет что каждый из них там был, ведь никто не знал изначальную позицию книги. Правда спрашивать придётся каждого по отдельности.

0

Share this post


Link to post
Share on other sites
Никто ничего не двигает, каждый запоминает изначальное расположение книги, скажем синяя книга лежит обратной стороной,так как все басмачи скажут одну и ту же позицию, то это докажет что каждый из них там был, ведь никто не знал изначальную позицию книги. Правда спрашивать придётся каждого по отдельности.

Ржачь. Еще одно решение тогда. Все читают эти две книги. по очереди пересказывают и выходят на свободу. :mellow:

0

Share this post


Link to post
Share on other sites
Никто ничего не двигает, каждый запоминает изначальное расположение книги, скажем синяя книга лежит обратной стороной,так как все басмачи скажут одну и ту же позицию, то это докажет что каждый из них там был, ведь никто не знал изначальную позицию книги. Правда спрашивать придётся каждого по отдельности.

Кто и кого будет спрашивать? Петруха - басмачей? Или товарищ Сухов?

Им пофигу как книги лежат.

А басмачи друг с другом общаться не могут (прочитайте условие)

0

Share this post


Link to post
Share on other sites

А книгу можно оставлять открытой?

 

 

Кто и кого будет спрашивать? Петруха - басмачей? Или товарищ Сухов?

Им пофигу как книги лежат.

А басмачи друг с другом общаться не могут (прочитайте условие)

Почему б и не поспаршивать? в условии вроде сказано "если он будет прав". значит каким то образом они это выяснят?

0

Share this post


Link to post
Share on other sites
Нет. Он обязательно должен дождаться 18-го раза

Возможная ситуация:

1 раз книга лежала неправильно - он ее посчитал.

Потом 8 зеков зашли по 2 раза и он их постчитал, всего получится 17 раз.

Поэтому ему надо дождаться 18-го, раза чтобы гарантировать результат

 

В предложенном мной варианте он первый свой заход не считает независимо от того как лежала книга. Потом считает 17 раз.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.