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

Жадный алгоритм для определения последовательности обхода городов. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Рекурсивная сортировка разделением http://www.cyberforum.ru/cpp-beginners/thread224291.html
ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается... не могу...
C++ Блок схема для Паскаля Помогите с блок схемой(Особое благодарность Натали) Вот задача Записать в файл последовательного доступа N натуральных чисел: a1, a2,..., an (числа получить с помощью датчика случайных чисел).... http://www.cyberforum.ru/cpp-beginners/thread224259.html
Если в матрице есть одна строка, сумма элементов которой отрицательна, создать новую матрицу по правилу C++
Люди, кто-нибудь знает как задачку решить? Хотя бы на мысль подтолкните плизззз)) Составить программу, которая получает матрицу А размером m*n. Если в исходной матрице есть, по крайней мере,...
C++ Многомерные массивы и строки.
Извиняюсь, что просто с нуля, но очень надо. Будьте добры) Программирование на языках С 1)Дана целочисленная квадратная матрица. Определить: а)сумму элементов в тех столбцах, которые не...
C++ запись структуры в файл http://www.cyberforum.ru/cpp-beginners/thread224224.html
ПОМОГИТЕ пожалуйста......... не могу сделать так чтобы в файл по завершению работы программы записывалось действие которое выполнялось......например...считалась сред.зарплата-----и в файл...
C++ Блог схема Пожалуйста помогите с блог схемой! Вот условие задачи: Записать в файл последовательного доступа N натуральных чисел: a1, a2,..., an (числа получить с помощью датчика случайных чисел).... подробнее

Показать сообщение отдельно
palamarchukn
9 / 9 / 1
Регистрация: 26.11.2009
Сообщений: 78
02.04.2012, 18:40
Может быть кому пригодится:

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
// KomiV.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h" // заголовочный файл 
#include <iostream> // заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++
#include "conio.h"  // заголовочный файл, используемый в старых компиляторах, работающих в операционных системах MS-DOS, для создания текстового интерфейса пользователя.
                    // в данном случае использовали для останова. ( чтобы консоль незакрывалась после ее выполнения)
#include <clocale>  // заголовочный файл стандартной библиотеки языка программирования С, который используется для задач, связанных с локализацией.
                    // в данном случае исплоьзовали для подключения библиотеку русского языка
using namespace std; // Если поместить using namespsce std; то все последующие операторы будут брать переменные и ф-ции из области std
#define n 100        // //кол-во эл-в массива
int _tmain(int argc, _TCHAR* argv[])  
{
   setlocale(LC_CTYPE, "rus"); // использование библ-ки русского языка
      int N, mas[n][n]={0}, i, j, mas_res[n-1], res=0, min, tmp=0;   // обычное заполнение массива. 
      bool mas1[n]={false};
      cout<<"Количество городов: ";
      cin>>N;
 
      for(i=0; i<N-1; i++) // Берется N-ый город
              for(j=i+1; j<N; j++) // и заполняется расстояние между ним и остальными городами
              {
                      cout<<"Расстояние между "<<i+1<<" и "<<j+1<<"  "<<" городом: ";
  cin>>mas[i][j]; 
                      mas[j][i]=mas[i][j];
              }
      mas1[0]=true;
      for(i=0; i<N-1; i++) // цикл по городам
      {
              min=-1; // начальное значение минимума
              for(j=0; j<N; j++)// цикл по расстояниям между городом, из вышенаписанного цикла и остальными городами
                    if(!mas1[j] && mas[tmp][j]>0)// !mas1[j] - если город j еще не посещали и mas[tmp][j]>0 - путь из города в котором находимся tmp в город j есть
                      {
                              if(min==-1) min=j; // если минимум равен -1, то минимум присвоить индексу
                                                // если не -1, то сравниваем значения и ищем минимальное среди них
                              else
                              { // ну тут считаем все делается аналогично циклу заполнение расстояний
                                // только тут вместо того, чтобы вводить значения в массивы между городами,
                                // их тут сравнивают. берут расстояние между первым и второым городом и сравнивается с 1ым и 3им.
                                // потом 1ым и 4ым и так далее. Увеличили i, город уже стал вторым и заново пошел цикл. Между 2ым и 3им городом
                                 // т.к. между 2ым и 1ым городом сравнение было б на предыдущем этапе, когда i=1 (ну 1ый город со 2ым сравнивали). 
                                 // смысл еще раз сравнивать 2ой с 1ым)) 
                                      if(mas[tmp][j]<mas[tmp][min])
                                              min=j;
                              }
                      }
              mas_res[res++]=min; // записали это минимальное расстояние
                                  // перед этим нашли, что самый короткий путь из вершины где сейчас находимся tmp лежит в врешину с индексом min
              mas1[min]=true;     // помечаем вершину min как пройденную
                  tmp=min;        // считаем что вершина где сейчас находимся - вершина с индексом min (переходим из вершины tmp в вершину min)
 
  }
      cout<<"Получен путь:"<<endl;
      cout<<"1 ";
      for(i=0; i<N-1; i++)         // обычный вывод результирующего массива
              cout<<mas_res[i]+1<<" ";
      cout<<"1 "<<endl;   
      _getch();
return 0;
 
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru