大学院入試の問題です！解けません！

[morokosiQ]

とある情報系の大学院の入試問題です。
今年８月に受験をひかえているのですが、学部での専攻が情報系ではなく、現段階で初歩的な教本を片手に勉強しているところです。教本に書かれていることは理解できるのですが、いざ問題を解くとなるとなかなかできません。


（１）は実際にプログラムを再現してみて、値を代入したら答えはわかるのですが、このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。

（２）は題意はわかるのですが、まったくアイデアが思い浮かびません。

[chop.chop]

院試の問題ということで拝見しました。
私自身も今年８月に院試を控えている身ですが、こういうプログラミングの問題は往々にして「コードないし実行結果からやりたいことを読み取る」という力が必要です。

”このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか”
これは半分正解です。
上でも言ったとおり、コードから目的を読み取ることは大事ですがそれはワリと難しいです。コードになぜコメントがいるのかを考えて見ましょう。
そこで院試の問題を解くにあたっては、このような問題は頭の中だけでなく実際に実行結果をループごとに書き出して見ましょう。そうすれば見えてくるものが必ずあります。

たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか？

こちらがループごとの結果となります。
----------------------------------------------------------
2 17 12 4 6 19 10 13 12 7
2 0 0 0 0

2 17 12 4 6 19 10 13 12 7
17 2 0 0 0

2 17 12 4 6 19 10 13 12 7
17 12 2 0 0

2 17 12 4 6 19 10 13 12 7
17 12 4 2 0

2 17 12 4 6 19 10 13 12 7
17 12 6 4 2

2 17 12 4 6 19 10 13 12 7
19 17 12 6 4

2 17 12 4 6 19 10 13 12 7
19 17 12 10 6

2 17 12 4 6 19 10 13 12 7
19 17 13 12 10

2 17 12 4 6 19 10 13 12 7
19 17 13 12 12

2 17 12 4 6 19 10 13 12 7
19 17 13 12 12
----------------------------------------------------------
これで何をやっているかはもうわかったと思うのですが、いかがでしょうか？
ええ、そうです。配列aを降順にソートしたした先頭の５要素をbに代入しているだけです。
試験では、これを手書きでつくるのです。普通は半分かそこらで主旨を理解できるので後は簡単ですね。

もう2番のとき方はよろしいでしょうか？
現在のループで参照しているaの要素とbの全要素を先頭から比較して、大小関係を満たしたところに挿入してやればいいだけの話です。


追記：
これは俗に言う挿入ソートと呼ばれるアルゴリズムです。
本来は線形リストを用いて実装するのが非常に楽なのですが、配列を使ってやるとなるとこのようにややこしくなってしまいます。


それではお互い、院試に向かいがんばりましょう。

[たいちう]

> （１）は実際にプログラムを再現してみて、値を代入したら答えはわかるのですが、
> このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。

大学院の難易度や、院試全体でのこの問題の難易度が判りませんが、情報系の大学院なら、
この程度の問題を時間をかけずに答えを出すことが期待されているのではないでしょうか。

(1)が何をするプログラムか日本語で正確に説明できますか？
何かをするプログラムを自分で考えて自由に作れるようになれば、
プログラムを読んで、何をするプログラムなのか判るようになります。
圧倒的に練習不足でしょう。


> （２）は題意はわかるのですが、まったくアイデアが思い浮かびません。

「題意」だけではなく、f1の仕様さえ判れば、上述した練習問題にすぎません。

[morokosiQ]

chop.chopさん
ありがとうございます！

”たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか？”
いいえ、ループ毎の結果ではなくて、最終的な19 17 13 12 12の答えだけでした。

質問なのですが、

一回目のループでは

コード:

 for (i=0;i<na;i++){
    for (j=nb-1;j>=0;j--){
        if (b[j] > a[i]){
            break;
            }
        } 

この文でbreakされることはなく、j＝０の状態で下のスクリプトを読み込みますよね。
それで、
最後の
b[j+1] = a;では
b[1]=a[0]になり
一回目のbのループ結果は
0 2 0 0 0　になると思うのですが、どこか考え方が間違っているのでしょうか？

[morokosiQ]

たいちうさん

回答ありがとうございます。
院試の為にC言語の勉強を始めたのが最近なので、練習不足なのは自覚しています。。

書かかれたスクリプトの意図がわかるようになるまで、頑張ります。

[みけCAT]

一回目のループでは

コード:

 for (i=0;i<na;i++){
    for (j=nb-1;j>=0;j--){
        if (b[j] > a[i]){
            break;
            }
        } 

この文でbreakされることはなく、j＝０の状態で下のスクリプトを読み込みますよね。
それで、
最後の
b[j+1] = a;では
b[1]=a[0]になり
一回目のbのループ結果は
0 2 0 0 0　になると思うのですが、どこか考え方が間違っているのでしょうか？

j=0の状態ではj>=0が真であり、内側のfor文の中身が実行されたあと、j--が実行されてj=-1になります。
j=-1になるとj>=0が偽になるので、内側のfor文を抜けます。
したがって、「j＝０の状態で下のスクリプトを読み込みますよね。」は誤りです。

[chop.chop]

それは初学者がよくミスする部分ですね。

for文の仕様から考えてみましょう。
このコードでは

コード:

for (j=nb-1;j>=0;j--){}

となっています。j==0まで{}内の文を実行し、そこでさらにj--することで、j==-1となります
ここで初めてforループの条件から外れるため、forループを出るのは、j==-1のときになるのです。

[morokosiQ]

chop.chopさん

すみません先ほどの追加の質問解決しました。
コンパイラで確認したら、j=-1になってたので、理解できました！
ありがとうございます。

[morokosiQ]

chop.chopさん

お返事を見る前に返事しちゃっていました。すみません。
丁寧な説明ありがとうございます。

院試がんばりましょう！

[morokosiQ]

みけCATさんもありがとうございます！

[morokosiQ]

(2)の問題を解いてみたのですが、うまくいきません。

コード:

#include <stdio.h>

int    a[]={2,17,12,4,6,19,10,13,12,7};
int    b[]={0,0,0,0,0};

void f1(int na, int a[], int nb, int b[]){
    int i,j,k;
    for (i=0;i<na;i++){
    for (j=0;j<nb;j++){
        if (a[i]>b[j]){
            break;
            }
        }
        if (j <nb-1){
            for (k=nb-2;k>j;k--){
            b[k+1]=b[k];
            }
            b[j]=a[i];
        }
    }
}

int main(void){
    int t=0;
    f1(10,a,5,b);
    for (t=0;t<=4;t++){
        printf("%d\n",b[t]);
}

return (0);
}

本来なら実行結果は
19 17 13 12 12
になるのですが、

自分の書いたのだと
19 13 12 12 10

になってしまいます。

どこが間違っているのでしょうか、、、

[chop.chop]

そのコードですと、もとの関数の仕様を満たしていないですね。

例えばj==0でaの方が大きいと判定されたとき、
for (k=nb-2;k>j;k--)
つまりk==3からk==1まで配列bの要素を後にずらすわけです。
そうすると
-------------------------------
5 4 3 2 1
\/
5 4 4 3 2
-------------------------------
これではおかしいですね。
本当は
-------------------------------
5 5 4 3 2
-------------------------------
となったあとにb[0]に5の代わりにaを入れるのですから。

あとj==4のときとかどうするんでしょうか……後半のif文の条件はj<nb-1、つまりj<=3までしか対応してくれません
これだとaがb[4]より大きいような場合、更新できませんね


追記:
インデントをちゃんと揃えましょう
非常に読みづらいです

[みけCAT]

(2)の問題は

コード:

break;
}
/* ここにf1の外側のfor文の中身を書き写す */
while(0) {

で条件に合うコードになるでしょう。簡単ですね。

[morokosiQ]

chop.chopさん
みけCAT
ありがとうございます。

お二人のおかげで、一応ソートができるプログラムが書けました！
これが最適なプログラムではない気がしますが、よしとします。

ご教示ありがとうございます！！

コード:

#include <stdio.h>

int    a[]={1,2,3,4,5,6,7,8,9,10};
int    b[]={0,0,0,0,0};

void f1(int na, int a[], int nb, int b[]){
    int i,j,k;
    for (i=0;i<na;i++){
        for (j=0;j<nb;j++){
            if(a[i]>b[j]){
                break ;
            }
        }
        if (j==4){
            b[j]=a[i];
         }else{
            for(k=nb-2;k>j-1;k--){
                b[k+1]=b[k];
            }
            b[j]=a[i];
         }
    }
}

int main(void){
    int t=0;
    f1(10,a,5,b);
    for (t=0;t<=4;t++){
        printf("%d\n",b[t]);
}

return (0);
}

インデント揃えていなくて、すみませんでした。

[たいちう]

題意としては、2重のforループでf1と同じ処理を書け、だと思います。