忍者ブログ
[PR]
×

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



2017/07/26 15:47 |
PHP5.3.7 「第9回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/7c46e8409c456e8fabd1
http://nabetani.sakura.ne.jp/hena/ord9nummake/

与えられたカードから4桁の順列を作る問題です。
解く方法は、カードから順列を作成する方法と、全数探査のふたつにおおまかにわけられるでしょう。
Rubyだとpermutationなどという反則メソッドがありますが、何故かPHPにはありません。
全数探査で解いてみます。
<?php
	class NUMMAKE{
		
		/**
		* 4桁の数を作って指定番目の値を返す
		* @param String 「13:01167」みたいな文字列
		* @return String 1109 (01167で作れる数のうち13番目)、無しの場合は「-」
		*/
		public function get($input){
			$nowCount = 0;
			
			// 入力を分解
			list($count, $tmp) = explode(':', $input);
			$tmp = str_replace('9', '6', $tmp);
			$nums = array_fill(0, 9, 0);
			for($i=0; $i<strlen($tmp); $i++){
				$nums[$tmp[$i]]++;
			}
			
			foreach(range('1000', '9999') as $int){
				$numbers = $nums;
				$str = str_replace('9', '6', $int);
				
				// 適合しなければ次に進む
				for($i=0; $i<strlen($str); $i++){
					if($numbers[$str[$i]]-- <= 0){
						continue 2;
					}
				}
				
				if(++$nowCount >= $count){
					// 規定番目がみつかった
					return (string)$int;
				}
			}
			
			// 見つからなかった
			return '-';
		}
	}
	
	// テスト
	$test = [
		['13:01167', '1109'],
		/* 省略 */
	];

	$num = new NUMMAKE();
	foreach($test as $key=>$data){
		$answer = $num->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

今回は全数が9000個しかなかったので手っ取り早くforeachで回してます。
これが今度は6桁7桁の順列を作る、とかになったらカードから順列を作成する方法を取らないといけなくなるでしょう。

かかった時間は2時間程度。
最初カードから順列で作ろうとしてめんどくさいことになり、全数探査で作り直したら30分で終わったとかいう。


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


2013/07/15 20:55 | Comments(0) | PHP

コメント

コメントを投稿する






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



<<PHP5.3.7 「第8回オフラインリアルタイムどう書くの問題」をPHPで解く | HOME | 買ったものリスト 2013/07/14>>
忍者ブログ[PR]