修正版~Googleの入社試験(非公式)にチャレンジしてみた~

Googleの入社試験(非公式)にチャレンジしてみたで、チャレンジしたGoogleの入社試験(非公式)。
久しぶりに見直してみたら、間違ったソースコードだったので修正しました。

さらに、ソースを見ていると、長ったらしくてイライラしたので書き直すことにしてみました。

とりあえず、以下が問題文。

▼問題文

整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。

前回のソースは色々と無駄だらけなので、2番目に大きいnを探すだけに書き直してしまいます。


▼以下、問題にチャレンジ


とりあえず、まとめてソースを書いちゃいます。

class GoogleTest {
    private $anw;        // 1.答えを格納するプライベート変数

    /**
     * 答えを返す
     *
     * @param    $search     int    検索する値を整数値で指定
     * @param    $start      int    検索を開始する値を整数値で指定
     * @param    $cnt        int    検索を開始する値までに必要な$searchの数を整数値で指定
     * return    int    『f(n)=n』となるような、2番目に大きいnを返す
     */
    public function getAnw() {
        // 2.答えがセットされていない場合、nを求める。
        // 3.f(1)=1になる事は分かっているので、2から数える
        if(!$this->anw) $this->setAnw(2, 1);

        return $this->anw;
    }

    /**
     * 引数nの中にある「1」の数を返す
     *
     * @param    $n        int    検索を開始する値を整数値で指定
     * @param    $count    int    0から$nの間の全ての数を書くのに必要とされる「1」の数を整数値で指定
     */
    public function setAnw($n, $count) {
        $count += substr_count($n, 1);

        if($n == $count) {
            // 4.答えを変数に格納する。
            $this->anw = $n;
        } else {
            // 5.再帰でもう一度計算する
            $this->setAnw($n+1, $count);
        }
    }
}

$gT = new GoogleTest();
echo $gT->getAnw();

【ソースコードの説明】


ざっとソースを説明します。

1.まずは答えを格納する変数を用意します。

2.答えが変数に格納されていない場合、答えを求めます。

3.『f(1) = 1』となるのは分かっているので、2からカウントします。
この時、1を書くのに必要な1の数は1なので、第2引数には1を指定します。

(文字にするとややこしいですね。。。)

4.nを書くのに必要な1の数がnと等しくなった場合、答えを変数に格納します。

5.nを書くのに必要な1の数がnと等しくない場合、再帰処理を行います。

これで終了です。
前回より見やすいソースになったと思います(たぶん・・・)

このままじゃ、0からnの間の全ての数を書くのに必要とされる「1」の数がnと等しい2番目に大きいnしか求めれないのでダメダメな感じですけど・・・
とりあえず、ソースも短くなったし、実行時間も早くなったので、よしとしておきます><

PHP publicとかprivateとかの修飾子

PHP5から使えるprivateやprotectedとかの修飾子について。


public

メンバ変数・メンバメソッドに指定できる。
どこからでもアクセスできる。


private

メンバ変数・メンバメソッドに指定できる。
そのクラス内からしかアクセスできない。


protected

メンバ変数・メンバメソッドに指定できる。
そのクラスかサブクラスからしかアクセスできない。


static

メンバ変数・メンバメソッドに指定できる。
インスタンス化していないクラスでも関係なくアクセスできる。
static宣言したメンバ変数はインスタンス化されたクラスオブジェクトからはアクセスできない。


final

クラスとメンバメソッドに指定できる。
クラスに指定した場合は、このクラスを拡張することができなくなる。
メソッドに指定した場合は、サブクラスからオーバーライドできなくなる。


abstract

クラスとメンバメソッドに指定できる。
抽象クラスや抽象メソッドとなる。
メソッドに指定した場合は、そのクラスではメソッドの実装を定義することはできない。必ずサブクラスで実装する。
長くなりそうなので、コチラの『PHP:クラスの抽象化』をどうぞ・・・


番外編


__construct

コンストラクタメソッドとして使用できる。


__destruct

デストラクタメソッドとして使用できる。


Category » PHP

Googleの入社試験(非公式)にチャレンジしてみた

プログラマーを目指す前の話なんですが、大阪の『ちちんぷいぷい』という番組で『Googleの入社試験を紹介』というコーナーを見たことがありました。
その時は、「この人たちの頭の中はどうなっているんだ・・・」と思うだけだったのですが、僕も今ではプログラムを嗜む身。
1問ぐらいは解いてやろうと思い、ググってみると面白そうな問題がありました。

▼問題文
整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。

面白そうな問題でしょ?
さっそくチャレンジしてみましょ。
僕は、PHPerなのでPHPで解いてみます。


2012/01/06  追記

ソースコードを間違っていました・・・。
修正版に書き直しています。


▼以下、問題にチャレンジ


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』になってました^^
いや~。解けてよかった><
また問題にチャレンジしてみよ~。


追記
まあ、本当にこれで正解なのかは分かりませんが・・・。
「間違ってるよ」とか「無駄な処理してるよ」という方。ご指摘頂けたら嬉しいです。

『PHP』か『JavaScript』で指定した年月のd曜日は何日かを取得する方法

『PHP』か『JavaScript』で指定した年月のd曜日は何日かを取得する方法を紹介したいと思います。
例えば「2011年9月の金曜日」を指定したら、戻り値で「2・9・16・23・30」が返ってくるような感じです。

最初は、PHPのソースコードから。
▼PHP版

/**
 * $year	int	求めたい年を指定
 * $month	int	求めたい月を指定
 * $day		int	求めたい曜日。0〜6までの数字で指定
 */
