Для Вас, студенты!!!Для Вас, студенты!!!
Задачи по машине Поста
Задача №1
Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
Решение:
1
удалить 2
2
вправо 3
3
? 4,2
4
метка 5
5
вправо 6
6
? 8,7
7
стоп 7
8
влево 9
9
? 10,8
10
вправо 1
Задача №2
Нахождение суммы любого количества массивов, которые отделены друг от друга одной ячейкой. Каретка находится над крайней левой меткой первого массива.
Решение:
1
удалить 2
2
вправо 3
3
? 4,2
4
метка 5
5
вправо 6
6
? 10,7
7
влево 8
8
? 9,7
9
вправо 1
10
стоп 10
Задача №3
Дан массив меток. Проверить, делится ли он нацело на 3. Если да, то слева от него, через одну пустую ячейку поставить метку; если нет, то ничего не делать. Каретка располагается над первой пустой ячейкой, примыкающей к массиву слева.
Решение:
1
вправо 2
2
? 3,4
3
стоп 3
4
вправо 5
5
? 3,6
6
вправо 7
7
? 8,1
8
вправо 9
9
метка 3
Задача №4
Дано несколько массивов меток. Удалить четные массивы. Каретка находится где-то над первым массивом.
Решение:
1
вправо 2
2
? 3,1
3
вправо 4
4
вправо 5
5
вправо 6
6
? 14,7
7
удалить 8
8
вправо 9
9
? 10,7
10
вправо 11
11
вправо 12
12
вправо 13
13
? 14,1
14
стоп 14
Задача №5
Дано некоторое число (в виде меток). Найти остаток от деления его на 3. Каретка располагается над первой пустой ячейкой, примыкающей к массиву меток справа.
Решение:
1
влево 2
2
? 1,3
3
влево 4
4
? 5,6
5
стоп 5
6
влево 7
7
? 5,8
8
влево 9
9
? 5,10
10
вправо 11
11
удалить 12
12
вправо 13
13
удалить 14
14
вправо 15
15
удалить 1
Задача №6
Удвоить данный массив справа от него, через ячейку, и затем стереть исходный. Каретка находится над крайней левой меткой.
Решение:
1
влево 2
2
? 3,1
3
вправо 4
4
удалить 5
5
вправо 6
6
? 7,5
7
вправо 8
8
? 9,7
9
метка 10
10
вправо 11
11
метка 12
12
влево 13
13
? 14,12
14
влево 15
15
? 16,1
16
стоп 16
Задача №7
Даны два целых положительных числа. Найти их разность по модулю.
Решение:
1
вправо 2
2
? 3,1
3
влево 4
4
удалить 5
5
влево 6
6
? 14,7
7
вправо 8
8
? 7,9
9
удалить 10
10
вправо 11
11
? 17,12
12
влево 13
13
? 12,4
14
вправо 15
15
? 14,16
16
удалить 17
17
стоп 17
Задача №8
Дано несколько массивов. Определить их количество. Каретка находится над крайней левой меткой первого массива.
Решение:
1
влево 2
2
влево 3
3
метка 4
4
вправо 5
5
вправо 6
6
? 7,5
7
метка 8
8
вправо 9
9
? 18,10
10
влево 11
11
? 12,10
12
влево 13
13
? 14,12
14
метка 15
15
вправо16
16
? 17,15
17
вправо 6
18
влево 15
19
удалить 20
20
влево 21
21
? 22,19
22
стоп 22
Задача №9
Найти масив и встать на его начало. Каретка располагается в любом месте, но не над массивом.
Решение:
1
влево 2
2
? 3,2
3
вправо 4
4
вправо 5
5
? 6,23
6
влево 7
7
метка 8
8
влево 9
9
? 10,8
10
влево 11
11
? 12,20
12
вправо 13
13
метка 14
14
вправо 15
15
? 16,14
16
вправо 17
17
? 18,23
18
влево 19
19
метка 8
20
влево 21
21
? 22,20
22
вправо 23
23
стоп 23
Задача №10
Дан массив из 2N-1 меток. Найти и удалить среднюю. Каретка над второй меткой, если считать справа.
Решение:
1
влево 2
2
? 3,1
3
вправо 4
4
удалить 5
5
вправо 6
6
? 7,5
7
влево 8
8
удалить 9
9
влево 10
10
? 11,9
11
метка 12
12
вправо 13
13
удалить 14
14
вправо 15
15
? 22,16
16
влево 17
17
вправо 18
18
? 19,17
19
метка 20
20
влево 21
21
удалить 9
22
метка 23
23
стоп 23
Задача №11
Дано N массивов меток. После последнего массива на расстоянии более трёх пустых ячеек находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массиве >=2. Если количество меток в массиве кратно трём, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.
Решение:
1
вправо 2
2
? 7,3
3
вправо 4
4
? 7,5
5
вправо 6
6
? 13,1
7
влево 8
8
? 9,7
9
вправо 10
10
удалить 11
11
вправо 12
12
? 19,10
13
влево 14
14
? 15,13
15
вправо 28
16
удалить 17
17
вправо 18
18
вправо19
19
? 20,16
20
вправо 21
21
? 20,22
22
вправо 23
23
? 25,24
24
влево 1
25
влево 26
26
удалить 27
27
стоп 27
28
вправо 16
Задача №12
Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
Решение:
1
удалить 2
2
влево 3
3
? 4,2
4
вправо 5
5
вправо 6
6
вправо 7
7
? 13,8
8
влево 9
9
? 31,10
10
удалить 11
11
вправо 12
12
вправо 13
13
? 14,8
14
влево 15
15
удалить 16
16
вправо 17
17
метка 18
18
вправо19
19
вправо 20
20
? 26,21
21
влево 22
22
удалить 23
23
вправо 24
24
вправо 25
25
? 26,20
26
влево 27
27
влево 28
28
? 27,30
29
удалить 30
30
удалить 31
31
стоп 31
Задача №13
Составить программу нахождения разности двух целых неотрицательных чисел a и b. Если a меньше b, то перед разностью через одну пустую ячейку поставить метку. Каретка находится над крайней левой меткой левого числа.
Решение:
1
вправо 2
2
? 18,3
3
влево 4
4
удалить 5
5
вправо 6
6
? 7,5
7
вправо 8
8
? 7,9
9
вправо 10
10
? 29,11
11
влево 12
12
удалить 13
13
влево 14
14
? 13,15
15
влево 16
16
? 17,15
17
вправо 1
18
влево19
19
удалить 20
20
вправо 21
21
? 20,22
22
удалить 23
23
вправо 24
24
? 28,25
25
влево 26
26
влево 27
27
метка 28
28
стоп 28
29
влево 30
30
удалить 31
31
стоп 31
Задача №14
Произвести умножение двух чисел. Каретка располагается над пустой ячейкой, которая разделяет данные массивы.
Решение:
1
вправо 2
2
? 1,3
3
влево 4
4
? 5,14
5
вправо 6
6
удалить 7
7
вправо 8
8
? 7,9
9
удалить 10
10
вправо 11
11
? 12,10
12
метка 13
13
стоп 13
14
вправо 15
15
удалить 16
16
вправо 17
17
? 16,18
18
удалить 19
19
вправо 20
20
? 21,19
21
вправо 22
22
? 23,21
23
метка 24
24
влево 25
25
? 26,24
26
влево 27
27
? 28,26
28
метка 29
29
вправо 30
30
? 31,18
31
влево 32
32
? 1,31
Задача №15
Дан массив из N Меток. Сделать из него массив, в котором будет 2N+1 меток. Если полученный массив делится нацело на 3, то справа от него, через одну пустую ячейку, поставить две метки; если нет - то три метки. Каретка находится над крайней левой меткой.
Решение:
1
удалить 2
2
вправо 3
3
? 4,2
4
вправо 5
5
? 6,4
6
метка 7
7
вправо 8
8
метка 9
9
влево 10
10
? 11,9
11
влево 12
12
? 13,15
13
вправо 14
14
метка 18
15
влево 16
16
? 17,15
17
вправо 1
18
вправо 19
19
вправо 20
20
вправо 21
21
? 22,18
22
влево 23
23
? 24,37
24
влево 25
25
? 38,26
26
вправо 38
27
метка 28
28
вправо 29
29
метка 30
30
вправо 31
31
метка 36
32
вправо 33
33
метка 34
34
вправо 35
35
метка 36
36
стоп 36
37
вправо 32
38
вправо 27
Задачи по машине Тьюринга
Задача №1
На ленте машины Тьюринга записан массив из 2N меток. Задание: уменьшить его в два раза.
Обозначения в таблице:
  •  "ri"-указание машине пойти вправо.

  •  "le"-указание машине пойти влево.

  •  "pr"-указание машине поставить пробел.

  •  "!"-указание машине остановиться.

  •  "q1, q2, q3..."-переход соответственно в состояние q1, q2, q3 и т. д.)
Решение:
q0
q1
q2
q3
q4
*
*-ri-q0
|-le-q4
|
*-ri-q1
|-ri-q1
pr-le-q3
|-le-q3
pr
pr-le-q4
pr-le-q2
pr-le-q4
pr!q4
Задача №2
Дан массив из букв "А" и "В". Нужно сжать массив, удалив все буквы "В", но оставив буквы "А".
Решение:
q0
q1
q2
q3
q4
q5
A
A-le-q0
A-ri-q1
A-le-q3
pr-ri-q4
A-le-q5
B
B-le-q0
pr-ri-q1
*
pr-!-q3
pr
*-ri-q1
pr-le-q2
pr-le-q2
pr-le-q3
pr-ri-q4
A-le-q3
Задача №3
Дана конечная последовательность из символов "+" и "—". Заменить "+" на "—" на каждом втором месте.
Решение:
q1
q2
q3
+
+-ri-q0
+-le-q2
—-le-q1
pr
pr-le-q1
pr-!-q1
pr-!-q2
Задача №4
Дана последовательность символов "*". Требуется записать их количество числом десятеричной системы счисления.
Решение:
q0
q1
q2
q3
q4
0
0-ri-q4
1-le-q4
0-ri-q4
1
2-le-q4
1-ri-q4
2
3-le-q4
2-ri-q4
3
4-le-q4
3-ri-q4
4
5-le-q4
4-ri-q4
5
6-le-q4
5-ri-q4
6
7-le-q4
6-ri-q4
7
8-le-q4
7-ri-q4
8
9-le-q4
8-ri-q4
9
9-ri-q4
0-le-q3
9-ri-q4
*
*-ri-q0
pr-le-q2
*-le-q2
pr
pr-le-q1
pr-!-q1
pr-le-q3
1-ri-q4
pr-ri-q0
Задача №5
Дано слово из букв "a", "b", "c", "d". Сосчитать количество букв "a", записать его слева от данного слова через одну ячейку. Каретка располагается над крайней левой буквой.
Решение:
q0
q1
q2
q3
q4
0
1-ri-q3
0-ri-q3
1
2-ri-q3
1-ri-q3
2
3-ri-q3
2-ri-q3
3
4-ri-q3
3-ri-q3
4
5-ri-q3
4-ri-q3
5
6-ri-q3
5-ri-q3
6
7-ri-q3
6-ri-q3
7
8-ri-q3
7-ri-q3
8
9-ri-q3
8-ri-q3
9
0-le-q2
9-ri-q3
a
*-le-q1
b
b-ri-q0
b-le-q1
c
c-ri-q0
c-le-q1
d
d-ri-q0
d-le-q1
*
*-ri-q0
*-le-q1
a-le-q4
pr
pr-le-q4
pr-le-q2
1-ri-q3
pr-ri-q0
pr-!-q4
Задача №6
Данное число в двоичной системе счисления перевести в число в восьмеричной системе. Каретка располагается над крайней левой цифрой.
Решение:
q0
q1
q2
q3
q4
q5
0
0-ri-q0
1-le-q1
0-le-q2
1-ri-q4
0-ri-q4
pr-ri-q5
1
1-ri-q0
0-le-q2
1-le-q2
2-ri-q4
1-ri-q4
pr-ri-q5
2
3-ri-q
2-ri-q4
3
4-ri-q4
3-ri-q4
4
5-ri-q4
4-ri-q4
5
6-ri-q4
5-ri-q4
6
7-ri-q4
6-ri-q4
7
0-le-q3
7-ri-q4
pr
pr-le-q1
pr-ri-q5
pr-le-q3
1-ri-q4
pr-ri-q0
pr-!-q5
Задача №7
Дано число в десятичной системе счисления. Записать его цифры наоборот.
Решение:
q0
q1
q2
q3
q4
q5
0
0-ri-q0
9-le-q1
0-ri-q2
1-le-q4
0-le-q4
1
1-ri-q0
0-ri-q2
1-ri-q2
2-le-q4
1-le-q4
2
2-ri-q0
1-ri-q2
2-ri-q2
3-le-q4
2-le-q4
3
3-ri-q0
2-ri-q2
3-ri-q2
4-le-q4
3-le-q4
4
4-ri-q0
3-ri-q2
4-ri-q2
5-le-q4
4-le-q4
5
5-ri-q0
4-ri-q2
5-ri-q2
6-le-q4
5-le-q4
6
6-ri-q0
5-ri-q2
6-ri-q2
7-le-q4
6-le-q4
7
7-ri-q0
6-ri-q2
7-ri-q2
8-le-q4
7-le-q4
8
8-ri-q0
7-ri-q2
8-ri-q2
9-le-q4
8-le-q4
9
9-ri-q0
8-ri-q2
9-ri-q2
0-ri-q3
9-le-q4
pr-ri-q5
pr
pr-le-q1
pr-ri-q5
pr-ri-q3
1-le-q4
pr-le-q1
pr-!-q5
Задача №8
Дано число в десятичной системе счисления и число в троичной системе счисления. Найти их суммму и ответ записать в десятичной системе счисления (например 576+100). Каретка располагается над крайней правой цифрой правого числа.
Решение:
q0
q1
q2
q3
q4
q5
0
2-le-q4
0-le-q1
1-ri-q3
1-le-q4
2-le-q4
1
0-le-q1
1-le-q1
2-ri-q3
2-le-q4
0-le-q1
2
1-le-q1
2-le-q1
3-ri-q3
3-le-q4
1-le-q1
pr-ri-q5
3
4-ri-q3
4
5-ri-q3
5
6-ri-q3
6
7-ri-q3
7
8-ri-q3
8
9-ri-q3
9
0-le-q2
pr
pr-le-q0
pr-!-q5
+
+-le-q2
+-ri-q3
pr-ri-q5
Задача №9
Дано некоторое слово из букв "A" и"B". Оработать его так, чтобы слева были буквы "A", а справа-"B". Каретка находится над крайней левой буквой.
Решение:
q0
q1
q2
q3
q4
q5
q6
q7
A
A-ri-q0
A-le-q1
A-ri-q2
A-ri-q3
A-le-q4
A-le-q5
pr-ri-q7
A-ri-q7
B
*-ri-q0
B-le-q1
B-ri-q2
B-le-q4
*
|-ri-q2
|
|-le-q1
|-ri-q2
|-ri-q3
pr-le-q5
|-le-q5
|-ri-q6
|-ri-q7
pr
pr-le-q1
pr-ri-q3
B-le-q1
pr-!-q4
pr-ri-q6
A-le-q4
Задача №10
Дано число в десятичной системе счисления. Умножить его на 11.
Решение:
q0
q1
q2
q3
q4
q5
q6
q7
q8
0
0-ri-q0
9-le-q1
0-le-q2
1-ri-q4
0-le-q4
0-le-q6
1-ri-q7
0-ri-q7
1
1-ri-q0
0-le-q2
1-le-q2
2-ri-q4
1-le-q4
1-le-q6
2-ri-q7
1-ri-q7
2
2-ri-q0
1-ri-q2
2-le-q2
3-ri-q4
2-le-q4
2-le-q6
3-ri-q7
2-ri-q7
3
3-ri-q0
2-ri-q2
3-le-q2
4-ri-q4
3-le-q4
3-le-q6
4-ri-q7
3-ri-q7
4
4-ri-q0
3-ri-q2
4-le-q2
5-ri-q4
4-le-q4
4-le-q6
0-le-q6
4-ri-q7
5
5-ri-q0
4-ri-q2
5-le-q2
6-ri-q4
5-le-q4
5-le-q6
5-ri-q7
5-ri-q7
6
6-ri-q0
5-ri-q2
6-le-q2
7-ri-q4
6-le-q4
6-le-q6
6-ri-q7
6-ri-q7
7
7-ri-q0
6-ri-q2
7-le-q2
8-ri-q4
7-le-q4
7-le-q6
7-ri-q7
7-ri-q7
8
8-ri-q0
7-ri-q2
8-le-q2
9-ri-q4
8-le-q4
8-le-q6
8-ri-q7
8-ri-q7
9
9-ri-q0
8-ri-q2
9-le-q2
0-le-q3
9-le-q4
9-le-q6
0-le-q6
9-ri-q7
pr-ri-q8
pr
pr-le-q1
pr-ri-q8
pr-le-q3
1-ri-q4
pr-le-q5
pr-ri-q0
pr-!-q8
Задача №11
На ленте машины Тьюринга записан массив из N штук звёздочек ("*"). Задание: если N>5, то вывести N-2; если N=5, то вывести 1; если N<5, то вывести 2N.
Решение:
q0
q1
q2
q3
q4
q5
q6
q7
*
*-ri-q1
*-ri-q2
*-ri-q3
*-ri-q4
*-ri-q14
*-ri-q9
*-ri-q10
pr-ri-q11
pr
pr-le-q8
pr-le-q7
pr-le-q6
pr-le-q5

Продолжение

q8
q9
q10
q11
q12
q13
q14
q15
*
*-ri-q12
*-ri-q17
*-le-q16
pr
*-ri-q10
*-ri-q11
*-ri-q12
*-ri-q13
pr-!-q13
pr-le-q15

Продолжение

q16
q17
q18
q19
q20
*
pr-le-q16
*-ri-q17
pr-le-q19
pr-le-q20
*-!-q20
pr
pr-!-q16
pr-le-q18
Ждите обновления страницы и другую полезную информацию!
HotLog
Hosted by uCoz