слева свободно справа свободно
| A | B | C | D | E | F |
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
1) 1 2) 0 3) 3 4) 4
НАЧАЛО
ПОКА <справа свободно> вправо
ПОКА <сверху свободно> вверх
ПОКА <слева свободно> влево
ПОКА <снизу свободно> вниз
КОНЕЦ
36. Имеется фрагмент алгоритма, записанный на алгоритмическом языке:
n:= Длина(а)
m:= 6
b:= Извлечь(а, m)
с:= Извлечь(а, m-4)
b:= Склеить(b, с)
с:= Извлечь(а, m+2)
b:= Склеить(b, с)
Нц для i от 10 до n
с:= Извлечь(а, i)
b:= Склеить(b, с)
кц
Здесь переменные a, b и с - строкового типа; переменные n, m, k – целые. В алгоритме используются следующие функции:
Длина(х) – возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х,i) – возвращает i -й символ слева в строке х. Имеет строковый тип.
Склеить(х,у) – возвращает строку, в которой записаны подряд сначала все символы
строки х, а затем все символы строки у. Имеет строковый тип.
Значения строк записываются в кавычках (одинарных), например x='школа'.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма,
если переменная а имела значение 'КИБЕРНЕТИКА'?
1) ‘БЕРЕТ’ 2) ‘НИТКА’ 3) ‘ТИБЕТ’ 4) ‘НЕРКА’
37. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
38. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q 1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
39. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q 1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
40. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q 1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
41. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “()”.
Например, дано “) (() (()”, надо получить “)... ((”.
Автомат в состоянии q 1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
42. Дана строка из букв “ a ” и “ b ”. Разработать машину Тьюринга, которая переместит все буквы “ a ” в левую, а буквы “ b ” — в правую части строки. Автомат в состоянии q 1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
43. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q 1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
44. Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q 1обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
45. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q 1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n. Известно, что m > n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
46. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
47. На ленте машины Тьюринга записано слово на латинице. Совпадают ли первая и последняя буквы этого слова? Вывести "да" или "нет" справа от слова.
48. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток.
49. Дана десятичная запись натурального числа n>1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 5. При этом запись числа n–5 не должна содержать левый нуль, например, 100–5=95, а не 095.
50. На информационной ленте машины Тьюринга записано число в двоичной системе счисления. Определить, является ли это число степенью числа 2. Ответ в виде слова "да" или "нет" записать справа от числа.
51. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Перенести первый символ непустого слова Р в его конец.
52. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Если первый и последний символы (непустого) слова Р одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово.
53. Машина Тьюринга. Имеется алфавит: А={a,b}. Удалить из слова Р его второй символ, если такой есть.
54. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Удалить из слова Р первое вхождение символа a, если такое есть.
55. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ a.
56. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Вставить в слово P символ a за первым вхождением символа c, если такое есть.
57. Машина Тьюринга. Имеется алфавит: А={a,b,c}. Удалить из P все вхождения символа a.
58. Машина Тьюринга. Имеется алфавит: А={a,b}. Удвоить слово P, поставив между ним и его копией знак =.
59. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Приписать слева к слову P символ b (P → bP).
60. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).
61. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Заменить на a каждый второй символ в слове P.
62. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).
63. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять).
64. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.
65. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).
66. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.
67. Машина Тьюринга. Имеется алфавит: A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).
68. Машина Тьюринга. Имеется алфавит: A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.
69. Машина Тьюринга. Имеется алфавит: A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.
70. Машина Тьюринга. Имеется алфавит: A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.
71. Машина Тьюринга. Имеется алфавит: A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
72. Машина Тьюринга. Имеется алфавит: A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).
73. Машина Тьюринга. Имеется алфавит: A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 → 101).
74. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.
75. Машина Тьюринга. Имеется алфавит: A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)
76. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ.
77. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину.
78. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Приписать слева к непустому слову P его первый символ.
79. Машина Тьюринга. Имеется алфавит: A={a,b}. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово.
80. Машина Тьюринга. Имеется алфавит: A={a,b}. В непустом слове P поменять местами его первый и последний символы.
81. Машина Тьюринга. Имеется алфавит: A={a,b}. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово.
82. Машина Тьюринга. Имеется алфавит: A={a,b}. Заменить в P каждое вхождение a на bb.
83. Машина Тьюринга. Имеется алфавит: A={a,b,c}. Заменить в P каждое вхождение ab на c.
84. Машина Тьюринга. Имеется алфавит: A={a,b}. Удвоить слово P (например: abb → abbabb).
85. Машина Тьюринга. Имеется алфавит: A={a,b}. Удвоить каждый символ слова P (например: bab → bbaabb).
86. Машина Тьюринга. Имеется алфавит: A={a,b}. Перевернуть слово P (например: abb → bba).
87. Машина Тьюринга. Имеется алфавит: A={0,1}. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)
88. Машина Тьюринга. Имеется алфавит: A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.
89. Машина Тьюринга. Имеется алфавит: A={0,1,2}. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на 1.
90. Машина Тьюринга. Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе.
91. Машина Тьюринга. Пусть P имеет вид Q–R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q≥R, выдать в качестве ответа запись разности этих чисел в той же троичной системе.
92. Машина Тьюринга. Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
93. Машина Тьюринга. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
94. Машина Поста. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
95. Машина Поста. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
96. Машина Поста. На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.
97. Машина Поста. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
98. Машина Поста. На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
99. Машина Поста. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.
100. Машина Поста. На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.
101. Машина Поста. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.
102. Машина Поста. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
103. Машина Поста. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
104. Машина Поста. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
105. Машина Поста. На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек.
106. Машина Поста. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
107. Машина Поста. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.
108. Машина Поста. На ленте машины Поста расположен массив из 2 n – 1 меток. Составить программу удаления средней метки массива.
109. Машина Поста. На ленте машины Поста расположен массив из 2 n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива.
110. Машина Поста. На ленте расположены два массива разной длины. Каретка обозревает крайний элемент одного из них. Составьте программу для машины Поста, сравнивающую длины массивов и стирающую больший из них. Отдельно продумайте случай, когда длины массивов равны.
111. Машина Поста. На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.
112. Машина Поста. Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.
113. Машина Поста. На ленте машины Поста записано натуральное число N. Необходимо справа от него через одну пустую секцию разместить число вдвое большее. Исходное число может быть стерто.
114. Машина Поста. На ленте машины Поста находятся n массивов меток. Каретка находится где-то над первым массивом. Удалить все четные массивы, если все массивы разделены тремя пустыми секциями.
115. Машина Поста. Составить программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.
116. Машина Поста. На ленте машины Поста записано число. Найти остаток от деления этого числа на 3.
117. Машина Поста. На ленте машины Поста записано натуральное число N. Найти целую часть от деления этого числа на 2.
118. Машина Поста. На ленте машины Поста записано N массивов меток, отделенных друг от друга одной свободной ячейкой. Каретка находится над первой меткой первого массива. Определить количество массивов.
119. Нормальные алгоритмы Маркова. А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c.
120. Нормальные алгоритмы Маркова. А={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символы a, а в конце – все символы b. Например: babba → aabbb
121. Нормальные алгоритмы Маркова. А={a,b}. Удалить из непустого слова Р его первый символ. Пустое слово не менять.
122. Нормальные алгоритмы Маркова. А={0,1,2,3}. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись этого же числа, но в двоичной системе. Например: 0123 → 00011011
123. Нормальные алгоритмы Маркова. А={a,b}. Требуется приписать символ a к концу слова Р. Например: bbab → bbaba
124. Нормальные алгоритмы Маркова. А={a,b}. В слове Р заменить на aa последнее вхождение символа a, если такое есть. Например: bababb → babaabb
125. Нормальные алгоритмы Маркова. А={a,b}. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять. Например: bbaba → babab
126. Нормальные алгоритмы Маркова. А={a,b}. Удвоить слово Р, т.е. приписать к P (слева или справа) его копию. Например: abb → abbabb
127. Нормальные алгоритмы Маркова. A={f,h,p}. В слове P заменить все пары ph на f.
128. Нормальные алгоритмы Маркова. A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть.
129. Нормальные алгоритмы Маркова. A={a,b,c}. Приписать слово bac слева к слову P.
130. Нормальные алгоритмы Маркова. A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы.
131. Нормальные алгоритмы Маркова. A={a,b,c}. Заменить любое входное слово на слово a.
Литература:
1. Стариченко Б.Е. Теоретические основы информатики. -М.: Горячая линия-Телеком, 2003. - 312 с.
2. Андреева Е.В. Математические основы информатики. Элективный курс: Учебное пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина - М.: БИНОМ. Лаборатория знаний, 2005 – 328 с.: ил.
3. https://inf.1september.ru/articlef.php?ID=200600802
4. https://komp-model.narod.ru/gl-14.htm
5. https://kpolyakov.narod.ru/download/turmar.pdf
6. https://kpolyakov.narod.ru/prog/turing.htm
7. https://kpolyakov.narod.ru/prog/post.htm
8. https://kpolyakov.narod.ru/prog/nma.htm
9. https://kpolyakov.narod.ru/school/ege.htm задания из разделов Информация, Системы счисления, Алгоритмизация и программирование (А13, В1)