Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми обходу дерев
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2017
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Методи і системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІСЬКА ПОЛІТЕХНІКА»
Кафедра ІСМ
Звіт
До лабораторної роботи №3
З дисципліни:
«Методи та системи штучного інтелекту»
На тему:
«Алгоритми обходу дерев»
Львів-2017
Мета роботи: полягає у вивченні алгоритмів обходу дерев та застосування їх для запису та обчислення виразів у спеціальних (польських) нотаціях.
Теоретичні відомості
Існує багато задач, які можна моделювати використовуючи деревовидні структури. Поширеною є така загальна постановка задачі: виконати задану операцію D з кожною вершиною дерева. Тут D розглядається як параметр більш загальної задачі відвідування всіх вершин, або, як кажуть, обходу дерева. Якщо розглядати цю задачу як єдиний послідовний процес, то окремі вершини відвідуються у деякому визначеному порядку і можуть вважатись розташованими одна за однією, у лінійному порядку. Опис багатьох алгоритмів істотно спрощується, якщо можна говорити про наступну вершину дерева, маючи на увазі деяке упорядкування.
Існує три принципи впорядкування вершин, які природно випливають із структури дерева. Як і саму деревовидну структуру, їх зручно виразити за допомогою рекурсії. Обходи:
Зверху вниз або обхід у прямому порядку (preorder): R, A, B –тобто відвідати корінь до відвідування піддерев;
Зліва направо або обхід у внутрішньому порядку (inorder): A, R, B;
Знизу вверх або обхід у зворотному порядку (postorder): A, B, R - тобто відвідати корінь після відвідування піддерев.
Прямий польський запис відповідає обходу дерева виразу зверху внизу (префіксна форма запису виразу). Правило обчислення значення виразу у прямому польському записі описується таким алгоритмом. Проглядається справа наліво і виділяються два операнди разом із знаком операції, який їм передує. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.
Обернений польський запис відповідає обходу дерева знизу вверх (постфіксна форма запису). Правило обчислення значення виразу в оберненому польському записі описується таким алгоритмом. Вираз проглядається зліва направо, виділяються два операнди разом із знаком операції, яка стоїть після них. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записується на місце вилучених символів.
Завдання лабораторної роботи:
Виконати обхід заданого дерева зверху донизу, знизу доверху та зліва направо. Дерево може задаватись списками вершин або матрицею суміжності. Програма повинна дозволяти здійснювати обхід, починаючи з кореневої вершини.
Для довільного алгебраїчного виразу, що містить операції додавання, віднімання, множення та ділення та логічного виразу з операціями заперечення, кон’юнкції та диз’юнкції побудувати відповідні пряму та обернену польські записи.
Обчислити значення алгебраїчного та логічного виразів, записаних у прямій та оберненій польських нотаціях.
Результати виконання роботи:
package PHSHI.Lab3;
import java.util.Scanner;
public class ObchPol {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
System.out.println("Введіть вираз: ");
String s=scanner.next();
System.out.println("Виберіть тип польської нотації:\n 1.Пряма\n 2.Обернена");
int n=scanner.nextInt();
switch (n){
case 1:Pryam(s); break;
case 2:Obern(s); break; } }
static void Obern(String s) {
String copy=s;
String s2="";
for(int i=0;i<s.length();i++)
s2+=copy.substring(s.length()-(i+1),s.length()-i);
Pryam(s2); }
static void Pryam(String s) {
String copy=s;
String sub;
boolean flag=false;
int r=0,indx=0,d=0;
while(copy.length()!=1) {
for(int i=0;i<copy.length();i++)
if(copy.charAt(i)=='+'||copy.charAt(i)=='-'||copy.charAt(i)=='/'||copy.charAt(i)=='*') {indx=i; break;}
sub=copy.substring(indx-2,indx+1);
if(sub.charAt(2)=='+')
if(sub.charAt(0)=='r'&&sub.charAt(1)!='d') r=r+sub.charAt(1)-48; else
if(sub.charAt(1)=='r'&&sub.charAt(0)!='d') r=r+sub.charAt(0)-48; else
if(sub.charAt(0)!='r'&&sub.charAt(1)=='d') {d=d+sub.charAt(0)-48;flag=true;} else
if(sub.charAt(0)=='r'&&sub.charAt(1)=='d') r=d+r; else
if(sub.charAt(1)=='r'&&sub.charAt(0)=='d') r=d+r; else
if(sub.charAt(1)!='r'&&sub.charAt(0)=='d'){ d=d+sub.charAt(1)-48;flag=true;} else
if(r==0) r=sub.charAt(0)+sub.charAt(1)-96; else
if(r!=0) {d=sub.charAt(0)+sub.charAt(1)-96;flag=true;}
if(sub.charAt(2)=='-')
if(sub.charAt(0)=='r'&&sub.charAt(1)!='d') r=r-sub.charAt(1)-48; else
if(sub.charAt(1)=='r'&&sub.charAt(0)!='d') r=sub.charAt(0)-48-r; else
if(sub.charAt(0)!='r'&&sub.charAt(1)=='d') {d=sub.charAt(0)-48-d;flag=true;} else
if(sub.charAt(0)=='r'&&sub.charAt(1)=='d') r=r-d; else
if(sub.charAt(1)=='r'&&sub.charAt(0)=='d') r=d-r; else
if(sub.charAt(1)!='r'&&sub.charAt(0)=='d') {d=d-sub.charAt(1)-48;flag=true;} else
if(r==0) r=sub.charAt(0)-sub.charAt(1); else
if(r!=0) {d=sub.charAt(0)-sub.charAt(1);flag=true;}
if(sub.charAt(2)=='*')
if(sub.charAt(0)=='r'&&sub.charAt(1)!='d')r=r*(sub.charAt(1)-48); else
if(sub.charAt(1)=='r'&&sub.charAt(0)!='d')r=r*(sub.charAt(1)-48); else
if(sub.charAt(0)!='r'&&sub.charAt(1)=='d') {d=d*(sub.charAt(0)-48);flag=true;} else
if(sub.charAt(0)=='r'&&sub.charAt(1)=='d')r=d*r; else
if(sub.charAt(1)=='r'&&sub.charAt(0)=='d')r=d*r; else
if(sub.charAt(1)!='r'&&sub.charAt(0)=='d') {d=d*(sub.charAt(1)-48);flag=true;} else
if(r==0) r=(sub.charAt(0)-48)*(sub.charAt(1)-48); else
if(r!=0) {d=(sub.charAt(0)-48)*(sub.charAt(1)-48);flag=true;}
if(sub.charAt(2)=='/')
if(sub.charAt(0)=='r'&&sub.charAt(1)!='d')r=r/(sub.charAt(1)-48); else
if(sub.charAt(1)=='r'&&sub.charAt(0)!='d')r=(sub.charAt(0)-48)/r; else
if(sub.charAt(0)!='r'&&sub.charAt(1)=='d') {d=(sub.charAt(0)-48)/d;flag=true;} else
if(sub.charAt(0)=='r'&&sub.charAt(1)=='d') r=r/d; else
if(sub.charAt(1)=='r'&&sub.charAt(0)=='d') r=d/r; else
if(sub.charAt(1)!='r'&&sub.charAt(0)=='d')
{d=d/(sub.charAt(1)-48);flag=true;} else
if(r==0) r=(sub.charAt(0)-48)/(sub.charAt(1)-48); else
if(r!=0) {d=(sub.charAt(0)-48)/(sub.charAt(1)-48);flag=true;}
if(flag) copy=copy.substring(0,indx-2)+"d"+copy.substring(indx+1,copy.length()); else copy=copy.substring(0,indx-2)+"r"+copy.substring(indx+1,copy.length());
flag=false; }
System.out.println("Результат: "+r); }}
package PHSHI.Lab3;
import java.util.Scanner;
public class Polsk {
static String s="";
public static void main(String[] args) {
Scanner r=new Scanner(System.in);
System.out.println("Введіть вираз: ");
s=r.next();
System.out.println("Виберіть вид польського запису:\n 1.Прямий\n 2.Зворотній\n");
int choice=r.nextInt();
switch (choice) {
case 1: Pryam(); break;
case 2: Zvorot(); break; } }
static void Zvorot() {
int count=0,count2=0,indxL=0,indxR=0,indx=0,countDL=0,countDR=0;
String sub="",copy="",copy2="";
for(int i=0;i<s.length();i++)
if(s.charAt(i)==')'){ count++; count2++;}else if(s.charAt(i)=='(') count--;
if(count!=0) {
System.out.println("К-ть дужок різна"); return;}
copy=s;
while(count2>0) {
for(int i=0;i<copy.length();i++)
if(copy.charAt(i)==')') { indxR=i; break;}
for(int i=indxR;i>=0;i--)
if(copy.charAt(i)=='(') {indxL=i; break;}
sub=copy.substring(indxL+1,indxR);
System.out.println("sub "+sub);
countDR=0; countDL=0; count=0;
if(sub.length()==1) {copy2=sub+copy2; sub="";}
if(sub.length()==3) sub=sub.charAt(1)+""+sub.charAt(0)+sub.charAt(2);
else if(sub.length()==2)
{ for(int i=0;i<s.length()-3;i++)
if(s.charAt(i+1)==sub.charAt(0)&&s.charAt(i+2)==sub.charAt(1)) indx=i;
if(s.charAt(indx)=='(') count=0; else
for(int i=indx;i>0;i--)
{ if(s.charAt(i)==')') countDR++; else if(s.charAt(i)=='(') countDL++; else count++;
if(countDR==countDL) break; }
{copy2=copy2.substring(0,copy2.length()-count)+sub.charAt(0)+copy2.substring(copy2.length()-count,copy2.length()); sub=""+sub.charAt(1); } }
copy2+=sub;
System.out.println("copy2 "+copy2);
copy=copy.substring(0,indxL)+copy.substring(indxR+1,copy.length());
System.out.println("copy "+copy);
sub="";
count2--; }
System.out.println("Результат: "+copy2); }
static void Pryam() {
int count=0,count2=0,indxL=0,indxR=0;
String sub="",copy="",copy2="";
for(int i=0;i<s.length();i++)
if(s.charAt(i)==')'){ count++; count2++;}else if(s.charAt(i)=='(') count--;
if(count!=0) {
System.out.println("К-ть дужок різна"); return;}
copy=s;
while(count2>0) {
for(int i=0;i<copy.length();i++)
if(copy.charAt(i)==')') { indxR=i; break;}
for(int i=indxR;i>=0;i--)
if(copy.charAt(i)=='(') {indxL=i; break;}
sub=copy.substring(indxL+1,indxR);
if(sub.length()==3) sub=sub.charAt(0)+""+sub.charAt(2)+sub.charAt(1);
else if(sub.length()==2) sub=""+sub.charAt(1)+sub.charAt(0);
copy2+=sub;
copy=copy.substring(0,indxL)+copy.substring(indxR+1,copy.length());
sub="";
count2--; }
System.out.println("Результат: "+copy2); }}
package PHSHI.Lab3;
import java.util.Scanner;
public class Trees {
static int matrsymiz[][];
static String nazvyversh[];
public static void main(String[] args) {
System.out.println("Введіть кількість вершин дерева:");
Scanner scanner=new Scanner(System.in);
int number=scanner.nextInt();
System.out.println("Введіть назви вершин зверху вниз по рівнях:");
matrsymiz=new int[number][number];
nazvyversh=new String[number];
for(int i=0;i<number;i++)
nazvyversh[i]=scanner.next();
System.out.println("Введіть матрицю суміжності зверху вниз по рівнях:");
for(int i=0;i<number;i++)
for(int j=0;j<number;j++)
matrsymiz[i][j]=scanner.nextInt();
System.out.println("Виберіть тип обходу:\n 1.Зверху донизу\n 2.Знизу доверху\n 3.Зліва направо");
int chosen=scanner.nextInt();
switch(chosen) {
case 1: aboveTobelow(); break;
case 2:belowToabove(); break;
case 3:leftToright(); break; } }
static void aboveTobelow(){
String obh=nazvyversh[0];
int mat[][]=new int[nazvyversh.length][nazvyversh.length];
for(int j=0;j<nazvyversh.length;j++)
for(int i=0;i<nazvyversh.length;i++)
mat[j][i]=matrsymiz[j][i];
String set=""+0;
boolean flag = false,flag2=false;
int indx = 0;
m1: while(!flag2) {
flag = false;
m2: for(int j=0;j<nazvyversh.length;j++) {
for(int i=0;i<nazvyversh.length;i++) {
if (mat[indx][i] == 1) {
mat[indx][i] = 0;
indx = i;
flag = true;
break; } }
if(flag) {
obh += nazvyversh[indx];
set += indx;
flag=false;
} else break m2; }
if(set.length()>0) { indx=set.charAt(set.length()-1)-48;
set=set.substring(0,set.length()-1); }
flag2=true;
for(int j=0;j<nazvyversh.length;j++)
for(int i=0;i<nazvyversh.length;i++)
if(mat[i][j]==1) flag2=false; }
System.out.println(obh); }
static void belowToabove() {
String obh="";
int mat[][]=new int[nazvyversh.length][nazvyversh.length];
for(int j=0;j<nazvyversh.length;j++)
for(int i=0;i<nazvyversh.length;i++)
mat[j][i]=matrsymiz[j][i];
String set="";
boolean flag = false,flag2=false;
int indx = 0;
m1: while(!flag2) {
flag = false;
m2: for(int j=0;j<nazvyversh.length;j++) {
for (int i = 0; i < nazvyversh.length; i++) {
if (mat[indx][i] == 1) {
indx = i;
flag = true;
break; } } }
if(flag) {
obh += nazvyversh[indx];
set += indx;
}
for(int j=0;j<nazvyversh.length;j++)
mat[j][indx]=0;
indx=0;
flag2=true;
for(int j=0;j<nazvyversh.length;j++)
for(int i=0;i<nazvyversh.length;i++)
if(mat[i][j]==1) flag2=false; }
obh+=nazvyversh[0];
System.out.println(obh); }
static void leftToright() {
String obh="";
int mat[][]=new int[nazvyversh.length][nazvyversh.length];
for(int j=0;j<nazvyversh.length;j++)
for(int i=0;i<nazvyversh.length;i++)
mat[j][i]=matrsymiz[j][i];
String set="",set2="";
boolean flag = false,flag2=false;
boolean matflag[]=new boolean[nazvyversh.length];
for(int i=0;i<nazvyversh.length;i++)
matflag[i]=false;
int indx = 0,count=0,count2=0;
for(int i=0;i<nazvyversh.length;i++)
if(mat[0][i]==1) count++;
m1: while(!flag2) {
flag = false;
m2: for(int j=0;j<nazvyversh.length;j++) {
for (int i = 0; i < nazvyversh.length; i++) {
if (mat[indx][i] == 1) {
indx = i;
flag = true;
flag2=true;
break; } }
if(flag2) {
flag2=false;
set+=nazvyversh[indx];
set2+=indx; } }
if(flag&&set.length()>1) {
if(!matflag[set2.charAt(set2.length()-1)-48])
obh += set.substring(set.length()-1,set.length());
if(!matflag[set2.charAt(set2.length()-2)-48])
obh+=set.substring(set.length()-2,set.length()-1);
matflag[set2.charAt(set2.length()-1)-48]=true;
matflag[set2.charAt(set2.length()-2)-48]=true; }
for(int j=0;j<nazvyversh.length;j++)
mat[j][indx]=0;
for(int j=0;j<nazvyversh.length;j++)
if(mat[0][j]==1) count2++;
if(!matflag[0]) if(count!=count2) { obh+=nazvyversh[0]; matflag[0]=true; }
count2=0;
indx=0;
flag2=true;
for(int j=0;j<nazvyversh.length;j++)
for (int i = 0; i < nazvyversh.length; i++)
if(mat[i][j]==1) flag2=false; }
System.out.println(obh); }}
В даній програмі використовувався тестовий інтерфейс. Спершу необхідно ввести кількість вершин у дерева, потім назви вершин та матрицю їх суміжності. В результаті буде виведена послідовність обходу даного дерева. (Рис. 2 - 4).
Рис. 1.
/
Рис. 2. Результат виконання програми обходу дерева зверху донизу
/
Рис. 3. Результат виконання обходу дерева знизу доверху
/
Рис. 4. Результат виконання програми обходу дерева зліва направо
/
Рис. 5. Результат перетворення звичайного виразу у польський запис
/
Рис. 6. Результат обчислення польського виразу
Висновок
Виконавши дану лабораторну роботу, вивчила алгоритми обходу дерев та застосування їх для запису та обчислення виразів у спеціальних (польських) нотаціях.
30.05.2019 15:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора