Файл: Обзор языков программирования высокого уровня (Языки программирования: понятие и история развития).pdf

Первой особенностью объектно-ориентированных языков программирования, о которой упомянули бы программисты, является сокрытие данных (инкапсуляция).^[20] Объектно-ориентированные языки (ООП) программирования придают огромное значение данным. Программист может скрыть действительно важные ключевые данные от внешнего мира, используя инструменты ООП.

Базовая концепция ООП основана на понятии, схожем с понятием структуры в ПОП и называемым классом. Класс представляет собой важную особенность ООП, он позволяет упаковать вместе различные типы данных наряду с различными функциями, манипулирующими элементами данных этого класса. Элементы данных внутри класса могут быть объявлены как локальные (private) или глобальные (public). Для того, чтобы спрятать данные от внешнего мира, программист должен объявить их как private. В общем, класс действительно схож со структурой в языке C. Как и любая структура, он объединяет в единое целое различные объекты. Основное отличие между классом и структурой кроется в функциях. Структуры не позволяют объединять в себе данные и функции (структуры работают только с данными), тогда как классы позволяют упаковывать данные вместе со связанными с ними функциями.

Кроме того, имеются еще различия, вроде сокрытия данных с помощью private/public. Структуры не облегчают сокрытие данных. В структуре к ее элементам получают доступ с помощью так называемых структурных переменных. В ООП используют другое понятие для доступа к данным и функциям внутри класса — объект. Данные и функции внутри класса называются членами или элементами класса. К элементу класса может быть получен доступ из внешнего мира (вне класса) только с помощью объекта класса.

Возможность сокрытия данных называется инкапсуляцией данных. Таким образом, один из главных недостатков ПОП решается в ООП. Объектно-ориентированный язык программирования тесно связывает данные с определенным классом и его объектами. Здесь нет необходимости в глобальных типах данных, как в ПОП, и, следовательно, данные не могут свободно «течь» по всей программе. Это гарантирует то, что не произойдет какой-либо случайной модификации важных данных.

Еще одной особенностью, привнесенной в ООП, является возможность повторного использования кода. Это просто означает то, что кусок кода, который был написан ранее, может быть использован в будущем. Это стало возможным благодаря особенности классов под названием наследование. Благодаря наследованию один класс может приобрести свойства другого класса. Это можно объяснить с помощью простого примера. Возьмем систему школьного управления. Изначально руководство решило разработать программу, сфокусированную только на учеников (без учета данных об учителях). Программист превосходно справился со своей работой, и в процессе программирования он объявил класс для сбора персональных данных, таких как имя, возраст, пол, адрес и т.д. Через год руководство школы решило включить в список данные об учителях. Теперь программист способен добавить эти данные за очень короткое время, поскольку он может использовать многие части кода, которые он написал ранее, благодаря наследованию. Класс персональных данных имеет общий характер (возраст, пол и пр. те же самые для человека вне зависимости от того, учитель он или ученик). Программист может наследовать данный класс новому классу, а также расширять этот новыми записями, например, записью о квалификации учителя. У ООП имеется еще много возможностей, вроде полиморфизма (перегрузки операторов и функций), динамического связывания и т.д. Обо всем этом можно почитать в соответствующей литературе.^[21]

Ниже представим неполный список объектно-ориентированных языков программирования: C#; C++; Java; Delphi; Eiffel; Simula; Objective-C; Swift; Object Pascal; Visual DataFlex; Perl; PowerBuilder; Python; Scala; ActionScript (3.0); Dylan; JavaScript; JScript .NET; Ruby; Smalltalk; Ada; Xbase++; X++; Vala; PHP; Cyclone.

3 Составление программы на примере языка программирования C++

3.1 Обоснование выбора языка программирования

В качестве задания мной была выбрана задача коммивояжера. Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

В качестве языков программирование был выбран С++, так как в нем:

1. Поддерживаются различные стили и технологии программирования, включая традиционное директивное программирование, ООП, обобщённое программирование, метапрограммирование (шаблоны, макросы).
2. Предсказуемое выполнение программ является важным достоинством для построения систем реального времени.
3. Автоматический вызов деструкторов объектов при их уничтожении, причём в порядке, обратном вызову конструкторов.
4. Пользовательские функции-операторы позволяют кратко и ёмко записывать выражения над пользовательскими типами в естественной алгебраической форме.
5. Язык поддерживает понятия физической (const) и логической (mutable) константности.
6. Используя шаблоны, возможно создавать обобщённые контейнеры и алгоритмы для разных типов данных, а также специализировать и вычислять на этапе компиляции.
7. Возможность имитации расширения языка для поддержки парадигм, которые не поддерживаются компиляторами напрямую.
8. Возможность создания встроенных предметно-ориентированных языков программирования.
9. Используя шаблоны и множественное наследование можно имитировать классы-примеси и комбинаторную параметризацию библиотек.
10. Кроссплатформенность: стандарт языка накладывает минимальные требования на ЭВМ для запуска скомпилированных программ.
11. Эффективность. Язык спроектирован так, чтобы дать программисту максимальный контроль над всеми аспектами структуры и порядка исполнения программы.
12. Имеется возможность работы на низком уровне с памятью, адресами.

3.2 Пример решения задачи коммивояжера методом Прима на C++

Алгоритм исходника решения задачи коммивояжера методом Прима на C++:

Пусть n - это количество вершин графа. Тогда в цикле n-1 выбирается самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранным. Для проверки того, что новое ребро не образует цикла с уже выбранными, каждую вершину i окрашивают в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет i.

Таким образом после выбора n-1 ребер все вершины получают один цвет.  Алгоритм Прима: 

1. (ввод). Ввести матрицу расстояний D={dij}, i,j=1,…,n. 

2. (инициализация). Приписать разные цвета всем вершинам: coli:=i; длина дерева L:=0. 

3. (общий шаг). В цикле по k:=1 to n-1 do найти ребро минимальной длины между вершинами разного цвета: пусть это ребро (i,j).

Запомнить результат: res1[k]:=i; res2[k]:=j;

Перекрасить вершины: I1:=col[i]; j1:=col[j].

В цикле по m:=1 to n do If col[m]=j1 then col[m]:=i1;

Нарастить длину дерева: L:=L+d[i,j].

Конец цикла по k.

4.(вывод). Вывести res1, res2.

Код на C++

1. #include <stdlib.h>
2. #include <time.h>
3. #include <stdio.h>
5. int wpchk(int w, int *wpts)
6. {
7. int i=0;
8. int flg=0;
9. while(wpts[i]!=-1)
10. {
11. if(wpts[i]==w){flg=1;}
12. i++;
13. }
15. if (flg==0) {return 0;} else return 1;
16. }
18. void main()
19. {
20. srand( (unsigned)time( NULL ) );
22. //int prices[10][10];
23. int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};
24. int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
25. int start=-1;
26. int end=-1;
27. int min;
28. int imin;
30. */// 0 1 2 3 4 5 6 7 8 9
31. int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
32. 0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
33. 0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
34. 0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
35. 0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
36. 0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
37. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
38. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
39. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
40. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9
42. printf("Enter № of start location:");
43. scanf("%i",&start);
44. printf("Enter № of finish location:");
45. scanf("%i",&end);
46. waypoint[0]=start;
47. int n=0;
48. int w;
49. while(waypoint[n]!=end)
50. {
51. min=0;
52. w=waypoint[n];
53. for(int i=0;i<10;i++)
54. {
55. if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;}
56. }
57. n++;
58. waypoint[n]=imin;
59. }
61. printf("\nThe way is:\n");
62. int i=0;
63. while(waypoint[i]!=-1)
64. {
65. printf("%i ",waypoint[i]);
66. i++;
67. }
68. getchar();
69. getchar();
70. }

3.3 Решение задачи при помощи алгоритма Дейкстры на C++

Задача: Определить длину (Q) кратчайшего маршрута (L) коммивояжера.

Расстояния (Q_ij) между шестью городами представлены в таблице 1.

Таблица 1 – Условие задачи

В ходе выполнения курсового проекта требуется написать программу, выполняющую решение аналогичных задач линейного программирования с помощью алгоритма Дейкстры.

Построим математическую модель:

n - число городов.

X_{i j} , i, j=1..N - матрица затрат, где C_{i j} - затраты на переход из i-го города в j-й.

X_{i j} - матрица переходов с компонентами:

X_{i j} = -1, если коммивояжер совершает переход из i-го города в j-й,

X_{i j} = 0, если не совершает перехода,

где i, j = 1..N и i≠j.

Критерий:

, (1)

где С_ij – матрица стоимости переходов,

X_ij – матрица переходов, где x_ij=0, если переход совершен и x_ij=1 в противном случае

Ограничения:

, i = 1..N (2)

, j = 1..N (3)

