Задание 12

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

Пример 1

Задача

Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.

нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Дана программа для исполнителя Редактор:

    НАЧАЛО
    ПОКА нашлось (2222) ИЛИ нашлось (8888)
        ЕСЛИ нашлось (2222)
        ТО заменить (2222, 88)
        ИНАЧЕ заменить (8888, 22)
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
    КОНЕЦ

Какая строка получится в результате применения приведённой программы к строке, состоящей из $70$ идущих подряд цифр $8$? В ответе запишите полученную строку.

нашлось и заменить - типовые строковые операции, поэтому просто напишем код, соответстувующий описанному алгоритму

Java

public class Example2 {

    public static void main(String[] args) {
        // создаём строку
        String s = "";
        // добавляем в неё 70 символов '8'
        for (int i = 0; i < 70; i++) {
            s += "8";
        }
        // пока строка содержит "2222" или "8888"
        while (s.contains("2222")||s.contains("8888")){
            // если строка содержит "2222"
            if(s.contains("2222"))
                // заменяем "2222" на "88"
                // (очень важно писать именно s = s.replace(), иначе java создаст
                // новую строку с заменой, но никуда её не положит
                s = s.replace("2222","88");
            // если строка содержит "8888"
            else
                // заменяем "8888" на "22"
                s = s.replace("8888","22");
        }
        // выводим результат
        System.out.println(s);

    }
}

C++

#include <iostream>

int main() {
    // создаём строку
    std::string s = "";
    // добавляем в неё 70 символов '8'
    for (int i = 0; i < 70; i++) {
        s += "8";
    }
    // пока строка содержит "2222" или "8888"
    while (s.find("2222") != std::string::npos || s.find("8888") != std::string::npos) {
        // если строка содержит "2222"
        if (s.find("2222") != std::string::npos)
            // заменяем "2222" на "88"
            s = s.replace(s.begin(), s.end(), "88", "2222");
        // если строка содержит "8888"
        else
            // заменяем "8888" на "22"
            s = s.replace(s.begin(), s.end(), "22", "8888");

    }
    // выводим результат
    std::cout << s;
    return 0;
}

Python

# создаём строку
s = ""
# добавляем в неё 70 символов '8'
for i in range(70):
    s = s + "8"

# пока строка содержит "2222" или "8888"
while s.find("2222") != -1 or s.find("8888") != -1:
    # если строка содержит "2222"
    if s.find("2222") != -1:
        # заменяем "2222" на "88"
        s = s.replace("2222", "88")
    # если строка содержит "8888"
    else:
        # заменяем "8888" на "22"
        s = s.replace("8888", "22")

# выводим результат
print(s)

Вывод программы:

22

Ответ: 22

Пример 2

Задача

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл
    ПОВТОРИ число РАЗ
        последовательность команд
КОНЕЦ ПОВТОРИ

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

НАЧАЛО
сместиться на (–1, –2)
ПОВТОРИ n РАЗ
    сместиться на (a, b)
    сместиться на (-1, -2)
КОНЕЦ ПОВТОРИ
сместиться на (–24, -12)
КОНЕЦ

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

Эту задачу проще решить с помощью уравнения

запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:

$$\varDelta x = -1+n(a-1)-24=n(a-1)-25\\ \varDelta y = -2+n(b-1)-12=n(b-2)-14$$

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

$$0 = n(a-1)-25\\ 0 = n(b-2)-14$$

разрешима в целых числах относительно $a$ и $b$

Упростим:

$$n(a-1)=25\\ n(b-2)=14$$

Чтобы эта система решалась в целых числа, необходимо чтобы число n было одновременно делителем чисел $14$ и $25$

Наибольший общий делитель чисел $14$ и $25$ равен $1$

Ответ: 1.

Пример 3

Задача

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

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

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

сверху свободно     снизу свободно
слева свободно      справа свободно

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

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

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

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

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

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

1) 8

2) 12

3) 17

4) 21

   ПОКА слева свободно ИЛИ сверху свободно
   ЕСЛИ слева свободно
    ТО влево
      ИНАЧЕ вверх
    КОНЕЦ ЕСЛИ
   КОНЕЦ ПОКА

в программе один цикл со сложным условием, внутри которого расположен условный опера-тор «если»

в этой программе Робот не может разрушиться, так как возможность шага влево проверяется, а если влево ходить нельзя, то можно идти вверх, так как условие цикла «слева свободно ИЛИ сверху свободно» выполнено

Робот останавливается в клетке, где нарушается условие «слева свободно ИЛИ сверху свобод-но», в этой клетке должны быть стенки слева и сверху; таких клеток на поле всего три: конечная цель маршрута А1 и две «ложные цели» в В3 и Е1:

