МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний Університет "Львівська Політехніка" Розрахункова робота з дисципліни:"Теорія алгоритмів" Варіант 9 Пройдіть в лабіринті від майданчика 1 до майданчика 8: а) так, щоб відвідати всі майданчики по одному разу; б) найкоротшим шляхом.
Програмний код: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Zik { public partial class Form1 : Form { int endElement = 8; public List<int>[] list = new List<int>[8]; public List<List<int>> playList = new List<List<int>>(); public List<int> way = new List<int> (); Point[] poi = new Point[18] { new Point(45, 160), new Point(85, 160), new Point(96, 149), new Point(96, 76), new Point(104, 76), new Point(182, 149), new Point(106, 160), new Point(172, 160), new Point(192, 160), new Point(250, 160), new Point(260, 150), new Point(260, 86), new Point(270, 160), new Point(330, 160), new Point(270, 76), new Point(342, 150), new Point(351, 160), new Point(413, 160)}; public Form1() { InitializeComponent(); list[0] = new List<int> { 1 }; list[1] = new List<int> { 2 }; list[2] = new List<int> { 4, 3 }; list[3] = new List<int> { 4 }; list[4] = new List<int> { 5 }; list[5] = new List<int> { 7, 6 }; list[6] = new List<int> { 7 }; list[7] = new List<int> { 8 }; } private void startToolStripMenuItem_Click(object sender, EventArgs e) { panel1.Visible = true; FormStartPicture(); } public void FormStartPicture() { Graphics g = panel1.CreateGraphics(); Pen rp = new Pen(Color.Black, 1); g.DrawLine(rp, poi[0], poi[1]); g.DrawLine(rp, poi[2], poi[3]); g.DrawLine(rp, poi[4], poi[5]); g.DrawLine(rp, poi[6], poi[7]); g.DrawLine(rp, poi[8], poi[9]); g.DrawLine(rp, poi[10], poi[11]); g.DrawLine(rp, poi[12], poi[13]); g.DrawLine(rp, poi[14], poi[15]); g.DrawLine(rp, poi[16], poi[17]); } private void порахуватиToolStripMenuItem_Click(object sender, EventArgs e) { foreach (int n in list[0]) { way.Add(n); if (n != endElement) { List<int> way1 = new List<int>(); foreach (int c in way) { way1.Add(c); } Recursive(n, way1); } else { playList.Add(way); } } MessageBox.Show("Пораховано !!!", "Ahtung", MessageBoxButtons.OK, MessageBoxIcon.Information); } private void Recursive(int n, List<int> way) { foreach (int i in list[n]) { if(i != list[n][0]) way.RemoveAt(way.Count-1); way.Add(i); if (i != endElement) { List<int> way1 = new List<int>(); foreach (int c in way) way1.Add(c); Recursive(i, way1); } else { playList.Add(way); } } } private void вихідToolStripMenuItem_Click(object sender, EventArgs e) { Close(); } private void результатиToolStripMenuItem_Click(object sender, EventArgs e) { panel2.Visible = true; richTextBox1.Text = " Всього шляхів:" + playList.Count + "\n"; for (int i = 0; i < playList.Count; i++) { richTextBox1.Text += i + ") "; for (int j = 0; j < playList[i].Count; j++) { richTextBox1.Text += playList[i][j] + " "; } richTextBox1.Text += "\n"; } } private void button9_Click(object sender, EventArgs e) { int len = 10; int num = 0; for (int i = 0; i < playList.Count; i++) { if (playList[i].Count < len) { len = playList[i].Count; num = i; } } Graf(playList[num]); } private void Graf(List<int> way) { Graphics g = panel1.CreateGraphics(); g.Clear(Color.White); Pen rp = new Pen(Color.Red, 4); for (int i = 0; i < way.Count - 1; i++) { int j = way[i + 1]; int z = way[i]; if (z == 1) g.DrawLine(rp, poi[0], poi[1]); if ((z == 2) && (j == 3)) g.DrawLine(rp, poi[2], poi[3]); if ((z == 3) && (j == 4)) g.DrawLine(rp, poi[4], poi[5]); if ((z == 2) && (j == 4)) g.DrawLine(rp, poi[6], poi[7]); if ((z == 4) && (j == 5)) g.DrawLine(rp, poi[8], poi[9]); if ((z == 6) && (j == 7)) g.DrawLine(rp, poi[14], poi[15]); if ((z == 5) && (j == 6)) g.DrawLine(rp, poi[10], poi[11]); if ((z == 5) && (j == 7)) g.DrawLine(rp, poi[12], poi[13]); if ((z == 7) && (j == 8)) g.DrawLine(rp, poi[16], poi[17]); } } private void button10_Click(object sender, EventArgs e) { int len = 0; int num = 0; for (int i = 0; i < playList.Count; i++) { if (playList[i].Count > len) { len = playList[i].Count; num = i; } } Graf(playList[num]); } private void button11_Click(object sender, EventArgs e) { int num = Int32.Parse(comboBox1.Text); Graf(playList[num]); } } } Програма в роботі: / / / Висновок: Після початку роботи програми - потрібно натиснути кнопку "Start", щоб вивести граф на форму(на екран). Потім потрібно підрахувати обхід за допомогою кнопки "Порахувати", після чого програма прораховує обхід графа, щоб вивести результати потрібно натиснути кнопку "Результат". В любий момент користувач може закінчити роботу програми натиснувши кнопку "Вихід". Програма написана рекурсивним методом, вона переходить на наступну позицію до тих пір, поки не знайде декілька шляхів. У разі знаходження декількох шляхів, програма робить перевірку чи можна перейти таким чином, щоб шлях обходу став швидшим(у разі знаходження "Найкоротшого шляху"). І проходить по кожній позиції послідовно(у разі знаходження "Повного шляху"). Розберемо "Найкоротший шлях". Почнемо з 1 позиції, з 1 позиції є тільки один шлях тому програма переходить на наступний елемент і записує дані про перший крок. З 2 позиції є два шляхи, вона робить перевірку (якщо можливо перейти зразу на 4 позицію - тоді переходить. З 4 позиції програма знову перевіряє скільки є можливих шляхів, у нашому випаду один шлях і програма переходить на 5 позицію. На 5 позиції програма знову шукає усі можливі шляхи, перевіряє і знаходить коротший шлях, в нашому випадку перейшла на 7 позицію. З 7 позиції програма знову перевіряє кількість можливих шляхів, так як є один шлях, вона переходить на 8 позицію. Програма закінчила обхід і записала дані про цей обхід. Розберемо "Повний шлях". Тут все значно простіше, програма починає з 1 позиції і робить перехід на 2 позицію. З 2 позиції є два шляхи, програма переходить просто на наступну 3 позицію. З 3 позиції, програма переходить на наступну 4 позицію. З 4 позиції програма переходить на 5 позицію. З 5 позиції є два шляхи, і програма знову шукає наступну позицію, і переходить на 6 позицію. З 6 позиції програма переходить на 7 позицію. З 7 позиції теж один шлях і програма переходить на 8 позицію. Програма закінчила обхід і записала дані про цей обхід. Програма може знаходити ще усі можливі шляхи, окрім знаходження "Повного шляху" і "Найшвидшого шляху". Алгоритм розробленої програми розрахований для розрахунку різних графів.