最後の数

質問

以前Basicの勉強をしていたときに
課題で出された問題なのですが…
(部屋を掃除していたらノートに問題とソースが書かれていて…)

問題は
「n個の数を並べ、3つめの数ごとに消していく。
で、最後に残る数はいくつか」というものです。

例)５個の数「1.2.3.4.5」として
　fir→1.2.4.5
sec→1.2.5
thi→1.2
for→2

といった感じですf^^;
で、basicのプログラムは

100 input "number of people =" ; a
110 N=3*a
120 if N>a then goto 140
130 goto 180
140 C=(N-a-1)/2
150 C=int(C)
160 N=C+N-a
165 print N;",";
170 goto 120
180 print "J3(";a;")=";N
190 end

という風になっていたのですが、どうしてこういった
解き方になったのかがどうしても思い出せません。
(なさけないですねf^^;)
だれかわかる方がいたらアドバイスをお願いします。
(できればこのプログラムにそったやり方だと良いのですが…)

回答No.4

noname#33973 · ベストアンサー

ようやく判りました(激遅

「最後に残る数はいくつか」
というのはミスディレクション(ひっかけ)で、
「最後に消える数はいくつか」
を考えると良いようです。

例えば、a=5のとき、
第12カウントで「2」が消えた時点で最後に残る数「4」が決まりますが、「4」が消えるまでカウントするとします。
最初にa個の数があって、3カウント毎に1減り、最終的に0個になるので、総カウント数は3*aになります。
これが最初のNです。

さて、例えば、a=5のときどのようにカウントするかを列挙すると、
数列A：1,2,3,4,5,1,2,4,5,2,4,2,4,4,4
となります。

プログラムが表示する、
15,14,13,11,8,4
という数列は、数列Aにおける最後に消える数「4」の位置を表しています。

プログラムは、これを使って右から、最後に消える数の位置を計算しているのです。

…大雑把で申し訳ありませんが、終業時間になりましたので、とりあえず方針だけ。

お礼

遅くなって申し訳ありません。ありがとうございます
m(_ _)m

えっと…なんとなくですが理解できたので、
似たような例をいくつか解いてみて、
あとは自己解決できるようにしたいと思います

ありがとうございました☆

回答No.3

noname#33973

あ、ごめんなさい。剰余系云々の話はなし(滝汗

回答No.2

noname#33973

…ですね。

そういう解釈でよければ、
これは一般に「継子立て」と呼ばれる問題になります。
(「継子立て」・「継子立」で検索すると多少ページがあります）

継子立ての解法は、たしか、剰余系ごとに取り除いていって、それから、え～っとぉ、ツメが良く判りません(ぉぃ

プログラムが何やってるかもいまだ不明です。

もう少し考えてみますので、しばらくお待ちを(汗
(その前に別の方から回答がつくかも…)

回答No.1

noname#33973

課題の解釈、違いません？？

“例”のように解釈すると、ｎがどんな値でも2が残ると思うのですが…。

一方、プログラムの方は、例えばnが6のとき1を返します…と思います(ぉぃ

補足

はい、まちがえました(-_-;

えっと5個の数1.2.3.4.5として

fir→1.2.(3).4.5 「3が消えます。」
sec→(1).2.4.5 「firの3から数えて3つめなので1が消えます。」
thi→2.4.(5)
for→(2).4

で、答えが4…と(-_-;)

>一方、プログラムの方は、例えばnが6のとき1を返します…と思います

そう、nが6のときは1であってます。この解釈の仕方が知りたかったのです。ほんとスイマセン(-_-;)