Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
#1

Попасть из одной точки двумерного массива в другую

21.12.2015, 15:02. Просмотров 827. Ответов 21

Создать вектор, в котором генерируются вектора разной длинны (аналог ступенчатого массива), и заполняются случайными значениями. Затем по принципу жадного алгоритма организовать поиск кратчайшего пути от одного значения к другому. Двигаться можно в любую сторону, но если пути от одного вектора к другому нету (например первый короче второго), то двигаться нельзя.Значения, по которым шли - просуммировать.
Пример :

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Миниатюры
Попасть из одной точки двумерного массива в другую  
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2015, 15:02
Ответы с готовыми решениями:

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

Количество путей из одной точки в другую
Доброго времени суток. Есть такая задачка: дана матрица, состоящая из нулей...

Переход с одной строки массива на другую
проблема собственно в том что с первой строки массива цикл не переходит на...

Перенос динамического массива из одной функции в другую
Всем привет, задача отдельными функция реализовать заполнение и вывод массива...

Передача элементов массива из одной функции в другую
Подскажите пожалуйста, хочу написать тест проверки знаний, генерацию случайных...

21
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
21.12.2015, 15:36  [ТС] #2
вот что у меня получилось для одномерного массива :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int r = 1;
 
 vector<int> v;
 for(int i=0;i<r*rand()%10;i++)
     v.push_back(rand()%15);
 vector<int>::iterator beg=v.begin();
 vector<int>::iterator end=v.end();
 while(beg!=end)
     cout<< *(beg++)<<' ';
 cout<<endl;
 system("pause");
 return 0;
}
0
Миниатюры
Попасть из одной точки двумерного массива в другую  
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
21.12.2015, 15:41 #3
C++
1
for(int i=0;i<r*rand()%10;i++)
МихаилЗеленски, мммммм. Отложите это задание и начните с простых. Жадный алгоритм не для вас - учитывая ваши знания
0
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
21.12.2015, 16:01  [ТС] #4
я в курсе, что мои знания в области программирования оставляют желать лучшего, поэтому и обратился сюда за помощью. попытался сделать что смог. и я в курсе, что такое "жадный алгоритм", в моём коде он и близко не раализовывается
0
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
21.12.2015, 16:05 #5
МихаилЗеленски, ну так напишите ступенчетые массивы на С++, а я вам переведу на STL потом. Сейчас я вижу, что вы хотите взяться за тему которая еще рано вам.

Как будут массивы - напишете уже потом алгоритм поиска
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
21.12.2015, 16:08 #6
это динамикой решается а не жадным
0
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
21.12.2015, 16:11  [ТС] #7
Хорошо, сейчас попробую. Прошу прощение за грубость, но сейчас просто сессия, надо сдаваться, а скилл почти на нуле...)) сейчас попробую что-то сделать

Добавлено через 1 минуту
Преподаватель сказал , цитирую : "реализовать переход из одной точки массива векторов в другую (пример - жадный алгоритм).". Но возможно Вы правы.
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
21.12.2015, 16:19 #8
тут даже динамика ыидать не поможет ,думаю всю эту ерунду как граф надо представить ,и пройтись флойдом или дейкстрой в зависимость от значений
0
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
21.12.2015, 16:47 #9
Dimension, жадный алгоритм это тема, реализацию которой хочет увидить преподаватель. Зачем другие алгоритмы решения - если задание ( "ТЗ" ) чёткое более-менее.
1
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
21.12.2015, 18:58 #10
1. Двигаемся вверх до конечной строки, пока можем (в этом смысле алгоритм "жадный"). Если не можем, шаг влево и п1.
2. Двигается по строке в нужную точку.
0
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
22.12.2015, 07:48  [ТС] #11
Окей, я честно попробовал решить эту задачу сам, но увы.... Я не могу понять, какова моя точка отсчёта, то есть как задавать условие стартового и финишного елементов. вот алгоритм для создания ступенчатого массива:
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
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int const n=10;
    //vector<int> SumVec; по идее это должен быть вектор в который мы записываем значения, по которым прошли. 
    vector<vector<int> > MainVec(n); 
    cout<<"Our matrix"<<endl;
    for (int i=0;i<n;cout<<endl,++i) 
    { 
        int m=rand()%10+4; 
        for(int j=0;j<m;cout<<"  ",++j)
        {
            MainVec[i].push_back(rand()%10);
            cout<<MainVec[i][j];
        }
    }
 
 
 
    system("pause");    
    return 0;
}
0
SatanaXIII
Супер-модератор
Эксперт С++
5768 / 2766 / 375
Регистрация: 01.11.2011
Сообщений: 6,725
Завершенные тесты: 1
22.12.2015, 10:28 #12
Цитата Сообщение от zer0mail Посмотреть сообщение
1. Двигаемся вверх до конечной строки, пока можем (в этом смысле алгоритм "жадный"). Если не можем, шаг влево и п1.
2. Двигается по строке в нужную точку.
И в самой верхней строке получится такая большая загибулина вправо.

Надо составить двумерный массив по длине векторов и обычной дейкстрой его пройтись.
0
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
24.12.2015, 11:41 #13
Лучший ответ Сообщение было отмечено МихаилЗеленски как решение

Решение

МихаилЗеленски,
Внимание! Код не дописанный - писал пока не заскучаю - написал 188 строк и понял, что надо и ТСу хоть что-то оставить.

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <iostream>
#include <vector>
 
using namespace std;
 
//////////////////////////////////////////////////////////////////////////
 
struct Index
{
   static const Index INVALID_INDEX;
   int _x;
   int _y;   
   Index( const int x, const int y );
   Index( const Index& copy );
   bool operator==( const Index& right ) const;
   Index operator+( const Index& right ) const;
};
 
const Index Index::INVALID_INDEX = {-1,-1};
 
//////////////////////////////////////////////////////////////////////////
 
Index::Index( const int x, const int y )
{
   _x = x;
   _y = y;
}
Index::Index( const Index& copy )
{
   _x = copy._x;
   _y = copy._y;
}
bool Index::operator==( const Index& right ) const
{
   return _x == right._x && _y == right._y;
}
Index Index::operator+( const Index& right ) const
{
   Index result( *this );
   result._x += right._x;
   result._y += right._y;
   return result;
}
 
//////////////////////////////////////////////////////////////////////////
 
class Field
{
public:
   typedef vector<Index>                     IndexArray;
 
private:
   vector<vector<int>>                       m_field;
 
   //recursiveVariables
   IndexArray                                m_bestWay;
 
 
   bool                                      isCorrectIndex( const Index& index );
   void                                      recursiveSeach( const Index& from, const Index& to, IndexArray& way );
 
 
public:
   Field();
 
   IndexArray                                getWayFromTo( const Index& from, const Index& to );
   void                                      show();
};
 
//////////////////////////////////////////////////////////////////////////
 
 
Field::Field()
{
   const int n = 10;
   m_field.resize( n );
   for(int i = 0; i < n; ++i)
   {
      int m = rand() % 10 + 4;
      for(int j = 0; j < m; ++j)
      {
         m_field[i].push_back( rand() % 10 );        
      }
   }
 
}
bool Field::isCorrectIndex( const Index& index )
{
   bool result = true;
 
   const int& y = index._y;
   const int& x = index._x;
 
   if(m_field.size() < y && y >= 0 && !m_field.empty())
   {
      if(m_field[y].size() < x && x >= 0 && !m_field[y].empty())
      {
         result = true;
      }
      else
         result = false;
   }
   else
      result = false;
   return true;
}
 
 
void Field::recursiveSeach( const Index& from, const Index& to, IndexArray& way )
{
   if(!isCorrectIndex( from ) || !isCorrectIndex( to ))
       return;     // incorrect parametrs
   
 
 
   //////////////////////////////////////////////////////////////////////////
   // recuirsive end
   //////////////////////////////////////////////////////////////////////////
   if(from == to)
   {
      if(!m_bestWay.empty())
      {
         if(m_bestWay.size() > way.size())
         {
            m_bestWay = way;
         }
      }
      else
         m_bestWay = way;
   }
   //////////////////////////////////////////////////////////////////////////
   // recuirsive call
   //////////////////////////////////////////////////////////////////////////
   else
   {
      way.push_back( from );
 
      recursiveSeach( from + Index(-1,0), to, way );
      recursiveSeach( from + Index(+1,0), to, way );
      recursiveSeach( from + Index(0,-1), to, way );
      recursiveSeach( from + Index(0,+1), to, way );
 
   }
}
 
Field::IndexArray Field::getWayFromTo( const Index& from, const Index& to )
{
   IndexArray result;
 
   // algorithm
   if(isCorrectIndex( from ))
   {
      if(isCorrectIndex( to ))
      {
 
      }
      else
         result.push_back( Index::INVALID_INDEX );
   }
   else
      result.push_back( Index::INVALID_INDEX );
 
   return result;
}
 
void Field::show()
{
   for(auto& it : m_field)
   {
      for(auto& q : it)
      {
         cout << q << " ";
      }
      cout << endl;
   }
}
 
//////////////////////////////////////////////////////////////////////////
 
int main()
{
   Field a;
 
   a.show();
 
   system( "pause" );
   return 0;
}
1
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
24.12.2015, 15:34 #14
Цитата Сообщение от SatanaXIII Посмотреть сообщение
И в самой верхней строке получится такая большая загибулина вправо.
Или влево. И чё - это как-то противоречит условию задачи? Или есть путь с меньшим количеством шагов?
Нет и нет. Тогда в чем проблема?
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
24.12.2015, 15:45 #15
Цитата Сообщение от zer0mail Посмотреть сообщение
Или есть путь с меньшим количеством шагов
кто вам сказал что нужно кол-во шагов считать ,а не их стоимость
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
24.12.2015, 15:52 #16
Цитата Сообщение от Dimension Посмотреть сообщение
кто вам сказал что нужно кол-во шагов считать ,а не их стоимость
Никто, но и про минимальную стоимость ничего не было. Я предложил простой алгоритм, решающий поставленную задачу, к чему было замечание про "загибулину"?
0
SatanaXIII
Супер-модератор
Эксперт С++
5768 / 2766 / 375
Регистрация: 01.11.2011
Сообщений: 6,725
Завершенные тесты: 1
24.12.2015, 16:09 #17
Цитата Сообщение от zer0mail Посмотреть сообщение
это как-то противоречит условию задачи?
Да. Там на картинке показано.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
24.12.2015, 16:11 #18
Я никакого противоречия не вижу.
0
cyber-satyr
393 / 164 / 32
Регистрация: 10.12.2015
Сообщений: 717
24.12.2015, 16:14 #19
Цитата Сообщение от SatanaXIII Посмотреть сообщение
обычным дейкстрой его пройтись
fix
0
МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
Завершенные тесты: 1
24.12.2015, 22:37  [ТС] #20
Спасибо большое) А ТС это кто?)
0
24.12.2015, 22:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2015, 22:37

Разделить строку двумерного массива на другую строку этого массива
Есть вот такой код, но в самом конце он не делит строки Не могу понять почему...

Передача размерности массива как параметр из одной функции в другую.
Вообщем написал программу. Всё работает как надо, кроме одного, никак не могу...

Передача массива из одной функции в другую, и сложение его элементов.
Здравствуйте, задание: Создать две функции для работы с массивом: ...


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

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

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