Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.82
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
#1

Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут.... - C++

22.07.2010, 04:46. Просмотров 4333. Ответов 30
Метки нет (Все метки)

Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, который позволил бы посетить их все по одному разу. Построить графическое изображение маршрута?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2010, 04:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут.... (C++):

Проложить если возможно маршрут между противолежащими углами - C++
Практическое задание: 9. Двумерный квадратный массив заполнен нулями и единицами. Проложить если возможно маршрут между противолежащими...

Кратчайший маршрут - C++
Очень сложная задачка на мой взгляд. Подскажите хотя-бы алгоритм! Буду очень благодарен.

Найти кратчайший маршрут - C++
Найти кратчайший маршрут, который начинается и завершается в заданной вершине ориентированному графу, проходя через все его вершины...

Найти число точек и сумму расстояний от первой точки до остальных точек - C++
Вектора X и Y задаются вводом; n — размер каждого из векторов X и Y. Пара (Xk, Yk) представляет координаты одной из n точек на...

Отпечатать расстояния от начала координат для тех точек,которые принадлежат кругу с заданным радиусом, и число таких точек. - C++
1)Значение f(k) заключено между значениями t1= -a - √(b+m), t2=√(a+b+m),но не равно нулю. 2)Дана матрица из 2 столбцов и 10 строк.Первый...

Подсчитать количество точек, которые находятся в кругу радиусом R с центром в начале координат. Координаты точек заданы массивами X (100), Y (100) - C++
Подсчитать количество точек, которые находятся в кругу радиусом R с центром в начале координат. Координаты точек заданы массивами X (100),...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
22.07.2010, 06:16 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от SergProgC++ Посмотреть сообщение
Построить графическое изображение маршрута?
Построй
4
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.07.2010, 21:22 #3
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
/////////////////////////////////////////////////////////////////////////////
//Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, 
//который позволил бы посетить их все по одному разу.
/////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <numeric>
#include <vector>
 
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef T_coord                T_dist;
typedef T_point                T_shift;
typedef std::vector<T_shift>   T_shifts;
/////////////////////////////////////////////////////////////////////////////
struct T_numbered_point : T_point
{
    //-----------------------------------------------------------------------
    int  num_;
    //-----------------------------------------------------------------------
    T_numbered_point
        (
            T_point  point,
            int      num           
        ) 
        : T_point(point), 
          num_   (num)
    {}
    //-----------------------------------------------------------------------
    T_shift operator- (const T_numbered_point&  np)//Для алгоритма std::adjacent_difference
    {        
        return T_point(*this) - np;                
    }
    //-----------------------------------------------------------------------        
    bool operator < (const T_numbered_point&  np)//Для алгоритма  std::next_permutation.
    {
        return num_ < np.num_;
    }
    //-----------------------------------------------------------------------    
};
/////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_numbered_point>   T_numbered_points;
/////////////////////////////////////////////////////////////////////////////
T_numbered_points  input_numbered_points()
{
    const int  POINTS_TOTAL_MIN = 2;
    int        points_total;    
    do
    {
        std::cout << "Введите количество точек >= "
                  << POINTS_TOTAL_MIN   
                  << ": ";
        std::cin >> points_total;
    }while(points_total < POINTS_TOTAL_MIN);
    
    std::cout << "Введите координаты "
              << points_total
              << " различных точек:"
              << std::endl;
    
    T_numbered_points  numbered_points;
    
    while(   numbered_points.empty()
          || numbered_points.size() != points_total)
    {        
        int point_num = numbered_points.size() + 1;
        std::cout << "X" 
                  << point_num
                  << " = ";
        int x;
        std::cin >> x;
        std::cout << "Y" 
                  << point_num
                  << " = ";
        int y;
        std::cin >> y;                
        T_numbered_point  numbered_point(T_point(x, y), point_num);
        if( !numbered_points.empty()
            && std::find(numbered_points.begin(), 
                         numbered_points.end(), 
                         numbered_point) != numbered_points.end() )
        {
             std::cout << "Такая точка уже есть."
                       << std::endl;       
        }
        else
        {
            numbered_points.push_back(numbered_point);
        }
        std::cout << std::endl;
    }    
    return  numbered_points;
}
/////////////////////////////////////////////////////////////////////////////
void print_optim_posledov_obchoda(const T_numbered_points&  numbered_points)
{    
    T_numbered_points  temp_numbered_points(numbered_points);    
    T_shifts           shifts(numbered_points.size());
    T_numbered_points  numbered_points_v_optim_posledov;
    T_dist             dist_sum_min;
    bool               dist_sum_min_is_init = false;
    do
    {
        std::adjacent_difference(temp_numbered_points.begin(), 
                                 temp_numbered_points.end(), shifts.begin());
 
        struct T_dist_sum
        {
            T_dist operator() (const T_shift& p1, const T_shift& p2)
            {
                return abs(p1) + abs(p2);
            }
        };   
 
        T_dist  dist_sum = std::accumulate(shifts.begin() + 1, shifts.end(), 
                                           T_dist(), T_dist_sum());
        if(!dist_sum_min_is_init
           || dist_sum < dist_sum_min)
        {
            dist_sum_min                      = dist_sum;
            dist_sum_min_is_init              = true;
            numbered_points_v_optim_posledov  = temp_numbered_points;
        }
    }while
         ( 
             std::next_permutation
                 (
                     temp_numbered_points.begin() + 1, 
                     temp_numbered_points.end()                     
                 ) 
         );
 
    struct T_print_point_num
    {
        void operator() (T_numbered_points::value_type  numbered_point)
        {
            std::cout << numbered_point.num_
                      << ' ';
        }
    };
 
    std::cout << "Минимальный путь обхода "
              << numbered_points.size()
              << " заданных точек в последовательности "
              << std::endl;
    
    std::for_each(numbered_points_v_optim_posledov.begin(),
                  numbered_points_v_optim_posledov.end(), T_print_point_num());    
 
    std::cout << std::endl
              << "равен "
              << dist_sum_min
              << "."
              << std::endl;
}
/////////////////////////////////////////////////////////////////////////////
 
int main()
{    
    std::locale::global(std::locale(""));
    T_numbered_points  numbered_points = input_numbered_points();
    print_optim_posledov_obchoda(numbered_points);   
    return 0;
}
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
29.07.2010, 20:44  [ТС] #4
я не очень разбираюсь в стандартной библиотеке пока, объяснить можешь? че где да как делается? кстати почему у меня компилятор ошибки выдает проект както надо настраивать что ли
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
29.07.2010, 20:59 #5
Цитата Сообщение от SergProgC++ Посмотреть сообщение
... у меня компилятор ошибки выдает проект както надо настраивать что ли
Не знаю, у меня в Visual Studio нормально работает.
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
01.08.2010, 21:23  [ТС] #6
А используя стандартные динамические массивы это можно реализовать?
error C2918: 'T_dist_sum' : illegal use of local type in template instantiation
error C2780: '_Ty __cdecl std::accumulate(_II,_II,_Ty)' : expects 3 arguments - 4 provided
see declaration of 'accumulate'
error C2918: 'T_print_point_num' : illegal use of local type in template instantiation

вот какие ошибки, прокомментируй пожалусто код, если не трудно плизззз :-)

Добавлено через 5 минут
Вообщем я задаю количество точек и создаю два массива динамический для Y и X координат точек, нашел длинны между точками. А дальше не знаю чего делать. Без стандартной библиотеки можно это как нибудь решить. А и классы мы еще не проходили я их пока смутно понимаю:-(((
0
Crudelis
Шаровик затейник
674 / 416 / 13
Регистрация: 06.05.2010
Сообщений: 1,109
02.08.2010, 13:48 #7
Цитата Сообщение от SergProgC++ Посмотреть сообщение
классы мы еще не проходили
в приведенном коде нет классов, только структуры
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
02.08.2010, 15:10 #8
Цитата Сообщение от Crudelis Посмотреть сообщение
в приведенном коде нет классов, только структуры
А vector - уже не шаблонный класс?

Кстати, структуры С++ от классов отличаются только доступом по умолчанию.

Цитата Сообщение от SergProgC++ Посмотреть сообщение
А и классы мы еще не проходили я их пока смутно понимаю
Почитай литературу на эту тему, потом пригодится
1
Crudelis
Шаровик затейник
674 / 416 / 13
Регистрация: 06.05.2010
Сообщений: 1,109
02.08.2010, 16:16 #9
Цитата Сообщение от Nameless One Посмотреть сообщение
А vector - уже не шаблонный класс?
я изучаю с++ и до векторов не дошел к сожалению, не могу ничего сказать
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
02.08.2010, 21:38  [ТС] #10
Цитата Сообщение от Crudelis Посмотреть сообщение
я изучаю с++ и до векторов не дошел к сожалению, не могу ничего сказать
Вот и я не дошел :-). Но зато, изучая вопрос нашел что его можно решить с помощью алгоритма Дейкстера. Я написал пример, но чтобы не вводить данные использовал массивы заранее заданного размера на 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
#include <iostream.h>
#include <math.h>
 
 
const int KolT=5;//количество точек
///////////////////////////////////
void main()
{
    double X[]={1,2,3,4,5}, Y[]={1,1,1,1,1},//координаты точек
           MasDl[KolT][KolT],//массив для хранения матрицы длин
           DlToch[KolT],//массив куда копируются длины от текущей точки до всех остальных
           Dlin, Dt, 
           NToch[KolT];//массив хранящий последовательность номеров точек
    int j=0,i=0,k=0;
    unsigned long int Max;// бесконечно большое число
    bool IndT[KolT];// массив индикатор прошли точку 1 или нет 0
//////////////////показываем какие у нас координаты/////////////////
    cout << "Vvedennie coord:\n";
        for(i=0; i<KolT; i++)
        {
            cout <<"Tochka "<<i+1<<": X="<<X[i]<<"Y="<<Y[i]<<"\n";
            for (j=0;j<KolT;j++)
            {
            Dlin=sqrt(((X[i]-X[j])*(X[i]-X[j]))+((Y[i]-Y[j])*(Y[i]-Y[j])));//находим расстояния между точками
 
                if(Dlin!=0)// если не 0 записываем в массив матрицы длин
                {
                MasDl[i][j]=Dlin;
                }
                else // иначе приравниваем длинну к бесконечно большой
                {
                MasDl[i][j]=Max;
                }
 
            }
        }
        cout<<"\n";
/////////////////проверка матрицы длин///////////////
cout<<"Matrica Dlin megdu tochkami\n";
 
    for (i=0;i<KolT;i++)
    {
        for (j=0;j<KolT;j++)
        {
        
        cout << MasDl[i][j]<<"   ";
        }
    cout<<"\n";
    }
    cout<<"\n";
/////////////////проверка массива индикатора и обнуление его///////////////
    cout<<"Massiv Indikator"<<"\n";
    for (i=0;i<KolT;i++)
    {   
        IndT[i]=0;
        cout << IndT[i]<<" ";
    }
    cout<<"\n";
////////////////////////////////
////////////////подготовка данных////////////////
    for (i=0;i<KolT;i++)
    {
        NToch[i]=i;cout<<"Tochka:"<<NToch[i]<<" ";// номер  точки
        IndT[i]=0;cout<<"Ee indikator:"<<IndT[i]<<" ";//обнуление (еще раз ну это можно удалить)
        DlToch[i]=MasDl[i][0];cout<<"Perv znac:"<<DlToch[i]<<" \n";//первая длинна текущей точки
    }
////////////////Поиск кратчайшего пути////////////////
    NToch[0]=0;//задаем начало
    IndT[0]=1;
    Dt=Max;// минимальная длина делаем ее большой
    cout<< "Posled tochek:";
    for(i=0;i<(KolT-1);i++)
    {
        Dt=Max;
        for (j=0;j<KolT;j++)
        {
        if((IndT[j]==0)&&(Dt>DlToch[j]))// сравниваем и ищем минимальную длинну для точки
        {
            Dt=DlToch[j];
            k=j;//запоминаем близ лежащую точку
        }
 
        IndT[k]=1;// меняем индикатор длижней точки на пройденную
        if((IndT[j]==0)&&(DlToch[j]>(DlToch[k]+MasDl[k][j]))) //еще раз смотрим массив на наличие блжайшей точки и сравниваем расстояние уже с найденной
        {
            DlToch[j]=DlToch[k]+MasDl[k][j];
            NToch[j]=k;//запоминаем номер
        }
        }
        cout<<NToch[k]<<" "; //вывод точек как они связываются
    }
 
    
    cout<<"\nMinimalnoe rasstoyanie: "<<Dt<<"\n";// вывод мин.расстояния
////////////////////////////////
    cout<<"Massiv Indikator"<<"\n";
    for (i=0;i<KolT;i++)
    {   
        cout << IndT[i]<<" ";//проверим индикатор все ли точки прошли
    }
    cout<<"\n";
////////////////////////////////
}
Кстати я планирую вывод графика на OpenGL сделать может кто сразу до ума доведет прогу :-)))

Добавлено через 2 минуты
И еще если код пишите хоть какой нибудь коммент вставляйте, ведь уровень у всех разный. Заранее спасибо:-)))

Добавлено через 2 минуты
Цитата Сообщение от Mr.X Посмотреть сообщение
Не знаю, у меня в Visual Studio нормально работает.
Что у всех эта прога работает? :-((( Я что один такой у которого ошибки
0
CyBOSSeR
Эксперт C++
2302 / 1672 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:39 #11
Цитата Сообщение от SergProgC++ Посмотреть сообщение
Что у всех эта прога работает? :-((( Я что один такой у которого ошибки
Что за среду используете?
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
02.08.2010, 21:41  [ТС] #12
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Что за среду используете?
Microsoft Visual C++ 6.0 и Windows 7

это у меня или я не так понимаю?:-(
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:45 #13
Цитата Сообщение от SergProgC++ Посмотреть сообщение
изучая вопрос нашел что его можно решить с помощью алгоритма Дейкстера.
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Или это именно Дейкстер О_о ?
0
CyBOSSeR
Эксперт C++
2302 / 1672 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:45 #14
Цитата Сообщение от SergProgC++ Посмотреть сообщение
Microsoft Visual C++ 6.0
Эта среда устарела и не поддерживает ни один из стандартов С++ (только проект C++98), поэтому и ошибки. Скачайте более новую версию MSVS (минимум 2005), подойдет и Express версия. Ссылку на скачивание можете узнать в теме Бесплатные среды(IDE) для программирования на С/С++.
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
02.08.2010, 22:09  [ТС] #15
Цитата Сообщение от Хохол Посмотреть сообщение
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Так может другой алгоритм предложете? Вместе и обдумаем!

Добавлено через 2 минуты
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Эта среда устарела и не поддерживает ни один из стандартов С++ (только проект C++98), поэтому и ошибки. Скачайте более новую версию MSVS (минимум 2005), подойдет и Express версия. Ссылку на скачивание можете узнать в теме Бесплатные среды(IDE) для программирования на С/С++.
Понимаете среда должна быть эта и не каких шаблонов использовать нельзя, Мне вообще ее показывать на Borland C++ 3.0

Добавлено через 2 минуты
Цитата Сообщение от Хохол Посмотреть сообщение
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Или это именно Дейкстер О_о ?
Я так понял длины это веса ребер, точки задаются координатами, отсюда следует что это граф, вот почему этот алгоритм использую :-)) но если предложите свой не обижусь. А лучше и реализацию посмотреть:-)))

Добавлено через 4 минуты
Очень прошу пишите по теме, че вокруг да около ходим, то среду обсуждаем то че такое вектор :-(((

Добавлено через 12 минут
Извиняюсь но у меня иногда ощущение складывается что, одни знают о чем говорят,а другим лишьбы че нить ляпнуть:-)))
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2010, 22:09
Привет! Вот еще темы с ответами:

Дан проходной лабиринт с одним входом и выходом. Найти кратчайший путь для прохождения этого лабиринта - C++
Дан проходной лабиринт с одним входом и выходом. Найти кратчайший путь для прохождения этого лабиринта.

Вывести в столбик цифры введённого числа, начиная с первой - C++
Напишите программу, которая выводит в столбик цифры введённого числа, начиная с первой. Используйте процедуру. Входные данные ...

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

Проложить маршрут - Unity, Unity3D
Народ, подскажите или дайте ссылку ибо у самого найти не получается. Есть четырехэтажное здание, нужно сделать такую вещь, чтоб при выборе...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.08.2010, 22:09
Ответ Создать тему
Опции темы

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