Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
I94
0 / 0 / 0
Регистрация: 10.05.2013
Сообщений: 32
1

Динамическое программирование

21.11.2015, 21:54. Просмотров 565. Ответов 4
Метки нет (Все метки)

Помогите решить задачу! Я что-то особо не соображу...
1.Написать программу, реализующую действия:
а. сформировать ленточную матрицу заданного размера,
б. заполнить её случайными числами с учетом ограничений,
в. определить кратчайший маршрут из первой вершины в последнюю.
2.Нарисовать фрагмент сети, описываемый полученной матрицей.


Число вершин: 11, Ограничения: 1 связан с 2 и 3, лента шириной 7
Распределение: Равномерное
Дуги: Несимм.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2015, 21:54
Ответы с готовыми решениями:

Динамическое программирование
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один...

динамическое программирование
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в...

Динамическое программирование
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда...

Динамическое программирование
очень нужна реализация(завтра дедлайн) Будем называть натуральное число...

Динамическое программирование
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник...

4
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
21.11.2015, 22:05 2
C++
1
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
0
I94
0 / 0 / 0
Регистрация: 10.05.2013
Сообщений: 32
22.11.2015, 11:27  [ТС] 3
И куда это встраивать в код?)
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
22.11.2015, 11:34 4
я пока никакого кода от вас не вижу
0
I94
0 / 0 / 0
Регистрация: 10.05.2013
Сообщений: 32
22.11.2015, 11:37  [ТС] 5
Вообще, для этой задачи нужно было взять матрицу из моего предыдущего кода, только преобразовать ее в ленточную
C++
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <math.h>
#include <iomanip>
#include <ctime> 
#include <windows.h>
using std::cout;
using std::cin;
using std::endl;
    
char NEWT[256];
char*RUS(char*TEXT) {
CharToOem(TEXT,NEWT);
return NEWT;}
 
int v;
 
int main()
{   int i=0,j=0;
const int n=9, m=9;
 
   int infinity=1000;                     // Бесконечность
int VES[n][m];                         // Матрица весов графа                                          // Количество вершин в графе
   void randomize();
   srand((unsigned)time(NULL));
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(i==j)
            VES[i][j] = 0;
            else
            VES[i][j] = rand() % 10; // Каждый элемент случайному числу от 0 до 9
            VES[0][4]=5;
            VES[4][0]=5;
            if ((i==0 && j==4)!=0)
                VES[0][0]=0;
                VES[0][1]=0;
                VES[0][2]=0;
                VES[0][3]=0;
                VES[0][4]=0;
                VES[0][7]=0;
                VES[1][0]=0;
                VES[2][0]=0;
                VES[3][0]=0;
                VES[4][0]=0;
                VES[7][0]=0;
        
            cout << VES[i][j] << " "; // Вывести элементы на консольку
             
        }
        cout << endl;
    } 
    
 
   int x[100];                            //Массив, содержащий единицы и нули для каждой вершины,
                                          // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                                          // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   
   int DlinaPuti[100];                    //t[i] - длина кратчайшего пути от вершины s в i
 
   int PredVertex[100];                   //h[i] - вершина, предшествующая i-й вершине
                                          //на кратчайшем пути
   int VERTEX;
   int p;       
 
//cout<<RUS("Ввести количество вершин в графе ")<<endl;
//cin>>VERTEX; 
p= VERTEX=9;                    //Число вершин в графе
//cout<<RUS("Заполните матрицу весов графа ")<<endl;      // Матрица весов графа
//cout<<"    ";
 
 
 
 
                                        // Будем искать путь из вершины s в вершину g по циклу
   int start;                           // Номер исходной вершины
   int end;                             // Номер конечной вершины
N: cout<<RUS("Введите стартовую вершину: ");    // Номер может изменяться от 0 до p-1
   cin>>start;
   if (start>(p-1) && start<0) 
   {cout<<RUS("Нет такой вершины повторите ввод...")<<endl; goto N; } // на случай неверных данных
   start=start-1;                       //так как массив начинается с 0 отнимаем от вводимой цифры 1
   for (int prosto=0;prosto<VERTEX;prosto++)
   {end=prosto;                         //цикл прогоняет алгоритм Флойда p-ое количество раз преврашая его в алгоритм Дейкстры  
   if (end==start) continue;            //исключаем просчет растояния между одной и той же точкой
   else
   {
 
                                         // Инициализируем начальные значения массивов
   int u;                                // Счетчик вершин
   for (u=0;u<p;u++)
   {
       DlinaPuti[u]=infinity;                    //Сначала все кратчайшие пути из s в i 
                                         //равны бесконечности
      x[u]=0;                            // и нет кратчайшего пути ни для одной вершины
   }
   PredVertex[start]=0;                     // s - начало пути, поэтому этой вершине ничего не предшествует
   DlinaPuti[start]=0;                      // Кратчайший путь из s в s равен 0
   x[start]=1;                              // Для вершины s найден кратчайший путь
   v=start;                                 // Делаем s текущей вершиной
   
   while(1)
   {
                                        // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(VES[v][u]==0)continue;      // Вершины u и v несмежные
         if(x[u]==0 && DlinaPuti[u]>DlinaPuti[v]+VES[v][u]) //Если для вершины 'u' еще не 
                                        //найден кратчайший путь
                                        // и новый путь в 'u' короче чем 
                                        //старый, то
         {
            DlinaPuti[u]=DlinaPuti[v]+VES[v][u];            //запоминаем более короткую длину пути в
                                                     //массив t[и]
           PredVertex[u]=v;                     //запоминаем, что v->u часть кратчайшего  пути из s->u
                                       
         }
      }
 
                                         // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;                   // Для поиска самого короткого пути
      v=-1;                             // В конце поиска v - вершина, в которую будет 
                                        // найден новый кратчайший путь. Она станет 
                                        // текущей вершиной
    
      for(u=0;u<p;u++)                  // Перебираем все вершины.
      {
         if(x[u]==0 && DlinaPuti[u]<w)           // Если для вершины не найден кратчайший 
                                         // путь и если длина пути в вершину 'u' меньше
                                         // уже найденной, то
         { 
             v=u; // текущей вершиной становится 'u'-я вершина
                       w= DlinaPuti[u];
 
                       cout<< RUS("Пройден вес: ")<<DlinaPuti[u]<<endl;
         }
      }
      if(v==-1)
      {
         cout<<RUS("Нет пути из вершины ")<<start+1;cout<<RUS(" в вершину ")<<end+1<<"."<<endl;
         break;
      }
      if(v==end)                            // Найден кратчайший путь,
      {                                 // выводим его
         cout<<RUS("\nКратчайший путь из вершины ")<<start+1;
         cout<<RUS(" в вершину ")<<end+1<<":";
       u=end;
       while(u!=start)
         {
            cout<<" "<<u+1;
            u=PredVertex[u];
         }
         cout<<" "<<start+1<<RUS(". Длина пути - ")<< DlinaPuti[end];cout<<endl;
       break;
      }
      x[v]=1;
   }}}
   _getch();
return 0;}
0
22.11.2015, 11:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2015, 11:37

Динамическое программирование
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить...

Динамическое программирование
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У...

Динамическое программирование
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru