МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ ТЕХНІЧНИЙ КОЛЕДЖ НАЦІОНАЛЬНОГО УНІВЕРСИТЕТУ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» ВІДДІЛЕННЯ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА КОМП'ЮТЕРНОЇ ТЕХНІКИ Лабораторна робота №5 з Алгоритмів і структури даних на тему: Алгоритми Маркова Мета: Навчитись реалізовувати систему підстановок для вхідного слова з метою вдосконалення та оволодіння навиками мов програмування. Постановка задачі: Скласти програму, що дозволяє автоматично реалізовувати НАМ та зміну вхідного слова за допомогою системи підстановок. Завдання: ввести з клавіатури слово і розташувати його літери за абеткою, попередньо сформувавши необхідну систему підстановок. Теоретична інформація Нормальні алгоритми Маркова – це є алгоритмічні системи, до складу яких, крім алфавіту (чи алфавітів), належать елементарні припустимі операції двох видів: елементарні підстановки та елементарні розпізнавачі. Елементарні підстановки — це алфавітні оператори, послідовність яких може реалізувати будь-які алгоритми перетворення інформації. Елементарні розпізнавачі перевіряють наявність тих чи інших властивостей перетворюваної алгоритмами інформації, а результат розпізнавання визначає послідовність виконання елементарних підстановок. Існують узагальнений і нормальний алгоритми Маркова. Для того, щоб впорядкувати літери за алфавітом потрібно використати нормальний алгоритм. Код програми #include "stdafx.h" #include<stdio.h> #include<conio.h> #include<iostream> using namespace std; int main(void) { char c[10]="yuriybishko"; char t; int i; cout<<c<<endl; for(i=1;i<10;i++) for(i=1;i<10;i++) { if((c[i-1]=='y')&&(c[i]=='b')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='i')&&(c[i]=='b')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='b')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='b')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='b')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='s')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='i')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='i')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='u')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='i')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='s')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='i')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='i')&&(c[i]=='h')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='s')&&(c[i]=='k')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='k')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='r')&&(c[i]=='k')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='k')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='k')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='s')&&(c[i]=='o')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='o')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='hr')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='r')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='s')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='u')&&(c[i]=='s')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='s')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} if((c[i-1]=='y')&&(c[i]=='u')) {t=c[i-1];c[i-1]=c[i];c[i]=t; cout<<c<<endl;break;} } cout<<c; _getch(); return 0; } Блок-схема:
Результат виконання:
Висновок: навчився реалізовувати систему підстановок для вхідного слова.