Солдаты и бандиты
От: Pushkin Россия www.linkbit.com
Дата: 04.02.03 11:09
Оценка:
Вот задачка скорее детская, но если у кого будет перерыв в важных делах ...

Три солдата подвели трёх бандитов к переправе.
На переправе лодка, вмещающая не более двух человек.
Как им всем переправиться, если:
— грести может любой
— одних бандитов оставлять можно и в лодке и на берегу (не убегут)
— никогда ни на одном берегу (включая тех кто в лодке у берега) не должно быть бандитов больше, чем солдат (убьют на фиг)

Сколько раз лодка переплывёт реку?
Re: Солдаты и бандиты
От: Flea  
Дата: 04.02.03 11:15
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Вот задачка скорее детская, но если у кого будет перерыв в важных делах ...


P>Три солдата подвели трёх бандитов к переправе.

P>На переправе лодка, вмещающая не более двух человек.
P>Как им всем переправиться, если:
P>- грести может любой
P>- одних бандитов оставлять можно и в лодке и на берегу (не убегут)
P>- никогда ни на одном берегу (включая тех кто в лодке у берега) не должно быть бандитов больше, чем солдат (убьют на фиг)

P>Сколько раз лодка переплывёт реку?

1 — бандит + солдат
2 — бандит плывет обратно
3 — два бандита в лодке туда
4 — один бандит назад
5 — бандит с солдатом туда
6 — бандит один назад
7 — два бандита в лодке туда
Re[2]: Солдаты и бандиты
От: mrhru Россия  
Дата: 04.02.03 11:20
Оценка:
Здравствуйте, Flea, Вы писали:


P>>Сколько раз лодка переплывёт реку?

F>1 — бандит + солдат
F>2 — бандит плывет обратно
F>3 — два бандита в лодке туда

1 солдат и 2 бандита — "убьют на фиг" (с) Pushkin

...
Евгений
Re[3]: Солдаты и бандиты
От: Flea  
Дата: 04.02.03 11:44
Оценка:
Здравствуйте, mrhru, Вы писали:

M>Здравствуйте, Flea, Вы писали:


M>1 солдат и 2 бандита — "убьют на фиг" (с) Pushkin


Блин...
1 — два бандита туда
2 — один бандит назад
3 — бандит + солдат туда
4 — бандит назад
5 — бандит + солдат туда
6 — бандит назад
7 — бандит + солдат туда
8 — бандит назад
9 — 2 бандита туда
Re[4]: Солдаты и бандиты
От: mrhru Россия  
Дата: 04.02.03 11:55
Оценка:
Здравствуйте, Flea, Вы писали:

F>Здравствуйте, mrhru, Вы писали:


M>>Здравствуйте, Flea, Вы писали:


M>>1 солдат и 2 бандита — "убьют на фиг" (с) Pushkin


F>Блин...


сссббб :



F>1 — два бандита туда

сссб : бб



F>2 — один бандит назад

сссбб : б



F>3 — бандит + солдат туда

ссб : сбб
Вот здесь и убьют



F>4 — бандит назад

ссбб : сб



F>5 — бандит + солдат туда

сб : ссбб



F>6 — бандит назад

сбб : ссб
И здесь



F>7 — бандит + солдат туда

б : сссбб



F>8 — бандит назад
бб : сссб



F>9 — 2 бандита туда
бб : сссб

Итого: два убивства.

Что-то сдается, задача нерешаемая...
Если только не допустить, что ситуация бандитов > солдат — допустима кратковременно.
Евгений
Re[5]: Солдаты и бандиты
От: Gollum Россия  
Дата: 04.02.03 11:58
Оценка: 22 (3)
1. 2 бандита туда, 1 обратно
2. 2 бандита туда, 1 обратно
3. 2 солдата туда, солдат +бандит обратно
4. 2 солдата туда, бандит обратно.
5. Все бандиты едут на другой берег.

Хотя я бы — убежал
... << RSDN@Home 1.0 beta 5 >>
Eugene Agafonov on the .NET

Re[5]: Солдаты и бандиты
От: Pushkin Россия www.linkbit.com
Дата: 04.02.03 12:00
Оценка:
Здравствуйте, mrhru, Вы писали:

M>Что-то сдается, задача нерешаемая...


Решаемая-решаемая
Re[6]: Солдаты и бандиты
От: mrhru Россия  
Дата: 04.02.03 12:04
Оценка:
Здравствуйте, Gollum, Вы писали:

сссббб :


G>1. 2 бандита туда, 1 обратно

сссб : бб
сссбб : б



G>2. 2 бандита туда, 1 обратно

ссс : ббб
сссб : бб



G>3. 2 солдата туда, солдат +бандит обратно

сб : ссбб
ссбб : сб



G>4. 2 солдата туда, бандит обратно.

бб : сссб
ббб : ссс



G>5. Все бандиты едут на другой берег.

: бббссс





G>Хотя я бы — убежал

На месте кого?
Евгений
Re[6]: Солдаты и бандиты
От: Pushkin Россия www.linkbit.com
Дата: 04.02.03 12:04
Оценка:
Здравствуйте, Gollum, Вы писали:

G>1. 2 бандита туда, 1 обратно

G>2. 2 бандита туда, 1 обратно
G>3. 2 солдата туда, солдат +бандит обратно
G>4. 2 солдата туда, бандит обратно.
G>5. Все бандиты едут на другой берег.

Итого? Число переплываний лодки?
Re[7]: Солдаты и бандиты
От: Gollum Россия  
Дата: 04.02.03 12:10
Оценка: 9 (1)
Здравствуйте, Pushkin, Вы писали:

G>>1. 2 бандита туда, 1 обратно

2
G>>2. 2 бандита туда, 1 обратно
2
G>>3. 2 солдата туда, солдат +бандит обратно
2
G>>4. 2 солдата туда, бандит обратно.
2
G>>5. Все бандиты едут на другой берег.
3

P>Итого? Число переплываний лодки?

Вроде, 11
... << RSDN@Home 1.0 beta 5 >>
Eugene Agafonov on the .NET

Re[7]: Солдаты и бандиты
От: Gollum Россия  
Дата: 04.02.03 12:22
Оценка:
Здравствуйте, mrhru, Вы писали:

G>>Хотя я бы — убежал


M>На месте кого?


И тех и других
... << RSDN@Home 1.0 beta 5 >>
Eugene Agafonov on the .NET

Re[5]: Солдаты и бандиты
От: Flea  
Дата: 04.02.03 12:53
Оценка:
Здравствуйте, mrhru, Вы писали:

M>>>Здравствуйте, Flea, Вы писали:


M>Итого: два убивства.


M>Что-то сдается, задача нерешаемая...

M>Если только не допустить, что ситуация бандитов > солдат — допустима кратковременно.
Бандит не выходит из лодки...
Re: Солдаты и бандиты
От: Кодт Россия  
Дата: 04.02.03 12:59
Оценка: 74 (5)
Здравствуйте, Pushkin, Вы писали:

P>Сколько раз лодка переплывёт реку?


  Возможные состояния:
  (обозначение: (солдаты+бандиты слева , солдаты+бандиты справа) )
  (запрещенные состояния - (31,13), (21,12), (12,21), (13,31) не именуем)

  a = (33,00)
  b = (32,01)
  c = (31,02)
  d = (30,03)
  e = (22,11)
  f = (11,22)
  g = (03,30)
  h = (02,31)
  i = (01,32)
  j = (00,33)

  Возможные переходы:
  ( x< означает "лодка слева", x> - "лодка справа)
  
  a<  -->  b> c> e>
  b<  -->  c> d> e>      b>  -->  a<
  c<  -->  d> f>         c>  -->  a< b<
  d<  -->  нет           d>  -->  b< c<
  e<  -->  f> h>         e>  -->  a< b<
  f<  -->  i> j>         f>  -->  c< e<
  g<  -->  h> i>         g>  -->  нет
  h<  -->  i> j>         h>  -->  e< g<
  i<  -->  j>            i>  -->  f< g< h<
                         j>   финиш.

  Отследим пути (волновой алгоритм):

  a<
  b> c> e>
  (a<) (a<) b< (a<) (b<)
  (c>) d> (e>)
  (b<) c<
  (d>) f>
  (c<) e<
  (f>) h>
  (e<) g<
  (h>) i>
  f< (g<) h<
  (i>) j> (j>)

  Получается такой путь:
  a<
  c> e>  -- здесь возможны оба варианта
  b<
  d>
  c<
  f>
  e<
  h>
  g<
  i>
  f< h<  -- и здесь два варианта
  j>

Итого, 11 плаваний на лодке.
Перекуём баги на фичи!
Re[2]: Солдаты и бандиты
От: Gollum Россия  
Дата: 04.02.03 13:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Итого, 11 плаваний на лодке.



... << RSDN@Home 1.0 beta 5 >>
Eugene Agafonov on the .NET

Re[2]: Солдаты и бандиты
От: Pushkin Россия www.linkbit.com
Дата: 04.02.03 14:35
Оценка:
Здравствуйте, Кодт, Вы писали:

К> Отследим пути (волновой алгоритм):


В данном случае волновой алгоритм сводится к простому соображению, что раз мы пошли по какой-то дороге, нет смысла делать по ней шаги назад.
Re[3]: Солдаты и бандиты
От: Кодт Россия  
Дата: 04.02.03 15:05
Оценка:
Здравствуйте, Pushkin, Вы писали:

К>> Отследим пути (волновой алгоритм):


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


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

Нужно заметить, что все-таки ширина фронта достигает 2 в двух местах. А "простым соображением" мы могли и не найти эти варианты.
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.