

毎度テキスト関係の質問すみません。  
今回聞きたいことは、指定された行からテキストの各行の最小値（０除く）を読み込み、それからその最小値のある列と同じ行番号に向かい、それら最小値の数値を足していくというプログラムですが、  
単にそれだけではなく、最小値として選ばれた行と同じ番号の列は、初期化し二度考えないというものです。

文章にしただけではわかりにくいと思うので、具体例を上げて以下に説明します。(今回用いたテキストは「euro.txt」)

<euro.txt>

[code]

    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
    
    
[/code]

上記に示したテキストの場合で、例えば「１行目」を指定したとします。  
①その場合、１行目の最小値は「一行二列目の３４０」である。⇒ 二行目に向かう  
②二行目の最小値は３４０だが、先程一行目は選ばれたので、一列目を除く最小値を考えると、  
「二行六列目の４９０となる」 ⇒ 六行目に向かう  
③六行目の最小値は４９０だが、先程一、二行目は選ばれたので、一、二列目を除く最小値を考えると、  
「六行四列目の７００となる」 ⇒ 四行目に向かう  
④四行目の最小値は７００だが、③で六行目は選ばれたため、1,2,6列目を除く最小値を考えると、  
「四行目五列目の１０４０」となる ⇒ 五行目に向かう  
⑤五行目の最小値は１０４０だが、④で四行目は選ばれたため、1,2,4,6列目を除く最小値を考えると、  
残りは一つしかなく「五行三列目の２３７０」となる ⇒ 三行目に向かう。  
⑥三行目ではすべての行が選ばれているため、もとの一行目に戻るべく「三行一列目の１２７０」を選ぶ。⇒一行目に向かう  
（最後の操作では、一番最初に選んだ行と同じ列を選ぶ）

上記のことから、訪れた列番号を順に示すと 1, 2, 6, 4, 5, 3, 1 となる。  
また、これらの和は、340+490+700+1040+2370+1270=6210となるため、期待する実行結果は

[code]

    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です。
    
    
[/code]

のようにしたいのですが、このようにかなりややこしい仕組みでプログラムを作成しなければいけないので、  
丸一週間友達に聞いたり、自分で考えていてもまったくゴールの兆しが見えてきませんでした。

よって、ファイルから数字を読み込むところまでしかプログラミングはできておりませんが、  
とりあえず以下にプログラムを示します。

[code]

    #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 ---- */
     
    }
    
[/code]

かなり丸投げな質問だということは重々承知ですが、もしお分かりいただけるのであれば、  
プログラムを示していただけないでしょうか。


CC BY-SA 4.0
2021-01-07T13:56:55.930
73143
2021-01-21T12:20:43.583
41837
question
c
テキストから各列の最小値を読み込んで、それらの数値を足していくプログラム


ソースコードそのものは提示しません。  
提示された①~⑥の手順を実装するならば、以下を参考にコーディングしてみてください。

  * 訪問順の配列は、最後に出発都市に戻る分があるので、最大数`+1`の分を確保する

  * 初期化の必要な変数で定義時に初期化出来るものは定義と同時に初期化しておく(ちなみに訪問順配列は-1で初期化する必要は無い)

  * `貪欲算法`の部分は以下のように作り直し

    * UIで表示する都市の番号(1オリジン)と内部の配列で扱う都市の番号(0オリジン)は違うので意識して書き分ける
    * 訪問済みと訪問順の出発都市のおよび`for`ループの処理で扱う最初の都市の情報を、あらかじめ`for`ループの外で初期設定しておく
    * 外側の`for`ループは訪問順配列を最初から最後まで設定していくために行う
    * 最小値`min`は`int`ではなく`double`で、かつ外側の`for`ループ内の最初に定義する。そしてdouble型の最大値で初期化しておく。
    * 内側の`for`ループで判定した最小値のインデックス値を、内側ループ終了後に使うために記憶しておく変数を定義する 
      * 内側の`for`ループはその行位置で示す都市から他の都市への距離の情報が各列にあるので、次に訪問するための未訪問で最短の都市のインデックス値と距離の情報を取得するために行う
      * 訪問済み(訪問済み==1)か自分自身(距離==0.0)だった場合は処理を行わず、ループの次の回へ移動する
      * 記憶している最小値よりも現在のループ位置で示す値が小さいならば、その値を最小値とし、かつインデックス値も記憶する
    * 内側の`for`ループ終了後に最小値のインデックス値を次の訪問都市として訪問済み配列に設定、訪問順配列に追加し、最小値を総移動距離に加算する
    * 外側の`for`ループ終了後に最初の都市を訪問順配列に追加し、最後の都市から最初の都市への距離を総移動距離に加算する
  * 巡回路表示は、訪問順配列を0から都市数の値まで表示する(ことで出発都市に戻るまでが表示される)。なお、表示時には格納されているデータの0/1オリジン種別に注意


CC BY-SA 4.0
2021-01-08T04:59:01.197
73154
2021-01-08T09:38:15.543
2021-01-08T09:38:15.543
26370
26370
73143
answer

[code]

    #!/usr/bin/env bash
    set -o errexit
    set -o nounset
    
    R="${1}"
    
    >route.txt
    for i in $(seq 1 $(head -n 1 data.txt)); do
      echo $R
      sed 1d data.txt \
        | sed -n ${R}p \
        | xargs -n 1 echo \
        | nl -n ln \
        | grep -v '\t0\.0$' \
        | sort -k2,2n \
        | sed -n 's/\s.*//p' \
          >tmp.txt
    
      while read C; do
        grep $C route.txt >/dev/null && continue
    
        echo $R >>route.txt
        R=$C
        break
      done <tmp.txt
    done
    echo "${1}"
    
[/code]


CC BY-SA 4.0
2021-01-21T12:20:43.583
73474
2021-01-21T12:20:43.583
34583
73143
answer