Описание использованных программных средств
Таблица 4.2.1–Описание переменных
Кроме стандартных функций из библиотек iostream.h, string.h, stdio.h, conio.h были использованы также следующие функции. · word minim(word x, word y) – функция, которая возвращает минимальное из x и y.
Рис. 4.2.1 · int min(int n) – функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0). Рис. 4.2.2 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
При запуске программы на экране появится окно с инструкциями. Выполняйте эти инструкции, а именно: 1. Введите количество вершин исследуемого графа. 2. Введите веса рёбер (положительное число). В программе расстояния от хi до xi+1 и xi+1 до хi считаются равными, а расстояния от хi до хi – не существующими. Если ребра между указанными вершинами не существует, введите 0 (ноль). На экран выводится матрица смежности, отображающая введённую информацию. 3. Введите номер вершины, от которой начинается искомый путь. 4. Введите номер вершины, в которой путь заканчивается. 5. Чтоб завершить работу программы после получения результата нажмите Enter. ЗАКЛЮЧЕНИЕ
Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual C++ 6.0. Её недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование». ПЕРЕЧЕНЬ ССЫЛОК 1. Бондарев В.М. Программирование на С++.–Х: «Компания СМИТ», 2004 2. Страуструп Бьярн Язык программирования С++(2 ч).–«К:ДиаСофт», 1993 3. Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).–Кафедра АПВТ, 2002 4. Алгоритм Дейкстры 5. Конспект лекций. Приложение А Текст программы #include<iostream.h> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<conio.h> #define word unsigned int
int i, j, n, p, xn, xk; int flag[11]; word c[11][11], l[11]; char s[80], path[80][11];
int min(int n) { int i, result; for(i=0;i<n;i++) if(!(flag[i])) result=i; for(i=0;i<n;i++) if((l[result]>l[i])&&(!flag[i])) result=i; return result; }
word minim(word x, word y) { if(x<y) return x; return y; }
void main() { cout<<"Vvedite kolichestvo tochek: "; cin>>n; for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) { cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do x"<<j+1<<": "; cin>>c[i][j]; } cout<<" "; for(i=0;i<n;i++) cout<<" X"<<i+1; cout<<endl<<endl; for(i=0;i<n;i++) { printf("X%d",i+1); for(j=0;j<n;j++) { printf("%6d",c[i][j]); c[j][i]=c[i][j]; } printf("\n\n"); } for(i=0;i<n;i++) for(j=0;j<n;j++) if(c[i][j]==0) c[i][j]=65535; //бесконечность cout<<"Vvedite nachalnuy tochku: "; cin>>xn; cout<<"Vvedite konechnuy tochku: "; cin>>xk; xk--; xn--; if(xn==xk) { cout<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl; getch(); return; }
for(i=0;i<n;i++) { flag[i]=0; l[i]=65535; } l[xn]=0; flag[xn]=1; p=xn; itoa(xn+1,s,10); for(i=1;i<=n;i++) { strcpy(path[i],"X"); strcat(path[i],s); } do { for(i=0;i<n;i++) if((c[p][i]!=65535)&&(!flag[i])&&(i!=p)) { if(l[i]>l[p]+c[p][i]) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); strcat(path[i+1],s); } l[i]=minim(l[i],l[p]+c[p][i]); } p=min(n); flag[p]=1; } while(p!=xk); if(l[p]!=65535) { cout<<"Put: "<<path[p+1]<<endl; cout<<"Dlina puti: "<<l[p]<<endl; } else cout<<"takogo puti ne syshestvuet!"<<endl; getch(); } Приложение Б Результат Приложение В
Схема программной реализации алгоритма Дейкстры
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (348)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |