Автор работы: Пользователь скрыл имя, 19 Июня 2014 в 19:26, курсовая работа
В данной курсовой работе рассмотрены два вопросы. Первый из них – генерация подмножеств. Второй – дерево Штейнера и алгоритмы его построения.
В работе я рассмотрела следующие понятия: множество, генерация подмножеств, понятие минимального по включению дерева Штейнера; описание и обоснование алгоритма построения всех минимальных по включению деревьев Штейнера, как одного из алгоритмов точного решения задачи Штейнера на графе.
Приложение А- листинг программы "Генерация подмножеств"
Исходный код на C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("введите множество");
string[] str = Console.ReadLine().Split(' ');
int b;
int j;
for (int i = 0; i < Math.Pow(2, str.Length); i++)
{
b = i;
j = 0;
Console.Write("{ ");
while (b>0)
{
if (b % 2 == 0)
{
b /= 2;
j++;
}
else
{
b /= 2;
Console.Write(str[j]+" ");
j++;
}
}
Console.WriteLine("}");
}
Console.ReadKey();
}
}
}
Приложение Б- листинг программы "Дерево Штейнера"
Исходный код на C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static void Cheng_mark(int[] mark, int l, int m)
{
if (m < l)
{
int buf = m;
m = l;
l = buf;
}
for (int i = 0; i < mark.Length; i++)
if (mark[i] == m)
mark[i] = l;
}
public static int [ , ] Ostov(int [,] matrix, int n)
{
int[,] re = new int[3, n];
int[] mark = new int[matrix.GetLength(1)];
for (int i = 0; i < matrix.GetLength(1); i++)
mark[i] = i;
int k = -1, t = matrix.GetLength(1)-1, v, kol=0;
while (k < matrix.GetLength(1) - 1)
{
v = -1;
do
{
v++;
k++;
}
while ((v <= t) && (mark[matrix[1, v] - 1] == mark[matrix[0, v] - 1]));
if (matrix[0, v] * matrix[1, v] != 0)
{
Console.WriteLine("{0} {1}", matrix[0, v], matrix[1, v]);
re[0, kol] = matrix[0, v];
re[1, kol] = matrix[1, v];
re[2, kol] = matrix[2, v];
Cheng_mark(mark, mark[matrix[0, v] - 1], mark[matrix[1, v] - 1]);
kol++;
}
}
return re;
}
static void Main(string[] args)
{
#region Ввод
Console.Write(" введите кол-во вершин ");
int n = int.Parse(Console.ReadLine());
Console.Write(" введите кол-во ребер в графе ");
int m = int.Parse(Console.ReadLine());
int[,] p = new int[3, m];
int[] metka = new int[n];
Console.WriteLine("ребро х у вес");
for (int i = 0; i < m; i++)
{
string[] str = Console.ReadLine().Split(' ');
p[0, i] = int.Parse(str[0]);
p[1, i] = int.Parse(str[1]);
p[2, i] = int.Parse(str[2]);
metka[int.Parse(str[0])-1] = 1;
metka[int.Parse(str[1])-1] = 1;
}
int kol = 0;
for (int i = 0; i < n; i++)
if (metka[i] == 0)
kol++;
int vg=n-kol;
int[,] p1 = new int[3, (n - kol) * kol + (kol*kol*(kol-1))/(2*kol)];
Console.WriteLine(" введите вес ребер ");
kol=0;
for (int i = 0; i < n; i++)
if (metka[i] == 0)
for (int j = 0; j < n; j++)
if (metka[j] == 1)
{
Console.Write("{0} {1} ", i + 1, j + 1);
p1[0, kol] = i + 1;
p1[1, kol] = j + 1;
p1[2, kol] = int.Parse(Console.ReadLine());
kol++;
}
for (int i = 0; i < n; i++)
{
if (metka[i] == 0)
{
for (int j = i + 1; j < n; j++)
if (metka[j] == 0)
{
Console.Write("{0} {1} ", i+1, j+1);
p1[0, kol] = i + 1;
p1[1, kol] = j + 1;
p1[2, kol] = int.Parse(Console.ReadLine());
kol++;
}
}
}
#endregion
#region слияние
int[,] p2 = new int[3, p.GetLength(1) + p1.GetLength(1)];
for (int i = 0; i < m; i++)
{
p2[0, i] = p[0, i];
p2[1, i] = p[1, i];
p2[2, i] = p[2, i];
}
kol = 0;
for (int i = m; i < p2.GetLength(1); i++)
{
p2[0, i] = p1[0, kol];
p2[1, i] = p1[1, kol];
p2[2, i] = p1[2, kol];
kol++;
}
Console.WriteLine();
#endregion
#region сортировка
for (int i = 0; i < p2.GetLength(1); i++)
for (int j = i; j < p2.GetLength(1); j++)
if (p2[2, i] > p2[2, j])
{
int buf = p2[0, i]; p2[0, i] = p2[0, j]; p2[0, j] = buf;
buf = p2[1, i]; p2[1, i] = p2[1, j]; p2[1, j] = buf;
buf = p2[2, i]; p2[2, i] = p2[2, j]; p2[2, j] = buf;
}
#endregion
int[,] ostov = Ostov(p2,n-1);
for (int i = 0; i < ostov.GetLength(1); i++)
if(ostov[0,i]!=0)
Console.WriteLine("{0} {1} {2}", ostov[0, i], ostov[1, i], ostov[2, i]);
Console.ReadKey();
}
}
}
Информация о работе Задачи и алгоритмы дискретной математики