忍者ブログ
[PR]
×

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



2017/12/17 05:43 |
PHP5.6.0 「第17回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
http://qiita.com/Nabetani/items/dabe8ec57e0313229552

10進数の数値を別の進数になおしたら、その数が回文数になることがある。
そうなる場合の基数を列挙せよ。
ちょっと考えただけで計算量が凄いことになりそうだが大丈夫だろうか。
<?php

	class SCHEHERAZADE{
	
		/**
		* 回文基数
		* @param String 「17301」みたいな文字列
		* @return String 「5,38,100,218,236,5766,17300」みたいな文字列
		*/
		public function get($input){
			$input = (int)$input;
			$ret = [];
			
			// 2からinput-1進数
			for($i=2;$i<$input;$i++){
				// 進数表現を取得
				$arr = $this->baseConvert($input, $i);
				// 逆順と等しければ回文
				if($arr === array_reverse($arr)){
					$ret[] = $i;
				}
			}
			// 答えがなければ-
			return $ret ? implode(',', $ret) : '-';
		}
		
		/**
		* $base進数を求める
		* @param int 元の数
		* @param int 基数
		* @return array ex:数字が1001、基数が25のとき、[1, 15 ,1]
		*/
		function baseConvert($num, $base){
			$result = [];
			while($num > 0){
				$result[] = $num % $base;
				$num = floor($num / $base);
			}
			return $result;
		}
	}
	
	// 以下はテスト
	$test = [
		['17301', '5,38,100,218,236,5766,17300'],
		['2', '-'],
		['1', '-'],
		['3', '2'],
		['4', '3'],
		['5', '2,4'],
		['6', '5'],
		['10', '3,4,9'],
		['101', '10,100'],
		['1001', '10,25,76,90,142,1000'],
		['10001', '10,24,30,42,80,100,136,10000'],
		['1212', '22,100,201,302,403,605,1211'],
		['123412', '62,100,205,215,30852,61705,123411'],
		['5179', '5178'],
		['4919', '4918'],
		['5791', '5790'],
		['5498', '2748,5497'],
		['453', '150,452'],
		['134', '66,133'],
		['8489', '27,652,8488'],
		['1234', '22,616,1233'],
		['5497', '41,238,5496'],
		['4763', '19,35,432,4762'],
		['3974', '17,27,1986,3973'],
		['3521', '44,55,502,3520'],
		['5513', '20,38,53,148,5512'],
		['8042', '23,29,60,4020,8041'],
		['7442', '37,60,121,3720,7441'],
		['4857', '25,1618,4856'],
		['22843', '49,69,91,141,430,22842'],
		['194823', '84,121,21646,64940,194822'],
		['435697', '160,169,235,626,1822,435696'],
		['142', '3,7,70,141'],
		['886', '5,14,442,885'],
		['3102', '7,65,93,140,281,516,1033,1550,3101'],
		['17326', '11,28,99,105,8662,17325'],
		['32982', '13,72,238,477,716,1433,5496,10993,16490,32981'],
		['36', '5,8,11,17,35'],
		['37', '6,36'],
		['251', '8,250'],
		['252', '5,10,17,20,27,35,41,62,83,125,251'],
		['253', '12,14,22,252'],
		['6643', '2,3,9,81,90,510,948,6642'],
		['5040', '71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039'],
		['9240', '23,38,62,104,109,119,131,139,153,164,167,209,219,230,263,279,307,329,384,419,439,461,615,659,769,839,923,1154,1319,1539,1847,2309,3079,4619,9239'],
	];

	$scheherazade = new SCHEHERAZADE();
	foreach($test as $key=>$data){
		$answer = $scheherazade->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}
わりと大丈夫だった。
作成30分、実行0.2秒。
まあ高速化とかは何も考えてないけど充分でしょう。
PR


2014/04/14 23:19 | Comments(0) | PHP

コメント

コメントを投稿する






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



<<デッドアイランド リップタイド 3日目 | HOME | 買ったものリスト 2014/04/13>>
忍者ブログ[PR]