The website "komp-model.narod.ru." is not registered with uCoz.
If you are absolutely sure your website must be here,
please contact our Support Team.
If you were searching for something on the Internet and ended up here, try again:

About uCoz web-service

Community

Legal information

Майер Р.В. Задачи, алгоритмы, программы

АЛГОРИФМЫ МАРКОВА

Задача 1.

Напишите программу, позволяющую автоматически реализовать нормальный алгоритм Маркова, обрабатывающий входное слово с помощью системы подстановок. Например, дано слово из алфавита {a,b,c,d}, следует расположить буквы в алфавитном порядке.

Нормальная система подстановок осуществляется так: сначала выполняется первая подстановка (x[1] заменяется на y[1]), слово переписывается. Затем - снова первая подстановка; если невозможно - вторая; если вторая не проходит, то третья. Слово переписывается. Снова первая подстановка, если невозможно - вторая; если невозможно - третья. Слово переписывается. Система подстановок, позволяющая расположить буквы в алфавитном порядка, представлена ниже:

slovo:='dabadbcadcbd';
------------
x[1]:='ba';  y[1]:='ab';
x[2]:='ca';  y[2]:='ac';
x[3]:='da';  y[3]:='ad';
x[4]:='cb';  y[4]:='bc';
x[5]:='db';  y[5]:='bd';
x[6]:='dc';  y[6]:='cd';

Для автоматического выполнения нормальногой алгоритм Маркова используется программа ПР-1. Результат работы программы - на рис. 1.


1 daabdbcadcbd | подстановка 1
2 daabdbacdcbd | подстановка 2
3 daabdabcdcbd | подстановка 1
4 adabdabcdcbd | подстановка 3
5 aadbdabcdcbd | подстановка 3
6 aadbadbcdcbd | подстановка 3
7 aadabdbcdcbd | подстановка 1
8 aaadbdbcdcbd | подстановка 3
9 aaadbdbcdbcd | подстановка 4
10 aaabddbcdbcd | подстановка 5
11 aaabdbdcdbcd | подстановка 5
12 aaabbddcdbcd | подстановка 5
13 aaabbddcbdcd | подстановка 5
14 aaabbddbcdcd | подстановка 4
15 aaabbdbdcdcd | подстановка 5
16 aaabbbddcdcd | подстановка 5
17 aaabbbdcddcd | подстановка 6
18 aaabbbcdddcd | подстановка 6
19 aaabbbcddcdd | подстановка 6
20 aaabbbcdcddd | подстановка 6
21 aaabbbccdddd | подстановка 6

Рис. 1. Перестановка букв по алфавиту

Задача 2.

Дана последовательность скобок. С помощью нормальной системы подстановок Маркова определите правильность скобочной структуры.

Чтобы реализовать нормальную систему подстановок Маркова, в программу ПР-1 следует вставить код:

slovo:='()()(())(()())(())';
--------------
x[1]:='**';   y[1]:='*';
x[2]:='()*';  y[2]:='*';
x[3]:='*()';  y[3]:='*';
x[4]:='(*)';  y[4]:='*';
x[5]:='()';  y[5]:='*';

Результат исполнения программы представлен на рис. 2.


1 *()(())(()())(()) | подстановка 5
2 *(())(()())(()) | подстановка 3
3 *(*)(()())(()) | подстановка 5
4 **(()())(()) | подстановка 4
5 *(()())(()) | подстановка 1
6 *(*())(()) | подстановка 5
7 *(*)(()) | подстановка 3
8 **(()) | подстановка 4
9 *(()) | подстановка 1
10 *(*) | подстановка 5
11 ** | подстановка 4
12 * | подстановка 1

Рис. 2. Определение правильности скобочной структуры.

Задача 3.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, переводящий число из двоичной системы счисления в унарную.

Чтобы решить эту задачу, в программу ПР-1 следует вставить код:

slovo:='10011';
----------
x[1]:='|0'; y[1]:='0||';
x[2]:='1';  y[2]:='0|';
x[3]:='0|';  y[3]:='|';

Результат решения задачи -- на рис. 3.


1 0|0011 | подстановка 2
2 00||011 | подстановка 1
3 00|0||11 | подстановка 1
4 000||||11 | подстановка 1
5 000||||0|1 | подстановка 2
6 000|||0|||1 | подстановка 1
7 000||0|||||1 | подстановка 1
8 000|0|||||||1 | подстановка 1
9 0000|||||||||1 | подстановка 1
10 0000|||||||||0| | подстановка 2
11 0000||||||||0||| | подстановка 1
12 0000|||||||0||||| | подстановка 1
13 0000||||||0||||||| | подстановка 1
14 0000|||||0||||||||| | подстановка 1
15 0000||||0||||||||||| | подстановка 1
16 0000|||0||||||||||||| | подстановка 1
17 0000||0||||||||||||||| | подстановка 1
18 0000|0||||||||||||||||| | подстановка 1
19 00000||||||||||||||||||| | подстановка 1
20 0000||||||||||||||||||| | подстановка 3
21 000||||||||||||||||||| | подстановка 3
22 00||||||||||||||||||| | подстановка 3
23 0||||||||||||||||||| | подстановка 3
24 ||||||||||||||||||| | подстановка 3

Рис. 3. Перевод числа из двоичной системы в унарную

Задача 4.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, складывающий два числа.

В программу ПР-1 следует вставить код:

slovo:='8eight+5five';
-------------
x[1]:='1one'; y[1]:='|';
x[2]:='2two'; y[2]:='||';
x[3]:='3three'; y[3]:='|||';
x[4]:='4four'; y[4]:='||||';
x[5]:='5five'; y[5]:='|||||';
x[6]:='6six'; y[6]:='||||||';
x[7]:='7seven'; y[7]:='|||||||';
x[8]:='8eight'; y[8]:='||||||||';
x[9]:='9nine'; y[9]:='|||||||||';
x[10]:='|+|'; y[10]:='||';
x[11]:='||||||||||'; y[11]:='10';
x[12]:='0|||||||||'; y[12]:='9';
x[13]:='0||||||||'; y[13]:='8';
x[14]:='0|||||||'; y[14]:='7';
x[15]:='0||||||'; y[15]:='6';
x[16]:='0|||||'; y[16]:='5';
x[17]:='0||||'; y[17]:='4';
x[18]:='0|||'; y[18]:='3';
x[19]:='0||'; y[19]:='2';
x[20]:='0|'; y[20]:='1';
x[21]:='|||||||||'; y[21]:='9';
x[22]:='||||||||'; y[22]:='8';
x[23]:='|||||||'; y[23]:='7';
x[24]:='||||||'; y[24]:='6';
x[25]:='|||||'; y[25]:='5';
x[26]:='||||'; y[26]:='4';
x[27]:='|||'; y[27]:='3';
x[28]:='||'; y[28]:='2';
x[29]:='|'; y[29]:='1';

Результат решения задачи - на рис. 4.


slovo:='8eight+5five';
----------------
1 8eight+||||| | подстановка 5
2 ||||||||+||||| | подстановка 8
3 ||||||||||||| | подстановка 10
4 10||| | подстановка 11
5 13 | подстановка 18

Рис. 4. Сложение двух чисел

Задача 5.

Напишите программу, автоматически реализующий нормальный алгоритм Маркова, умножающий два числа.

В программу ПР-1 следует вставить код:

slovo:='1111*111';
----------
x[1]:='*11'; y[1]:='A*1';
x[2]:='*1'; y[2]:='A';
x[3]:='1A'; y[3]:='A1B';
x[4]:='BA'; y[4]:='AB';
x[5]:='B1'; y[5]:='1B';
x[6]:='A1'; y[6]:='A';
x[7]:='AB'; y[7]:='B';
x[8]:='B'; y[8]:='1';

