Образовательный портал Павла Добряка

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

Задача 6.1.1. Из букв О, С, Л, Ь, М, 3, А, И фор­ми­ру­ет­ся слово. Известно, что слово сфор­ми­ро­ва­но по сле­ду­ю­щим правилам:

а) в слове глас­ные буквы не стоят рядом;

б) пер­вая буква слова не яв­ля­ет­ся гласной и в рус­ском алфавите стоит до буквы «П».

Какое из сле­ду­ю­щих слов удо­вле­тво­ря­ет всем пе­ре­чис­лен­ным усло­ви­ям?

1) СОЛЬ

2) ОАЗИС

3) ОСЛО

4) МОЛЬ

Задача 6.1.2. Соня забыла пароль для запуска компьютера, но пом­нила алгоритм его получения из символов «КВМАМ9КВК» в строке подсказки. Если все последовательности символов «МАМ» заменить на «RP», «КВК» — на «1212», а из получив­шейся строки удалить 3 последние символа, то полученная пос­ледовательность и будет паролем:

1) KBRP91

2) 1212RP91

3) KBRP9

4) КВ91212

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

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

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

Пример. Ис­ход­ное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127. Ука­жи­те наи­мень­шее число, в ре­зуль­та­те об­ра­бот­ки ко­то­ро­го ав­то­мат вы­даст число 1412.

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

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

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

Пример. Ис­ход­ное число: 2366. Суммы: 2 + 3 = 5; 6 + 6 = 12. Результат: 512. Ука­жи­те наи­боль­шее число, в ре­зуль­та­те об­ра­бот­ки ко­то­ро­го ав­то­мат вы­даст число 117.

Задача 6.2.3. Автомат получает на вход четырёхзначное число (число не может начинаться с нуля). По этому числу строится новое число по следующим правилам:

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

2. Наименьшая из полученных трёх сумм удаляется.

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

Пример. Исходное число: 1984. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 4 = 12. Удаляется 10. Результат: 1217.

Укажите наибольшее число, при обработке которого автомат выдаёт результат 613.

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

1. Первая цифра числа Y (разряд сотен) — остаток от деления X на 4.

2. Вторая цифра числа Y (разряд десятков) — остаток от деления X на 3.

3. Третья цифра числа Y (разряд единиц) — остаток от деления X на 2.

Пример.

Исходное число: 63179. Остаток от деления на 4 равен 3; остаток от деления на 3 равен 2; остаток от деления на 2 равен 1. Результат работы автомата: 321.

Укажите наименьшее двузначное число, при обработке которого автомат выдаёт результат 101.

Задача 6.2.5. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

     а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

     б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

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

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

Задача 6.2.6. Автомат обрабатывает натуральное число N (0 ≤ N ≤ 255) по следующему алгоритму:

1. Строится восьмибитная двоичная запись числа N.

2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).

3. Полученное число переводится в десятичную запись.

4. Из нового числа вычитается исходное, полученная разность выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом.

1. Восьмибитная двоичная запись числа N: 00001101.

2. Все цифры заменяются на противоположные, новая запись 11110010.

3. Десятичное значение полученного числа 242.

4. На экран выводится число 242 − 13 = 229.

Какое число нужно ввести в автомат, чтобы в результате получилось 133?

Задача 6.2.7. Автомат убирает левую 1 из двоичной записи числа и вычитает полученное число из исходного. Числа от 10 до 1000. Сколько различных чисел получится в результате работы автомата, если вводятся на обработку числа от 10 до 1000.

Задача 6.3.1. Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 5 – Кузнечик прыгает вперёд на 5 единиц,

Назад 3 – Кузнечик прыгает назад на 3 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21? 

Задача 6.3.2. Исполнитель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плоскости, остав­ляя след в виде линии. Чертёжник может вы­пол­нять команду Сместиться на (a, b) (где a, b — целые числа), пе­ре­ме­ща­ю­щую Чертёжника из точки с координатами (x, у) в точку с ко­ор­ди­на­та­ми (x + а, у + b). Если числа a, b положительные, зна­че­ние соответствующей ко­ор­ди­на­ты увеличивается; если отрицательные - уменьшается.

 Например, если Чертёжник на­хо­дит­ся в точке с координатами (4, 2), то ко­ман­да Сместиться на (2, −3) пе­ре­ме­стит Чертёжника в точку (6, −1). 

 Запись 

Повтори k раз

Команда1 Команда2 Ко­ман­даЗ 

Конец

означает, что по­сле­до­ва­тель­ность команд Команда1 Команда2 КомандаЗ по­вто­рит­ся k раз.

 Чертёжнику был дан для ис­пол­не­ния следующий алгоритм: 

Повтори 2 раз

Команда1 

Сме­стить­ся на (3, 2) 

Сме­стить­ся на (2, 1) 

Конец

Сместиться на (−6, −4)

После вы­пол­не­ния этого ал­го­рит­ма Чертёжник вер­нул­ся в ис­ход­ную точку. Какую ко­ман­ду надо по­ста­вить вместо ко­ман­ды Команда1?

1) Сместиться на (−2, −1)

2) Сместиться на (1, 1)

3) Сместиться на (−4, −2)

4) Сместиться на (2, 1)

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

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

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

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

НАЧАЛО

сместиться на (1, 2)

ПОВТОРИ … РАЗ

сместиться на (…, …)

сместиться на (-1, -2)

КОНЕЦ ПОВТОРИ

сместиться на (-26, -12)

КОНЕЦ

В ре­зуль­та­те вы­пол­не­ния этого ал­го­рит­ма Чертёжник воз­вра­ща­ет­ся в ис­ход­ную точку. Какое наи­боль­шее число по­вто­ре­ний могло быть ука­за­но в кон­струк­ции «ПОВТОРИ … РАЗ»?

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

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

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

Цикл

ПОКА < условие >

последовательность команд

КОНЕЦ ПОКА

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

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

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

ТО команда1

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

КОНЕЦ ЕСЛИ

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

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

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

НАЧАЛО

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

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

вниз

КОНЕЦ ПОКА

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

вправо

КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

Задача 6.4.2. Пояснение и лабиринт такие же, как и в предыдущей задаче:

Алгоритм:

НАЧАЛО

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

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

вниз

КОНЕЦ ПОКА

ЕСЛИ < справа свободно >

вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Задача 6.4.3. Пояснение и лабиринт такие же, как и в задаче 6.4.1:

Алгоритм:

НАЧАЛО

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

ЕСЛИ < снизу свободно >

вниз

КОНЕЦ ЕСЛИ

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

вправо

КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

Задача 6.4.4. Пояснение и лабиринт такие же, как и в задаче 6.4.1:

Алгоритм:

НАЧАЛО

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

ЕСЛИ < снизу свободно >

вниз

КОНЕЦ ЕСЛИ

ЕСЛИ < справа свободно >

вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Задача 6.4.5. Пояснение такое же, как и в задаче 6.4.1.

Схема лабиринта:

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

НАЧАЛО

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

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

               вниз

          КОНЕЦ ПОКА

          вправо

     КОНЕЦ ПОКА

КОНЕЦ

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

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

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

Цикл

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

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

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

НАЧАЛО

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

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

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

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

КОНЕЦ

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

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

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

заменить (555, 63)

преобразует строку 12555550 в строку 1263550.

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

Б) нашлось (v).

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

Цикл

  ПОКА условие

      последовательность команд

  КОНЕЦ ПОКА

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

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

  ЕСЛИ условие

      ТО команда1

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

  КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

ПОКА нашлось (999) ИЛИ нашлось (888)

  ЕСЛИ нашлось (888)

    ТО заменить (888, 9)

    ИНАЧЕ заменить (999, 8)

  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Задача 6.5.2. Какая строка получится в результате применения приведённой ниже программы к строке вида 1…12…2 (39 единиц и 39 двоек)?

НАЧАЛО

ПОКА нашлось (111)

    заменить (111, 2)

    заменить (222, 1)

КОНЕЦ ПОКА

КОНЕЦ