参考にしたプログラムが...
Posted: 2011年12月14日(水) 03:09
今プログラムを作るにあたり、あるプログラムを参考にしようとしたのですが、
あまりプログラムが得意でないため動きがいまいちわかりません
そこで、よかったらどなたか解説していただけませんか？
特に、探索をしている関数 search_rootの中が、分かりません。
ちなみに参考にしているプログラムの大まかな流れとしては、
・まず制限時間と移動速度を入力する
・そして、それをもとにプログラムに書かれている全ての点を巡回するルートで時間内で回れるかを判定する
・時間内に回れなかった場合は、最後に回った点を除いたルートを作り、また判定する
・最終的に時間内で回れたルートを出力する
というものらしいです。
またvisual studioでc言語で作っています。
あまりプログラムが得意でないため動きがいまいちわかりません
そこで、よかったらどなたか解説していただけませんか？
特に、探索をしている関数 search_rootの中が、分かりません。
ちなみに参考にしているプログラムの大まかな流れとしては、
・まず制限時間と移動速度を入力する
・そして、それをもとにプログラムに書かれている全ての点を巡回するルートで時間内で回れるかを判定する
・時間内に回れなかった場合は、最後に回った点を除いたルートを作り、また判定する
・最終的に時間内で回れたルートを出力する
というものらしいです。
またvisual studioでc言語で作っています。
#include "stdafx.h"
#include <stdio.h>
#include <math.h> //sqrt()
#define sq(a, b) (p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)
#define N 5
struct data{
double x,y;
};
struct view{
int key,pnumber[N];
double span[N],all_span;
int option;
};
double search_root(struct data p[], struct view *root, int n){ /* 探索 */
int table[24]={43210,34210,42310,24310,32410,23410,
43120,34120,41320,14320,31420,13420,
42130,24130,41230,14230,21430,12430,
32140,23140,31240,13240,21340,12340};
int i,j,present,past;
int temp,min_code;
double min,total,note[N]={0.0};
/* 全経路について検索 */
for(i=0; i<24; i++){ /* 24->(N-1)! */
total=0.0;
temp=table[i];
past=temp % 10;
temp /= 10;
for(j=1; j<N; j++){
present = temp % 10;
total += note[j]=sqrt(sq(present, past));
past=present;
temp /= 10;
}
if(i==0){
min=root->all_span=total;
min_code=root->key=table[i];
for(j=0; j<N; j++) root->span[j]=note[j];
}else if(min>total){
min=root->all_span=total;
min_code=root->key=table[i];
for(j=0; j<N; j++) root->span[j]=note[j];
}
}
/* 経路地点整理 */
j=root->pnumber[0]=0;
for(i=root->key/10; i != 0; i /= 10){
root->pnumber[++j] = i % 10;
}
return min; /* 最短距離を返す */
}
int main(int argc, char *argv[]){ /* main文 */
struct data point[N]={{6,7},{3,5},{10,6},{1,18},{2,-3}};
struct view root={0};
double _time, _speed, miles;
int i,k=N-1;
printf("速度と制限時間は(speed time)? ");
scanf(" %lf %lf", &_speed, &_time);
miles= search_root(point, &root, N);
while(k && miles/_speed > _time){
miles-=root.span[k--];
}
printf("<最短ルート>\n");
miles=0.0;
printf("point%d(区間距離 %.2f[%g,%g])\n",root.pnumber[0], root.span[0], point[0].x, point[0].y);
for(i=1; i<=k; i++){
miles+=root.span[i];
printf(" ↓\npoint%d(区間距離 %.2f[%g,%g])\n", root.pnumber[i],
root.span[i],point[root.pnumber[i]].x, point[root.pnumber[i]].y);
}
printf("最終移動距離: %.2f (所用時間: %.2f < %g)\n",
miles, miles/_speed, _time);
if(N-k>1){
printf("<回避ポイント>\n");
for(i=k+1; i<N; i++){
printf("point%d(区間距離 %.2f/速度 %g => 追加所用時間 %.2f)\n",
root.pnumber[i], root.span[i], _speed, root.span[i]/_speed);
}
}
return 0;
}