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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Блок схема для Паскаля http://www.cyberforum.ru/cpp-beginners/thread224259.html
Помогите с блок схемой(Особое благодарность Натали) Вот задача Записать в файл последовательного доступа N натуральных чисел: a1, a2,..., an (числа получить с помощью датчика случайных чисел). Сформировать новый файл последовательного доступа, элементами которого являются числа а1, а1•а2, а1•а2•а3,..., al•a2•a3•...•an. Вот решение на Паскале) program mynumbers; var f1,f2:text; ...
C++ Если в матрице есть одна строка, сумма элементов которой отрицательна, создать новую матрицу по правилу Люди, кто-нибудь знает как задачку решить? Хотя бы на мысль подтолкните плизззз)) Составить программу, которая получает матрицу А размером m*n. Если в исходной матрице есть, по крайней мере, одна строка, сумма элементов которой отрицательна, то формируется новая матрица из исходной так, что строки в ней расположены в порядке возрастания сумм элементов этих строк. http://www.cyberforum.ru/cpp-beginners/thread224251.html
C++ Многомерные массивы и строки.
Извиняюсь, что просто с нуля, но очень надо. Будьте добры) Программирование на языках С 1)Дана целочисленная квадратная матрица. Определить: а)сумму элементов в тех столбцах, которые не содержат отрицательных эле¬ментов; б)упорядочить строки по убыванию произведений их элементов. 2)Дано предложение. Вывести его на экран, заменив каждую первую букву слов, начинающихся с гласной на...
C++ запись структуры в файл
ПОМОГИТЕ пожалуйста......... не могу сделать так чтобы в файл по завершению работы программы записывалось действие которое выполнялось......например...считалась сред.зарплата-----и в файл выводится----- все сотрудники+ Srednyaya zarplata= "<<sredzap<<" rublei :cry:......помогите ))))))))) #include <conio.h> #include <iostream>
C++ Блог схема http://www.cyberforum.ru/cpp-beginners/thread224206.html
Пожалуйста помогите с блог схемой! Вот условие задачи: Записать в файл последовательного доступа N натуральных чисел: a1, a2,..., an (числа получить с помощью датчика случайных чисел). Сформировать новый файл последовательного доступа, элементами которого являются числа а1, а1•а2, а1•а2•а3,..., al•a2•a3•...•an. Вот решение на С++: #include <fstream.h> #include <iostream.h> #include...
C++ Как правильно передавать указатели на класс на другую форму в общем добрый день, пытаюсь создать собственную телефонную книгу используя ооп. ну дак вот я описал в cpp файле два класса: один предок другого + управляющий класс. Начинаю привинчивать к формам, но у меня при добавлении нового человека вылазит ошибка: Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 00408119 in module 'Project1.exe'.write... подробнее

Показать сообщение отдельно
alloyr
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 8
27.11.2012, 20:46     Жадный алгоритм для определения последовательности обхода городов.
valeriikozlov, Был у преподавателя программа почти правильна, только должна работать не из клавиатуры, а из файла (создать input.txt - потом появится output.txt)(таково условие преподавателя). Поэтому решенную задачу (кому нибудь пригодится) прикладываю здесь - путь коммивояжера начинается с 1 города (5 городов), ответ таков: путь 1-5-3-4-2-1 и сумма пути 13. Матрица стоимостей такова:

100 1 2 7 5
1 100 4 4 3
2 4 100 1 2
7 4 1 100 3
5 3 2 3 100

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
#pragma once
 
#define WIN32_LEAN_AND_MEAN     // Exclude rarely-used stuff from Windows headers                       
 
#include <stdio.h>
#include <conio.h>
#include <fstream>
#include <tchar.h>
#include <iostream> // заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++
using namespace std; // Если поместить using namespsce std; то все последующие операторы будут брать переменные и ф-ции из области std
 
 
 
Ход выполнения задачи:
 
#include "stdafx.h"
 
void print_matr(int**a,int n )
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cout.width(4);
            cout<<a[i][j];
        }
        cout<<'\n';
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
     setlocale(LC_CTYPE, "russian"); // использование библ-ки русского языка
     ifstream fin;
     ofstream fout;
     int N, **mas, i, j, *mas_res, res=0, min, tmp=1, sum=0; // обычное заполнение массива.
     bool *mas1;
     fin.open("input.txt");
     fout.open("output.txt");
     fin>>N;
     cout<<N<<'\n';
     mas=new int*[N];
     for (i=0; i<N; i++)
         mas[i]=new int[N];
     mas_res=new int[N-1];
     mas1=new bool[N];
     for (i=0; i<N; i++)
        mas1[i]=false;
     for( i=0; i<N; i++) // Берется N-ый город
           for( j=0; j<N; j++) // и заполняется расстояние между ним и остальными городами
           {
               fin>>mas[i][j];
           }
     print_matr(mas,N);
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            fout.width(4);
            fout<<mas[i][j];
        }
        fout<<'\n';
    }
 
      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<<"Получен путь: \n";
      cout<<"1 "; // исходный город (начало пути коммивояжера)
      for(i=0; i<N-1; i++) // обычный вывод результирующего массива (по городам)
      cout<<mas_res[i]+1<<" ";
      cout<<"1 \n"; // возвращение коммивояжера к исходному городу
      cout<<"Получена сумма пути: \n";
      fout<<"Получен путь: \n";
      fout<<"1 "; // исходный город (начало пути коммивояжера)
      for(i=0; i<N-1; i++) // обычный вывод результирующего массива (по городам)
       fout<<mas_res[i]+1<<" ";
      fout<<"1 \n"; // возвращение коммивояжера к исходному городу
      fout<<"Получена сумма пути: \n";
      if(N>1)
      {
      sum+=mas[0][mas_res[0]]; 
      for(i=0; i<N-2; i++) // обычный вывод результирующего массива (по расстояниям)
      sum+=mas[mas_res[i]][mas_res[i+1]];
      sum+=mas[0][mas_res[N-2]];
      }
      cout<<sum<<" \n";
      fout<<sum<<" \n";
      fout.close();
    return 0;
}
Валерий, я очень прошу тебя помочь мне - моя задача такая же, только путь коммивояжера начинается со 2 города и придумать квадратную матрицу 5(i) на 5(j)(i-строка, j-столбец) (придумать матрицу-образец смотреть выше), следовательно путь и сумма пути будут другими. Программа также должна работать из файла input.txt(в этом файле создать матрицу). Очень прошу в каждой строке программы дать очень подробный комментарий-что это и что там такое. Буду благодарен.
 
Текущее время: 13:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru