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

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

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

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

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

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

P>Сколько раз лодка переплывёт реку?
1 — бандит + солдат
2 — бандит плывет обратно
3 — два бандита в лодке туда
4 — один бандит назад
5 — бандит с солдатом туда
6 — бандит один назад
7 — два бандита в лодке туда

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


P>>Сколько раз лодка переплывёт реку?
F>1 — бандит + солдат
F>2 — бандит плывет обратно
F>3 — два бандита в лодке туда

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

...

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

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

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

Блин...
1 — два бандита туда
2 — один бандит назад
3 — бандит + солдат туда
4 — бандит назад
5 — бандит + солдат туда
6 — бандит назад
7 — бандит + солдат туда
8 — бандит назад
9 — 2 бандита туда

Здравствуйте, 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 бандита туда
бб : сссб

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

Что-то сдается, задача нерешаемая...
Если только не допустить, что ситуация бандитов > солдат — допустима кратковременно.

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

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

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

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

Решаемая-решаемая

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

сссббб :

---

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

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

---

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

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

---

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

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

---

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

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

---

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

: бббссс

---

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

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

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

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

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

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

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

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

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

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

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

И тех и других

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

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

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

M>Что-то сдается, задача нерешаемая...
M>Если только не допустить, что ситуация бандитов > солдат — допустима кратковременно.
Бандит не выходит из лодки...

Здравствуйте, 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 плаваний на лодке.

Здравствуйте, Кодт, Вы писали:

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

Здравствуйте, Кодт, Вы писали:

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

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

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

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

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

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

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