(Д5) Анализ работы автомата, формирующего число по заданным правилам & Конспект При решении задач, в которых…

(Д5) Анализ работы автомата, формирующего число по заданным правилам

& Конспект

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

Основание системы счисления	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
MaxЦифра	1	2	3	4	5	6	7	8	9	А	В	C	D	E	F
MaxСумма цифр	IO2	H3	124	135	146	157	168	179	1810	19ц	IAi2	IBi3	ICu	IDi5	IEi6

1 Разбор типовых задач

Задача 1. Устройство считывает три двухзначных числа и строит по ним новое число по следующему алгоритму:

1) вычисляется сумма старших разрядов заданных чисел;

2) вычисляется сумма младших разрядов заданных чисел;

3) эти суммы записываются друг за другом без разделителей по возрастанию.

Пример. Заданы двухзначные числа: 11, 19, 87. Поразрядные суммы: 10, 17. Результат: 1017.

Какое из чисел может быть результатом работы такого устройства.

1) 2528 2) 129 3)311 4) 1613

Решение

В данной задаче речь идёт о сложении цифр неизвестных чисел. Пусть эти числа обознача­ются как X, У и ZИ записываются их в виде:

X = x1x2; У = z∕1z∕2; Z = z1z2

Суммы цифр, которые вычисляет автомат, есть:

Si = xχ + y1.κ S2 = x2 + <∕2.

Чтобы оценить возможные значения этих сумм, следует сложить цифры. Старшая цифра в двузначном числе может иметь значение от 1 до 9 (если она равна нулю, то число уже не бу­дет двузначным!), а младшая — значение от 0 до 9. Тогда сумма S1 = X1 + Y1Может иметь зна­чение от 3 до 27 (исходных чисел — три), а сумма S2 = x2 + У2 — значение от 0 до 27.

Теперь нужно просмотреть предлагаемые варианты ответов.

1) Число 2528.Оно может быть составлено из сумм 25 и 28. Но тогда вторая сумма превы­шает максимально возможное значение суммы трёх цифр (27), поэтому данный вариант отве­та не может быть правильным.

2) Число 129.Его можно представить или как сочетание сумм 1 и 29, или как сочетание сумм 12 и 9. Но первый вариант не подходит (сумма старших цифр трёх двузначных чисел может иметь наименьшее значение 3). Варианты 12 и 9 тоже не годится в качестве ответа, так как в условии задачи указано, что суммы должны записываться по возрастанию. Значит, этот вариант ответа тоже неверен.

3) Число 311.Рассуждая аналогично, его можно представить тоже как 3 и 11 или как 31 и 1. Очевидно, второй вариант записи не подходит, — а вот первый (3 и 11) вполне удовлетво­ряет условию задачи.

4) Число 1613.Его можно разделить на числа (суммы) 16 и 13, но они записаны не по воз­растанию, значит данный вариант ответа тоже ложный.

Следовательно, правильным является ответ 311, как запись сумм 3 и 11.

Ответ: число 311 (вариант ответа №3).

Задача 2. Устройство считывает три двухзначных числа и строит по ним новое число по следующему алгоритму:

1) вычисляется сумма старших разрядов заданных чисел;

2) вычисляется сумма младших разрядов заданных чисел;

3) эти суммы записываются друг за другом без разделителей по убыванию.

Пример. Заданы двухзначные числа: 11, 19, 87. Поразрядные суммы: 10, 17. Результат: 1710. Какое из чисел НЕ Может быть результатом работы такого устройства.

1) 228 2) 282 3) 120 4) 222

Решение

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

1) Число 228.Можно представить его как 2 и 28 или как 22 и 8. Первый вариант не годит­ся, но второй удовлетворяет условиям задачи.

2) Число 282.Его можно представить как 2 и 82 или как 28 и 2. Ни один из этих двух ва­риантов не годится: в обоих случаях одна из предполагаемых сумм выходит за пределы воз­можного диапазона значений суммы трёх цифр (от 3 до 27 — для старших и от 0 до 27 — для младших цифр).

3) Число 120.Представимо как 1 и 20 или как 12 и 0. Второй вариант удовлетворяет усло­виям Задачи.

4) Число 222. Представимо как 2 и 22 или как 22 и 2. Второй вариант также удовлетворя­ет условиям задачи.

Следовательно, единственный вариант ответа, который НЕ может быть результатом рабо­ты описанного в задаче автомата, — это число 282.

Ответ: число 282 (вариант ответа №2).

Задача 3. Устройство считывает четырёхзначное восьмеричное число и строит по нему но­вое число по следующему алгоритму:

1) вычисляется сумма первой и второй цифр;

2) вычисляется сумма третьей и четвёртой цифр;

3) эти суммы записываются друг за другом без разделителей по убыванию.

Пример. Задано число 7145. Суммы: 7 + 1 = 10; 4 + 5 = 11. Результат: 1110.

Какое из чисел может быть результатом работы такого устройства.

1) 119 2) 1213 3) 1411 4) 1715

Решение

Эта задача отличается от предыдущих тем, что к ней вычисления производятся в недеся­тичной системе счисления. В остальном принцип решения остается тот же.

Обозначаются неизвестные цифры числа как Х, у, г и T(подразумевается, что само число тогда имеет вид: Xyzt).

Суммы цифр, которые вычисляет автомат, — это:

S1 = х + у и S2 = 2 + T.

Оценивая возможные значения этих сумм, складываются восьмеричные цифры, которые могут меняться от 0 до 7. Тогда, согласно правилам восьмеричной арифметики, сумма двух таких цифр может меняться от 0 до 78 + 78 = 168.

Предлагаемые варианты ответов:

1) Число 119.Можно представить его как 11 и 9 или как 1 и 19. Однако ни один из этих вариантов записи не годится: в первом случае восьмеричная запись суммы не может содер­жать цифры больше 7, а во втором число 19 не может быть суммой двух восьмеричных цифр.

2) Число 1213.Его можно представить как 12 и 13. Оба эти числа могут быть суммами восьмеричных цифр (так как удовлетворяют допустимому диапазону значений таких сумм). Однако они записаны по возрастанию (а не по убыванию, как требуется в условии задачи). Поэтому данное число не может быть решением.

3) Число 1411.Его можно представить как 14 и 11. Обе эти составляющие могут быть зна­чениями сумм восьмеричных цифр, записаны они по убыванию. Значит, это число может быть решением данной задачи.

4) Число 1715.Может быть представлено как 17 и 15. Поскольку его первая составляю­щая (17) превышает максимально возможное значение суммы, данное число не может быть решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 1411.

Ответ: число 1411 (вариант ответа №3).

Задача 4. Алёша и Лена придумали такую игру с числами. Лена записывает четырёхзнач­ное шестнадцатеричное число, в котором все цифры не превышают 6, а Алёша придумывает новое шестнадцатеричное число по следующему алгоритму:

1) вычисляется шестнадцатеричная сумма двух первых разрядов числа, записанного Ле­ной, и сумма двух последних разрядов этого числа;

2) две вычисленные шестнадцатеричные суммы записываются друг за другом без раздели­телей по убыванию.

Пример. Лена записала число 3456. Поразрядные суммы: 7, В. Число, придуманное Алё­шей: В7.

Какое из чисел может получиться у Алёши (исходное число, записанное Леной, не извес­тно).

1)93 2) D5 3) 119 4) 6В

Решение

Задача решается аналогично предыдущей, однако при определении возможного диапазо­на значений сумм следует учитывать, что в задаче используется шестнадцатеричная система счисления, а на значения цифр исходного числа наложено ограничение: они не могут быть больше 6.

Обозначаются неизвестные цифры числа как Х, у, ZИ T(подразумевается, что само число тогда имеет вид: Xyzt).

Суммы цифр, которые вычисляет автомат, — это:

S1 = Х + у и S2= Z + T.

Оценивая возможные значения этих сумм, складываются шестнадцатеричные цифры, ко­торые по условию задачи могут меняться от 0 до 6. Тогда, согласно правилам шестнадцате­ричной арифметики, сумма двух таких цифр может меняться от 0 до 616 + 616 = C16 (1210).

Теперь просматриваются предлагаемые варианты ответов.

1) Число 93.Можно представить его как 9 и 3. Обе эти составляющие входят в допусти­мый диапазон значений суммы, записаны они по убыванию, значит, данное число может быть решением задачи.

2) Число D5.Его можно представить как D и 5. Поскольку первая составляющая (D) пре­вышает максимальное Значение шестнадцатеричной суммы двух шестербк, данное число не может быть решением.

3) Число 119.Его можно представить как 11 и 9 или как 1 и 19. В обоих вариантах пред­ставления числа в нём имеются составляющие, не являющиеся шестнадцатеричными цифра­ми (11 и 19) и превышающие максимально возможное значение суммы двух шестнадцатерич­ных шестёрок. Значит, это число тоже не может быть решением данной задачи.

4) Число 6В. Может быть представлено как 6 и В. Обе эти составляющие могут быть шест­надцатеричными суммами двух шестерок, но записаны они не по убыванию. Поэтому данное число не может быть решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 93.

Ответ: число 93 (вариант ответа №1).

Задача 5. Устройство считывает два двухзначных шестнадцатеричных числа, в которых все цифры не превышают 5, и вырабатывает новое шестнадцатеричное число по алгоритму:

1) вычисляется шестнадцатеричная сумма старших разрядов считанных чисел;

2) вычисляется шестнадцатеричная сумма младших разрядов считанных чисел;

3) вычисленные шестнадцатеричные суммы записываются друг за другом без разделителя по возрастанию.

Пример. Заданы числа 66 и 43. Поразрядные суммы: А, 9. Результат: 9А.

Какое из чисел может быть результатом работы такого устройства.

1) 8А 2)410 3) 9С 4)76

Решение

Задача решается аналогично предыдущей, но максимальное значение каждой из склады­ваемых цифр здесь равно 5 (а не 6).

Если складываются шестнадцатеричные цифры, которые по условию задачи могут ме­няться от 0 до 5, то сумма двух таких цифр может меняться от 0 до 516 + 516 = ∙A∙ιβ (lθιo)’

Теперь следует просматреть предлагаемые варианты ответов.

1) Число 8А. Можно представить его как 8 и А. Обе эти составляющие входят в допусти­мый диапазон значений суммы, записаны они по возрастанию, значит, данное число может быть решением задачи.

2) Число 410.Его можно представить как 4 и 10 или как 41 и 5. В обоих вариантах пред­ставления числа в нём имеются составляющие, не являющиеся шестнадцатеричными цифра­ми (10 и 41) и превышающие максимально возможное значение суммы двух шестнадцатерич­ных пятерок. Значит, это число не может быть решением данной задачи.

3) Число 9С. Его можно представить как 9 и С. Поскольку вторая составляющая (C) пре­вышает максимальное значение шестнадцатеричной суммы двух пятерок, данное число не может быть решением.

4) Число 76.Может быть представлено как 7 и 6. Обе эти составляющие могут быть шест­надцатеричными суммами двух пятерок, но записаны они не по возрастанию. Поэтому дан­ное число не может быть решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 8А.

Ответ: число 8А (вариант ответа №1).

Задача 6. Устройство считывает два двухзначных восьмеричных числа и вырабатывает новое восьмеричное число по алгоритму:

1) вычисляется восьмеричная сумма старших разрядов считанных чисел;

2) вычисляется восьмеричная сумма младших разрядов считанных чисел;

3) вычисленные восьмеричные суммы записываются друг за другом без разделителя по убыванию.

Пример. Заданы числа 66 и 24. Поразрядные суммы: 10, 12. Результат: 1210.

Какое из чисел может быть результатом работы такого устройства.

1)27 2)112 3) 129 4)2111

Решение

В данной задаче используется восьмеричная арифметика. Решение аналогично решению задачи №3.

Обозначаются неизвестные числа как X = x1x2иY=J∕ιi∕2∙

Суммы цифр, которые вычисляет автомат, — это:

Sι = xι + У1 иS2 = X2 + У2-

Оценивая возможные значения этих сумм, складываются восьмеричные цифры, которые могут меняться от 0 до 7. Тогда, согласно правилам восьмеричной арифметики, сумма двух таких цифр может меняться от 0 до 78 + 78 = 168.

Теперь просматриваются предлагаемые варианты ответов.

1) Число 27.Можно представить как 2 и 7 или как 0 и 27. Второй случай явно недопустим (число 27 слишком велико). В первом случае обе составляющие входят в допустимый диапа­зон значений суммы восьмеричных цифр, но записаны не по убыванию. Поэтому данное чис­ло не может быть решением задачи.

2) Число 112.Его можно представить как 11 и 2 или как 1 и 12. В обоих случаях составля­ющие числа допустимы по величине, при этом в первом случае они записаны по убыванию. Значит, данное число может быть решением задачи.

3) Число 129.Его можно представить как 12 и 9 или как 1 и 29. В первом случае в записи числа присутствует цифра 9, недопустимая в восьмеричной системе счисления. Во втором случае вторая составляющая превышает максимально возможное значение суммы восьме­ричных цифр и также содержит недопустимую цифру (9). Следовательно, это число не явля­ется решением задачи.

4) Число 2111.Может быть представлено как 21 и 11. Первая составляющая превышает максимально возможное значение суммы восьмеричных цифр, поэтому данное число тоже не является решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 112.

Ответ: число 112 (вариант ответа.№2).

Задача 7. Устройство считывает трёхзначное десятичное число и вырабатывает новое чис­ло по алгоритму:

1) вычисляется произведение первой и второй цифр считанного числа;

2) вычисляется произведение второй и третьей цифр считанного числа;

3) вычисленные произведения записываются друг за другом без разделителя по возраста­нию.

Пример. Задано трёхзначное число 157. Произведения: 1 • 5 = 5; 5 • 7 = 35. Результат: 535.

Какое из чисел может быть результатом работы такого устройства.

1) 1214 2) 1612 3)2433 4)244

Решение

Здесь вместо сложения используется операция умножения цифр, но смысл решения оста­ется прежним.

Обозначается неизвестное число как X = x1x2x3. Тогда произведения цифр, которые вы­числяет автомат, — это:

Pi = xi ∙ X2и P2 = x2 ∙ х3

Оценивая возможные значения этих произведений, умножаются десятичные цифры, ко­торые могут меняться от 0 до 9. Произведение двух таких цифр может меняться от 0 до 81. Однако из-за того, что цифра X2входит в оба этих произведения, кроме вхождения в допусти­мый диапазон при анализе записи числа необходимо также проверять, чтобы обе составляю­щие числа имели общий делитель, равный от 1 до 9, и при делении на него также давали ре­зультат от 1 до 9.

Теперь просматриваются предлагаемые варианты ответов.

1) Число 1214.Можно представить его как 12 и 14. Обе составляющие входят в допусти­мый диапазон значений произведений десятичных цифр, имеют общий делитель 2 (12 = 2 • 6, 14 = 2- 7), записаны по возрастанию, поэтому данное число может быть решением задачи.

2) Число 1612.Его можно представить как 16 и 12. Обе составляющие входят в допусти­мый диапазон значений произведений десятичных цифр, но записаны не по возрастанию, по­этому данное число не является решением задачи.

3) Число 2433.Его можно представить как 24 и 33. Обе составляющие входят в допусти­мый диапазон значений произведений десятичных цифр и имеют единственный общий дели­тель 3. Но 24 = 3 • 7, а 33 = 3 • 11, т. е. число 33 не может быть произведением цифр при общем делителе 3. Поэтому данное число не является решением задачи.

4) Число 244.Может быть представлено как 2 и 44 или как 24 и 4. В первом случае общим делителем может быть только 2, но тогда второе число 44 — 2 • 22 и не может быть произведе­нием цифр. Во втором случае имеется два общих делителя: 2 и 4. При общем делителе, рав­ном 2, получается: 24 = 2 • 12. Такой вариант, очевидно, недопустим. При общем делителе, равном 4, получается: 24 = 4 • 6. Этот вариант «разложения» числа 244 допустим, но состав­ляющие 24 и 4 записаны не по возрастанию. Поэтому данное число тоже не является решени­ем задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 1214.

Ответ: число 1214 (вариант ответа №1).

Задача 8. Автомат получает на вход два трёхзначных числа. По этим числам строится но­вое число по следующим правилам.

1. Вычисляются три числа — сумма старших разрядов заданных трёхзначных чисел, сум­ма средних разрядов этих чисел, сумма младших разрядов.

2. Полученные три числа записываются друг за другом в порядке убывания (без раздели­телей).

Пример. Исходные трёхзначные числа: 835, 196. Поразрядные суммы: 9, 12, 11. Резуль­тат: 12119.

Определите, какое из следующих чисел может быть результатом работы автомата.

1) 15012 2) 191313 3) 121111 4) 10911

Решение

Усложнение данной задачи по сравнению с предыдущими — в том, что автомат вычисляет не два, а три числа.

Обозначаются неизвестные числа как X = xix2x3иY= УгУгУз*

Суммы цифр, которые вычисляет автомат, — это:

Si = Xi + t/р S2 = x2 + У2 и S3 = x3 + y3.

Используется десятичная система счисления, поэтому цифры могут меняться от 0 до 9, а их сумма может меняться от 0 до 18.

Теперь просматриваются предлагаемые варианты ответов.

1) Число 15012.Можно представить следующим образом:

• 1, 50, 12 — число 50 превышает максимально возможное значение суммы цифр;

• 15, 0, 12 — значения составляющих допустимы, но записаны не по убыванию.

Поэтому данное число не может быть решением задачи.

2) Число 191313.Его можно представить как 19, 13 и 13. Первая составляющая превыша­ет максимально допустимую величину суммы двух десятичных цифр. Поэтому данное число тоже не может быть решением задачи.

3) Число 121111.Его можно представить как 12, 11 и 11. Все три составляющие соответс­твуют диапазону возможных значений суммы двух десятичных цифр и записаны по убыва­нию (невозрастанию). Следовательно, это число может являться решением задачи.

4) Число 10911. Можно представить его следующим образом:

• 10, 9, 11 — значения составляющих допустимы, но записаны не’по убыванию;

• 10, 91, 1 — число 91 превышает максимально возможное значение суммы цифр.

Поэтому данное число не может быть решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 121111.

Ответ: число 121111 (вариант ответа №3).

Задача 9. Предлагается некоторая операция над двумя произвольными трёхзначными де­сятичными числами:

1) записывается результат сложения значений старших разрядов заданных чисел;

2) к нему дописывается результат сложения значений средних разрядов этих чисел по та­кому правилу: если он меньше первой суммы, то второе полученное число приписывается к первому слева, иначе — справа.

3) итоговое число получают приписыванием справа к полученному после второго шага числу суммы значений младших разрядов исходных чисел.

Определите, какое из предложенных чисел может быть результатом такой операции.

1) 161312 2) 171918 3) 131808 4) 141711

Решение

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

Используется десятичная система счисления, поэтому цифры могут меняться от 0 до 9, а их сумма может меняться от 0 до 18.

Теперь просматриваются предлагаемые варианты ответов.

1) Число 161312.Его можно представить как 16, 13 и 12. Все три составляющие соответс­твуют диапазону возможных значений суммы двух десятичных цифр, но записаны они в по­рядке, не удовлетворяющем условию задачи (вторая составляющая меньше первой). Значит, данное число не может быть решением задачи.

2) Число 171918.Его можно представить как 17, 19 и 18. Вторая составляющая превыша­ет максимально допустимую величину суммы двух десятичных цифр, поэтому данное число тоже не может быть решением задачи.

3) Число 131808.Его можно представить как 13, 18 и 08. Здесь запись третьей составляю­щей некорректна (если бы сумма младших цифр исходных чисел была равна 8, то полученное число имело бы вид 13188). Поэтому данное число также не может являться решением задачи.

4) Число 141711.Его можно представить как 14, 17 и 11. Все три составляющие соответс­твуют диапазону возможных значений суммы двух десятичных цифр, записаны они в поряд­ке, удовлетворяющем условию задачи (вторая составляющая больше первой). Значит, данное число может быть решением задачи.

Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 141711.

Ответ: число 141711 (вариант ответа №4).

X Задачи для самостоятельного решения

1. Устройство получает на вход два двузначных шестнадцатеричных числа. В этих чис­лах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат от­казывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

1. Вычисляются два шестнадцатеричных числа — сумма старших разрядов заданных чисел и сумма младших разрядов этих чисел.

2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Определите, какое из предложенных чисел может быть результатом работы автомата.

1)AF 2)410 3) 4)76

2. Устройство получает на вход четырёхзначное восьмеричное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая И вторая, а также третья и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке возрастания (без раз­делителей).

Определите, какое из следующих чисел может быть результатом работы автомата.

1)912 2) 1213 3) 1517 4) 1715

3. Устройство получает на вход трёхзначное пятеричное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, а также вторая и третья цифры.

2. Полученные два числа записываются друг за другом в порядке убывания (без разде­лителей).

Определите, какое из следующих чисел может быть результатом работы такого уст­ройства.

1)35 2)604 3)81 4)91

4. Автомат получает на вход четыре трёхзначных троичных числа. По этим числам стро­ится новое число по следующим правилам.

1. Вычисляются три числа — сумма старших разрядов заданных чисел, сумма их сред­них разрядов и сумма младших разрядов.

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

Какое из следующих чисел не может быть результатом работы такого автомата.

1) 738 2) 782 3) 321 4) 100

5. Автомат получает на вход два трёхзначных числа. По этим числам строится новое чис­ло по следующим правилам.

1. Вычисляются три числа — сумма старших разрядов заданных трёхзначных чисел, сумма средних разрядов этих чисел, сумма младших разрядов.

2. Полученные три числа записываются друг за другом в порядке убывания (без разде­лителей).

Определите, какое из следующих чисел может быть результатом работы автомата.

1)151413 2)141513 3)14019 4)191611

Ответы для самопроверки

№ задания	Ответ
1	3
2	2
3	3
4	1
5	1

1 О день

Элементы теории алгоритмов

ζ А1з) Робот в лабиринте

О Конспект

Исполнитель — Любое устройство или живое существо, которое способно точно и одно­значно выполнять заданные команды (действия, заданные алгоритмом).

Система команд исполнителя — Совокупность команд, которые он способен выполнять.

Алгоритм — Запись в той или иной форме (словесной, графической, на языке программи­рования) последовательности команд для исполнителя. Команды алгоритма должны соот­ветствовать системе команд исполнителя.

Исполнитель РОБОТ — Перемещается по клеткам лабиринта.

Типичная система команд:

• перемещение: вверх, вниз, влево, вправо;

• проверка наличия препятствия (стенки): сверху свободно, снизу свободно, слева свобод­но, справа свободно — играют роль условия;

• команда ветвления:

ЕСЛИ <условие>

ТО команда!

ИНАЧЕ команДа2

КОНЕЦ ЕСЛИ

— выполняется Команда! (если Условие истинно) или Команда2 (если Условие ложно), где ус­ловие — это команда проверки наличия препятствия;

• команда цикла:

ПОКА <условие> команда или

ПОКА <условие> последовательность команд

КОНЕЦ ПОКА

— выполняется, пока Условие истинно (условие — это команда проверки наличия препят­ствия).

IBlРазбор типовых задач

Задача 1*. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабирин­те на клетчатой плоскости:

Вверх

Вниз

Влево

Вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответ­ственно: вверх ↑, вниз влево вправо —

Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цйкл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную про­

НАЧАЛО

ПОКА ссправа свободно> вправо ПОКА ссверху свободно> вверх ПОКА <слева свободно> влево ПОКА <снизу свободно> вниз КОНЕЦ

Решение

Проще всего решить эту задачу, что называется, «в лоб», — поочередно перебирая каж­дую клетку лабиринта и «проводя» робота из неё по маршруту согласно заданной програм­ме. Но такой способ требует слишком много времени, поскольку приходится проверять 36 вариантов (клеточек). Поэтому основная задача — научиться заранее отсекать заведомо не­подходящие варианты, чтобы найти решение достаточно быстро (так как время на ЕГЭ ог­раничено).

