3 ведра

и задачки для интервью.
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

3 ведра

Post by Alex_197 »

Есть 3 ведра

2 полных
1. в одном 5 литров
2. в другом 3 литра

надо наполнить 3-е ведро, ровно на 4 литра.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »


2->3: 5,0,3
1->2: 2,3,3
2->3: 2,0,6
1->2: 0,2,6
3->1: 5,2,1
1->2: 4,3,1
2->3: 4,0,4
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Post by Alex_197 »

venco wrote:

2->3: 5,0,3
1->2: 2,3,3
2->3: 2,0,6
1->2: 0,2,6
3->1: 5,2,1
1->2: 4,3,1
2->3: 4,0,4
User avatar
Julio Metazzo
Уже с Приветом
Posts: 1414
Joined: 18 Aug 2005 13:42

Post by Julio Metazzo »

Альтернативный вариант, при котором третье ведро может быть объемом 5 (а не 6) литров, но нужно часть воды вылить, например, в окно :)

1->3 (0, 3, 5)
2->1 (3, 0, 5)
3->2 (3, 3, 2)
2->1 (5, 1, 2)
2->окно (5, 0, 2)
1->2 (2, 3, 2)
1->3 (0, 3, 4)
User avatar
wireless
Уже с Приветом
Posts: 1168
Joined: 23 Sep 2001 09:01

Post by wireless »

Вроде что то похожее было в 3 -ей серии Die Hard? И они там за меньшее количество шагов перелили. Или я чего то путаю?
sergant
Уже с Приветом
Posts: 1127
Joined: 11 Apr 2004 03:28

Post by sergant »

wireless wrote:Вроде что то похожее было в 3 -ей серии Die Hard? И они там за меньшее количество шагов перелили. Или я чего то путаю?


1-й шаг лишний

2->3 (5,0,3)
1->2 (2,3,3)
2->3 (2,1,5)
2->окно (2,0,5)
3->2 (2,3,2)
1->3 (0,3,4)
User avatar
Artemk
Уже с Приветом
Posts: 4790
Joined: 21 Jul 2002 21:55
Location: Minsk -> Louisville, KY

Post by Artemk »

Ну так же нельзя головоломки загадывать... А то с такими условиями и решение будет "Налить 4 литра в третье ведро" :)
Мне повезло, я такой как все. Я работаю в офисе.
М@ш@
Уже с Приветом
Posts: 23488
Joined: 05 Jan 2005 11:11
Location: Israel->NJ

Post by М@ш@ »

Artemk wrote:Ну так же нельзя головоломки загадывать... А то с такими условиями и решение будет "Налить 4 литра в третье ведро" :)

+1
Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Re: 3 ведра

Post by Deynekin »

Alex_197 wrote:Есть 3 ведра
2 полных
1. в одном 5 литров
2. в другом 3 литра
надо наполнить 3-е ведро, ровно на 4 литра.

Признаться, стоило большого труда понять, что все вёдра действительно разного размера (т.е. слова "2 полных: в одном 5, в другом 3" - не описка), причём третье ведро предполагается "достаточно большим"...

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

В нашем случае это будет правильный треугольник высотой в 8 единиц, соответствующих общему количеству воды в задаче. Как известно, для любой точки внутри такого треугольника (включая также и его стороны) сумма растояний до его сторон инвариантна и равна всё тем же восьми единицам. - Вот и готов метод изображения состояния системы: содержимое вёдер - это расстояния от точки до сторон треугольника.

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

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

- Дальше сами. Кто поленивее, может просто проследить, как движется точка на этой диаграмме в соответствии с решением venco

Дисклаймер: Идея не моя, но заимствована из журнала "Квант" более двадцати лет тому назад.
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

Замечательный способ!
Я сделал иллюстрацию по Вашему описанию.

Голубая точка - старт.
Красный параллелограм - область допустимых состояний.
Зеленая линия - требуемое решение.
You do not have the required permissions to view the files attached to this post.
Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Post by Deynekin »

Иоп wrote:Я сделал иллюстрацию по Вашему описанию...

Спасибо, совершенно правильный рисунок. Если бы на него ещё траекторию решения venco нанести, чтобы уж совсем всем всё понятно было...

Резюме: Начали с решения конкретной задачи, а закончили методом для класса задач. - Как там, бишь, восточные люди говорят: "Дай рыбу - накормишь на день; дай удочку - накормишь на всю жизнь."
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Post by Alex_197 »

Deynekin wrote:
Иоп wrote:Я сделал иллюстрацию по Вашему описанию...

Спасибо, совершенно правильный рисунок. Если бы на него ещё траекторию решения venco нанести, чтобы уж совсем всем всё понятно было...

Резюме: Начали с решения конкретной задачи, а закончили методом для класса задач. - Как там, бишь, восточные люди говорят: "Дай рыбу - накормишь на день; дай удочку - накормишь на всю жизнь."


Цитата немножко неверно сформулирована:

Чтобы накормить голодного не давай ему хлеба. Дай ему удочки и научи ловить рыбу. Но - не говори ему - где водится рыба.
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Re: 3 ведра

Post by Alex_197 »

Deynekin wrote:
Alex_197 wrote:Есть 3 ведра
2 полных
1. в одном 5 литров
2. в другом 3 литра
надо наполнить 3-е ведро, ровно на 4 литра.

Признаться, стоило большого труда понять, что все вёдра действительно разного размера (т.е. слова "2 полных: в одном 5, в другом 3" - не описка), причём третье ведро предполагается "достаточно большим"...
.


Простите, если не верно сформулировал: ведра по размеру одинаковые.
User avatar
Artemk
Уже с Приветом
Posts: 4790
Joined: 21 Jul 2002 21:55
Location: Minsk -> Louisville, KY

Re: 3 ведра

Post by Artemk »

Alex_197 wrote:
Deynekin wrote:
Alex_197 wrote:Есть 3 ведра
2 полных
1. в одном 5 литров
2. в другом 3 литра
надо наполнить 3-е ведро, ровно на 4 литра.

Признаться, стоило большого труда понять, что все вёдра действительно разного размера (т.е. слова "2 полных: в одном 5, в другом 3" - не описка), причём третье ведро предполагается "достаточно большим"...
.


Простите, если не верно сформулировал: ведра по размеру одинаковые.

Одинаковые? Так хоть скажите какого размера? 3 литра? 4? 5? 10?

Написали уж бы тогда - "Есть три ведра с водой. Надо в третье налить 4 литра"
Мне повезло, я такой как все. Я работаю в офисе.
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Re: 3 ведра

Post by Alex_197 »

Artemk wrote:
Alex_197 wrote:
Deynekin wrote:
Alex_197 wrote:Есть 3 ведра
2 полных
1. в одном 5 литров
2. в другом 3 литра
надо наполнить 3-е ведро, ровно на 4 литра.

Признаться, стоило большого труда понять, что все вёдра действительно разного размера (т.е. слова "2 полных: в одном 5, в другом 3" - не описка), причём третье ведро предполагается "достаточно большим"...
.


Простите, если не верно сформулировал: ведра по размеру одинаковые.

Одинаковые? Так хоть скажите какого размера? 3 литра? 4? 5? 10?

Написали уж бы тогда - "Есть три ведра с водой. Надо в третье налить 4 литра"


5 литров каждое и в 3-е ведро нужно налить 4 литра
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Как может в полном ведре на 5л быть 3л воды?
Остальные 2 литра песок?
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Post by Alex_197 »

venco wrote:Как может в полном ведре на 5л быть 3л воды?
Остальные 2 литра песок?


Сорри за описку:

Все ведра одного объема - 5 литров.

Ведра заполнены следующим образом:

1 ведро - 5 литров
2 ведро - 3 литра
3 ведро пустое - необходимо налить 4 литра.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Alex_197 wrote:
venco wrote:Как может в полном ведре на 5л быть 3л воды?
Остальные 2 литра песок?


Сорри за описку:

Все ведра одного объема - 5 литров.

Ведра заполнены следующим образом:

1 ведро - 5 литров
2 ведро - 3 литра
3 ведро пустое - необходимо налить 4 литра.

Вёдра одинаковые? (Вес, форма).
Alex_197
Уже с Приветом
Posts: 230
Joined: 10 May 2006 21:04
Location: New York

Post by Alex_197 »

venco wrote:
Alex_197 wrote:
venco wrote:Как может в полном ведре на 5л быть 3л воды?
Остальные 2 литра песок?


Сорри за описку:

Все ведра одного объема - 5 литров.

Ведра заполнены следующим образом:

1 ведро - 5 литров
2 ведро - 3 литра
3 ведро пустое - необходимо налить 4 литра.

Вёдра одинаковые? (Вес, форма).


да
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Тогда, наверно, решение - в делении 8 литров пополам.

Return to “Головоломки”