На трёх путях сортировочной станции стоят вагоны с абрикосами (А), бананами (Б) и вишней (В) так, как это показано на рисунке.
Машинист тепловоза (Т) может за один раз прицепить к тепловозу один или несколько вагонов с какого-нибудь пути, передвинуть их на правый путь, после чего передвинуть их на любой левый путь. Например, если тепловоз заберет 2 вагона с пути номер 3 на путь номер 1, то после такого действия распределение вагонов по путям будет таким.
А В Б А В
Б В А
Б
Соответствующую команду перемещения будем записывать так.
2 3 1
Что означает, что необходимо передвинуть 2 вагона с пути номер 3 на путь номер 1. Первое число обозначает количество перемещаемых вагонов, второе число – номер пути, с которого нужно забрать вагоны, третье число – номер пути, на который нужно передвинуть вагоны.
Разработайте алгоритм действий машиниста, необходимых для того, чтобы сформировать на каждом из путей составы с одинаковыми фруктами (не важно, на каком именно пути). Алгоритм оформите в виде последовательности команд, записанных в отдельных строках. Каждая команда имеет указанный выше вид: сначала записано число передвигаемых вагонов, потом номер пути с которого передвигаются вагоны, затем номер пути, на который передвигаются вагоны.
Например, следующая запись:
2 3 1
1 2 3
означает «передвинуть 2 вагона с пути 3 на путь 1, затем передвинуть 1 вагон с пути 2 на путь 3».
1. Считаем количество вагонов с абрикосами, бананами и вишней на каждом пути. Для этого пройдемся по каждому пути и подсчитаем количество вагонов каждого фрукта. Инициализируем переменные a, b, c, которые будут хранить количество вагонов с абрикосами, бананами и вишней соответственно. Также создадим массивы fruits1, fruits2 и fruits3 для хранения порядка фруктов на каждом пути.
- Если ветки программы требуют объяснения, учителю следует объяснить их использование и необходимость для дальнейшего решения задачи.
2. Проверяем, есть ли фрукты, которых необходимо переместить. Сравниваем количество каждого фрукта на путях с общим количеством вагонов. Если какого-то фрукта нет на путях или его количество меньше общего количества вагонов, значит, нужно его переместить.
3. Если требуется переместить абрикосы:
- Если на пути 1 нет ни одного вагона с абрикосами, то нужно переместить все вагоны с абрикосами с других путей на путь 1. Для этого добавляем команду: "a 2 1", где a - количество вагонов с абрикосами, 2 - номер пути, с которого нужно переместить вагоны, 1 - номер пути, на который нужно переместить вагоны.
- Если на пути 2 нет ни одного вагона с абрикосами, а на пути 1 есть, то нужно переместить вагоны с пути 1 на путь 2. Для этого добавляем команду: "a 1 2".
- Если на пути 3 нет ни одного вагона с абрикосами, а на пути 1 и/или 2 есть, то нужно переместить вагоны с пути 1 и/или 2 на путь 3. Для этого добавляем команды: "a 1 3" и/или "a 2 3".
4. Если требуется переместить бананы и/или вишни, применяем аналогичные шаги для каждого фрукта.
5. Повторяем шаги 2-4 до тех пор, пока все фрукты не окажутся на одном пути.
6. В конце алгоритма добавляем команду "0 1 2" для перемещения всех вагонов с пути 1 на путь 2. Это необходимо, чтобы сформировать на каждом пути составы с одинаковыми фруктами.
Пример алгоритма для данной задачи:
a = количество вагонов с абрикосами
b = количество вагонов с бананами
c = количество вагонов с вишней
fruits1 = порядок фруктов на пути 1
fruits2 = порядок фруктов на пути 2
fruits3 = порядок фруктов на пути 3
Если a < общее количество вагонов или a = 0:
Если a = 0:
Добавить команду: "b 2 1"
Добавить команду: "c 3 1"
Иначе:
Если b = 0:
Добавить команду: "a 1 2"
Если c = 0:
Добавить команду: "a 1 3"
Иначе:
Добавить команду: "a 1 2"
Добавить команду: "c 3 2"
Иначе:
Если c = 0:
Добавить команду: "a 1 3"
Добавить команду: "b 2 3"
Иначе:
Добавить команду: "a 1 2"
Добавить команду: "b 1 3"
Добавить команду: "c 2 3"
Повторять шаги 2-4 пока a+b+c > общее количество вагонов:
Если b < общее количество вагонов или b = 0:
Если b = 0:
Добавить команду: "a 2 1"
Добавить команду: "c 3 1"
Иначе:
Если a = 0:
Добавить команду: "b 1 2"
Если c = 0:
Добавить команду: "b 1 3"
Иначе:
Добавить команду: "b 1 2"
Добавить команду: "c 3 2"
Иначе:
Если c = 0:
Добавить команду: "b 1 3"
Добавить команду: "a 2 3"
Иначе:
Добавить команду: "b 1 2"
Добавить команду: "a 1 3"
Добавить команду: "c 2 3"
Если c < общее количество вагонов или c = 0:
Если c = 0:
Добавить команду: "a 3 1"
Добавить команду: "b 2 1"
Иначе:
Если a = 0:
Добавить команду: "c 1 2"
Если b = 0:
Добавить команду: "c 1 3"
Иначе:
Добавить команду: "c 1 2"
Добавить команду: "b 2 3"
Иначе:
Если b = 0:
Добавить команду: "c 1 3"
Добавить команду: "a 3 2"
Иначе:
Добавить команду: "c 1 2"
Добавить команду: "a 1 3"
Добавить команду: "b 2 3"
Добавить команду: "0 1 2"