function getDayOfMonth($year, $month, $day) {
	// 1・指定した年月の日数を取得
	$allDays = date("t", mktime(0, 0, 0, $month, 1, $year));

	// 2・指定した年月の最初の曜日を取得
	$firstDay = date("w", mktime(0, 0, 0, $month, 1, $year));

	// 3・求めたい曜日の第1週の日付けを計算する
	$day = $day - $firstDay + 1;
	if($day <= 0) $day += 7;

	// 4・指定した年月の最終日を越えるまで1週間を足す
	while($allDays >= $day) {
		$arrDays[sizeof($arrDays)] = $day;
		$day += 7;
	}

	return $arrDays;
}

次は、JavaScriptのソースコード。
▼JavaScript版

/**
 * year		int		求めたい日付の年を指定
 * month	int		求めたい日付の月を指定
 * day		int		求めたい曜日。0〜6までの数字で指定
 */
function getDayOfMonth(year, month, day) {
	// 1・指定した年月の日数を取得
	var date = new Date(year,month,0);
	var allDays = date.getDate();

	// 2・指定した年月の最初の曜日を取得
	date = new Date(year+"/"+month+"/1");
	var firstDay = date.getDay();

	// 3・求めたい曜日の第1週の日付けを計算する
	var day = day - firstDay + 1;
	if(day <= 0) day += 7;

	// 4・指定した年月の最終日を越えるまで1週間を足す
	var arrDays = [];
	while(allDays >= day) {
		arrDays[arrDays.length] = day;
		day += 7;
	}

	return arrDays;
}

これで、指定した年月・曜日の日付を取得することができます。
getDayOfMonth(2011, 9, 1)
と書けば、配列形式で
Array([0] => 5 [1] => 12 [2] => 19 [3] => 26)
と、結果が返ってきます。

【ソースコードの説明】
前回同様、PHPもJavaScriptも同じような処理をしているので、まとめて説明します。


1・まずは、指定された年月の総日数を取得します。


2・指定した年月の最初の曜日を取得。
PHPもJavaScriptも曜日を数値型で返すので、変数firstDayには曜日を表す数値が入ります。


3・求めたい曜日の第1週目が何日なのかを計算します。
引数dayが初日の曜日より前の曜日か後の曜日かを計算し、前の曜日なら1週間分足してしまいます。
(初日より前なら、指定した曜日は翌週にしかないから)


4・あとは、指定された年月の最終日を超えるまで1週間を足していき、日付けを配列に追加していきます。


5・日数を格納した配列を返して終了です^^


※もっとスマートなやり方があるような気もしますが・・・

次は、指定した年月日が第n d曜日なのかを判別する方法を書こうかな~?

『PHP』か『JavaScript』で指定した年月の第n d曜日は何日かを取得する方法


ちょっと前の案件で、第n d曜日だけ(第2 水曜日だけとかです)
画像を変えたいという要求があったので、メモも兼ねてブログに残しておこうと思います。

最初は、PHPのソースコードから。
▼PHP版

<?php
/**
 * $year	int	求めたい日付の年を指定
 * $month	int	求めたい日付の月を指定
 * $week	int	第n週か。第1週なら1、第3週なら3を指定
 * $day		int	求めたい曜日。0〜6までの数字で指定
 */
function getWeekOfDay($year, $month, $week, $day) {
	// 1・指定した年月の最初の曜日を取得
	$firstDay = date("w", mktime(0, 0, 0, $month, 1, $year));

	// 2・求めたい曜日の第1週の日付けを計算する
	$day = $day - $firstDay + 1;
	if($day <= 0) $day += 7;

	// 3・n週まで1週間を足す
	$day += 7 * ($week - 1);

	// 4・結果を返す
	return date("Y-m-d", mktime(0, 0, 0, $month, $day, $year));
}
?>

次は、JavaScriptのソースコード。
▼JavaScript版

/**
 * year		int		求めたい日付の年を指定
 * month	int		求めたい日付の月を指定
 * week		int		第n週か。第1週なら1、第3週なら3を指定
 * day		int		求めたい曜日。0〜6までの数字で指定
 */
function getWeekOfDay(year, month, week, day) {
	// 1・指定した年月の最初の曜日を取得
	var date = new Date(year+"/"+month+"/1");
	var firstDay = date.getDay();

	// 2・求めたい曜日の第1週の日付けを計算する
	var day = day - firstDay + 1;
	if(day <= 0) day += 7;

	// 3・n週まで1週間を足す
	day += 7 * (week - 1);

	// 4・結果
	result = new Date(year+"/"+month+"/"+day);

	var Y = parseInt(result.getFullYear());
	var m = parseInt(result.getMonth())+1;
	var d = parseInt(result.getDate());

	return (Y+"-"+m+"-"+d);
}

これで、日付を取得することができます。
例えば、
getWeekOfDay(2011, 8, 2, 3)
と書けば、
2011-08-10
結果が返ってきます。

【ソースコードの説明】
PHPもJavaScriptも同じような処理をしているので、まとめて説明しちゃいますね。


1・まずは、指定された年月の初日の曜日を取得します。
PHPもJavaScriptも曜日を数値型で返すので、変数firstDayには曜日を表す数値が入ります。


2・求めたい曜日の第1週目が何日なのかを計算します。
引数dayが初日の曜日より前の曜日か後の曜日かを計算し、前の曜日なら1週間分足してしまいます。
(初日より前なら、指定した曜日は翌週にしかないから)


3・あとは、指定されたn週まで1週間を足していきます。


4・これで日付が分かったので、あとは目的にあった返し方をしてあげるだけとなります^^


PHPは探しきれなかっただけで、カレンダー関数とかで定義されているのかな~??