“旅行推销商问题”简易暴力实现

  1 #include <bits/stdc++.h>
  2 #include <windows.h>
  3 
  4 int start = 0;
  5 
  6 // 城市名称
  7 char city_name[6] = { 'A', 'B', 'C', 'D', 'E', 'F' };
  8 
  9 // 记录到过的城市
 10 int city[6] = {0};
 11 
 12 
 13 int pass_count = 0;                // 记录当前经到过的城市数量
 14 char pass_path[7] = {0};        // 记录路线
 15 
 16 
 17 // 城市之间的路径
 18 int city_path[6][6] =
 19 {
 20     { 0, 6, 7, 2, 9, 16 },        // a
 21     { 6, 0, 3, 11, 12, 15 },    // b
 22     { 7, 3, 0, 9, 18, 5 },        // c
 23     { 2, 11, 9, 0, 13, 18 },    // d
 24     { 9, 12, 18, 13, 0, 13 },    // e
 25     { 16, 15, 5, 18, 13, 0 }    // f
 26 };
 27 
 28 
 29 // 判断是否已经到过a城市
 30 bool ispassed( int a )
 31 {
 32     return city[a] > 0;
 33 }
 34 
 35 void init()
 36 {
 37     start = 0;
 38     pass_count = 0;
 39     int i;
 40     for( i = 0; i < 6; i ++ )
 41     {
 42         city[i] = 0;
 43         pass_path[i] = 0;
 44     }
 45     pass_path[i] = 0;
 46 }
 47 
 48 //////////////////////////////////////////////////////////////
 49 // 功能：找出与当前城市最近且没有到达过的城市
 50 // 参数：输入当前城市a,输出下一个城市b，
 51 // 返回：两个城市之间的路程
 52 //////////////////////////////////////////////////////////////
 53 int calc_path( int a,int& b )
 54 {
 55     int i =0;
 56     int min = 1000;
 57     b = 0;
 58     for(  i= 0; i < 6; i ++ )
 59     {
 60         if( min > city_path[a][i] && !ispassed(i) )
 61         {
 62             min = city_path[a][i];
 63             b = i;
 64         }
 65     }
 66     if( min < 1000 )
 67         city[b] = 1;
 68     return min;
 69 }
 70 
 71 
 72 bool input_city_num( int &city_num )
 73 {
 74     char city_name = 'A';
 75     printf( "输入起点城市编号(A~F或a~f):" );
 76     scanf( "%c", &city_name );
 77     if( city_name >= 'a' && city_name <= 'f' )
 78         city_name -= 32;
 79     fflush(stdin);
 80 
 81     city_num = city_name - 'A' + 1;
 82     if( city_num > 7 || city_num <= 0 )
 83     {
 84         return false;
 85     }
 86     return true;
 87 }
 88 
 89 
 90 void start_travel()
 91 {
 92     int city_num = 0;
 93     int i = 0;
 94     int path = 0;
 95     int ret = 0;
 96     int b;
 97 
 98     // 初始化数据
 99     init();
100 
101     // 输入起始城市编号
102     while( !input_city_num(city_num) )
103     {
104         printf( "输入有误，请重新输入！n" );
105     }
106 
107     city_num --;
108     city[city_num] = 1;
109     start = city_num;
110     pass_path[ pass_count ++ ] = city_name[city_num];
111 
112     // 开始旅行规划
113     printf( "n从城市[%c]出发n" , city_name[city_num] );
114     printf( "n" );
115     for( i = 0;i < 6; i ++ )
116     {
117         b = 0;
118         ret = calc_path( city_num, b );
119         if( ret > 0 && ret < 1000 )
120         {
121             path += ret;
122             printf( "当前到达%c城市n", city_name[b] );
123             printf( "当前走过路程：%d", path );
124             printf( "n" );
125             city_num = b;
126             pass_path[ pass_count ++ ] = city_name[city_num];
127         }
128     }
129 
130     // 回到起点
131     path += city_path[start][city_num];
132     printf( "当前到达 %c 城市n", city_name[start] );
133     printf( "当前走过路程：%d", path );
134     printf("n");
135     pass_path[pass_count++] = city_name[start];
136 
137     printf( "n" );
138     printf( "旅行结束，总路程为：%dn路线：", path );
139     for( i = 0; i < 7; i ++ )
140     {
141         if( i !=6 )
142             printf( "%c--->", pass_path[i] );
143         else
144             printf( "%c", pass_path[i] );
145     }
146 }
147 
148 int main()
149 {
150     while(1)
151     {
152         start_travel();
153         printf("n----------------------------------------------------nn");
154     }
155     return 0;
156 }