毎度テキスト関係の質問すみません。
今回聞きたいことは、指定された行からテキストの各行の最小値(0除く)を読み込み、それからその最小値のある列と同じ行番号に向かい、それら最小値の数値を足していくというプログラムですが、
単にそれだけではなく、最小値として選ばれた行と同じ番号の列は、初期化し二度考えないというものです。
文章にしただけではわかりにくいと思うので、具体例を上げて以下に説明します。(今回用いたテキストは「euro.txt」)
<euro.txt>
6
0.0 340.0 1270.0 1450.0 2400.0 780.0
340.0 0.0 1060.0 1120.0 2100.0 490.0
1270.0 1060.0 0.0 1370.0 2370.0 1250.0
1450.0 1120.0 1370.0 0.0 1040.0 700.0
2400.0 2100.0 2370.0 1040.0 0.0 1620.0
780.0 490.0 1250.0 700.0 1620.0 0.0
上記に示したテキストの場合で、例えば「1行目」を指定したとします。
①その場合、1行目の最小値は「一行二列目の340」である。⇒ 二行目に向かう
②二行目の最小値は340だが、先程一行目は選ばれたので、一列目を除く最小値を考えると、
「二行六列目の490となる」 ⇒ 六行目に向かう
③六行目の最小値は490だが、先程一、二行目は選ばれたので、一、二列目を除く最小値を考えると、
「六行四列目の700となる」 ⇒ 四行目に向かう
④四行目の最小値は700だが、③で六行目は選ばれたため、1,2,6列目を除く最小値を考えると、
「四行目五列目の1040」となる ⇒ 五行目に向かう
⑤五行目の最小値は1040だが、④で四行目は選ばれたため、1,2,4,6列目を除く最小値を考えると、
残りは一つしかなく「五行三列目の2370」となる ⇒ 三行目に向かう。
⑥三行目ではすべての行が選ばれているため、もとの一行目に戻るべく「三行一列目の1270」を選ぶ。⇒一行目に向かう
(最後の操作では、一番最初に選んだ行と同じ列を選ぶ)
上記のことから、訪れた列番号を順に示すと 1, 2, 6, 4, 5, 3, 1 となる。
また、これらの和は、340+490+700+1040+2370+1270=6210となるため、期待する実行結果は
Data file name: euro.txt
データファイル名: euro.txt
0.000 340.000 1270.000 1450.000 2400.000 780.000
340.000 0.000 1060.000 1120.000 2100.000 490.000
1270.000 1060.000 0.000 1370.000 2370.000 1250.000
1450.000 1120.000 1370.000 0.000 1040.000 700.000
2400.000 2100.000 2370.000 1040.000 0.000 1620.000
780.000 490.000 1250.000 700.000 1620.000 0.000
出発地の都市番号(1-- 6)を入力して下さい。 1
巡回路は 1 2 6 4 5 3 1
総移動距離は 6210.000です。
のようにしたいのですが、このようにかなりややこしい仕組みでプログラムを作成しなければいけないので、
丸一週間友達に聞いたり、自分で考えていてもまったくゴールの兆しが見えてきませんでした。
よって、ファイルから数字を読み込むところまでしかプログラミングはできておりませんが、
とりあえず以下にプログラムを示します。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int FNLEN=50; /* ファイル名の長さ */
const int MAX_CITY=100; /* 都市数最大値 */
int main()
{
FILE *fp;
int i,j,ncity,dept;
int visit[MAX_CITY]; /* 0: 未訪問、1: 訪問済み (訪問したかどうか)*/
int visit_list[MAX_CITY]; /* 訪問順 */
double dist[MAX_CITY][MAX_CITY],total_dist,min_dist;
char file_name[FNLEN]; /* データファイル名 */
printf("Data file name: ");
scanf("%s",file_name);
if ((fp = fopen(file_name,"r")) == NULL){ /* ファイルオープンに失敗した場合は終了 */
printf("%s: ファイルをオープンできません!\n",file_name);
return -1;
}
/* ファイルからデータを読み込む */
printf("データファイル名: %s\n",file_name);
fscanf(fp,"%d",&ncity); /* 都市数の読み込み */
if (ncity > MAX_CITY){
printf("都市の数は%3d以下にしてください!\n",MAX_CITY);
return -1;
}
for (i=0;i<ncity;i++){ /* 距離行列の読み込み */
for (j=0;j<ncity;j++){
fscanf(fp,"%lf",&dist[i][j]);
printf("%10.3lf",dist[i][j]);
}
printf("\n");
}
fclose(fp); /* ファイルクローズ */
/* 出発する都市の都市番号をキーボード入力 */
printf("出発地の都市番号(1--%3d)を入力して下さい。 ",ncity);
scanf("%d", &dept);
if (dept > ncity || dept < 0){
printf("都市番号が無効です。\n");
return(-1);
}
/* 配列 visit および visit_list の初期化 */
for (i=0;i<ncity;i++){
visit[i]=0;
visit_list[i] = -1;
}
/* ---- 貪欲算法 start ---- */
int min;
min=visit[0];
for(i=dept;i<ncity;i++)
for(j=0;j<ncity;j++)
if(min<visit[j])
min=visit[j];
/* ---- 貪欲算法 end ---- */
}
かなり丸投げな質問だということは重々承知ですが、もしお分かりいただけるのであれば、
プログラムを示していただけないでしょうか。