Алгоритмы. Исполнители

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

Тема: Алгоритмы

Исполнители.

Выполнил: Севрюкова Н.Н.

МКОУ БСШ № 2

с.Богучаны, Красноярского края

Задача

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

1. прибавь 3

2. умножь на 4

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

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

умножь на 4

прибавь 3

умножь на 4

прибавь 3

прибавь 3

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

из числа 3 числа 57

1. прибавь 3

2. умножь на 4

«обратный ход»:

22111

22111

Ответ:

Ответ:

очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение ( прибавь 3 ), над стрелкой записан номер команды:

число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение

Задача

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

3233241

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

Нарисуем 3233241

1 (вверх), 2 (вниз), 3 (вправо), 4 (влево)

144

Ответ:

414

441

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

( A 18)

Задача 1:

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

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

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

слева свободно справа свободно

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

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

НАЧАЛО

ПОКА вниз

ПОКА влево

ПОКА вверх

ПОКА вправо

КОНЕЦ

6

A

5

B

4

C

3

D

2

E

1

F

НАЧАЛО

КОНЕЦ

ПОКА вниз

ПОКА влево

ПОКА вверх

ПОКА вправо

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

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

НАЧАЛО

КОНЕЦ

ПОКА вниз

ПОКА влево

ПОКА вверх

обратим внимание, что возможны еще «вырожденные» варианты, вроде таких

ПОКА вправо

A

6

B

5

C

4

D

3

E

2

F

1

итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты

если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли , а остальные клетки вертикали F условию не удовлетворяют

A



6

B

5

C

4

D

3

E

2

F

1

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



A

6

5

B

4

C

3

D

2

E

1

F



A

6

B

5

C

4

D

3

E

2

1

F

Задача 2

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

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

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

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

слева свободно справа свободно

65 4321ABCDEF Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение?

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

НАЧАЛО

ПОКА вверх

ПОКА вправо

ПОКА вниз

ПОКА влево

КОНЕЦ

6

A

5

B

4

C

3

D

2

E

1

F

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

рассмотрим первый цикл:

ПОКА вверх

понятно, что при движении вверх РОБОТ остановится в первой же клетке, где слева будет стена

НАЧАЛО

КОНЕЦ

ПОКА вверх

ПОКА вправо

ПОКА вниз

ПОКА влева

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

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

6

A

B

5

4

C

3

D

2

E

1

F

Задача

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

«сдвиг влево»

«* 2»

«сдвиг влево»

«* 2»

«/ 2»

«сдвиг вправо»

?

0

0

1

0

1

1

0

1

= 45

0 0 1 0 1 1 0 1

=90

важно, что числа однобайтовые – на число отводится 1 байт или 8 бит

главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса :

0

бит переноса

1. сдвинь влево

2. вычти 1

число 104 выполнил цепочку команд 11221

Код команды

Действие

Результат

Примечание

104

умножь на 2 208

1

mod 208*2 на 256

Умножить на 2

160

1

бит переноса

в большинстве случаев результат этой операции – умножение числа на 2,

однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна, поэтому мы получим остаток от деления числа 2x на 28=256

попутно заметим, что при сдвиге вправо в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка

2

159

159

2

2

2

Вычти 1

Вычти 1

Вычти 1

2

158

Вычти 1

1

60

Умножить на 2

mod 158*2 на 256

Код команды

Действие

Результат

1

Примечание

104

умножь на 2

1

умножь на 2

2

208

160

вычти 1

2

остаток от деления 208*2 на 256

вычти 1

159

1

158

умножь на 2

60

остаток от деления 158*2 на 256

0 нц c := Извлечь(a,i) b := Склеить(b,c) i := i – k кц b := Склеить(b,'Т') Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’ ? 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’ заметим, что последняя команда алгоритма, b :=Склеить( b ,'Т') , добавляет букву 'Т' в конец строки b , поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П') " width="640"

Задача

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные 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 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П')

0 нц c := Извлечь(a,i) b := Склеить(b,c) i := i – k кц b := Склеить(b,'Т') " width="640"

‘ ПОЕЗД’

i := Длина(a)

k := 2

b := « А »

пока i 0

нц

c := Извлечь(a,i)

b := Склеить(b,c)

i := i – k

кц

b := Склеить(b,'Т')

0? ДА c:=Извлечь(a,i) i:=Длина(a) 5 b:=Cклеить(b,c ) « А Д» « А Д» b:=Cклеить(b,c ) i:=i–k 3 Извлечь из А 5 элемент=Д i 0? ДА c:=Извлечь(a,i) «Е» b:=Cклеить(b,c ) « А ДЕ» 3) ‘АДТЕТПТ’ 2) ‘АДЗЕОП’ 1) ‘АДЕПТ’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’ 2) ‘АДЗЕОП’ 1) ‘АДЕПТ’ 3) ‘АДТЕТПТ’ 2) ‘АДЗЕОП’ 1) ‘АДЕПТ’ 1) ‘АДЕПТ’ 4) ‘АДЗОТ’ 3) ‘АДТЕТПТ’ 2) ‘АДЗЕОП’ 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ " width="640"

a

b

'ПОЕЗД'

c

?

i

?

k

?

?

i:=Длина(a)

5

k:=2

2

« А »

b:= « А »

i 0?

ДА

c:=Извлечь(a,i)

i:=Длина(a)

5

b:=Cклеить(b,c )

« А Д»

« А Д»

b:=Cклеить(b,c )

i:=i–k

3

Извлечь из А 5 элемент=Д

i 0?

ДА

c:=Извлечь(a,i)

«Е»

b:=Cклеить(b,c )

« А ДЕ»

3) ‘АДТЕТПТ’

2) ‘АДЗЕОП’

1) ‘АДЕПТ’

3) ‘АДТЕТПТ’

4) ‘АДЗОТ’

2) ‘АДЗЕОП’

1) ‘АДЕПТ’

3) ‘АДТЕТПТ’

2) ‘АДЗЕОП’

1) ‘АДЕПТ’

1) ‘АДЕПТ’

4) ‘АДЗОТ’

3) ‘АДТЕТПТ’

2) ‘АДЗЕОП’

1) ‘АДЕПТ’

2) ‘АДЗЕОП’

Материалы:

http://www.fipi.ru /