Найти способ переправить сундук через реку

@Danilkaa13 · Регистрация: 30.05.2022

Студворк — интернет-сервис помощи студентам

Четыре пирата нашли сундук с сокровищами. Они хотят переправиться через реку. Пираты весят 45, 50, 60 и 65 кг, сундук — 100 кг, их лодка выдерживает груз не более 200 кг. Сундук можно погрузить в лодку или вытащить из нее только вчетвером. Как им всё-таки всем переправиться, не оставив и сундук?
Помогите, пожалуйста

@Cyborg Drone · 20.12.2022, 23:33

Дурацкая задача. Самое простое и правильное решение: 45 и 50 на вёсла, а 60 и 65 за лодкой вплавь. Зачем пиратам действовать как-то сложнее - не постигаю. Ну ладно, допустим, что задачка про постапокалипсис, и речка сделана из серной кислоты, а лодка из полипропилена.

Алгоритм простой:
Сначала определяется множество негодяев, которых помещается в лодку не менее двоих. Затем "туда" перевозится максимальный вес, "обратно" - минимальный, но с условием: если на противоположном берегу нет ни одного легковесного негодяя, при очередном рейсе "туда" в лодке должно быть минимум два негодяя.

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

В данном случае получается так:

Множество легковесных пиратов: [45, 50].

Этот берег	Река	Тот берег
45 50 60 65
60 65	45 50 ->
60 65	<- 45	50
45 60	65 ->	50
45 60	<- 50	65
60	45 50 ->	65
60	<- 45	50 65
45	60 ->	50 65
45	<- 50	60 65
	45 50 ->	60 65
		45 50 60 65

Насчёт программы буду думать, потому что задача не только дурацкая, но и муторная.

@Danilkaa13 · 21.12.2022, 09:15 **[ТС]**

Да, в этом и вся проблема, что представление о решение есть, но как это описать в коде не особо понятно.

@mr-Crocodile · 21.12.2022, 10:16

была такая задачка: Задача на поиск решений

@Cyborg Drone · 22.12.2022, 02:16

Решение не оптимальное и не универсальное, написанное на Free Pascal, но подойдёт для любых диалектов паскаля, поддерживающих динамические массивы. Подойдёт и для Pascal ABC.NET, но с небольшими корректировками:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
type
  arr = array of integer;
 
const
  m = 200 - 100; //грузоподъёмность минус вес сундука
  weight: array[0..3] of integer = (45, 50, 60, 65); //вес пиратов
 
procedure Sort(x: arr); //сортировка негодяев по возрастанию
var
  i, j, k, t: integer;
begin
  for i := low(x) to high(x) - 1 do
    begin
      k := i;
      for j := i + 1 to high(x) do
        if x[j] < x[k] then k := j;
      if k > i then
        begin
          t := x[i];
          x[i] := x[k];
          x[k] := t
        end
    end
end;
 
procedure Debarkation(var x, y: arr); //высадка
var
  i: integer;
begin
  for i := low(x) to high(x) do //цикл по негодяям в лодке
    begin
      SetLength(y, length(y) + 1); //добавляем место на берегу
      y[high(y)] := x[i] //высаживаем одного
    end;
  SetLength(x, 0); //опустошаем лодку
  Sort(y) //сортируем негодяев
end;
 
procedure Embarkation(var x, y: arr; c: integer); //посадка
var
  i, j, s: integer;
begin
  case c of
    1: //грузим легковеса
      begin
        SetLength(y, 1); //одно место в лодке
        y[low(y)] := x[low(x)]; //грузим самого лёгкого в лодку
        x[low(x)] := x[high(x)]; //на берегу пересаживаем самого тяжёлого на место самого лёгкого
        SetLength(x, length(x) - 1); //корректируем количество негодяев
        Sort(x) //и рассаживаем их по порядку
      end;
    2: //грузим легковесов
      begin
        s := 0; //общий вес негодяев в лодке
        i := low(x) - 1; //номер меньше возможного
        while (s < m) and (i <= high(x)) do //цикл пока вес не превышен и негодяи не кончилиь
            begin
              inc(i); //плюс один
              inc(s, x[i]) //общий вес
            end;
        SetLength(y, i); //резервируем место в лодке по количеству негодяев
        for j := low(y) to i - 1 do y[j] := x[j]; //пересаживаем самых лёгких в лодку
        for j := i to high(x) do x[j-i] := x[j]; //оставшихся пересаживаем по порядку на место самых лёгких
        SetLength(x, length(x) - i) //и корректируем их количество
      end
    else //3: гружим тяжеловеса
      begin
        SetLength(y, 1); //одно место в лодке
        y[low(y)] := x[high(x)]; //грузим самого тяжёлого
        SetLength(x, length(x) - 1) //корректируем количество негодяев
      end
  end
end;
 
procedure pr(x: arr); //печать негодяев
var
  i: integer;
begin
  if length(x) > 0 then //если есть хоть один негодяй, то
    for i := low(x) to high(x) do write(x[i], ' ') //печатаем веса
  else write('nobody ') //иначе печатаем, что нет тут никого
end;
 
procedure prn(const x, y, z: arr; d: boolean); //печать состояния
var
  s: string;
begin
  if length(y) = 0 then s := '| ' //если начальное или конечное состояние, то никуда не плывём
  else //иначе, в зависимости от направления,
    if d then s := '> ' //плывём туда
    else s := '< '; //плывём обратно
  pr(x); //печатаем веса негодяев на первом берегу
  write(s); //печатаем, куда плывём
  pr(y); //печатаем веса негодяев в лодке
  write(s); //ещё раз печатаем, куда плывём
  pr(z); //печатаем веса негодяев на втором берегу
  writeln
end;
 
var
  riverside1, boat, riverside2: arr; //первый берег, лодка, второй берег
  direction: boolean; //направление: true - туда, false - обратно
  g: integer; //вес самого тяжёлого легковеса
begin
  SetLength(riverside1, length(weight)); //кучка негодяев погрузили сундук
  riverside1 := weight; //и расселись на первом берегу по порядку
  g := low(riverside1); //определяем вес наиболее тяжёлого легковеса
  while (riverside1[g] + riverside1[g+1] < m) and (g < high(riverside1) - 1) do inc(g);
  g := riverside1[g];
  direction := false; //сначала лодка на первом берегу
  prn(riverside1, boat, riverside2, direction); //печатаем начальное состояние
  repeat //##### цикл перевозок
    if not direction then //если лодка на первом берегу, то
      begin
        Debarkation(boat, riverside1); //выгружаемся
        if (length(riverside2) > 0) and (riverside2[low(riverside2)] <= g) then //если на втором берегу есть легковес, то
          Embarkation(riverside1, boat, 3) //гружим самого тяжёлого
        else //иначе (если на втором берегу нет легковесов), то
          Embarkation(riverside1, boat, 2) //грузим легковесов
      end
    else //если лодка на втором берегу, то
      begin
        Debarkation(boat, riverside2); //выгружаемся
        if length(riverside1) > 0 then //если на первом берегу кто-то остался, то
          Embarkation(riverside2, boat, 1) //грузим легковеса
      end;
    direction := not direction; //меняем направление движения
    prn(riverside1, boat, riverside2, direction) //печатаем состояние
  until length(boat) = 0; //##### если всех перевезли, то выход
  readln //негодяи уволокли сундук в неизвестном направлении
end.

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

Добавлено через 2 часа 58 минут
Для Pascal ABC.NET можно так;

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
procedure prn(const x, y, z: sequence of integer; d: boolean); //печать состояния
begin
  var s := y.Any ? d ? '>' : '<' : '|'; //Вычисляем направление движения
  PrintLn(x, s, y, s, z) //печатаем состояние
end; 
  
begin
  var m := 200 - 100; //грузоподъёмность минус вес сундука
  var riverside1 := Seq(45, 50, 60, 65); //негодяи загрузили сундук и раселись по порядку
  var g := riverside1.Pairwise.Last(x -> x[0] + x[1] <= m)[1]; //находим самого тяжёлого из легковесов
  var boat := SeqFill(0, 0); //в лодке и на втором берегу никого
  var riverside2 := boat;
  var direction := false; //сначала лодка на первом берегу
  prn(riverside1, boat, riverside2, direction); //печатаем начальное состояние
  repeat //##### цикл перевозок
    if not direction then //если лодка на первом берегу, то
      begin
        riverside1 := riverside1.Concat(boat).Sorted; //выгружаемся
        boat := boat.Take(0);
        if riverside2.Any(x -> x <= g) then //если на втором берегу есть легковес, то
          begin
            boat := Seq(Riverside1.Max); //грузим самого тяжёлого
            Riverside1 := Riverside1.Except(boat)
          end
        else //иначе (если на втором берегу нет легковесов), то
          begin //грузим легковесов
            boat := riverside1;
            while boat.Sum > m do boat := boat.Except(Seq(boat.max));
            riverside1 := riverside1.Except(boat)
          end
      end
    else //если лодка на втором берегу, то
      begin
        riverside2 := riverside2.Concat(boat).Sorted; //выгружаемся
        boat := boat.Take(0);
        if riverside1.Any then //если на первом берегу кто-то остался, то
          begin //грузим легковеса
            boat := Seq(riverside2.Min);
            Riverside2 := Riverside2.Except(boat)
          end
      end;
    direction := not direction; //меняем направление движения
    prn(riverside1, boat, riverside2, direction) //печатаем состояние
  until not boat.Any //##### если всех перевезли, то выход
  //негодяи уволокли сундук в неизвестном направлении
