スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
中学受験問題を無理やり解く

yyasuda ブログ「ECONO斬り!!」に灘中学校の数学入試問題が紹介されていた.「数列 207, 2007, 20007, 200007, ... の要素のうち 27 で割れて 81 で割れない最初の数を見つけよ」とのこと.

蛇足.なるほど 2007 年の今年にふさわしい問題だ.来年 2008 年にちなんだ似たような問題はできないかな.それにしても中学受験かぁ.ボクのときはすぐ近所にある公立に通う楽さを思えばどこも受験する気にならなかった.で,入学した公立には徒歩で通ったんだが,墓地のすぐそばにある池の横を通う日々だった.ときどきとても長いヘビがいて,それを避けながら歩こうとすると,ちがうヘビが出て来たりすることもしばしば.季節によるが,雨の日には近くの道路は潰れた平面カエルでいっぱいになって臭かった.そういえば最近水不足の香川は,発電用水や農業用水の水を水道に回すことにしたとか.ため池の水とかだろうか.ううむ,ヘビはまだいいとして,ため池のそばには古いお墓も多い (たぶん) のを考えると,あまり気持ちよくないな.じゃあ話を戻そう.

で,ボクがこの問題をみて最初に思ったのは,あたりまえだが素因数分解 (素数の積に直す) すればできるということ.(素因数分解ってのは「小学生の知らない高度な技」かも.それと,素因数分解というのは暗号にも使われていることから分かるように,なかなか計算するのがたいへん.) その際,まじめに素因素分解する必要はなくて,とりあえず 3 で何回割れるかを調べればいい.具体的には,207, 2007, 20007, 200007, ... をそれぞれ 3 で割って 69, 669, 6669, 66669, ... を得る.さらに 3 で割って 23, 223, 2223, 22223, ... を得る.これをまた 3 で割ると 7 余り 2; 74 余り 1; 741 余り 0; 7407余り 2; 74074 余り 1; 740741 余り 0;... を得る. このとき 222 が 3 で割り切れることを使うと少し楽になる. (下に引用する yyasuda ブログのコメント 7 とたぶん同様のやり方.)

以上のようにして正解を出すことは無理ではないが,yyasuda さんの言う「5分以内を目標に」はむずかしいかな.彼 (正解はこちら) やその友人の指摘するように,3 の倍数や 9 の倍数のある性質を利用することにより,以上の手続きはもっと簡単になる.特に最初に 9 で割ることが鍵で,それは中学受験経験がないとなかなか思いつかないという.どうだろう.むしろ 23, 223, 2223, ... のところから先にすすむとき 3 の倍数の性質を知っていれば有利だとは思うが.倍数のそういう性質を知っているという「特殊技能」よりも,「数列の各要素を一括して操作する」(数列全体に気を配りながら変換する) といった視点の方が鍵かもしれない.そして中学受験経験者は,特に「特殊技能」でもない後者の視点において優れている---ということかもしれない.

だとしたら,「特殊な知識に依存する」という,この試験問題にたいする批判はあまり的を得ていないかも.

さて,ボクはこの問題を無理やり解いてみることにした.そのため,去年少しかじった (その後も関連 web をちょくちょく覗いたりしている) Java でプログラミングの習作をしてみた.ソースコードはこちら: Nada2007Prob.java ファイル (テキストエンコーディングは日本語 Shift JIS).

テクニカルなリマーク.html の pre タグを使ってプログラムをここに載せたいところ.でも,pre タグをこのブログで使うと一部ブラウザで表示が崩れることが過去にあったので,別ファイルでしめす.最初,変数 a の型を int にしたところ javac でコンパイルしたとき「精度が落ちている可能性」のエラーが出た.Java の数値型には気をつけなければいけないらしいが,実のところどういうときにどの型を使うべきかボクはよく理解していない.(まさに「特殊技能」と言えないか.) 何回かの失敗を経て,よく分からないが変数 a の型を double にしてみたら,なんとかまともな結果が出た.ちなみに Math.pow というベキ乗を表す関数は入力も出力も double 型となっている.

上記プログラムを実行したアウトプットは以下の通り:

207は 27 でも割れないのでダメ
2007は 27 でも割れないのでダメ
20007は 81 で割れてしまう
200007は 27 でも割れないのでダメ
2000007は 27 でも割れないのでダメ
20000007は 27 で割れるが 81じゃ割れない.正解候補!
200000007は 27 でも割れないのでダメ
2000000007は 27 でも割れないのでダメ
20000000007は 27 で割れるが 81じゃ割れない.正解候補!
200000000007は 27 でも割れないのでダメ
2000000000007は 27 でも割れないのでダメ
20000000000007は 81 で割れてしまう
200000000000007は 27 でも割れないのでダメ
2000000000000007は 27 でも割れないのでダメ

追記 (6/27/2007; テクニカル). 上のプログラムでは数列の第 i 項を b_i=2*10^{i+1}+7 と,ベキ乗を使って表現した.そのため数値型を浮動小数点数の double にする必要があった.ベキ乗を使うのにこだわったのは,ベキ乗をつかいつつエラーをさける方法を探りたかったからだ.稚拙なプログラムになっているのはそういう事情もある.

しかし問題の趣旨から言えば,a_i=b_i-7 を項とする数列 200, 2000, 20000, ... が,10 を公比とする等比数列になっていると考えるほうが自然だ.(数列を文字列の列と考えて,文字 0 が毎回挿入されているとするほうがさらに自然だが.) そうすると a_i=a_{i-1} * 10 という具合に繰り返し処理のひとつ前の結果を使うことができる (プログラム中では単に a=a * 10 でいい).プログラムとしても毎回ベキ乗を計算する無駄をやらなくて済むので望ましい (?) のかもしれない.その方針でやってみたところ,たしかに数値型は整数型の long で通すことができた.もちろん long の保持できる桁数の 19 桁を超えるとうまくいかなくなるが.

さて,本職プログラマであれば 2分とかからずに紙に書き出せるようなこのプログラムだが,最近話題になっている記事によれば,(アメリカでは) プログラマ職に応募してくる人間のほとんどが,これと同じレベルのプログラムを書けないという.だから稚拙だって笑わないでくれ~.「習作」なんで.

【2007/06/24 01:15 】
| | コメント(0) | トラックバック(1) |
<<ありがた迷惑な copy editing | ホーム | 仲介者による囚人のジレンマ解決法>>
コメント
コメントの投稿











管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://theorist.blog6.fc2.com/tb.php/121-0aa28510
Ruby いいかも
オブジェクト指向言語 Ruby についてちょっと調べてみた.代表的なオブジェクト指向言語である Java とちがって,コンパイルなしで使えるのが魅力のひとつだ.(もっとも最近は掌田津耶乃の記事「コンパイル不要Javaの時代がや ある平凡助教授の,なんということもない日々【2007/08/19 01:05】
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。