Прежде всего, нужно обратить внимание на то, что Робот, с какой бы клеточки он ни на­чинал движение, однозначно останавливается (согласно программе) перед преграждающей ему путь стенкой. Поэтому проще всего сначала определить клеточки, в которых Робот дол­жен согласно его программе завершать движение. Таких клеточек будет не так много, а даль­ше можно проверять каждую из них на соответствие условию: мог ли Робот прийти в эту клетку, начав движение с неё же?

ABCDEF

В данном случае Робот завершает программу, если обнаружива­ет стенку снизу. Отмечаются на схеме лабиринта все такие точки, — их оказывается всего 12 (а не 36):

Теперь они поочередно перебираются и проверяются, сможет ли Робот, начав путь из ка­кой-либо точки, вернуться в неё. При этом следует учесть, что если движение в каком-то на­правлении невозможно, так как оно изначально! перекрыто стенкой, то соответствующая строка программы пропускается, и происходит переход к следующей.

6 5 4 3 2 1

ABCDEF

На рисунке ниже показаны маршруты движения Робота из каждой отмеченной точки (толстые стрелки — Робот возвращается в ту же точку; тонкие стрелки — Робот останавливается в другой клетке).

Итого — 4 клеточки, удовлетворяющие условию.

Ответ:4 (вариант №4).

Задача 2. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

Вверх	Вниз	Влево	Вправо
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответс­твенно: вверх ↑, вниз |, влево •<—, вправо Четыре команды проверяют истинность условия отсутствия стены у каждой той клетки, где находится РОБОТ:
Сверху свободно	Снизу свободно	Слева свободно	Справа свободно

Цикл

ПОКА <условие> команда

Выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток приведенного лабиринта соответствует требованию, что, выполнив пред­ложенную ниже программу, РОБОТ уцелеет и остановится в той же клетке, с которой он на­чал движение?

НАЧАЛО

ПОКА <сверху свободно> вправо

ПОКА <справа с'вободно> вниз ПОКА <снизу свободно> влево ПОКА <слева свободно> вверх

Решение

В этой задаче есть дополнительное усложнение. Ранее каждая команда ПОКА содержала как условие, так и команду движения, «одинаковой направленности», например: ПОКА <снизу свободно> вниз. Это было очевидным: РОБОТ двигается вниз, пока не встретит на своём пути стенку и не остановится. Теперь же направления движения и условия остановки РОБОТа в каждой команде ПОКА различны. Поэтому при решении такой задачи следует быть более внимательными: РОБОТ либо может остановиться, когда стенка (как условие останов­ки движения) появится в очередной клетке, в которую он перейдёт, с соответствующего бока, либо может разрушиться, если первой встретится стенка, перекрывающая ему путь (тогда как с соответствующего бока стенки, которая бы его остановила, нет). В условии таких задач обычно особо оговаривается факт разрушения РОБОТа, натолкнувшегося на полном ходу на стенку (в данном случае оно опущено).

В остальном же принципы решения такой задачи традиционны.

Сначала надо обратить внимание на последнюю команду программы РОБОТа, которая оп­ределяет клетку, в которой РОБОТ может остановиться (если, конечно, не разобьётся рань­ше) по окончании программы. В данном случае это команда

ПОКА <слева свободно> вверх

Т. е. РОБОТ может остановиться только в клетках, в которых имеется левая стенка. Все такие

Клетки помечаются кружочками:

Далее нужно проверить работу программы РОБОТа для каждой отмеченной точки, прори­совывая получаемые траектории и особо отмечая клетки, для которых выполняется условие задачи: совпадение начальной и конечной точки маршрута. Для наглядности это лучше раз­работать на отдельных рисунках для каждой намеченной ранее ячейки:

— сверху есть стенка — вправо движения нет;

— движение вниз, пока справа не появится стенка;

— снизу стенки нет, поэтому РОБОТ пойдёт влево и разобьётся.

— движение вправо, пока не появится стенка сверху;

— движение вниз, пока справа не появится стенка: однако ещё до этого РОБОТ наткнётся на стенку и разобьётся.

— очевидно, РОБОТ разобьётся сразу же, поскольку попытается двигаться вправо (сверху стенки нет).

— движение вправо, пока не появится стенка сверху;

— движение вниз, пока не появится стенка справа;

— движение влево, пока не появится стенка снизу, а поскольку её нет, РОБОТ разобьётся.

— движение вправо, пока не появится стенка сверху; очевидно, при этом РОБОТ разобьётся.

— движение вправо» пока не появится стенка сверху; аналогично, при этом РОБОТ разобьётся.

— сверху есть стенка — вправо движения нет;

— движение вниз, пока справа не появится стенка;

— снизу есть стенка — влево движения нет;

— движение вверх, пока слева не появится стенка.

ДАННАЯ КЛЕТКА УДОВЛЕТВОРЯЕТ УСЛОВИЮ ЗАДАЧИ

— сверху есть стенка — вправо движения нет;

— справа есть стенка — вниз движения нет;

— снизу стенки нет, поэтому РОБОТ начнёт двигаться влево и ра­зобьётся.

— сверху есть стенка — вправо движения нет;

— движение вниз, пока справа не появится стенка;

— снизу есть стенка — влево движения нет;

— движение вверх, пока слева не появится стенка.

ДАННАЯ КЛЕТКА ТАКЖЕ УДОВЛЕТВОРЯЕТ УСЛОВИЮ

ЗАДАЧИ

— движение вправо, пока не появится стенка сверху; очевидно, при этом РОБОТ разобьётся.

— поскольку данная ячейка окружена стенками со всех сторон, никакого движения РОБОТА не будет. Значит, можно формально считать, что РОБОТ по окончании работы программы будет в той же самой клетке, что и в начале.

ДАННАЯ КЛЕТКА УДОВЛЕТВОРЯЕТ УСЛОВИЮ ЗАДАЧИ

— стенки сверху нет, поэтому РОБОТ начнёт движение вправо и разобьётся.

— аналогично: стенки сверху нет, поэтому РОБОТ начнёт движе­ние вправо и разобьётся.

— движение вправо, пока сверху не появится стенка;