из п. 2 и 3 следует, что Робот успешно придет в клетку А1, если только он не попадёт в клетки В3 и Е1

подсчитаем, сколько есть клеток, из которых Робот попадает в клетку В3; Робот сначала идет влево до упора, потом – вверх, пока не упрётся в стенку сверху или не откроется «окно» влево; отметим голубым цветом все клетки, из которых Робот попадает в В3, их всего 13

кроме того, есть две клетки, из которых Робот попадает в Е1, они показаны фиолетовым цве-том:

таким образом, на поле есть всего 15 клеток, из которых Робот при выполнении заданной программы не попадает в клетку А1

следовательно, «нужных» клеток $36 – 15 = 21$

Ответ: 4.

Пример 4

Задача

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

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

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

сверху свободно     снизу свободно
слева свободно      справа свободно

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

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

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

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

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

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

1) 8

2) 15

3) 24

4) 27

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

обратим внимание, что в программе три цикла, причем два внутренних цикла вложены в один внешний

цикл

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

означает «двигаться вправо до упора», а цикл

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

означает «двигаться вниз до упора»

тогда программу можно записать в свободном стиле так:

ПОКА не пришли в угол
    двигаться вправо до упора
    двигаться вниз до упора
КОНЕЦ ПОКА

где угол – это клетка, в которой есть стенки снизу и справа

за каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь сначала вправо до упора, а затем – вниз до упора:

клетка, выделенная красным фоном особая – в ней заканчивается один шаг внешнего цик-ла и начинается следующий:

а) Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка

б) снизу есть стенка;

в) снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла.

в клетку F6 (это угол, где Робот остановился), Робот мог придти за один шаг внешнего цикла (за один «сапог») только из отмеченных клеток:

теперь отметим красным фоном особые клетки, которые удовлетворяют условиям а-в пункта 4 (см. выше), их всего 2:

7) отметим все пути в форме «сапога», которые приводят в особые клетки:

больше особых клеток (см. пункт 4) нет; всего отмечено 24 клетки (считая конечную клетку F6)

таким образом, правильный ответ – 3.

Ответ: 3.

Возможные ловушки и проблемы:

• нужно помнить, что внешний цикл может выполняться более одного раза; неучет этого обстоятельства приводит к неверному ответу 2 (15 клеток)
• важен порядок выполнения внутренних циклов (в данном случае сначала Робот идет вправо, а затем – вниз); при изменении этого порядка изменится и результат, в частно-сти, изменятся условия, определяющие особую клетку

Пример 6

Задача

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:

Длина(a) – возвращает количество символов в строке a. (Тип «целое») Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка») Склеить(a,b) – возвращает строку, в которой записаны сначала все символы

строки a, а затем все символы строки b. (Тип «строка»)

Значения строк записываются в одинарных кавычках (Например, a:='дом'). Фрагмент алгоритма:

i := Длина(a)
k := 2
b := 'А'
пока i > 0
    нц
    c := Извлечь(a,i)
    b := Склеить(b,c)
    i := i – k
    кц
b := Склеить(b,'Т')

Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?

1) ‘АДЕПТ’

2) ‘АДЗЕОП’

3) ‘АДТЕТПТ’

4) ‘АДЕОТ’

Эту задачу проще решить с помощью программирования. нц обозначает начало цикла, кц - конец.

Java

public class Example2 {

    public static void main(String[] args) {
        // создаём строку
        String a = "ПОЕЗД";
        int i = a.length();
        int k = 2;
        String b = "А";
        while (i > 0) {
            // индексация в строках идёт с нуля, а в задании с 1
            char c = a.charAt(i-1);
            b = b + c;
            i = i - k;
        }
        b = b + "Т";
        // выводим результат
        System.out.println(b);
    }
}

C++

#include <iostream>

int main() {
    // создаём строку
    std::string a = "POEZD";
    int i = a.length();
    int k = 2;
    std::string b = "A";
    while (i > 0) {
        // индексация в строках идёт с нуля, а в задании с 1
        char c = a[i-1];
        b = b + c;
        i = i - k;
    }
    b = b + "T";
    // выводим результат
    std::cout << b;
    return 0;
}

Python

# создаём строку
a = "ПОЕЗД"
i = len(a)
k = 2
b = "А"
while i > 0:
    # индексация в строках идёт с нуля, а в задании с 1
    c = a[i - 1]
    b = b + c
    i = i - k

b = b + "Т"
#  выводим результат
print(b)

На выходе получим:

АДЕПТ

Ответ: 1)

Задания для самостоятельного выполнения