Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 5 Дискретна математика
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
О
Факультет:
Не вказано
Кафедра:
КН
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Кафедра КН
Лабораторна робота №5
з дисципліни «Дискретна математика»
Тема: «: Побудова найкоротшого шляху у графі»
Виконали:
студенти групи 2КН – 15б
Ваховський В.М.
Ільченко О.В.
Перевірила:
Ваховська Л. М.
Вінниця
2016
Мета роботи: Набути навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри.
Завдання: розробити алгоритм та програму для алгоритму Дейкстри. Продемонструвати роботу програми на прикладі.
3. Завдання для виконання
Варіант 3
/
Варіант 7
/
Схема алгоритму
/
Рисунок 1 – Блок-схема алгоритму Дейкстри
Результати роботи:
Варіант 7
/
Рисунок 2 – Результат роботи програми для алгоритму Дейкстри
Варіант 3
/
Рисунок 3 – Результат роботи програми для алгоритму Дейкстри
Висновок
Під час виконання лабораторної роботи було розроблено алгоритм Дейкстри. Було розроблено програму для знаходження мінімального шляху графу. Продемонстровано результати роботи програми.
Додаток 1. Інструкція користувача
Для запуску програми мінімізації функції необхідно запустити файл
Algoritm_Dijkstra.exe. Ввести вектор або функцію.
Натиснути на кнопку «Найти кратчайший путь» для виконання пошуку мінімальної форми. Програма виведе найкоротший шлях та загальну вагу.
Додаток 2. Лістинги програми
//---------------------------------------------------------------------------
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vcl.h>
#pragma hdrstop
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class minterm {
public:
int a[4];
int size;
minterm(){
size=0;
}
minterm(int A,int B,int C,int D){
size=4;
a[0]=A;
a[1]=B;
a[2]=C;
a[3]=D;
}
void fill(int A,int B,int C,int D){
a[0]=A;
a[1]=B;
a[2]=C;
a[3]=D;
}
bool operator == (const minterm &m){
for(int i=0;i<size;i++){
if(a[i]!=m.a[i]) return 0;
}
return 1;
}
bool operator != (const minterm &m){
for(int i=0;i<size;i++){
if(a[i]!=m.a[i]) return 1;
}
return 0;
}
bool not_void(){
for(int i=0;i<size;i++){
if(a[i]!=-1) return 1;
}
return 0;
}
bool include(const minterm &m)
{
for(int k=0;k<4;k++)
{
if(m.a[k]!=-1 && a[k]!=m.a[k])
return 0;
}
return 1;
}
int count_1()
{
int c=0;
for(int i=0;i<4;i++)
if(a[i]==1)
c++;
return c;
}
bool positions_coincide(const minterm &m)
{
for(int i=0;i<4;i++)
if(a[i]==-1 && a[i]!=m.a[i])
return 0;
return 1;
}
bool can_be_united(const minterm &m)
{
for(int k=0;k<4;k++)
{
if(a[k]!=m.a[k])
{
for(int i=k+1;i<4 && k<3;i++)
if(a[i]!=m.a[i]) return false;
return true;
}
}
return true;
}
void glue(const minterm &m)
{
for(int k=0;k<4;k++)
{
if(a[k]!=m.a[k])
{
for(int i=k+1;i<4 && k<3;i++)
if(a[i]!=m.a[i]) return;
a[k]=-1;
return;
}
}
}
AnsiString print(){
AnsiString s;
if(!(a[0]==-1 && a[1]==-1 && a[2]==-1 && a[3]==-1)){
if(a[0]==1)
s=s+"A";
if(a[0]==0)
s=s+"!A";
if(a[1]==1)
s=s+"B";
if(a[1]==0)
s=s+"!B";
if(a[2]==1)
s=s+"C";
if(a[2]==0)
s=s+"!C";
if(a[3]==1)
s=s+"D";
if(a[3]==0)
s=s+"!D";
}
return s;
}
};
//---------------------------------------------------------------------------
class fal{
public:
minterm *mdnf;
int size,param;
class Table;
fal(){
size=0;
mdnf=0;
param=0;
}
fal(const AnsiString s,int param_){
minterm table[16]={
minterm(0,0,0,0),minterm(0,0,0,1),minterm(0,0,1,0),minterm(0,0,1,1),
minterm(0,1,0,0),minterm(0,1,0,1),minterm(0,1,1,0),minterm(0,1,1,1),
minterm(1,0,0,0),minterm(1,0,0,1),minterm(1,0,1,0),minterm(1,0,1,1),
minterm(1,1,0,0),minterm(1,1,0,1),minterm(1,1,1,0),minterm(1,1,1,1)};
int lenght=s.Length();
param=param_;
char* f= s.c_str();
for(int i=0;i<lenght;i++){
f[i]=f[i]-48;
}
size=0;
for(int i=0;i<lenght;i++){
if(f[i]==1){
++size;
}
}
mdnf=new minterm[size];
int j=0,koef=1;
if(param==3) koef=2;
if(param==2) koef=4;
for(int i=0;i<lenght;i++){
if(f[i]==1){
mdnf[j]=table[koef*i];
for(int k=param;k<4;++k)
mdnf[j].a[k]=-1;
j++;
}
}
}
fal(const Table &t,int param_)
{
mdnf=new minterm[t.size];
size=t.size;
param=param_;
for (int i = 0; i < size; i++) {
mdnf[i]=t.row[i]->m;
}
}
~fal(){
delete[] mdnf;
}
AnsiString print(){
int i;
AnsiString s;
for(i=0;!mdnf[i].not_void() && i<size;i++);
s=s+mdnf[i].print();
for(i=i+1;i<size;i++)
if(mdnf[i].not_void()){
s=s+" v ";
s=s+mdnf[i].print();
}
s=s+"\n";
return s;
}
int count(){
int n=0;
for(int i=0;i<size;i++)
if(mdnf[i].not_void()) n++;
return n;
}
//---------------------------------------------------------------------------
class Row
{
public:
int index;
int index_arr[8];
minterm m;
int n;
bool united;
Row()
{
index=n=0;
}
Row(int index_,minterm m_)
{
m=m_;
united=0;
index=index_+1;
for(int i=1;i<8;i++)
index_arr[i]=0;
index_arr[0]=index;
n=m.count_1();
}
Row(const Row &r)
{
m=r.m;
united=r.united;
index=r.index;
for(int i=0;i<8;i++)
index_arr[i]=r.index_arr[i];
n=r.n;
}
03.10.2018 00:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора