HOME»基本情報技術者試験掲示板»平成23年特別午後問8

基本情報技術者試験掲示板

掲示板検索:

[3881]平成23年特別午後問8

 きなこさん(No.1) 
https://www.fe-siken.com/kakomon/23_toku/pm08.html
この問題でのgが理解できませんでした。
この場合、Sの配列が10101の場合の最終配列を考えるのでしょうか。
仮に10101の場合で考えた時、  11111になってしまうのですが、私の理解が間違えているのでしょうか。
是非ご教授お願いいたします。
2021.11.23 11:39
chihiroさん(No.2) 
FE・シルバーエキスパート
>この場合、Sの配列が10101の場合の最終配列を考えるのでしょうか。
正確にはN=5,K=3における配列Sの最終配置(プログラム終了時のSの状態)を考えます。なので、配列Sの初期状態が{1,1,1,0,0}や{0,1,1,0,1}などでもいいです。最終配置はどれも同じになります。
>仮に10101の場合で考えた時、11111になってしまうのですが
そもそもプログラムはN個の要素からK個の要素を選ぶ組み合わせを求めるものなので、配列S中の0および1の個数が変化することはありえません。よって設問gのアおよびエは間違いだとわかります。また、ウはプログラムの繰り返し前の処理である、R←Init(S,N,K)の結果のSの内容なので、最終配置にはなりえないことがわかります(プログラムの関係上、同じ配置は二度と現れないので)。以上のことから、厳密なトレースをしなくても、消去法的にイが答えだとわかります。
2021.11.23 12:03
 きなこさん(No.3) 
丁寧な解説有難うございます。
しかし、未だ理解ができませんでした。
どのような配列でも最終は同じになるとのことでしたが、仮に、10110で考えた場合
L=4の時、Sは01101となり、Init(s、3、2)が呼び出される
Initで、L≦kが真になるためS[1と2]に1が入る
Sの配列が11110となってしまいます。
これが間違いであることは重々承知していますが、どの部分で自分が勘違いをしているのかがわかりません。

是非ご教授お願いいたします。
長々と失礼いたしました。
2021.11.23 22:35
chihiroさん(No.4) 
FE・シルバーエキスパート
>仮に、10110で考えた場合
>L=4の時、Sは01101となり、Init(s、3、2)が呼び出される
ここの意味がよくわからないのですが(Nextの処理ですかね?どういう経緯でL=4になっているのかはわかりませんが)、ひとまず置いておきます。
>Initで、L≦kが真になるためS[1と2]に1が入る
>Sの配列が11110となってしまいます。
これが間違ってます。S[1]とS[2]を1にするのはいいのですが、S[3]←0の処理を忘れています。
繰り返し条件が、L:1,L≦N(=3),1となっているので、L=3の処理までしてください。
2021.11.23 23:21
 きなこさん(No.5) 
>L=4の時、Sは01101となり、Init(s、3、2)が呼び出される

こちらは、L=1、2、3までのnextでの処理は理解しているつもりだったので引っ掛かっていたL=4の時の処理から書かせていただきました。
分かりづらい表現になってしまい、申し訳ございません。

>これが間違ってます。S[1]とS[2]を1にするのはいいのですが、S[3]←0の処理を忘れています。
繰り返し条件が、L:1,L≦N(=3),1となっているので、L=3の処理までしてください。

やっと理解ができてきたのですが、この場合だとSの最終的な配列は11001となり、正解とは違ってしまいます。
正解と同じ配列になるにはどのような処理が行われているのでしょうか。

何度も質問をしてしまい、申し訳ございませんが、是非ご教授お願いいたします。


2021.11.24 00:19
chihiroさん(No.6) 
FE・シルバーエキスパート
プログラムの処理を色々誤解しているように思われるので最初から説明します。
長くなったので分割します。
・R←Init(S,N,K)について
これはSの並びを初期化する処理です。N=5,K=3なので、S[1],S[2],S[3]には1が、S[4],S[5]には0が入ります。これにより、S[]={1,1,1,0,0}となります。最初に渡されるSの初期状態が何であろうと最終結果は同じになると言ったのはこのためです。
・R=0の繰り返し処理について
これはNextの返り値が0である限り、繰り返しを行うものです。NextによりSの並びが変化しなくなったとき、つまりSが最終配置になったときにNextはR=-1を返します。
2021.11.24 09:26
chihiroさん(No.7) 
FE・シルバーエキスパート
403forbiddenにより続きが投稿できないので、詳細な解説は遅れます。
Nextの繰り返し条件に注目ください。Nextの処理で配列Sの要素の交換が行われた時点で、Nextの処理は終了します。このときNextがR=0を返せば、R=0の繰り返し処理を再度行います(印字処理とNextの処理です)。
>こちらは、L=1、2、3までのnextでの処理は理解しているつもりだったので引っ掛かっていたL=4の時の処理から書かせていただきました。
この書き方から察するに、Nextの処理を途中で打ち切っていないように思われます。Nextの条件式に注意しながら、再度トレースをしてみてください。
2021.11.24 12:15
 きなこさん(No.8) 
何度も質問に答えていただき、誠にありがとうございます。
> N=5,K=3なので、S[1],S[2],S[3]には1が、S[4],S[5]には0が入ります。これにより、S[]={1,1,1,0,0}となります。最初に渡されるSの初期状態が何であろうと最終結果は同じになると言ったのはこのためです。
こちらは理解ができました。
本当にありがとうございます。

> Nextの処理を途中で打ち切っていないように思われます。Nextの条件式に注意しながら、再度トレースをしてみてください。
解説いただいたところを注意してトレースしました。
L=3の時、nextでの処理で、Rが0になるため、nextが打ち切られる
Init、印字の処理が行われる
再度L=1からnextの処理が行われる
これを繰り返す。

というか理解でよろしかったでしょうか。
2021.11.24 16:46
chihiroさん(No.9) 
FE・シルバーエキスパート
>L=3の時、nextでの処理で、Rが0になるため、nextが打ち切られる
>Init、印字の処理が行われる
>再度L=1からnextの処理が行われる
>これを繰り返す。
>というか理解でよろしかったでしょうか。
合ってます。
2021.11.24 18:39
 きなこさん(No.10) 
本当にありがとうございました。
大変丁寧な解説をしていただいたにも関わらず私の理解が追いつかず、申し訳ございませんでした。
今後も精進していきたいと思います。
2021.11.24 20:38

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2,000文字以内)

投稿削除用のパスワード(20文字以内)

プレビュー
※CBT方式においては出題内容の公開は禁止されているため、出題内容を尋ねたり、出題内容を特定できる類の投稿を禁止します。
※宣伝や迷惑行為を防止するため、当サイトとIPAサイト以外のURLを含む文章の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop