Отчёт по лабораторной работе №2

Выполнил:

студент 3 курса, гр. ИС-10-1

Е.В. Попов

Проверил:

преподаватель

Л.В. Аршинский

Представлен на проверку «__»_____________2013г.

Проверен «__»_____________2013г.

Примечания_________________________________

Оценка_____________________________________

Иркутск 2013

Лабораторная работа №2

Нормальный алгоритм Маркова

Цель: реализовать алгоритм Маркова на одном из языков программирования и представить описание его работы.

Порядок выполнения

1. Написать программу;

2. Преобразовать входную строку содержательного характера в другу строку с конкретным смыслом;

3. Система замен состоит из не менее 5 замен.

Краткое описание алгоритма

Алгоритм состоит из следующих этапов:

1. ищем вхождение подстроки s1 в строку s;

2. если s1 принадлежит s, заменяем на s1`;

3. вновь возвращаемся к исходной строке и снова отыскиваем s1, если нашлась, то к шагу 2, иначе

4. переходим к следующей по порядку замене (s2);

5. если замена s2 произошла, то рассматривая изменившуюся строку как исходную, снова возвращаемся к первой замене, иначе

6. переходим к замене s3;

7. если замена s3 не выполнилась, то к шагу 1;

8. если s1..s3 не выполнились, переходим к замене s4 и так далее, пока не выполнятся все возможные замены;

9. если после очередной замены система замен перестаёт срабатывать, процесс завершается.

Нормальный алгоритм Маркова на языке PHP

<?php

$str1 = "мама мыла раму";//Исходная строка

//массив замен на подстроки:

$s = Array(Array("мама","без сапог"), Array("мыла","гладила"), Array("раму","из головы"), Array("сапог","труда легко"), Array("гладила","и носки"), Array("головы","пруда"), Array("носки","рыбку"), Array("легко","не выловишь"));

print "Исходная строка: <br>".$str1."\n<br/>";

//Алгоритм маркова через рекурсию:

function Markov($string, $zamena, $i = 0, $n){

$s = $string;//Резервное копирование входной строки

$str = $s;

if($i>=$n)//проверка на завершение цикла

return $s;

$str = explode($zamena[$i][0],$s);//поиск вхождения подстроки

if (count($str)>1)//если подстроки найдены, заменить

$s = implode($zamena[$i][1],$str);

print "\n<br/>".$s. " (".$i.")";//вывод строки на текущем этапе

if ($i>0)//проверка предыдущих подстрок на текущем этапе

$str= Markov($s,$zamena,0,$i);

if ($i<$n)//переход на следующий этап

$str= Markov($s,$zamena,$i+1,$n);

return $str;

}

$str2 = Markov($str1,$s,0,count($s));//Пропустить исходную строку через алгоритм Маркова

print "<br>Конечная строка: ".$str2;

Результат программы

Исходная строка:

мама мыла раму

без сапог мыла раму (0)

без сапог гладила раму (1)

без сапог гладила раму (0)

без сапог гладила из головы (2)

без сапог гладила из головы (0)

без сапог гладила из головы (1)

без сапог гладила из головы (0)

без труда легко гладила из головы (3)

без труда легко гладила из головы (0)

без труда легко гладила из головы (1)

без труда легко гладила из головы (0)

без труда легко гладила из головы (2)

без труда легко гладила из головы (0)

без труда легко гладила из головы (1)

без труда легко гладила из головы (0)

без труда легко и носки из головы (4)

без труда легко и носки из головы (0)

без труда легко и носки из головы (1)

без труда легко и носки из головы (0)

без труда легко и носки из головы (2)

без труда легко и носки из головы (0)

без труда легко и носки из головы (1)

без труда легко и носки из головы (0)

без труда легко и носки из головы (3)

без труда легко и носки из головы (0)

без труда легко и носки из головы (1)

без труда легко и носки из головы (0)

без труда легко и носки из головы (2)

без труда легко и носки из головы (0)

без труда легко и носки из головы (1)

без труда легко и носки из головы (0)

без труда легко и носки из пруда (5)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (2)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (3)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (2)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (4)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (2)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (3)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (2)

без труда легко и носки из пруда (0)

без труда легко и носки из пруда (1)

без труда легко и носки из пруда (0)

без труда легко и рыбку из пруда (6)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (3)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (4)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (3)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (5)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (3)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (4)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (3)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (2)

без труда легко и рыбку из пруда (0)

без труда легко и рыбку из пруда (1)

без труда легко и рыбку из пруда (0)

без труда не выловишь и рыбку из пруда (7)