« ■コマネチ大学数学科102講:花の東大生数学祭り(2) | トップページ | ■海外ドラマ:NUMB3RS~天才数学者の事件ファイル »

2008年8月25日 (月)

■書籍:[非公認]Google入社試験

 「[非公認]Google入社試験」から問題をひとつ。たとえば、0~11までのすべての数に「1」という数字は、1、10、11だから4個含まれているよね。このように「1」の個数を数える関数があったとする。この関数に引数として与えた数と、返ってきた答えの数が一致、つまり、f(n)=n、となる、「1」を除き、次に条件が一致する数を答えよ!

【遊び方】ステッパーの「▲」と「▼」で数値を決め、「Start」ボタンをクリックする。「最大値」のチェックボックスをクリックすると、最大値「200000」までの「1」の数をカウントし、もし「f(n)=n」になったら、停止する。ま、f()の幅が広いので、かなり大きな数になるだろうと推測できる。これをすべて数え上げるには、大変な時間がかかる。結果を待っていられない人は、ひまつぶしに記事の「続き」を読んでね^^;

 このガスコン研究所でも、過去に「Google入社問題」と「平成教育委員会:Googleの入社適正試験」を紹介したが、本書「[非公認]Google入社試験」では、上の2つの問題を含め、37の問題が掲載されている。

 本書には「世界中にピアノの調律師は何人いる?」や「検索トラフィックの季節変動の予測方法を俳句にせよ」などの奇問も登場する。センスやコミュニケーション能力、プレゼン能力も要求されるわけね。

 ただし[非公認]となっているように、Googleは、人材募集広告などを除き、入社問題を基本的に公開していない。本書に掲載されている問題は、Googleの入社試験を受けた人たちが、インターネット上に公開している問題を集めたものだ。

 そして、その問題を、現役IT技術者や、数学科出身の塾講師、物理系大学院生、Google系プログラマー(※系ってなんだろう^^;)、文系を代表してスポーツインストラクター、そして、東大大学院生兼タレントの木村美紀に出題し、その解答に対して、編者、竹内薫センセがコメントを挟むという構成。

 なんか「コマ大数学科特別集中講座」と同じように、企画ものという感じがしないでもない。竹内薫センセと木村美紀の対談も載っているしね^^;

 さて、冒頭の問題なのだが、とりあえず、指定値を「99」に設定すると、f(99)=20になる(1の位に10個+10の位に10個で20個)。さらに「999」では(100+100+100)で、f(999)=300となる。爺が作成したFlashでは、このへんが時間的に待てる限界だが、それでも、なんとなく法則が見えてくる。つまり、f(9999)なら、「1」の数は、4000になるだろうということ。このことから、桁数を「k」とすると、f(9999…)=k*10^(k-1)と予想できる。これを信じるなら、f(99999)=50000だ。

 で、桁が1つ上がり、100000になったとき、これ以降、199999までの数には、無条件に「1」が1個ずつ加算される。99999までに50000個、199999までは、50000+100000+50000で、200000個という計算になる。つまり、199999<200000なので、このあたりに正解があることが推測できる。

 で、最大値「200000」に設定して、ローカルな状態で、自作のFlashを走らせ、この記事を書きながら(かつ、いいちこを飲みながら^^;)本当に、f(n)=nになった時点で停止し、正解を表示できるか、検証を試みているのだが、まだ結果が出ない;;

 ……けっきょく、酔い潰れるほうが先だった(いつものパターンだ;;)でも、起きてみたら、正解が表示されていた。たぶん、正解にたどりつくのに6時間以上はかかるだろう><;正解は本書を……と言いたいところだが、ここまで、読んでくれた人にだけ、こっそり正解を載せておこう。

20080825_01

20080825_02

 主要な部分のスクリプトも公開しておこう(誰も望んでいない;;)。数値を文字列に変換して、ひとつひとつ「1」の数を数えるのだが、文字列の中に「1」がひとつとは限らないので、「1」が見つかったら、nを加算し、以降の文字列を抜き出し、再び関数を呼び出す。これを「1」が見つからなくなるまで繰り返す。

 爺にしては、再帰呼び出しを使うなど、がんばったつもりだが、ひとつだけ、はっきりしているのは、ひとつひとつ「1」を数え上げているようでは、Googleへの入社は無理だということだ><;

Google_book01 [非公認]Google入社試験
竹内薫/編
徳間書店

Comaneci_book01 コマ大数学科特別集中講座
ビートたけし・竹内薫/著
フジテレビ出版


|

« ■コマネチ大学数学科102講:花の東大生数学祭り(2) | トップページ | ■海外ドラマ:NUMB3RS~天才数学者の事件ファイル »

コメント

今さらレスするのもなんですが、
偶然この記事を見つけましたのでレスしておきます。

解答が間違ってますよ^^
例えば
f(199990)=199990
f(199989)=199989
なので、少なくとも正解は199989以上になります^^

投稿: phero | 2009年12月25日 (金) 10時06分

ガスコン爺です。

「f(1)=1は自明として、2番目にf(n)=nとなるような、nを求めよ」という問題ですよ。確かに199981~199990の間は、f(n)=nになりますが……^^; f(1)=1を除くと、次にf(n)=nとなるのは、f(199981)=199981で間違いないように思うのですが……。

投稿: Gascon | 2009年12月26日 (土) 03時11分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/23240773

この記事へのトラックバック一覧です: ■書籍:[非公認]Google入社試験:

« ■コマネチ大学数学科102講:花の東大生数学祭り(2) | トップページ | ■海外ドラマ:NUMB3RS~天才数学者の事件ファイル »