end.

Может быть, можно сделать покороче. Но муторно это.

Добавлено через 2 часа 15 минут
Ещё один не оптимальный вариант, через множества, для любого диалекта паскаля:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
type
  pirates = set of byte;
 
function pr(x: pirates): string; //множетво негодяев в строку
var
  i: byte;
  s, r, n: string;
begin
  r := '';
  s := '[';
  for i := 0 to 255 do
    if i in x then
      begin
        str(i, n);
        s := s + r + n;
        r := ','
      end;
  pr := s + ']'
end;
 
procedure prn(const x, y, z: pirates; d: boolean); //печать состояния
const
  p: array[0..3] of string[3] = (' < ', ' > ', ' | ', ' | ');
var
  s: string;
  t: integer;
begin
  if y = [] then t := 2 else t := 0;
  if d then inc(t);
  s := p[t]; //вычисляем указатель
  writeln(pr(x), s, pr(y), s, pr(z)) //печатаем состояние
end;
 
const
  m = 200 - 100; //грузоподъёмность минус вес сундука
var
  riverside1, boat, riverside2: pirates; //первый берег, лодка, второй берег
  direction: boolean; //направление: true - туда, false - обратно
  g: byte; //вес самого тяжёлого легковеса
  t: array[byte] of byte;
  i, k, s: longint;
begin
  riverside1 := [45, 50, 60, 65]; //негодяи расселись на первом берегу по порядку
  boat := []; //в лодке и на втором берегу никого
  riverside2 := [];
  k := -1; //определяем вес самого тяжёлого легковеса
  for i := 0 to 255 do
    if i in riverside1 then
      begin
        inc(k);
        t[k] := i
      end;
  while t[k] + t[k-1] > m do dec(k);
  g := t[k];
  direction := false; //сначала лодка на первом берегу
  prn(riverside1, boat, riverside2, direction); //печатаем начальное состояние
  repeat //##### цикл перевозок
    if not direction then //если лодка на первом берегу, то
      begin
        riverside1 := riverside1 + boat; //выгружаемся
        boat := [];
        if riverside2 * [0..g] <> [] then //если на втором берегу есть легковес, то
          begin //гружим самого тяжёлого
            i := 255;
            while not (i in riverside1) do dec(i);
            boat := [i];
            exclude(riverside1, i)
          end
        else //иначе (если на втором берегу нет легковесов), то
          begin //грузим легковесов
            i := 0;
            while not (i in riverside1) do inc(i);
            s := 0;
            while (i <= 255) and (s + i <= m) do
              begin
                s := s + i;
                include(boat, i);
                repeat inc(i) until (i > 255) or (i in riverside1)
              end;
            riverside1 := riverside1 - boat
          end
      end
    else //если лодка на втором берегу, то
      begin
        riverside2 := riverside2 + boat; //выгружаемся
        boat := [];
        if riverside1 <> [] then //если на первом берегу кто-то остался, то
          begin //грузим легковеса
            i := 0;
            while not(i in riverside2) do inc(i);
            boat := [i];
            exclude(riverside2, i)
          end
      end;
    direction := not direction; //меняем направление движения
    prn(riverside1, boat, riverside2, direction) //печатаем состояние
  until boat = []; //##### если всех перевезли, то выход
  readln //негодяи уволокли сундук в неизвестном направлении
end.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Danilkaa13 2 / 2 / 0 Регистрация: 30.05.2022 Сообщений: 35

	Найти способ переправить сундук через реку 20.12.2022, 09:37. Показов 981. Ответов 4 Метки Pascal (Паскаль), pascal abc (Все метки) Четыре пирата нашли сундук с сокровищами. Они хотят переправиться через реку. Пираты весят 45, 50, 60 и 65 кг, сундук — 100 кг, их лодка выдерживает груз не более 200 кг. Сундук можно погрузить в лодку или вытащить из нее только вчетвером. Как им всё-таки всем переправиться, не оставив и сундук? Помогите, пожалуйста 0

@Danilkaa13 2 / 2 / 0 Регистрация: 30.05.2022 Сообщений: 35
	21.12.2022, 09:15 [ТС]
	Да, в этом и вся проблема, что представление о решение есть, но как это описать в коде не особо понятно. 0

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,380
	21.12.2022, 10:16
	была такая задачка: Задача на поиск решений 0