ニート歴10年からの数学日記

2008年〜2009年の高一の冬休みから無職。最長で4ヶ月ほどの中断アリ。

ステップの問題・コンピューターの問題への考察

結論から言えば、この時点までの変な種類の問題 - ニート歴10年からの数学日記の問題のほとんどに足りないものは、フローの進行方向の長さの決まって無さ、を表現する機能だと思う。
具体的には、スタートとゴールを決めて、その間のステップを明記するような、プログラミングのforループのような機能だと思う。
もちろん複数人ゲームの問題ではそれぞれの目的も記述する必要があるし、他にもいろんな機能は必要だけど、基本的にはそれだと思った。
最初から完璧を目指さずに、まず書いてから修正していきたい。とりあえず、ステップの問題とコンピューターの問題から。
 

ステップの問題

99年度トライアル問題 問題5

『貯金箱をあけると、1円玉、5円玉、10円玉ばかりで合計101枚出てきました。お母さんに、1円玉10枚を10円玉1枚と交かんしていってもらうと、1円玉をすべて交かんすることができて、合計の枚数は65枚になりました。1円玉は、はじめに何枚ありましたか。』


[子供] ← 101個 ← [1, 5, 10]のカブり有り。

記録1。

[
 [母] ← 10個 ← [子供]の[1]。
 [子供] ← 1個 ← [母]の[10]。
]
〜[子供]の[1]の数 = 0。

[子供]の数 = 65。

[結果]における[記録1]の[子供]の[1]の数。


まあなんかワチャワチャしているけど。
まず「記録1」でその時点の結果を記録する必要があるだろう。もちろん内部では全てが記録されているはずなので、これは記述するためのインターフェイスでしか無い。
「〜[子供]の[1]の数 = 0。」でfor文における完了条件を表現した。とりあえず今の想定では、「〜条件1。条件2。条件3。」と続けて書くことでandを表現する。
「[子供]の数 = 65」を参照せずにそれまでを完了させると計算量が膨大になってしまう。しかし問題のフローの記述ということであれば、こういうことになるだろうとも思う。繰り返すようだけどプログラミング言語では無いので、並列するフローなどをとりあえず正確に記述できて、計算量を減らす考察に使えればそれで良いのではないか。
 

コンピューターの問題

99年度トライアル問題 問題9

『片面が白色で片面が黒色のカードが6枚あり、今、図1のように6枚ともすべて白を上にして並べてあります。この6枚のカードをすべて図2のように黒を上にしたいと思います。
ただし、1回につきかならず5枚のカードをめくらなければいけません。図2のようにすべてを黒にするには、もっとも少ない場合で何回かかりますか。

(図1)白白白白白白 → (図2)黒黒黒黒黒黒』


カードリスト[白, 白, 白, 白, 白, 白]。

[カード反転] ← [
 [
  [
   カードリスト[a] = 白。

   カードリスト[a] ← 黒。
  ]
  ,
  [
   カードリスト[a] = 黒。

   カードリスト[a] ← 白。
  ]
 ]の1つ。
]。

[
 [カード反転] ← 5個 ← [カードリスト]のカブり無し。
]
〜の数 = b。[カードリスト] = [黒, 黒, 黒, 黒, 黒, 黒]。

bが最小になるように設定。


あー駄目だ、流石にマズい。しかしこう書かないと、煩雑になるしなあ。
俺は「理論上可能」と「計算量的に現実上可能」を分けたいだけで、「理論上可能」を記述できればそれで良いんだがな。
そもそも1行目の命名と内容を同時に表記するのはあれで良いのかな。[カード反転]の中のaの扱いはあれで良いのか。引数にあたるものは書かなくて問題無いのか。そもそも根本的にこれには意味があるのか。
テキストで書くというのでこうなっているだけで、目的はハッキリしているんだから、少しずつ改良していけば良いと思うが。
 

03年度ファイナル問題 問題6

『2003個の箱が横1列に並んでいます。これらの箱には、左から順に1、2、3、……、2002、2003と番号がついています。いま、このうちの1つの箱に「当たり」と書いた紙が入っていて、その箱より左側にあるすべての箱には「右」と書いた紙が、右側にあるすべての箱には「左」と書いた紙が入っています。このとき次の問に答えなさい。

(問い1)A君がこれらの箱の中から「当たり」と書いた紙を確実に取りだすまでには、最低何個の箱を開ければよいですか。
(問い2)(問い1)のとき、一番はじめに開けなければならない箱についている番号を〜以上〜以下の形で答えなさい。

ただし、開ける箱の選び方は、開ける箱の数が最も少なくなるよう最善の選び方をするものとします。』


箱[要素が2003個ある集合] ← 1個 ← [当たり]。

位置の制約で、[箱]の[? < 当たり] = [右]。
位置の制約で、[箱]の[当たり < ?] = [左]。

[
 [開けた箱] ← [箱]の1個。
 
 [
  [開けた箱] = [右]。
  位置の制約で、[箱]の[? < 開けた箱]は消す。
  ,
  [開けた箱] = [左]。
  位置の制約で、[箱]の[開けた箱 < ?]は消す。
  ,
  [開けた箱] = [当たり]。
 ]の1つ。
]
〜の数 = a。[開けた箱] = [当たり]。

aを最大化するように命令。


これは記述の研究では無いのだから、自分の中で何がやりたいかが意味論的にハッキリしていればそれで良い。位置の制約だとかも、少しずつ意味をハッキリさせていく。
「[開けた箱] ← [箱]の1個。」を書き換えることで、最大化したaを最小にする、という工夫のレベルというか、メタレベルの問題で。でもこれは、この体系で取り上げるべき問題では無いような気が今はする。
 

08年度ファイナル問題 問題4

『図のように、1~10が1つずつ書かれている10個の荷物がななめにならんでいます。次の操作をくり返して荷物をならびかえたいと思います。

(図) 斜めの坂になっていてこっちが下 8 6 2 5 10 1 3 7 9 4 こっちが上

操作:1回につき1個またはとなり合った2個か3個の荷物を取り出す。それと同時に取り出した荷物より右上にあった荷物がすべり落ちる。
   取り出した荷物をその順番のままに一番右上に置く。
   たとえば10、1を取り出したら操作後の順番は8、6、2、5、3、7、9、4、10、1に変わります。

この操作を5回行って、左下から小さい順に1、2、3、4、5…10とならべることが可能ですか。可能ならばその操作手順を、不可能ならばその理由を答えなさい。』


荷物[8, 6, 2, 5, 10, 1, 3, 7, 9, 4]。

[
 [
  [取り出した荷物] ← [荷物]の1つ。
  ,
  [取り出した荷物] ← [荷物]の[[荷物][a], [荷物][a+1]]の1つ。
  ,
  [取り出した荷物] ← [荷物]の[[荷物][a], [荷物][a+1], [荷物][a+2]]の1つ。
 ]の1つ。

 [荷物]の末尾 ← [取り出した荷物]。

 記録b。
]
〜の数 = 5。[荷物] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。

[結果]における[記録b]の全ての[荷物]。


末尾、記録b、に問題がある。
 

12年度ファイナル問題 問題3

『横にならんだ9つのマス目があり、各マスに1枚ずつコインが置かれています。はじめ、左から1、3、4、6、7、9マス目のコインは表、2、5、8マス目のコインは裏です。(図では表を○、裏を×で表しています。)

(図)○×○○×○○×○

以下の操作を考えます。
「表になっているコインを1枚選び、そのコインおよびそのコインより左側にあるコインをすべてひっくり返す。すべてのコインが裏になったら終了である。」
これについて次の問いに答えなさい。

(1)最小何回の操作で終了しますか。
(2)最大何回の操作で終了しますか。』


コインリスト[○, ×, ○, ○, ×, ○, ○, ×, ○]。

[コイン反転] ← [
 [
  [
   コインリスト[a] = ○。

   コインリスト[a] ← ×。
  ]
  ,
  [
   コインリスト[a] = ×。

   コインリスト[a] ← ○。
  ]
 ]の1つ。
]。

[
 [選ばれたコイン] ← [コインリスト]の[○]の1つ。

 並びの制約で、[コイン反転] ← 全部 ← [? < 選ばれたコイン]。
]
〜の数 = b。[コインリスト] = [×, ×, ×, ×, ×, ×, ×, ×, ×]。

bの値を最小にするように命令。

[結果]におけるb。


並びの制約の辺りが非常に怪しいので、近々改良する。
 

13年度トライアル問題 問題6

『ある整数に対して、次の2種類の操作ができるものとします。

操作1: その整数を2倍にする
操作2: 2013からその整数を引く

いま、最初の整数を1として、毎回いずれかの操作を選んで行っていき、2013を超えたところで操作を終了します。
このとき、①〜④の整数のうち操作の途中で作ることのできるものには○、できないものには×を書きなさい。

① 11 ② 35 ③ 61 ④ 1501』


[ある整数] = 1。

[
 [ある整数] ← [ある整数] * 2。
 ,
 [ある整数] ← 2013 - [ある整数]。
]の1つ。
〜[
  [ある整数] > 2013。
  ,
  [ある整数] = 11。
  ,
  [ある整数] = 35。
  ,
  [ある整数] = 61。
  ,
  [ある整数] = 1501。
 ]の1つ。

[結果]における[ある整数]の[? < 2013]。


11とかの結果が滅茶苦茶いっぱい表示されそう。