忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/10/17 14:50 |
PHP5.5.0 「第13回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/89fb0e2e712d4b396535
http://nabetani.sakura.ne.jp/hena/ord13updowndouble/

「+1」「-1」「*2」だけで目的の数値を求めるという問題。
単純にやったら最短にならない場合があります。
単調減少:59→58→29→28→14→7→6→3→2→1→0(10回)
最短:59→60→30→15→16→8→4→2→1→0(9回)
どうすればいいんだろう?

<?php
	class MULTIPLY{
		
		/**
		* 0になる最短の回数
		* @param  int 「59」みたいな数値
		* @return int 「9」みたいな数値
		*/
		public function get($input){
			
			// 偶数であれば2で割る、+1して4で割れれば+1する、それ以外は-1
			for($i=0;$input>4;$i++){
				$input = ($input%2) ? ( (($input+1)%4) ? $input-1 : $input+1 ) : $input/2 ;
			}
			// 3か4になったら2、1、0となるだけなので+3
			return $i+3;
		}
		
	}
	
	// テスト
	$test = [
		[59, 9],
		/* 省略 */
	];

	$multiply = new MULTIPLY();
	foreach($test as $key=>$data){
		$answer = $multiply->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}
なんかできた。
試行錯誤で1時間くらい。

なお、このアルゴリズムが普遍のものなのか、今回たまたま動いてるだけなのかは知りません。
どこかの数学パズルか何かでこの解き方を見たような記憶があるのですが、探しても見つかりませんでした。
というかどんなキーワードでググれバインダー


「オフラインリアルタイムどう書く」の一覧
PR


2013/08/23 23:59 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<今週の実績 2013/08/25 | HOME | PHP5.4.7 オブジェクトの数値キーにアクセスしたい>>
忍者ブログ[PR]