Результат работы программы - на рис. 5. Другой пример решения задачи:

slovo:='1111*111';
-----------
x[1]:='1*'; y[1]:='X';
x[2]:='_1'; y[2]:='1_Z';
x[3]:='Z1'; y[3]:='1Z';
x[4]:='1X'; y[4]:='X_';
x[5]:='X'; y[5]:='';
x[6]:='_'; y[6]:='';
x[7]:='Z'; y[7]:='1';


slovo:='1111*111';
-------------
1 1111A*11 | подстановка 1
2 1111AA*1 | подстановка 1
3 1111AAA | подстановка 2
4 111A1BAA | подстановка 3
5 11A1B1BAA | подстановка 3
6 1A1B1B1BAA | подстановка 3
7 A1B1B1B1BAA | подстановка 3
8 A1B1B1B1ABA | подстановка 4
9 A1B1B1BA1BBA | подстановка 3
10 A1B1B1AB1BBA | подстановка 4
11 A1B1BA1BB1BBA | подстановка 3
12 A1B1AB1BB1BBA | подстановка 4
13 A1BA1BB1BB1BBA | подстановка 3
14 A1AB1BB1BB1BBA | подстановка 4
15 AA1BB1BB1BB1BBA | подстановка 3
16 AA1BB1BB1BB1BAB | подстановка 4
17 AA1BB1BB1BB1ABB | подстановка 4
18 AA1BB1BB1BBA1BBB | подстановка 3
...............................
56 1111BBBBBBBB | подстановка 8
57 11111BBBBBBB | подстановка 8
58 111111BBBBBB | подстановка 8
59 1111111BBBBB | подстановка 8
60 11111111BBBB | подстановка 8
61 111111111BBB | подстановка 8
62 1111111111BB | подстановка 8
63 11111111111B | подстановка 8
64 111111111111 | подстановка 8

Рис. 5. Умножение целых чисел

Задача 6.

Имеется число в четверичной системе счисления. Предложите систему нормальных подстановок, которая переводит это число в двоичную систему счисления. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*3021032';
------------
x[1]:='*0';  y[1]:='00*';
x[2]:='*1';  y[2]:='01*';
x[3]:='*2';  y[3]:='10*';
x[4]:='*3';  y[4]:='11*';
x[5]:='*';   y[5]:=' ';

Задача 7.

Дано двоичное число. Предложите систему нормальных подстановок, которая инвертирует все 0 и 1. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*011010101';
-----------
x[1]:='*0';  y[1]:='1*';
x[2]:='*1';  y[2]:='0*';
x[3]:='*';   y[3]:=' ';

Задача 8.

Дано число в унарной системе счисления от 1 до 15. Предложите систему нормальных подстановок, которая представляет его как сумму степеней числа 2. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='|||||||||||||_';
-------------
x[1]:='||||||||';   y[1]:='8+';
x[2]:='||||';       y[2]:='4+';
x[3]:='||';         y[3]:='2+';
x[4]:='|';          y[4]:='1+';
x[5]:='+_';         y[5]:=' ';

Задача 9.

Имеется слово 'BAB_BA_AA_BABB_ABA'. Создайте нормальный алгоритм Маркова, который символы 'A' переносит влево, символы 'B' - вправо, а пробелы оставляет посередине. Промоделируйте на компьютере. (Ответ: 1) 'BA' => 'AB'; 2) 'B_' => '_B'; 3) '_A' => 'A_').

Задача 10.

Имеется слово 'abcbacbdacdb'. Создайте нормальный алгоритм Маркова, который кодирует это слово. Промоделируйте на компьютере. (Ответ: 1) 'a' => '00-'; 2) 'b' => '01-'; 3) 'c' => '10-'; 4) 'd' => '11-'; 5) 'e' => '111-').

Тексты программ находятся в zip-архиве, файл gl-15.pas.


ВВЕРХ

Майер, Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. - Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net .

Сайт управляется системой uCoz