U_i - U_j + N ⋅ X_{i j} ≤ N-1, i, j = 1..N, i ≠ j. (4)

, k= 1..N,t=k-1 (5)

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель; условие (5) – принцип треугольника: ранее выбранный путь оказался длиннее предыдущего.

Разработка алгоритма. Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы. В данном курсовом проекте реализуется задача коммивояжера методом алгоритма Дейкстры.

В 1959 г. Голландский математик Дейкстра предложил алгоритм, который решает задачу коммивояжёра для любой матрицы исходный данных: симметричной, несимметричный и смешанной (отсутствуют некоторые ребра графа).

Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов и вернуться обратно в исходный город, при этом выполняя две проверки:

1. Длина найденного ребра графа должна быть меньше или равна симметричному ребру графа. В противном случае выбирается симметричное ребро
2. треугольника: ранее выбранный путь оказался длиннее предыдущего.

Представим разработанный код.

Код программы «Решение задачи коммивояжера с помощью алгоритма Дейкстры».

//

#include <vcl.h>

#include <tchar.h>

#include <stdio.h>

#include <conio.h>

//

void main()

{

int c2,c3,i,k,j,n,e,q,v,m,z,x,min,a,min2,h=0,c=0;

printf("Koli4estvo gorodov : ");scanf("%i",&n); //ввод количество городов

int *t=new int[n];

int *t2=new int[n];

int **kg=new int*[n];

for(i=0;i<n;i++)

kg[i]=new int[n];

int **kg1=new int*[n];

for(i=0;i<n;i++)

kg1[i]=new int[n];

for(i=0;i<n;i++)

for(j=0;j<n;j++)

kg[i][j]=0;

for(i=0;i<n;i++) //заполнение расстояние между городами

for(j=i+1;j<n;j++)

{

printf("vedite racto9nnie %i do %i: ",i+1,j+1);

scanf("%i",&kg[i][j]);

kg1[i][j]=kg[i][j];

}

clrscr();

printf(" ");

for(i=0;i<n;i++)

printf("%3i",i+1);

printf("\n\n\n\n");

for(i=0;i<n;i++) // заполнение массива городов симметрично

{

printf("%2i ",i+1);

for(j=0;j<n;j++)

{

kg[j][i]=kg[i][j];

kg1[j][i]=kg[i][j];

printf("%3i",kg[i][j]);

}

printf("\n\n");

}

printf("Vvedite na4al'nuy to4ky : ");scanf("%i",&k); //ввод с какого города гачгётся путь

k--;

e=k;x=k;

q=1;c2=0;

v=0;z=2;

t[0]=k;

do //поиск минимального пути между городами

{

min=99999;

for(j=x+1;j<n;j++)

if(min>=kg[x][j] && kg1[x][j]!=-1)

{

min=kg[x][j];

m=j;

}

for(j=0;j<x;j++)

if(min>kg[j][x] && kg1[j][x]!=-1)

{

min=kg[j][x];

m=j;

}

t2[q]=x;

t[q]=m;

for(j=x+1;j<n;j++)

kg1[x][j]=-1;

for(j=0;j<x;j++)

kg1[j][x]=-1;

x=m;

z=0;

for(i=0;i<n && z!=1;i++)

for(j=i+1;j<n;j++)

if(kg1[i][j]==-1)

v=1;

else

{v=3;z=1;break;}

q++;

}

while(v!=1);

t2[q]=x;t[q]=k;q++;v=q;z=0;q=0;c=0;c2=0;e=0;

do // проверка условий алгоритма Дейкстры

{

if(q!=0)

{ c=c+kg[t2[e]][t[q]];

c2=c-kg[t2[e-1]][t[q-1]]-kg[t2[e]][t[q]]+kg[t[q]][t[q-1]]+kg[t2[e-1]][t[q]];}

if(c>c2 && q!=0 && z<q)

{

z=t2[e];

t2[e]=t2[e-1];

t2[e-1]=z;

z=t[q-1];

t[q-1]=t[q-2];

t[q-2]=z;

z=q;

q=-1;e=-1;c=0;c2=0;

}

q++;

e++;

}

while(v!=q);

printf("\n\nput : %i",t[0]+1); //вывод пути

for(i=1;i<q;i++)

printf("-%i",t[i]+1);

printf("\n\n");

printf("dlina puti : %i",c);//вывод длинны пути

getch();

}

Описание программы.

Для начала вычислений необходимо ввести количество городов.

На рисунке 2 показан этап выбора количества городов.