平成17年春  午前  問14

ppさん  
(No.1)
https://www.ap-siken.com/kakomon/17_haru/q14.html

こちらの解説ですが、
1回目はxの初期値が0で比較を行っており、
x = x + yでxが0、y += 1でyが1、
2回目の比較ではまだxが0ではないでしょうか?
yは「今まで何回比較をしたか」の合計値になっているとも捉えることができるアルゴリズムだと思います。(ループ抜けた時点では1回分少ない状態で終了しますが)
よって、y = 100になったときに、100回の比較が終了しており、この時点では
x = 99(1 + 99)/2
y = 99 + 1
であり、x = 4950
5000以下のためループに入り
x = 5050
y = 101
この時点で101回終了していることがわかります。
そして102回目の比較でx = 5050なのでループを抜ける。

だと思うのですが、間違っていますでしょうか?
2020.07.22 10:39
助け人さん 
AP ゴールドマイスター
(No.2)
2回目の比較ではまだxが0ではないでしょうか?
について、説明します。

解説のトレースの表にある「比較」「x」「y」は、比較の後、xはどうなり、yはどうなるかが書かれています。
1回目の比較の後、xは0になり、yは1になります。
2回目の比較の後、xは1になり、yに2になります。
・・・

2回目の比較のまさにそのときは、xは確かに0ですが、比較の後の代入でxは1になります。
2020.07.22 17:52
おわ!さん 
AP ブロンズマイスター
(No.3)
横から失礼致します。

仰る通り、解説のトレースの表にあるxとyは、
比較後の「x←x+y, y←y+1」の代入結果ですね。

n回目の比較結果が「x>5000」ということは、
・(n-1)回目の比較結果は「x<=5000」
・「x←x+y, y←y+1」の代入を(n-1)回行った
ということですので、以下のように考えました。

解説のトレース表に
7回目の比較後の「x←x+y」の代入結果が
x=0+1+2+・・・+6
とあるように、

(n-1)回目の比較後の「x←x+y」の代入結果は、
「0~(n-2)」までの数字の総和になるので、
x=0+1+2+・・・+(n-2)=(n-2)(n-1)/2

このxが、n回目の比較対象となり
比較結果が「x>5000」になるので、
{(n-2)(n-1)/2}>5000
(n-2)(n-1)>10000

選択肢の中で、nに代入して計算が楽なのは
「ウ:101、エ:102」なので、
n=101から代入すると、
(n-2)(n-1)=99×100<100×100
となり、ウはNG。
101より小さい「ア:99、イ:100」は除外され、
消去法で正解は「エ:102」に確定する。
念のため、n=102を代入すると
(n-2)(n-1)=100×101>100×100
となるので、エはOK。

長文、失礼致しました。
2020.07.23 01:03
助け人さん 
AP ゴールドマイスター
(No.4)
おわ!さんが登場されましたので、私の解き方です。

流れ図を見ると、x=0+1+2+・・・であり、「x:5000」の比較回数分の数値を加算しています。つまり、n回目の比較後には、x=0+1+2+・・・+(n-1)です。

この数値が次の比較で初めて「x>5000」となるのは、1からいくつまでの加算かを考えます。

昔、いつの頃だったか、1+2+・・・+10=55であり、1+2+・・・+100=5050であることを覚え、記憶に焼き付いてます。1+2+・・・+100=5050ということは、1+2+・・・+99=4950です。

ということは、n-1=100であり、n=101です。次の比較は102回目です。

推測ですが、「x:5000」は、「x:3000」でも「x:7000」でもいいのですが、出題者は、私と同じように、1から100まで加算すれば5050だということが頭にあって5000にしたように思います(考えすぎか)。
2020.07.23 08:59
おわ!さん 
AP ブロンズマイスター
(No.5)
助け人さん

最初に5000を超える加算として、
「1+2+・・・+100=5050」を求めるのは
いいアイデアですね。

末項を引いて、
最後に5000以下になる加算
「1+2+・・・+99=4950」を求めるのも、
都度公式に当てはめるよりいいですね。

流れ図で、
x>5000になるまで加算x=1+2+・・・を
実行しているのも、
上記の活用を誘導しているように見えます。

「x:5000」の比較回数は、やはり、
「x<=5000」をn回とし、
「x>5000」の1回を足して
(n+1)を解答するのが正攻法なんですね。

私は最後の「+1」を忘れがちなため、
「x:5000」の比較回数をn、
「x<=5000」を(n-1)回として、
(n-1)回目の比較後のxが「x>5000」になる
nを求めましたが、こちらも
「0+1+2+・・・+100=5050」を活用して、
x=0+1+2+・・・+(n-2)=5050となるとき、
n-2=100から、正解を求めればよかったです。
2020.07.23 14:00
ppさん  
(No.6)
なるほど!解説のは比較後の結果でしたか!
ありがとうございました!

余談ですが私も助け人さんと同じく、頭に1~100の総和が4950というのが入っていました。
小学生のときに覚えさせられていたのでw

おわ!さんも詳しく丁寧に解説していただきありがとうございます^^
2020.07.23 15:02
助け人さん 
AP ゴールドマイスター
(No.7)
1からnまでの整数を、その合計xがある値(この問題では5000)を超えない範囲内で加算する流れ図を素直に作るなら、
・合計を格納するxの初期値を0
・加算する値を表すyの初期値を1
・xにyを加算した後にある値を超えたかどうかを判定
(これだと、判定は100回。xの初期値を1、yの初期値を2とすると、判定は99回)
とするのですが、この問題では、yの初期値をと0として、1回分ほど間違えさせようとし、また、xにyを加算する前にある値を超えたかどうかを判定して、1回分ほど間違えさせようとしています。

このような罠に引っかからないように、注意深く考えないといけません。
2020.07.23 16:03
おわ!さん 
AP ブロンズマイスター
(No.8)
助け人さん

間違いやすいポイントについてご解説ありがとうございます。

加算する数字の初期値が0なので、
n回目の合計は1~nの合計にならず、0~(n-1)の合計になる。
そのため、合計が初めて5000を超えるのは
100回目の合計「0+1+2+・・・+99」ではなく、
101回目の合計「0+1+2+・・・+100」になる。

合計が5000を超過したかの判定を、合計後に行っているので、
判定の回数は、合計の回数より1多い102になる。

合計対象が1~100なのに対し、ループ内の処理が101回、
判定回数が102回になることについて、
やや違和感がありましたが、理由を掘り下げておりませんでした。

初期値の取り方と、判定のタイミングによるものだったのですね。
類題がありましたら、ループ内の処理を把握するだけでなく、
上記の情報についても注意しながら解くようにします。

また勉強になりました。ありがとうございました。
2020.07.23 23:26
おわ!さん 
AP ブロンズマイスター
(No.9)
ppさん

疑問が解決されたとのこと、よかったです。
助け人さんのご回答の賜物ですね。

私の脱線した投稿にも
丁寧なコメントをいただき、恐れ入ります。

ありがとうございました。
2020.07.23 23:49

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop