Тема № 4 (стр. 3 )

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные 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) ‘АДЗОТ’

Решение:

эта задача более близка к классическому программированию, здесь выполняется обработка символьных строк; вся информация для успешного решения, вообще говоря, содержится в условии, но желательно иметь хотя бы небольшой опыт работы с символьными строками на Паскале (или другом языке) заметим, что последняя команда алгоритма, b:=Склеить(b,'Т'), добавляет букву 'Т' в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П') для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):

a	b	c	i	k
'ПОЕЗД'	?	?	?	?

в первой команде длина строки a (она равна 5 символам) записывается в переменную i:

a	b	c	i	k
'ПОЕЗД'	?	?	?	?
i:=Длина(a)	5

следующие два оператора записывают начальные значения в k и b:

a	b	c	i	k
'ПОЕЗД'	?	?	?	?
i:=Длина(a)	5
k:=2	2
b:='А'	'A'

далее следует цикл пока с проверкой условия i>0 в начале цикла; сейчас i=5>0, то есть,  условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:

a	b	c	i	k
'ПОЕЗД'	?	?	?	?
i:=Длина(a)	5
k:=2	2
b:='А'	'A'
i > 0?	да
c:=Извлечь(a, i)	i:=Длина(a)	5
b:=Cклеить(b, c)	k:=2
i:=i–k	3

поскольку i=5, вызов функции Извлечь(a, i) выделяет из строки a символ с номером 5, это 'Д'; следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка 'АД'; в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2)

далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть 'Е':

a	b	c	i	k
...	'ПОЕЗД'	'АД'	…	3	2
i > 0?	да
c:=Извлечь(a, i)	'Е'
b:=Cклеить(b, c)	'АДЕ'
i:=i–k	1

условие i>0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть 'П':

a	b	c	i	k
...	'ПОЕЗД'	'АДЕ'	…	1	2
i > 0?	да
c:=Извлечь(a, i)	'П'
b:=Cклеить(b, c)	'АДЕП'
i:=i–k	–1

теперь i=-1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву 'Т':

a	b	c	i	k
...	'ПОЕЗД'	'АДЕП'	…	–1	2
i > 0?	нет
b:=Склеить(b,'Т')	'АДЕПТ'

у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов 'АДЕПТ' таким образом, правильный ответ – 1.

Пример 8.

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 3

2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

(Например, программа 21211 это программа

умножь на 4

прибавь 3

умножь на 4

прибавь 3

прибавь 3

которая преобразует число 2 в 50.)

Решение (вариант 1, «прямой ход»):

обратим внимание, что в условии ограничено число команд, поэтому неявно ставится задача написать самую короткую программу для решения задачи начнем решать задачу, «отталкиваясь» от начального числа на первом шаге с помощью имеющихся команд из числа 3 можно получить 6 или 12; на втором шаге из 6 можно получить 9 и 12, а из 12 – 15 и 48, и т. д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

уже чувствуется, что дерево сильно разрастается, на следующем уровне будет уже 8 вариантов, потом – 16 и т. д. (на каждом следующем уровне – в 2 раза большем, чем на предыдущем) нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 57) видим, что после второй операции ближе всего к результату оказалось число 48, попробуем начать анализ с этой ветки; если не получится – возьмем число 24 и т. д. ветка дерева, начиная от числа 48, построена на рисунке справа; красный крестик показывает, что полученное значение превышает 57 итак, мы вышли на число 57 в результате такой последовательности команд: 22111, ее длина равна 5, что удовлетворяет условию задачи. таким образом, правильный ответ – 22111.

Задания для самостоятельной работы.

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

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

3.        Определите значение переменной с после выполнения следующего фрагмента программы:

4.        Определите значение переменной с после выполнения следующего фрагмента программы:

5.        Определите значение переменной с после выполнения следующего фрагмента программы:

6.        Определите значение целочисленных переменных a и b после выполнения фрагмента программы:

7.        Определите значение целочисленных переменных a и b после выполнения фрагмента программы:

8.        Определите значение целочисленных переменных a и b после выполнения фрагмента программы: