Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 11.06.2014
Сообщений: 19

Определить кратчайший путь от начальной вершины к конечной

19.04.2015, 12:57. Показов 1193. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
определить кратчайший путь от начальной вершины к конечной. заполнить ленточную матрицу шириной 3, нормальное распределение. у меня 8 вершин, 1 вершина связана со 2 и 3. Матрица симметричная.
код есть только ничего не понимаю что к чему
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
uses crt;
const 
n=7;       {число вершин, размерность массива}
sh=3;      {ширина ленты}
masmin=0;  {минимум и максимум заполнения массива. Тут - от нуля до 100}
masmax=100; 
v1=3;      {это не трогайте}
v2=2; 
const veeery_large_number=99998; {o.O} {любое большое число. Пожалуйста, измените название этой переменной. Я вас очень прошу. Сразу, как только возьмёте мой код.}
 
var a:array[1..n,1..n] of real; {исходный массив}
i,j,npp, temp1, temp2:integer; 
pr:array[1..300] of real;       {массив путей по расстоянию}
pp:array[1..300] of real;       {массив самих путей в формате нулей и единиц, где единица означает, что через эту вершину проходим}
minrast:real;
 
function pow(xx:integer;yy:integer):real; {xx в степени yy}
var ii:integer;
qwe:real;
begin
qwe:=xx;
for ii:=2 to yy do
    qwe:=qwe*xx;
pow:=qwe;
end;
 
function normrasp(a,b:integer):real; {нормальное распределение}
var xxx:real;
bbb:boolean;
const maxnr=0.39894228;
begin
bbb:=false;
while (not bbb) do
begin                 
     xxx:=(random(600)/100)-3;
     if (random(100)<( (100*(exp(-xxx*xxx/2))/sqrt(2*pi))/maxnr )) then
        bbb:=true;
end;
normrasp:=a+(b-a)*(xxx+3)/6;
end;
 
function obrez:integer;  {функция, которая определяет, до куда надо заполнять "ленту" в данной строке, потому что лента на последних строчках "обрезается" как бы}
begin
if ((n-i)>=sh) then 
   obrez:=i+sh
else
   obrez:=n;
end;
///////////////////////////////////////////////////////////// 
function rf(af,bf:integer; r,p:real):real;     {реекууурсииияяяяяя!!!}
var min,x:real; jj:integer;
begin
if (a[af,bf]>0) then 
begin
     inc(npp);
     pp[npp]:=p;
     pr[npp]:=r+a[af,bf];
     min:=a[af,bf]+r;
end
else
    min:=veeery_large_number;
for jj:=1 to n do
    if ((a[af,jj]>0) and (jj<>af) and (jj<>bf)) then
    begin
         x:=rf(jj,bf,a[af,jj]+r,p+pow(10,jj)); {рекурсирует себя полностью!!!} 
         if (x<min) then 
            min:=x;
    end; 
rf:=min;     
end; 
////////////////////////////////////////////////////////////            
begin
randomize;
clrscr;
for i:=2 to n-1 do
    for j:=i+1 to obrez do
        a[i,j]:=normrasp(masmin,masmax);
a[1,2]:=normrasp(masmin,masmax);  {ваши начальные условия!!! У меня 1 связана с 2 и 3}
a[1,3]:=normrasp(masmin,masmax);
 
for i:=1 to n do
begin
write(i,':');
    for j:=1 to n do
        if (j<n) then
           if (a[i,j]<10) then 
              write(' ', a[i,j]:v1:v2,' ') 
           else 
              write(a[i,j]:v1:v2,' ') 
        else
              if (a[i,j]<10) then 
              writeln(' ', a[i,j]:v1:v2,' ') 
           else 
              writeln(a[i,j]:v1:v2,' '); 
end;
{-------------------------------------------------}         
npp:=0;
minrast:=rf(1,n,0,10+pow(10,n));      {после этой одной строчки всё уже будет готово. Вызываем рекурсию от первой до крайней вершины, с текушем пройденным путём ноль и текущими пройдеными вершинами первой и крайней}     
writeln(minrast:v1:v2);
for i:=1 to npp do
    if (pr[i]=minrast) then
    begin
       temp2:=0;
       while (pp[i]>0) do
       begin 
            temp1:=round(pp[i]) mod 10;    {проверяем, через какие вершины проходили - у этих вершин на соответствующих местах в pp[i] будет единица (pp[i] - это число!!! Например, для пути 1>3>6 это будет: 1001010, в конце всегда ноль.)}
            if (temp1>0) then 
               write(temp2,'>');
            inc(temp2);
            pp[i]:=round(pp[i]) div 10;
       end; 
       writeln('!');   {это можете заменить на какое-нибудь "Приеехалиии!"}
    end;         
readln;
end.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
19.04.2015, 12:57
Ответы с готовыми решениями:

Найти кратчайший путь из вершины u в вершину v
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Алгоритм Дейкстры - Найти кратчайший путь от 1 вершины
Вот рисунок по которому нада найти кратчайший путь от 1 вершины помагите плизз

Программа, способная отвечать на запросы и возвращать кратчайший путь до заданной вершины
Всем доброго времени суток! помогите пожалуйста реализовать код на Haskell &quot;программа, способная отвечать на запросы и возвращать...

1
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8652 / 4487 / 1669
Регистрация: 01.02.2015
Сообщений: 13,895
Записей в блоге: 12
19.04.2015, 18:36
Много теории в ответе не наберёшь. Поэтому отвечу ссылками.
1. Ленточная матрица. Массив хранения ленточной матрицы.
2. Поиск кратчайшего пути в тексте похож на рекурсивную реализацию поиска в глубину (dfs) [1], [2] с запоминанием лучшего варианта.

Всё остальное - каким местом здесь гауссово распределение, что такое obrez и т.п. - к автору программы, методичке, преподавателю или к сокурсникам. Очень уж самобытные названия переменных и процедур.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
19.04.2015, 18:36
Помогаю со студенческими работами здесь

Название рейса определить по кодам начальной и конечной остановок
Информационная система &quot;Междугороднее автобусное сообщение&quot;. Исходные данные хранятся в 3таблицах, имеющих следующую структуру: 1) код...

Кратчайший путь из одной вершины в другую с условием, что двигаться можно только прямо и вправо
Условие Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира,...

Определить разность потенциалов начальной и конечной точек пути электрона в электрическом поле.
Определить разность потенциалов начальной и конечной точек пути электрона в электрическом поле, если его скорость увеличилась от 10^6 до...

Алгоритм Дейкстры -определить кратчайший путь
Пожарной службе необходимо определить кратчайший путь от гаража (пункт А) до нефтеперерабатывающего завода (пункт В) по данным в...

Определить кратчайший путь между вершинами
Для графа считанного из фала определить кратчайший путь между вершинами, заданными в режиме диалога. Изучить и использовать алгоритм...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru