Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
 Аватар для МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95

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

21.12.2015, 15:02. Показов 3109. Ответов 21

Студворк — интернет-сервис помощи студентам
Создать вектор, в котором генерируются вектора разной длинны (аналог ступенчатого массива), и заполняются случайными значениями. Затем по принципу жадного алгоритма организовать поиск кратчайшего пути от одного значения к другому. Двигаться можно в любую сторону, но если пути от одного вектора к другому нету (например первый короче второго), то двигаться нельзя.Значения, по которым шли - просуммировать.
Пример :
Миниатюры
Попасть из одной точки двумерного массива в другую  
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
21.12.2015, 15:02
Ответы с готовыми решениями:

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

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

Лабиринт задан в виде матрицы.Определить, можно ли из одной точки попасть в другую
Лабиринт задан в виде матрицы размером n на m. Стенам лабиринта соответствуют единицы, проходам - нули. Определить, можно ли из точки с...

21
 Аватар для МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
21.12.2015, 15:36  [ТС]
вот что у меня получилось для одномерного массива :
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
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.12.2015, 15:41
C++
1
for(int i=0;i<r*rand()%10;i++)
МихаилЗеленски, мммммм. Отложите это задание и начните с простых. Жадный алгоритм не для вас - учитывая ваши знания
0
 Аватар для МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
21.12.2015, 16:01  [ТС]
я в курсе, что мои знания в области программирования оставляют желать лучшего, поэтому и обратился сюда за помощью. попытался сделать что смог. и я в курсе, что такое "жадный алгоритм", в моём коде он и близко не раализовывается
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.12.2015, 16:05
МихаилЗеленски, ну так напишите ступенчетые массивы на С++, а я вам переведу на STL потом. Сейчас я вижу, что вы хотите взяться за тему которая еще рано вам.

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

Добавлено через 1 минуту
Преподаватель сказал , цитирую : "реализовать переход из одной точки массива векторов в другую (пример - жадный алгоритм).". Но возможно Вы правы.
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
21.12.2015, 16:19
тут даже динамика ыидать не поможет ,думаю всю эту ерунду как граф надо представить ,и пройтись флойдом или дейкстрой в зависимость от значений
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.12.2015, 16:47
Dimension, жадный алгоритм это тема, реализацию которой хочет увидить преподаватель. Зачем другие алгоритмы решения - если задание ( "ТЗ" ) чёткое более-менее.
1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
21.12.2015, 18:58
1. Двигаемся вверх до конечной строки, пока можем (в этом смысле алгоритм "жадный"). Если не можем, шаг влево и п1.
2. Двигается по строке в нужную точку.
0
 Аватар для МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
22.12.2015, 07:48  [ТС]
Окей, я честно попробовал решить эту задачу сам, но увы.... Я не могу понять, какова моя точка отсчёта, то есть как задавать условие стартового и финишного елементов. вот алгоритм для создания ступенчатого массива:
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
5851 / 2862 / 392
Регистрация: 01.11.2011
Сообщений: 6,906
22.12.2015, 10:28
Цитата Сообщение от zer0mail Посмотреть сообщение
1. Двигаемся вверх до конечной строки, пока можем (в этом смысле алгоритм "жадный"). Если не можем, шаг влево и п1.
2. Двигается по строке в нужную точку.
И в самой верхней строке получится такая большая загибулина вправо.

Надо составить двумерный массив по длине векторов и обычной дейкстрой его пройтись.
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
24.12.2015, 11:41
Лучший ответ Сообщение было отмечено МихаилЗеленски как решение

Решение

МихаилЗеленски,
Внимание! Код не дописанный - писал пока не заскучаю - написал 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
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
24.12.2015, 15:34
Цитата Сообщение от SatanaXIII Посмотреть сообщение
И в самой верхней строке получится такая большая загибулина вправо.
Или влево. И чё - это как-то противоречит условию задачи? Или есть путь с меньшим количеством шагов?
Нет и нет. Тогда в чем проблема?
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
24.12.2015, 15:45
Цитата Сообщение от zer0mail Посмотреть сообщение
Или есть путь с меньшим количеством шагов
кто вам сказал что нужно кол-во шагов считать ,а не их стоимость
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
24.12.2015, 15:52
Цитата Сообщение от Dimension Посмотреть сообщение
кто вам сказал что нужно кол-во шагов считать ,а не их стоимость
Никто, но и про минимальную стоимость ничего не было. Я предложил простой алгоритм, решающий поставленную задачу, к чему было замечание про "загибулину"?
0
Почетный модератор
Эксперт С++
 Аватар для SatanaXIII
5851 / 2862 / 392
Регистрация: 01.11.2011
Сообщений: 6,906
24.12.2015, 16:09
Цитата Сообщение от zer0mail Посмотреть сообщение
это как-то противоречит условию задачи?
Да. Там на картинке показано.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
24.12.2015, 16:11
Я никакого противоречия не вижу.
0
393 / 165 / 32
Регистрация: 10.12.2015
Сообщений: 717
24.12.2015, 16:14
Цитата Сообщение от SatanaXIII Посмотреть сообщение
обычным дейкстрой его пройтись
fix
0
 Аватар для МихаилЗеленски
1 / 1 / 2
Регистрация: 14.10.2015
Сообщений: 95
24.12.2015, 22:37  [ТС]
Спасибо большое) А ТС это кто?)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
24.12.2015, 22:37
Помогаю со студенческими работами здесь

Как попасть из одной сети в другую под определённым ip?
Есть такой вопрос: Дано: Сетевуха eth0 ip-172.17.8.217 vpnc tun0 ip-dynamical 192.168.10.ххх uname -a Centos 5.5 через...

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

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

Доступ из одной сети в другую от точки А до точки Б без шлюза в точке Б
Здравствуйте уважаемые профессионалы! В сетях не силен поэтому спрашиваю, сильно не ругайте) Вопрос в следующем! Есть сеть комп...

Выведите информацию о минимальном количестве пересадок в метрополитене, чтобы попасть с одной линии на другую
В текстовом файле хранится информация о линиях метрополитена в формате &lt;название линии&gt;|&lt;название линии, на которую есть...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru