質問編集履歴
1
あ
test
CHANGED
@@ -1 +1 @@
|
|
1
|
-
C言語
|
1
|
+
C言語 質問の削除しました
|
test
CHANGED
@@ -1,195 +1 @@
|
|
1
|
-
|
2
|
-
```ここに言語を入力
|
3
|
-
#include <stdio.h>
|
4
|
-
#include <stdlib.h>
|
5
|
-
#include <math.h>
|
6
|
-
#define N 5 /* 都市の数 */
|
7
|
-
#define BUF_SIZE 256
|
8
|
-
|
9
|
-
/* 都市の座標構造体 */
|
10
|
-
struct City
|
11
|
-
{
|
12
|
-
int x, y;
|
13
|
-
};
|
14
|
-
|
15
|
-
/* 問題情報構造体 */
|
16
|
-
struct TSP {
|
17
|
-
struct City city[N]; /* 都市の位置 */
|
18
|
-
int order[N]; /* 巡回順 */
|
19
|
-
float cost; /* 総移動距離 */
|
20
|
-
};
|
21
|
-
|
22
|
-
/* 関数の宣言 */
|
23
|
-
void ReadData(struct TSP *tsp);
|
24
|
-
void ShowData(struct TSP *tsp);
|
25
|
-
float CalcDistance(struct City a, struct City b);
|
26
|
-
void SimpleOrder(struct TSP *tsp);
|
27
|
-
void CalcCost(struct TSP *tsp);
|
28
|
-
void ShowCost(struct TSP *tsp);
|
29
|
-
|
30
|
-
/*
|
31
|
-
* * * * メイン関数
|
32
|
-
* * * */
|
33
|
-
int main()
|
34
|
-
{
|
35
|
-
struct TSP tsp;
|
36
|
-
ReadData(&tsp);
|
37
|
-
ShowData(&tsp);
|
38
|
-
SimpleOrder(&tsp);
|
39
|
-
CalcCost(&tsp);
|
40
|
-
ShowCost(&tsp);
|
41
|
-
return 0;
|
42
|
-
}
|
43
|
-
|
44
|
-
/*
|
45
|
-
* * * * 都市座標データ読み込み
|
46
|
-
* * * * 引数:struct TSP *tsp : TSPデータ
|
47
|
-
* * * */
|
48
|
-
void ReadData(struct TSP *tsp)
|
49
|
-
{
|
50
|
-
FILE *fp=fopen("cities05.csv","r");
|
51
|
-
if(fp == NULL)
|
52
|
-
{
|
53
|
-
printf("Can't open data file.\n");
|
54
|
-
exit(1);
|
55
|
-
}
|
56
|
-
char buf[BUF_SIZE];
|
57
|
-
int i,a,b;
|
58
|
-
for(i=0;i<N;i++)
|
59
|
-
{
|
60
|
-
fgets(buf,BUF_SIZE-1,fp);
|
61
|
-
sscanf(buf,"%d,%d\n",&a,&b);
|
62
|
-
tsp->city[i].x=a;
|
63
|
-
tsp->city[i].y=b;
|
64
|
-
}
|
65
|
-
fclose(fp);
|
66
|
-
}
|
67
|
-
|
68
|
-
/*
|
69
|
-
* * * * 都市座標データ表示
|
70
|
-
* * * * 引数:struct TSP *tsp : TSPデータ
|
71
|
-
* * * */
|
72
|
-
void ShowData(struct TSP *tsp)
|
73
|
-
{
|
74
|
-
int i;
|
75
|
-
/* データ表示 */
|
76
|
-
printf("Cities location:\n");
|
77
|
-
for (i = 0; i < N; i ++)
|
78
|
-
{
|
79
|
-
printf("C%-2d : %4d,%4d\n",i + 1, tsp->city[i].x, tsp->city[i].y);
|
80
|
-
}
|
81
|
-
}
|
82
|
-
|
83
|
-
/*
|
84
|
-
* * * * 番号順に巡回する
|
85
|
-
* * * * 引数:struct TSP *tsp : TSPデータ
|
86
|
-
* * * */
|
87
|
-
void SimpleOrder(struct TSP *tsp)
|
88
|
-
{
|
89
|
-
printf("\nSimple order:\n"); /* 計算始めの表示 */
|
90
|
-
int i,order[N];
|
91
|
-
tsp->order[N]=0;
|
92
|
-
tsp->order[0]=0;
|
93
|
-
|
94
|
-
}/* 課題3で作成 */
|
95
|
-
void gen(struct TSP *tsp,int a[],int n,int i)
|
96
|
-
{ int order[N];
|
97
|
-
if(i<n)
|
98
|
-
{
|
99
|
-
for(int j=i;j<n;j++)
|
100
|
-
{
|
101
|
-
int t=a[i];
|
102
|
-
a[i]=a[j];a[j]=t;
|
103
|
-
gen(tsp,a,n,i+1);
|
104
|
-
t=a[i];a[i]=a[j];a[j]=t;
|
105
|
-
}
|
106
|
-
}
|
107
|
-
else
|
108
|
-
{
|
109
|
-
for(i=0;i<=n;i++)
|
110
|
-
{
|
111
|
-
printf("C%-2d>",a[i]);
|
112
|
-
}
|
113
|
-
printf("C%-2d cost=%7.1f\n", tsp->order[0] + 1, tsp->cost);
|
114
|
-
putchar('\n');
|
115
|
-
}
|
116
|
-
}
|
117
|
-
|
118
|
-
/*
|
119
|
-
* * * * 総移動距離を計算する
|
120
|
-
* * * * 引数:struct TSP *tsp : TSPデータ
|
121
|
-
* * * */
|
122
|
-
void CalcCost(struct TSP *tsp)
|
123
|
-
{
|
124
|
-
int i,k,l;
|
125
|
-
k=tsp->order[i];
|
126
|
-
l=tsp->order[i+1];
|
127
|
-
float kyori,wa=0;
|
128
|
-
for (i = 0; i < N-1; i ++)
|
129
|
-
{
|
130
|
-
wa+=CalcDistance(tsp->city[k],tsp->city[l]);
|
131
|
-
}
|
132
|
-
kyori=wa+CalcDistance(tsp->city[N-1],tsp->city[0]);
|
133
|
-
tsp->cost=kyori;
|
134
|
-
/* 課題3で作成 */
|
135
|
-
/* 計算した総移動距離は tsp->cost に代入する */
|
136
|
-
}
|
137
|
-
|
138
|
-
/*
|
139
|
-
* * * * 2都市間の距離を計算
|
140
|
-
* * * * 引数:struct City a : 都市1
|
141
|
-
* * * * 引数:struct City b : 都市2
|
142
|
-
* * * * 戻り値:距離
|
143
|
-
* * * */
|
144
|
-
float CalcDistance(struct City a, struct City b)
|
145
|
-
{
|
146
|
-
float A,B,kyori1;
|
147
|
-
A=b.x-a.x;
|
148
|
-
B=b.y-a.y;
|
149
|
-
kyori1=sqrt(A*A+B*B);
|
150
|
-
return (kyori1);
|
151
|
-
/* 課題3で作成 */
|
152
|
-
}
|
153
|
-
|
154
|
-
/*
|
155
|
-
* * * * 巡回順と総移動距離を表示
|
156
|
-
* * * * 引数:struct TSP *tsp : TSPデータ
|
157
|
-
* * * */
|
158
|
-
void ShowCost(struct TSP *tsp)
|
159
|
-
{
|
160
|
-
int i,a[]={1,2,3,4,5};
|
161
|
-
/* for (i = 0; i < N; i ++)
|
162
|
-
* * {
|
163
|
-
* printf("C%-2d> ", tsp->order[i] + 1);
|
164
|
-
* } */
|
165
|
-
gen(tsp,a,5,1);
|
166
|
-
/* printf("C%-2d cost=%7.1f\n", tsp->order[0] + 1, tsp->cost); */
|
167
|
-
}
|
168
|
-
|
169
|
-
```
|
170
|
-
コードを考えていたところでまず躓いた疑問なのですが、距離を求めるにあたってCalcCost関数内のtsp->city[i]、tsp->city[i+1]に巡回順であるtsp->orderの値を入れていき、巡回順の経路を求めていきたいのですが、このままCalcCost関数内で代入したら1つの巡回路しか入れられないし、その値が入っているかも微妙です。5都市なので初めと最後の都市は1番で固定できるので下の通り24通りあるのですが、この24通りをtsp->cityに代入して24通り分の経路を出すためにはどの部分を修正すればいいのでしょうか?アドバイスの方をよろしくお願いいたします。
|
171
|
-
C1 >C2 >C3 >C4 >C5 >C4 >C1
|
172
|
-
C1 >C2 >C3 >C5 >C4 >C4 >C1
|
173
|
-
C1 >C2 >C4 >C3 >C5 >C4 >C1
|
174
|
-
C1 >C2 >C4 >C5 >C3 >C4 >C1
|
175
|
-
C1 >C2 >C5 >C4 >C3 >C4 >C1
|
176
|
-
C1 >C2 >C5 >C3 >C4 >C4 >C1
|
177
|
-
C1 >C3 >C2 >C4 >C5 >C4 >C1
|
178
|
-
C1 >C3 >C2 >C5 >C4 >C4 >C1
|
179
|
-
C1 >C3 >C4 >C2 >C5 >C4 >C1
|
180
|
-
C1 >C3 >C4 >C5 >C2 >C4 >C1
|
181
|
-
C1 >C3 >C5 >C4 >C2 >C4 >C1
|
182
|
-
C1 >C3 >C5 >C2 >C4 >C4 >C1
|
183
|
-
C1 >C4 >C3 >C2 >C5 >C4 >C1
|
184
|
-
C1 >C4 >C3 >C5 >C2 >C4 >C1
|
185
|
-
C1 >C4 >C2 >C3 >C5 >C4 >C1
|
186
|
-
C1 >C4 >C2 >C5 >C3 >C4 >C1
|
187
|
-
C1 >C4 >C5 >C2 >C3 >C4 >C1
|
188
|
-
C1 >C4 >C5 >C3 >C2 >C4 >C1
|
189
|
-
C1 >C5 >C3 >C4 >C2 >C4 >C1
|
190
|
-
C1 >C5 >C3 >C2 >C4 >C4 >C1
|
191
|
-
C1 >C5 >C4 >C3 >C2 >C4 >C1
|
192
|
-
C1 >C5 >C4 >C2 >C3 >C4 >C1
|
193
|
-
C1 >C5 >C2 >C4 >C3 >C4 >C1
|
194
|
-
C1 >C5 >C2 >C3 >C4 >C4 >C1
|
195
|
-
|
1
|
+
ああああああああああああああああああああああああああああああああああああああああああああああああああああああ
|