「第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秒。
まあ高速化とかは何も考えてないけど充分でしょう。
Author And Source
この問題について(「第17回オフラインリアルタイムどう書くの参考問題」をPHPで解く), 我々は、より多くの情報をここで見つけました https://qiita.com/rana_kualu/items/8ffc6278fb64ad81366f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .