大学院入試の問題です!解けません!
大学院入試の問題です!解けません!
とある情報系の大学院の入試問題です。
今年8月に受験をひかえているのですが、学部での専攻が情報系ではなく、現段階で初歩的な教本を片手に勉強しているところです。教本に書かれていることは理解できるのですが、いざ問題を解くとなるとなかなかできません。
(1)は実際にプログラムを再現してみて、値を代入したら答えはわかるのですが、このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。
(2)は題意はわかるのですが、まったくアイデアが思い浮かびません。
今年8月に受験をひかえているのですが、学部での専攻が情報系ではなく、現段階で初歩的な教本を片手に勉強しているところです。教本に書かれていることは理解できるのですが、いざ問題を解くとなるとなかなかできません。
(1)は実際にプログラムを再現してみて、値を代入したら答えはわかるのですが、このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。
(2)は題意はわかるのですが、まったくアイデアが思い浮かびません。
Re: 大学院入試の問題です!解けません!
院試の問題ということで拝見しました。
私自身も今年8月に院試を控えている身ですが、こういうプログラミングの問題は往々にして「コードないし実行結果からやりたいことを読み取る」という力が必要です。
”このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか”
これは半分正解です。
上でも言ったとおり、コードから目的を読み取ることは大事ですがそれはワリと難しいです。コードになぜコメントがいるのかを考えて見ましょう。
そこで院試の問題を解くにあたっては、このような問題は頭の中だけでなく実際に実行結果をループごとに書き出して見ましょう。そうすれば見えてくるものが必ずあります。
たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか?
こちらがループごとの結果となります。
----------------------------------------------------------
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を降順にソートしたした先頭の5要素をbに代入しているだけです。
試験では、これを手書きでつくるのです。普通は半分かそこらで主旨を理解できるので後は簡単ですね。
もう2番のとき方はよろしいでしょうか?
現在のループで参照しているaの要素とbの全要素を先頭から比較して、大小関係を満たしたところに挿入してやればいいだけの話です。
追記:
これは俗に言う挿入ソートと呼ばれるアルゴリズムです。
本来は線形リストを用いて実装するのが非常に楽なのですが、配列を使ってやるとなるとこのようにややこしくなってしまいます。
それではお互い、院試に向かいがんばりましょう。
私自身も今年8月に院試を控えている身ですが、こういうプログラミングの問題は往々にして「コードないし実行結果からやりたいことを読み取る」という力が必要です。
”このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか”
これは半分正解です。
上でも言ったとおり、コードから目的を読み取ることは大事ですがそれはワリと難しいです。コードになぜコメントがいるのかを考えて見ましょう。
そこで院試の問題を解くにあたっては、このような問題は頭の中だけでなく実際に実行結果をループごとに書き出して見ましょう。そうすれば見えてくるものが必ずあります。
たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか?
こちらがループごとの結果となります。
----------------------------------------------------------
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を降順にソートしたした先頭の5要素をbに代入しているだけです。
試験では、これを手書きでつくるのです。普通は半分かそこらで主旨を理解できるので後は簡単ですね。
もう2番のとき方はよろしいでしょうか?
現在のループで参照しているaの要素とbの全要素を先頭から比較して、大小関係を満たしたところに挿入してやればいいだけの話です。
追記:
これは俗に言う挿入ソートと呼ばれるアルゴリズムです。
本来は線形リストを用いて実装するのが非常に楽なのですが、配列を使ってやるとなるとこのようにややこしくなってしまいます。
それではお互い、院試に向かいがんばりましょう。
Re: 大学院入試の問題です!解けません!
> (1)は実際にプログラムを再現してみて、値を代入したら答えはわかるのですが、
> このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。
大学院の難易度や、院試全体でのこの問題の難易度が判りませんが、情報系の大学院なら、
この程度の問題を時間をかけずに答えを出すことが期待されているのではないでしょうか。
(1)が何をするプログラムか日本語で正確に説明できますか?
何かをするプログラムを自分で考えて自由に作れるようになれば、
プログラムを読んで、何をするプログラムなのか判るようになります。
圧倒的に練習不足でしょう。
> (2)は題意はわかるのですが、まったくアイデアが思い浮かびません。
「題意」だけではなく、f1の仕様さえ判れば、上述した練習問題にすぎません。
> このような筆記試験では頭の中で場合分けを重ねて時間をかけて答えをだすしかないのでしょうか。
大学院の難易度や、院試全体でのこの問題の難易度が判りませんが、情報系の大学院なら、
この程度の問題を時間をかけずに答えを出すことが期待されているのではないでしょうか。
(1)が何をするプログラムか日本語で正確に説明できますか?
何かをするプログラムを自分で考えて自由に作れるようになれば、
プログラムを読んで、何をするプログラムなのか判るようになります。
圧倒的に練習不足でしょう。
> (2)は題意はわかるのですが、まったくアイデアが思い浮かびません。
「題意」だけではなく、f1の仕様さえ判れば、上述した練習問題にすぎません。
Re: 大学院入試の問題です!解けません!
chop.chopさん
ありがとうございます!
”たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか?”
いいえ、ループ毎の結果ではなくて、最終的な19 17 13 12 12の答えだけでした。
質問なのですが、
一回目のループでは この文でbreakされることはなく、j=0の状態で下のスクリプトを読み込みますよね。
それで、
最後の
b[j+1] = a;では
b[1]=a[0]になり
一回目のbのループ結果は
0 2 0 0 0 になると思うのですが、どこか考え方が間違っているのでしょうか?
ありがとうございます!
”たとえばこの問題、実行してみたといいましたが、それはループごとに結果を出力したものでしょうか?”
いいえ、ループ毎の結果ではなくて、最終的な19 17 13 12 12の答えだけでした。
質問なのですが、
一回目のループでは この文でbreakされることはなく、j=0の状態で下のスクリプトを読み込みますよね。
それで、
最後の
b[j+1] = a;では
b[1]=a[0]になり
一回目のbのループ結果は
0 2 0 0 0 になると思うのですが、どこか考え方が間違っているのでしょうか?
Re: 大学院入試の問題です!解けません!
たいちうさん
回答ありがとうございます。
院試の為にC言語の勉強を始めたのが最近なので、練習不足なのは自覚しています。。
書かかれたスクリプトの意図がわかるようになるまで、頑張ります。
回答ありがとうございます。
院試の為にC言語の勉強を始めたのが最近なので、練習不足なのは自覚しています。。
書かかれたスクリプトの意図がわかるようになるまで、頑張ります。
Re: 大学院入試の問題です!解けません!
j=0の状態ではj>=0が真であり、内側のfor文の中身が実行されたあと、j--が実行されてj=-1になります。
j=-1になるとj>=0が偽になるので、内側のfor文を抜けます。
したがって、「j=0の状態で下のスクリプトを読み込みますよね。」は誤りです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 大学院入試の問題です!解けません!
chop.chopさん
すみません先ほどの追加の質問解決しました。
コンパイラで確認したら、j=-1になってたので、理解できました!
ありがとうございます。
すみません先ほどの追加の質問解決しました。
コンパイラで確認したら、j=-1になってたので、理解できました!
ありがとうございます。
Re: 大学院入試の問題です!解けません!
chop.chopさん
お返事を見る前に返事しちゃっていました。すみません。
丁寧な説明ありがとうございます。
院試がんばりましょう!
お返事を見る前に返事しちゃっていました。すみません。
丁寧な説明ありがとうございます。
院試がんばりましょう!
Re: 大学院入試の問題です!解けません!
(2)の問題を解いてみたのですが、うまくいきません。
本来なら実行結果は
19 17 13 12 12
になるのですが、
自分の書いたのだと
19 13 12 12 10
になってしまいます。
どこが間違っているのでしょうか、、、
#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
になってしまいます。
どこが間違っているのでしょうか、、、
Re: 大学院入試の問題です!解けません!
そのコードですと、もとの関数の仕様を満たしていないですね。
例えば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]より大きいような場合、更新できませんね
追記:
インデントをちゃんと揃えましょう
非常に読みづらいです
例えば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]より大きいような場合、更新できませんね
追記:
インデントをちゃんと揃えましょう
非常に読みづらいです
Re: 大学院入試の問題です!解けません!
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 大学院入試の問題です!解けません!
chop.chopさん
みけCAT
ありがとうございます。
お二人のおかげで、一応ソートができるプログラムが書けました!
これが最適なプログラムではない気がしますが、よしとします。
ご教示ありがとうございます!!
インデント揃えていなくて、すみませんでした。
みけ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);
}