LoginSignup
1

More than 5 years have passed since last update.

基本情報技術者試験 平成29年度春期 午後のアルゴリズムの問題をC言語に起こしてみました。

Last updated at Posted at 2017-04-26

今年の基本技術者試験を受験しました。
午後の必須問題となっているアルゴリズムの問題が試験中1時間考えてもわからなかったので後日C言語に起こしてみました。

IPAの問題を公開しているページはこちら
午後試験の大問8(データ構造及びアルゴリズム:最短経路の探索)です。

そのコードが以下です。

#include <stdio.h>
#define nPoint 7
#define MAX 9999 

void main(void) {
    int sp = 0, dp = 6;
    int sDist;
    int sRoute[nPoint], pDist[nPoint], pRoute[nPoint];
    int pFixed[nPoint];
    int sPoint, i, j, newDist;
    int Distance[nPoint][nPoint];
    int sPointCount = 0;
    /*Distance投入*/
    Distance[0][0] = 0;
    Distance[0][1] = 2;
    Distance[0][2] = 8;
    Distance[0][3] = 4;
    Distance[0][4] = -1;
    Distance[0][5] = -1;
    Distance[0][6] = -1;

    Distance[1][0] = 2;
    Distance[1][1] = 0;
    Distance[1][2] = -1;
    Distance[1][3] = -1;
    Distance[1][4] = 3;
    Distance[1][5] = -1;
    Distance[1][6] = -1;

    Distance[2][0] = 8;
    Distance[2][1] = -1;
    Distance[2][2] = 0;
    Distance[2][3] = -1;
    Distance[2][4] = 2;
    Distance[2][5] = 3;
    Distance[2][6] = 1;

    Distance[3][0] = 4;
    Distance[3][1] = -1;
    Distance[3][2] = -1;
    Distance[3][3] = 0;
    Distance[3][4] = -1;
    Distance[3][5] = 8;
    Distance[3][6] = -1;

    Distance[4][0] = -1;
    Distance[4][1] = 3;
    Distance[4][2] = 2;
    Distance[4][3] = -1;
    Distance[4][4] = 0;
    Distance[4][5] = -1;
    Distance[4][6] = 9;

    Distance[5][0] = -1;
    Distance[5][1] = -1;
    Distance[5][2] = 3;
    Distance[5][3] = 8;
    Distance[5][4] = -1;
    Distance[5][5] = 0;
    Distance[5][6] = 3;

    Distance[6][0] = -1;
    Distance[6][1] = -1;
    Distance[6][2] = -1;
    Distance[6][3] = -1;
    Distance[6][4] = 9;
    Distance[6][5] = 3;
    Distance[6][6] = 0;

    /*ここからShortestPathのプログラム*/
    sDist = MAX; /*出発地から目的地までの最短距離を初期値に格納する*/
    for (i = 0; i < nPoint; i++) {
        sRoute[i] = -1; /*最短経路上の地点の地点番号に初期値を格納する*/
        pDist[i] = MAX; /*出発地から各地点までの最短距離に初期値を格納する*/
        pFixed[i] = 0; /*各地点の最短距離の確定状態に初期値を格納する*/
        pRoute[i] = 0; /*pRouteは0で初期化されている*/
    }
    pDist[sp] = 0; /*出発地から出発地自体への最短距離に0を設定する*/
    while(1) {
        i = 0;
        while(i < nPoint) { /*未確定の地点を一つ探す*/
            if (!(pFixed[i])) {
                break; /*最内側の繰返しから抜ける*/
            }
            i++;
        }
        if (i == nPoint) { /*出発地から全ての地点までの最短距離が確定*/
            break;            /*していれば、最短経路探索処理を抜ける*/
        }
        for (j = i +1; j < nPoint; j++) { /*最短距離がより短い地点を抜ける*/
            if (!(pFixed[j]) && (pDist[j] < pDist[i])) {
                i = j;
            }
        }
        sPoint = i;

/*α出力*/
        sPointCount++;
        if (sPointCount < 4) {
            printf("-----α-----count: %d \n", sPointCount);
            printf("sPoint: %d \n", sPoint);
        }

        pFixed[sPoint] = 1;
        for (j = 0; j < nPoint; j++) {  /*出発地からの最短距離を確定する*/
            if ((Distance[sPoint][j] > 0) && (!(pFixed[j]))) {
                newDist = pDist[sPoint] + Distance[sPoint][j];
                if (newDist < pDist[j]) {
                    pDist[j] = newDist;
                    pRoute[j] = sPoint;
                }
            }
        }

/*β出力*/
        if (sPointCount < 4) {
            printf("-----β-----count: %d \n", sPointCount);
            printf("pDist: (");
            for (i = 0; i < nPoint; i++) {
                printf("%d,", pDist[i]);
            }
            printf(") ");
            printf("pRoute: (");
            for (i = 0; i < nPoint; i++) {
                printf("%d,", pRoute[i]);
            }
            printf(") \n");
        }

    }
    sDist = pDist[dp];
    j = 0;
    i = dp;
    while (i != sp) {
        sRoute[j] = i;
        i = pRoute[i];
        j = j + 1;
    }
    sRoute[j] = sp;
}

問題の解答になる部分の出力も行っています。
最初に登場するwhileを抜けるbreakが用意されていることに気付くまでに時間がかかりました、whileを抜ける条件がわかりづらいですよね;
pFixedのフラグを立てた後の処理も説明ではわかるがコードにするとなんのこっちゃという感じでした。
最後のsRouteに経路を格納していくところではもうなにがなんだかで試験中はさっぱりでした。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1