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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.58
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
#1

Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей - C++

15.10.2012, 19:11. Просмотров 1642. Ответов 7
Метки нет (Все метки)

Здравствуйте, пожалуйста помогите...



На плоскости своими координатами задано n точек.Построить связный граф с вершинами во всех этих точках так, чтобы суммарная длина его ребра была наименьшей.

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





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

Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0 - C++
Здравствуйте. Условие задачи, собственно, в названии темы. Возникли проблемы с алгоритмом, не говоря уже про код. Ограничений на входной...

Изменить заданную строку текста так, чтобы её длина была равна указанной длине - C++
Здравствуйте!Столкнулся с такой задачей :Дана строка текста. Изменить его так, чтобы длина строки была равна заданной длине. Если исходная...

Вставить равномерно пробелы в строку, чтобы его длина была ровно 50 символов - C++
Помогите, пожалуйста В тексте, который состоит не более чем из 50 символов, вставить равномерно пробелы так, чтобы его длина была...

Записать граф и его ребра в список - C++
Помогите считать граф из текстового файла в список. Не ориентированный граф. На входе должны быть даны вершины и с какими вершинами они...

Построить множество треугольников с вершинами в заданных точках согласно условию - C++
Прошу помочь с одним заданием по С++, начали изучать не так давно, поэтому не особо разбираюсь, пробовал сам, но получается бред... А...

Каковы должны быть размеры участка, чтобы длина забора была наименьшей? - Математический анализ
Одна сторона прямоугольного участка земли примыкает к берегу канала, а три другие огораживаются забором. Каковы должны быть размеры этого...

7
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
15.10.2012, 19:16 #2
покажите что есть
0
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
15.10.2012, 23:03  [ТС] #3
Я так понял, что нужно сначала задать координаты точек (я буду задавать четыре точки), потом следует формула нахождения суммарной длины ребер L=sqrt(x2-x1)^2+(y2-y1)^2.
Сказали, что нужно создать два массива первый для координат(задает пользователь), второй нужно задать самому и выглядеть он должен так
C++
1
2
3
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
А для чего он нужен до сих пор непонятно.
Подскажите пожалуйста, для чего нужен второй массив?Как можно реализовать, что бы пользователь сам мог вводить координаты точек?
0
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
16.10.2012, 06:06 #4
Цитата Сообщение от nikolas982 Посмотреть сообщение
А для чего он нужен до сих пор непонятно.
Подскажите пожалуйста, для чего нужен второй массив?
У Вас задание:
Цитата Сообщение от nikolas982 Посмотреть сообщение
Построить связный граф с вершинами во всех этих точках так, чтобы суммарная длина его ребра была наименьшей.
результатом программы должна быть матрица смежности этого графа:
Цитата Сообщение от nikolas982 Посмотреть сообщение
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
в матрице смежности если 1 стоит в нулевом строке во втором столбце, то значит между 0-ой точкой и 2-ой точкой есть ребро. Если не знаете что такое матрица смежности, можно через поисковик найти материал и почитать.

Цитата Сообщение от nikolas982 Посмотреть сообщение
Как можно реализовать, что бы пользователь сам мог вводить координаты точек?
Да как угодно, например так:
Считываете значение n.
Создаете двумерный массив размером [n][2].
Затем в цикле:
C++
1
for(i=0; i<n; i++)
считываете значение координат в элементы: в [i][0] - координату x, в [i][1] - координату y
1
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
16.10.2012, 13:36  [ТС] #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Создаете двумерный массив размером [n][2]
Подскажите пожалуйста, а почему именно [n][2]?
0
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
16.10.2012, 21:33 #6
Цитата Сообщение от nikolas982 Посмотреть сообщение
Подскажите пожалуйста, а почему именно [n][2]?
Вот задание:

Цитата Сообщение от nikolas982 Посмотреть сообщение
На плоскости своими координатами задано n точек.
Т.е. входные данные это: n иксов и n игреков. Всего 2*n чисел.
0
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
18.10.2012, 19:59  [ТС] #7
А как можно задать точки координат?
Через двумерный массив.

Добавлено через 21 час 48 минут
Если кто может, пожалуйста, помогите написать программу.
0
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
18.10.2012, 21:14 #8
Цитата Сообщение от nikolas982 Посмотреть сообщение
Если кто может, пожалуйста, помогите написать программу
ну попробуйте такой вариант:
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
#include <iostream>
using namespace std;
 
 
int main(){
    int N, i, j, c[100][100], i_min, j_min;
    double a[100][2], b[100][100], min;
    bool d[100]={false}, fl;
    cout<<"Kol-vo vershin: "; cin>>N;
    for(i=0; i<N; i++)
    {
        cout<<"X"<<i+1<<"= "; cin>>a[i][0];
        cout<<"Y"<<i+1<<"= "; cin>>a[i][1]; 
    }
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
        {
            if(i!=j)
                b[i][j]=(a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]);
            c[i][j]=0;
        }
    }
    d[0]=true;
    while(true)
    {
        fl=false;
        min=-1.;
        for(i=0; i<N; i++)
            if(d[i]==false)
            {
                fl=true;
                for(j=0; j<N; j++)
                    if(d[j]==true)
                    {
                        if(min==-1.)
                        {
                            min=b[i][j]; i_min=i; j_min=j;
                        }
                        else
                        {
                            if(min>b[i][j])
                            {
                                min=b[i][j]; i_min=i; j_min=j;
                            }
                        }
                    }
            }
        if(!fl)
            break;
        d[i_min]=true;
        c[i_min][j_min]=c[j_min][i_min]=1;
    }
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
            cout<<c[i][j];
        cout<<endl;
    }
   return 0;
}
1
18.10.2012, 21:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2012, 21:14
Привет! Вот еще темы с ответами:

Выбрать место для постройки моста, чтобы длина дороги была наименьшей - Математический анализ
Добрый день) сестре в ВУЗе задали задачку на тему &quot;производные&quot;. Сижу, не понимаю че вообще от нас хотят) Выбрать место для постройки...

Разработать такой план газификации села, чтобы общая длина трубопроводов была наименьшей - Методы оптимизации
Районной администрацией принято решение о газификации одного из небольших поселков района, имеет 10 жилых домов. Расположение домов...

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

Построить множество всех треугольников с вершинами в заданных точках, которые не пересекаются - QBasic
Заданное случайное множество точек. Построить множество всех треугольников с вершинами в заданных точках, которые не пересекаются. Часть...


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

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

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