time 2017/10/17
プログラマーを目指す前の話なんですが、大阪の『ちちんぷいぷい』という番組で『Googleの入社試験を紹介』というコーナーを見たことがありました。
その時は、「この人たちの頭の中はどうなっているんだ・・・」と思うだけだったのですが、僕も今ではプログラムを嗜む身。
1問ぐらいは解いてやろうと思い、ググってみると面白そうな問題がありました。
▼問題文
整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。
面白そうな問題でしょ?
さっそくチャレンジしてみましょ。
僕は、PHPerなのでPHPで解いてみます。
ソースコードを間違っていました・・・。
修正版に書き直しています。
▼以下、問題にチャレンジ
2番目に大きいnってことは、『f(1)=1』の次の整数nを探せばクリア(って事ですよね・・・?)
とりあえず、関数f(n)を作成しない事には答え合わせもできないので、先に関数f(n)を作っちゃいます。
/** * 引数nの中にある「1」の数を返す * * $n int 整数値を指定 * return int 0からnの間の全ての数を書くのに必要とされる「1」の数を返す */ function f($n) { $count = 0; for($i = 1; $i
substr_countを使って、1の文字を数え、出現回数を返すだけの簡単な関数です。
これで、「0からnの間の全ての数を書くのに必要とされる1の数」を数える事ができました。
あとは、「2番目に大きいn」を探すだけです。
関数f(n)を使って総当りで調べてもいいんですが、さすがにそれはスマートじゃないし、タイムオーバーしちゃう。
ってわけで、こんな関数を作りました。
/** * 引数$startから引数$endの中にある「1」の数を返す * * $start int 1の出現回数を調べる範囲の開始値を整数値で指定 * $end int 1の出現回数を調べる範囲の終了値を整数値で指定 * return int $startから$endの間の全ての数を書くのに必要とされる「1」の数を返す */ function fEx($start, $end) { $count = 0; for(; $start
1~10までの数を書くのに必要とされる「1」の数を返す関数です。
この関数で、「1」を数える範囲を小分けにします。
次は、「2番目に大きいn」を探す関数を作ります。
/** * 0からnの間の全ての数を書くのに必要とされる「1」の数の2番目に大きいnを返す。 * * return int 2番目に大きいnを返す。 */ function main() { $allCnt = 0; // 『1』の数 $start = 1; // 『1』の数を数える開始範囲 $end = 10; // 『1』の数を数える終了範囲 $i = 0; // ループ回数をカウント(ログ用のオマケ) // 1・結果が見つかるまで無限ループを開始 while(true) { // 2・$startから$endの範囲の『1』の数を数え、前回の検索範囲の『1』の数と足す $allCnt += $this->fEx($start, $end); /* 3・「f(n) = n」となるということは、検索範囲の中に答えがあるはず(答えが「n == 1」なら1~10の間に答えがある)なので、検索範囲の中に『1』の数があればチェックする * 「f(1) = 1」は除外 */ if($allCnt >= $start && $allCnt <= $end && $start != 1) { // 4・開始範囲から1づつ足して確認したいため、開始の数を代入 // 5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す for($tmp = $start; $tmp <= $end; $tmp++) { if(($this->f($tmp) == $tmp)) { echo "
ヒットしました。 答えは、『 $tmp 』です。"; return $tmp; } } // 6・ヒットしなかったので、ログを出力。 $i++; echo "『 $start ~ $end 』の間ではヒットしませんでした。$i 回目のループに入ります
"; } // 7・3の条件にあてはまらなかったので、次の検索範囲を指定してループ再開 $start += 10; $end += 10; } }
【ソースコードの説明】
1・結果が見つかるまで無限ループを開始。
2・関数fEx($start, $end)を使って『1』の数を数え、前回検索した範囲の『1』の数と足す。
3・「f(n) = n」になるなら、検索した範囲の中にnがあるはずなので、『1』の数が検索範囲内ならチェック。
(f(1)=1になる事は分かっているので、$startが「1」の場合はチェックしません)
4・開始範囲から1づつ足して確認したいため、開始の数を代入
(2番目に大きい数なので、検索開始範囲から探した方が早いと思う)
5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す。
6・検索範囲内に答えがなければ、ログを出力。
7・『1』の数が検索範囲内になければ、次の検索範囲を指定してループを再開する。
これで、「2番目に大きいn」が見つかるはず・・・
んで、PHPを実行。
【実行結果】
『 11 ~ 20 』の間ではヒットしませんでした。1 回目のループに入ります
『 199911 ~ 199920 』の間ではヒットしませんでした。2 回目のループに入ります
『 199921 ~ 199930 』の間ではヒットしませんでした。3 回目のループに入ります
『 199931 ~ 199940 』の間ではヒットしませんでした。4 回目のループに入ります
『 199941 ~ 199950 』の間ではヒットしませんでした。5 回目のループに入ります
『 199951 ~ 199960 』の間ではヒットしませんでした。6 回目のループに入ります
『 199961 ~ 199970 』の間ではヒットしませんでした。7 回目のループに入ります
『 199971 ~ 199980 』の間ではヒットしませんでした。8 回目のループに入ります
ヒットしました。 答えは、『 199981 』です。
答え合わせに関数fで確認したところ、ちゃんと『f(n)=n』になってました^^
いや~。解けてよかった><
また問題にチャレンジしてみよ~。
追記
まあ、本当にこれで正解なのかは分かりませんが・・・。
「間違ってるよ」とか「無駄な処理してるよ」という方。ご指摘頂けたら嬉しいです。
コメント
1. たけのこ 2011 / 8 / 29 23:25
ヤシガニさんϵ( ‘Θ’ )϶
面白いですね。
私には何が何だかわからないので何も指摘出来なくて悔しい~(。-_-。)
指摘出来るお方がいたらいいですね∧( ‘Θ’ )∧
2. yasigani-ni 2011 / 8 / 30 11:33
たけのこさん。
プログラミングは、答えはひとつでも過程は人それぞれなので、個性が出て面白いですよ^^
指摘してくれる方がコメントを書いてくれたら、報告しますね^^
3. 修正版~Googleの入社試験(非公式)にチャレンジしてみた~ | Yasigani-ni Blog 2012 / 1 / 6 16:28
[…] Googleの入社試験(非公式)にチャレンジしてみたで、チャレンジしたGoogleの入社試験(非公式)。 久しぶりに見直してみたら、間違ったソースコードだったので修正しました。 […]