弱小PHPerの憂鬱

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時間くらい。

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


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