読者です 読者をやめる 読者になる 読者になる

7人がけイスの3人目

こんちは、実家から以下略(゜Д゜)いくら丼うめぇ JRの座席は7人掛けなわけですが、6人しか座れてない事が多々ありますな デブはどけヽ(`д´)丿 オッサンつめろ って話はどうしようもないので置いといて 普通に座っても6人しか座れないのには理由があるわけですな

きちっと座席にラインが引いてあって(いや、マークはあるんだけど) 皆がそのラインからはみ出ないように座れば、7人は簡単に座れるんだけど どうしても 隣の人とは密着したくない という心理が働くわけで 「流れで」6人が微妙な隙間を空けた状態で膠着しちゃう じゃあ、そうならないようにするにはどうすりゃ良いかというと タイトルの通り、3人目がどこに座るかだ 1人目、2人目は大体が端に座る。

|1□□□□□2|

ここで、3人目が中途半端な位置に座ると微妙な隙間が出来たまま6人になっちゃうので

|1□□3□□2|

鋼の意思でど真ん中に座ろう m9(゚Д゚) そうすると、4人目、5人目が中途半端な所に座っても 「一人が少し寄るだけで十分にもう一人座れる」事になる 一度真ん中に座ったら、決して動いてはいけない、隣からオッサンがプレッシャーかけてきても理我に有りとでも構えておけ 3人目が半端な位置に座っていても、位置次第じゃ4人目がど真ん中に陣取れば修正可能かも知れんぞ まー、世の中そんな上手くいかないので、直ぐに降りそうな人を見つける勘でも磨いてくれ で、だ。 前置きがとても長くなったような気がするが、別の話。 とある電車に乗る乗客は、以下のルールで席に着く。 1. 端が開いていればそこに座る 2. 連続している空きスペースの中央に座る (ちょうど1人分のスペースがあればそこに座る) このとき、幅1の座席には、1人が座れる。 幅2の座席にも、2人が座れる。 幅3の座席にも、3人が座れる。 幅4の座席には、3人しか座れない。 すなわち

|1□□2|

ここで空きスペースの中央に座るので

|1x3x2|

となって3人しか座れない、詰めなおしたりはしないのだ。 幅5の場合は5人が座れる。

|14352|

幅6の場合は、5人しか座れない

|1□x3x□2|→ |1.4.3.5.2|
(隙間は0.25なんだけど、テキストの表現力の限界だから勘弁)

さて、少し考えれば 幅N=4 以上の偶数の場合には無駄が出来てしまう事が分かる。 ならば、奇数ならば無駄が無く座れるだろうか? N=7

|1□□3□□2| → |1x4x3x5x2|

5人しか座れない。 N=8 は飛ばす N=9

|1□□□3□□□2| → |1□4□3□5□2| → |164738592|

みんな座れた! さて、幅Nの時に座れる人数を num(N) で表す事にする。 num(N) = N の時は、座席を無駄なく使えている。 これを「最適化選択が働く」と呼ぶ事にする(適当だよ) 最適化選択が働く(num(N)=N)時 os(N) = 1 、働かない時 os(N)=0 としよう。 さて、問題です。 Q1. num(9)~num(19) を求めなさい。 Q2. os(101), os(1001) を求めなさい。 要するに幅101、幅1001の時に無駄なく座れるかどうか求めなさい。 num(101), num(1001) を求めるだけ。 Q3. num(N) を求めなさい。 ついでにos(N)も Q4. os(N)=1 となるようなNの数列 a は以下のようになる a = {1,2,3,5,9....} 一般項を求めなさい。 (an を n の式で表せ) まー、数学じゃなくてプログラム的に考えても良いね じゃ、そんな感じで頭の体操でもしてくれ。