— стенки справа нет, поэтому РОБОТ начнёт движение вниз и ра­зобьётся.

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

Ответ:3 клетки (вариант ответа №3).

В подобных задачах в командах ПОКА проверяется наличие соответствующей стенки (левой, пра­вой, верхней или нижней) по отношению к Текущей Ячейке, в которой находится РОБОТ, а не по отношению к самому РОБОТу с учётом направления его движения.

Задача 3*. Система. команд исполнителя РОБОТ, «живущего» в прямоугольном лабирин­те на клетчатой плоскости:

Вверх

Вниз

Влево

Вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответ­ственно: вверх ↑, вниз |, влево ■<—, вправо →.

Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную про­грамму, РОБОТ остановится в той же клетке, с которой он начал движение?

НАЧАЛО

ПОКА <сверху свободно вправо ПОКА ссправа свободно вниз ПОКА <снизу свободно> влево ПОКА <слева свободно вверх КОНЕЦ

1) 1 2)2 3)3 4)4

Решение

Данная задача аналогична предыдущей и её решение аналогично.

Размечаются клетки окончания пути по признаку — стенка стоит слева от них:

Проверяются найденные клетки (толстые стрелки — успешный маршрут, тонкие — неус­пешный маршрут, крестиком показаны места разрушения РОБОТа при движении на стенку):

Ответ:1 клеточка (вариант №1).

Задача 4. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

Вверх

Вниз

Влево

Вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответ­ственно: вверх ↑, вниз влево ∙,~, вправо —*■.

Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл

ПОКА <условие> последовательность команд

КОНЕЦ ПОКА

Выполняется, пока условие истинно.

В конструкции

ЕСЛИ <условие> ТО команда! ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

Выполняется команда! (если условие истинно) или команда2 (если условие ложно).

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушит­ся и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и вы­полнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

НАЧАЛО

ПОКА Ссправа свободно ИЛИ снизу свободно> ПОКА <справа свободно> вправо КОНЕЦ ПОКА ПОКА Сснизу свободно> вниз КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

Решение

Особенность этой задачи по сравнению с традиционной в том, что здесь программа для PO — БОТа состоит не из линейной последовательности из нескольких циклов ПОКА, каждый из ко­торых определяет количество шагов движения в одном из четырёх направлений, а из вложен­ных циклов ПОКА. Соответственно, иным будет и путь решения задачи.

Проанализируем заданную в условии программу для РОБОТа.

Во-первых, вместо компактной однооператорной записи циклов ПОКА (например: ПОКА <справа свободней вниз) используется полная запись с использованием особой завершаю­щей команды КОНЕЦ ПОКА. Однако это — лишь формальное изменение, важное только для об­рамляющего цикла ПОКА, тогда как внутренние (вложенные) циклы легко представить в пре­жней, компактной форме:

НАЧАЛО

ПОКА <справа свободно ИЛИ снизу свободно>

ПОКА <справа свободно> вправо

ПОКА <снизу свободно> вниз

КОНЕЦ ПОКА

КОНЕЦ

В этом виде программа становится несколько более простой и понятной; в ней легче вы­явить аналогию с традиционным вариантом задач про РОБОТа.

Во-вторых, внутренние (вложенные) циклы ПОКА, как и раньше, определяют перемеще­ние РОБОТа в соответствующем направлении, пока с указанной стороны от него не будет об­наружена стенка: первый вложенный цикл ПОКА определяет движение вправо до стенки справа, а второй цикл ПОКА — движение вниз до стенки снизу. В сумме же это означает, что РОБОТ должен двигаться «Г-образно»: сначала вправо до препятствия, а потом вниз до пре­пятствия.

В-третьих, условие внешнего цикла ПОКА <справа свободно ИЛИ снизу свободно>по­казывает, что вся «Г-образная» траектория движения РОБОТа может повторяться много­кратно, если после остановки РОБОТа из-за препятствия в виде стенки внизу выяснится, что справа стенки нет: тогда РОБОТ может снова двигаться вправо до препятствия вправо, а по­том вниз до препятствия снизу. Согласно принципам работы цикла ПОКА, условие внешне­го цикла проверяется тогда и только тогда, когда РОБОТ уже завершил проход очередного «Г-образного» фрагмента пути, а не, например, по завершении выполнения первого из двух вложенных циклов ПОКА или в процессе их выполнения. То есть отработка каждого из внут­ренних циклов ПОКА является процессом, полностью не зависимым от условия внешнего цикла.

Наконец, запись условия внешнего цикла: <справа свободно ИЛИ снизу свободно>оз­начает, что завершение выполнения этого внешнего цикла ПОКА и, соответственно, заверше­ние работы программы РОБОТа происходит, когда препятствие (стенка) имеется И справа, И снизу от текущего расположения РОБОТа. Следовательно, «финальной» ячейкой (имеется в виду «благополучный» финал при корректном завершении работы программы, а не авария, когда РОБОТ разбивается о «незамеченную» им стенку; впрочем, структура вложенных цик­лов ПОКА такой аварийный случай исключает) может быть только ячейка, ограниченная стен­ками снизу и справа.

В представленном лабиринте:

Этим условиям соответствуют только три ячейки: F6 (требуемая), F2 и D5 («ложные»). При этом «ложные» ячейки можно рассматривать как «ловушки» для РОБОТа, попадание в кото­рые делает требуемый результат работы его программы невозможным.

Теперь, вернувшись к вложенным циклам ПОКА нужно рассмотреть, как РОБОТ будет со­гласно этим командам двигаться по лабиринту.

Очевидно, что первый вложенный цикл ПОКА для любой исходной ячейки определяет одно и то же движение РОБОТа вправо до ближайшей стенки справа. Следовательно, можно разде­лить весь лабиринт на такие фрагменты (последовательности ячеек в одной строке), которые завершаются стенкой справа (внешней границей лабиринта или промежуточной стенкой).

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

A1:F1, A2:F2, A3:F3, A4:F4, A5:D5, E5:F5, A6:F6.

Учитывая сказанное выше, не обязательно проверять все ячейки лабиринта — достаточно в каждом диапазоне проверить только по одной любой ячейке — например, крайней слева (т. е. проверить, например, ячейки Al, А2, АЗ, A4, A5, Е5 и А6). Однако в случае успешного перемещения POBOTa из проверяемой ячейки в «целевую» ячейку F6 нужно подсчитать как удовлетворяющие условию задачи все ячейки соответствующего диапазона.

Ячейка Al. Движение POBOTa вправо будет происходить до правой границы лабиринта, после чего он будет двигаться вниз до ячейки F2 («ловушки»). Поэтому ни одна ячейка диа­пазона Al :F1 не подходит.

Ячейка А2. РОБОТ из неё тоже будет двигаться вправо до правой границы лабиринта (до ячейки-«ловушки» F2), после чего в ней и останется, — второй вложенный цикл ПОКА просто не будет выполняться, так как снизу от ячейки F2 есть стенка. Значит, ни одна ячейка диапа­зона A2:F2 нам тоже не подходит.

Ячейка АЗ. Движение POBOTa вправо опять-таки будет совершаться до правой границы лабиринта, а затем РОБОТ пойдёт вниз до требуемой ячейки F6. Следовательно, все ячейки диапазона A3:F3 (их — 6) являются решениями данной задачи.

Ячейка А4. Повторив те же самые рассуждения для неё, выясняется, что все ячейки диа­пазона A4:F4 также являются решениями задачи (это ещё 6 ячеек).

Ячейка А5. Очевидно, что РОБОТ при движении вправо попадёт в ячейку-«ловушку» D5 и останется в ней (так как вниз идти ему некуда). Поэтому все ячейки диапазона A5:D5 не пригодны.

ABCDEF

Ячейка Е5. Здесь, напротив, РОБОТ, выполняя свою программу, благополучно дойдёт до нужной ячейки F6. Тем самым определились ещё 2Ячейки диапазона E5:F5, которые явля­ются решением задачи.

Ячейка А6. Для неё, а значит, и для всех 6 ячеек диапазона A6:F6 выполнение РОБОТом заданной программы благополучно приведёт его в нужную ячейку F6.

Итого решениями задачи являются: 6 ячеек диапазона A3:F3, 6 ячеек диапазона A4:F4, 2 ячейки диапазона E5:F5 и 6 ячеек диапазона A6:F6 (включая «целевую» F6: если РОБОТ изначально в ней находился, то в ней он и останется, т. е. условие задачи тоже будет выпол­нено), то есть всего — 6 + 6 + 2 + 6 = 20 ячеек.

 

Ответ:20 клеток (вариант ответа №4).

Задача 5. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

Вверх

Вниз

Влево

Вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответс­твенно: вверх ↑, вниз влево <—, вправо →.

Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл

ПОКА <условие> последовательность команд КОНЕЦ ПОКА

Выполняется, пока условие истинно.

В конструкции

ЕСЛИ <условие>

ТО команда!

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

Выполняется команда! (если условие истинно) или команда2 (если условие ложно).

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушит­ся и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и вы­полнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

НАЧАЛО

ПОКА <справа свободно ИЛИ снизу свободно> ПОКА Сснизу свободно> вниз’ КОНЕЦ ПОКА ПОКА Ссправа свободно> вправо КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

1) 14 3) 19

2) 17 4) 21

Решение

1. Вложенные циклы — их можно записать в компактной форме:

ПОКА <снизу свободно> вниз

ПОКА <справа свободно> вправо

Определяют «Г-образное» движение РОБОТа сначала вниз до обнаружения стенки внизу, а за­тем вправо до обнаружения стенки справа.

2. Внешний цикл ПОКА с условием <справа свободно ИЛИ снизу свободно>указыва­ет, что такие «Г-образные» фрагменты пути РОБОТа могут повторяться, если по завершении выполнения предыдущего такого фрагмента выяснится, что можно продолжить движение вниз. Завершится же этот внешний цикл ПОКА (и, соответственно, вся программа) тогда, ког­да стенка будет И снизу, И справа от текущего местоположения РОБОТа. То есть, финальны­ми могут быть ячейки, ограниченные стенками снизу и справа.

Из трёх таких ячеек две (F2 и D5) — ложные («ловушки»), а одна — требуемая согласно условию задачи (F6).

3. Из вложенных циклов ПОКА первым отрабатывается цикл, который определяет движе­ние РОБОТа по вертикали вниз до обнаружения первой же стенки снизу. Поэтому весь лаби­ринт можно разделить на фрагменты (диапазоны) столбцов ячеек, и в каждом таком диапазо­не все его ячейки «равноправны» (т. е. все они или являются, или не являются решениями за­дачи, если хотя бы одна любая ячейка диапазона является или, наоборот, не является решением). Поэтому из выделенных диапазонов: А1:А6, В1:В2, ВЗ:В5, В6 (диапазон может состоять и только из одной ячейки!), С1:С5, С6, D1:D2, D3:D5, D6, Е1:Е6, F1:F2, F3:F6, — до­статочно проверять ячейки: Al, Bl, ВЗ, В6, Cl, С6, Dl, D3, D6, El, Fl и F3.

4. Ячейка Al. РОБОТ Движется вниз до нижней границы лабиринта, затем при выполне­нии второго вложенного цикла ПОКА следует до требуемой ячейки F6. Значит, все 6 ячеек диапазона А1:А6 являются решениями задачи.

Ячейка Bl. РОБОТ дойдёт до промежуточной стенки, а затем, двигаясь вправо, попадёт в «ловушку» — ячейку F2. Значит, все ячейки диапазона В1:В2 не являются решением задачи.

Ячейка ВЗ. РОБОТ, выполняя программу, попадёт в «ловушку» D5, т. е. весь диапазон ВЗ:В5 не является решением.

Ячейка В6 (она одна в соответствующем диапазоне). РОБОТ вниз идти не может (внизу — граница лабиринта), поэтому первый из вложенных циклов не выполняется. В ходе же вы­полнения второго вложенного цикла РОБОТ благополучно попадает в требуемую ячейку F6. Значит, ячейка Вб — решение задачи.

Ячейка Cl. Повторяя рассуждения для неё, выясняется, что РОБОТ в результате выполне­ния программы попадёт в ячейку-«ловушку» D5. Значит, все ячейки рассматриваемого диа­пазона С1:С5 не являются решением.

Ячейка С6. Как и в случае с ячейкой Вб, она является решением.

Рассуждая далее в том же духе, нетрудно сделать выводы:

• ячейка Dl (и вообще все ячейки диапазона D1:D2) приведёт РОБОТа в «ловушку» F2, а ячейка D3 (как и все ячейки диапазона D3:D5) — в «ловушку» D5;

• ячейка D6 является решением;

• ячейка El (равно как и все ячейки диапазона Е1:Е6) тоже являются решениями (их — 6);

• ячейка Fl (и весь диапазон F1:F2) решением не является, так как приводит РОБОТа в «ловушку» F2, а вот ячейка F3 и вообще все 4 ячейки диапазона F3:F6 (включая «целе­вую») являются решениями.

Итого решениями задачи являются: 6 ячеек диапазона А1:А6, ячейки Вб, Сб, D6, б ячеек диапазона Е1:Еб и ещё 4 ячейки диапазона F3:F6. Всего — 6 + 1 + 1 + 1 + 6 + 4 = 19 ячеек.

Ответ:19 ячеек (вариант ответа №3).

ЗАдАча 6*. Исполнитель РОБОТ действует на клетчатой доске, между соседними клетка­ми которой могут стоять стены. РОБОТ передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направле­нии, указанном в скобках. Если в этом направлении между клетками стоит стена, то РОБОТ разрушается. Робот успешно выполнил программу 3233241.

Какую последовательность из трёх команд должен выполнить РОБОТ, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависи­мости от того, какие стены стоят на поле?

Решение

Это одна из более ранних задач про РОБОТа, несколько иная по характеру. Вид лабиринта здесь неизвестен, поэтому для решения требуется опираться только на информацию об успеш­ности прохождения заданного маршрута. Очевидно, что нужно построить такую эквивалент­ную программу, чтобы РОБОТ шёл по тем же самым клеткам, что и по исходной программе.

Вручную «интерпретируется» исходная программа для РОБОТа и одновременно прочер­чивается его маршрут:

Шаг программы	1	2	3	4	5	6	7
Команда	3	2	3	3	2	4	1 •
Расшифровка команды	Вправо	Вниз	Вправо	Вправо	Вниз	Влево	Вверх
Текущий маршрут Робота	—►

Полученный маршрут:

Этот маршрут содержит петлю, которую можно исключить и тем самым уменьшить длину программы. Оптимизированный маршрут имеет вид:

Соответствующая программа имеет вид: 323 (совпадает с началом исходной программы). Обратный маршрут имеет вид:

Соответствующая программа: 414 (влево, вверх, влево) Ответ:414.

Задача 7*. Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой до­ски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

Влево

Вверх вверх влево вниз вправо вправо вправо

Укажите наименьшее возможное число команд в программе, приводящей РОБОТа из той же начальной клетки в ту же конечную.

Решение

Эта задача во многом аналогична предыдущей — и даже проще неё, поскольку в условии не сказано, что нужно при движении РОБОТа опасаться стенок. Решение же в целом анало­гично предыдущему.

1. Рисуется маршрут РОБОТа, получаемый по исходной программе (на рисунке приведён окончательный вид маршрута; «н» — начало, «к» — конец):

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

Соответствующая программа: вверх, вправо, что составляет две команды.

Ответ:2.

X Задачи для самостоятельного решения

1. Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять коман­ды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направле­нии, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу 4413323.

Какой минимальной по длине последовательностью команд можно заменить эту про­грамму, чтобы Робот не разрушился вне зависимости от того, какие стены стоят на поле?

2. Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять коман­ды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направле­нии, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу 331133222441.

Какую минимальную по длине последовательность команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

3. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

Вверх вниз влево вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку со­ответственно: вверх ↑, вниз |, влево «—, вправо →.

Четыре команды проверяют истинность условия отсутствия стены у каждой сто­роны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл

ПОКА <условие> последовательность команд КОНЕЦ ПОКА

Выполняется, пока Условие истинно.

В конструкции

ЕСЛИ <условие>

ТО команда!

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

Выполняется команда! (если условие истинно) или команда2 (если условие ложно). Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разру­шится и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и вы­полнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клет­ке (клетка Е6)?

НАЧАЛО

ПОКА <справа свободно> И <снизу свободно ПОКА <справа свободно вправо КОНЕЦ ПОКА

ПОКА <снизу свободно вниз

КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

1) 8 2) 9 3) 10 4) 20

4. Система команд исполнителя РОБОТ:

Вверх

Вниз

Влево

Вправо

При выполнении команды РОБОТ перемещается на одну клетку: вверх ↑, вниз |,

Влево *—, вправо

Следующие команды проверяют истинность условия отсутствия стены у каждой стороны клетки, в которой находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Сколько клеток соответствуют требованию, что, начав движение в ней и выполнив

Предложенную программу, РОБОТ уцелеет и остановится в той же клетке, откуда на­

Чал движение:

ПОКА <слева свободно вниз ПОКА <снизу свободно> вправо ПОКА <справа свободно> вверх ПОКА <сверху свободно> влево КОНЕЦ

5. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

______ Вверх______ —J_______ Вниз______________ Влево_______ Вправо____________

При выполнении любой из этих команд РОБОТ перемещается на одну клетку со­ответственно: вверх ↑, вниз |, влево «—, вправо

Четыре команды проверяют истинность условия отсутствия стены у каждой сто­роны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл

ПОКА <условие> последовательность команд КОНЕЦ ПОКА

Выполняется, пока условие истинно.

В конструкции

ЕСЛИ <условие>

ТО команда!

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

Выполняется команда! (если условие истинно) или команда2 (если условие ложно).

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разру­шится и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и вы­полнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клет­ке (клетка F6)?

если <снизу . свободно то вниз конец если если <справа свободно> то вправо конец если конец пока
1) 18 2)24 3)21 4)27
» align=»left» width=»380″ height=»160″ class=»»/>1

2

3

4

5

6

Ответы для самопроверки

№ задания	Ответ
1	3
2	44
3	2
4	2
5	3

11 день