前回のカプレカ操作は、各引数を数値として計算しました。
マイナスするだけなので非常に簡単ではあるのですが、PHPの整数演算は大きな桁数を扱うことが出来ません。
その大きさはOSに依存するのですが、一般的な32ビットOSでわずか10桁程度です。
引数を文字列や配列として与えた場合、ほぼ無制限と言えるほど大量のデータでも扱うことが出来ます。
カプレカ操作を文字列や配列を使用して行ってみます。
kaprekar2.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
//配列でカプレカ
//検証する数
if(isset($_REQUEST['k'])){
$seed=$_REQUEST['k'];
}else{
$seed='32799999999999999999999999968';
}
//準備
$i=0;
$result_array=array();
$result_array[0]=$seed;
while(1){
//カプレカ
$tmp=kaprekar($result_array[$i]);
//返り値が既に存在すれば終了
if($a=array_search($tmp,$result_array)){
$result_array[$i+1]=$tmp.'='.$a;
break;
}
$result_array[$i+1]=$tmp;
$i++;
}
print("<pre>");print_r($result_array);die();
//一回のカプレカ
function kaprekar($seed){
//繰下がり用の変数
$borrow=0;
//配列に分割
$seed_array=str_split($seed);
//小さい順に並べる
rsort($seed_array);
$seed_max=count($seed_array)-1;
//差を計算
for($i=$seed_max;$i>=0;$i--){
//各桁の値
$ret_array[$i]=$seed_array[$i]-$seed_array[$seed_max-$i]-$borrow;
$borrow=0;
//繰下がり
if($ret_array[$i]<0){
$ret_array[$i]+=10;
$borrow=1;
}
}
//文字列として返却
ksort($ret_array);
return implode('',$ret_array);
}
|
前回の引数は数値でしたが、今回は文字列です。
それ以外はfunction kaprekar()以外は全く同じです。
今回のkaprekar()は少々分かり難いですが、やってることは昔懐かし繰下がりのある引き算です。
実際引き算を行うときに、一気に計算できる人なんてまず居ないでしょう。
下の位から順番に、一桁ずつ計算しているはずです。
今回はその計算方法を使用しています。
引数として32768が与えられたとして、まず以下のように一文字ずつに分解します。
Array
(
[0] => 8
[1] => 7
[2] => 6
[3] => 3
[4] => 2
)
for内では下の位から順に引き算を実行します。
最初は$i=4、$borrow=0なので
$ret_array[4]=Array[4]-Array[0]-0=2-8=-6となります。
マイナスの場合は上の位から1を借りてこないといけないので$borrow=1をセットします。
そして借りてきた1を使って現在の位を+10します。
これで$i=4の処理が完了となります。
次に$i=3の場合、$ret_array[3]を同様に計算します。
今度は$i=3、$borrow=1なので
$ret_array[3]=Array[3]-Array[1]-1=3-7-1=-5となります。
$borrowは使ったので0に戻します。
もっとも、答えがまたマイナスなのですぐに1に戻りますが。
同様に、$i=2、$i=1、$i=0と最後の桁まで繰り返して終了。
今度のkaprekar()は、せいぜい2桁の計算しかしていないにもかかわらず、メモリが許す限り大きな桁の計算が出来てしまいます。
出力例
Array
(
[0] => 32799999999999999999999999968
[1] => 76320999999999999999999987633
[2] => 97666332209999999998776633321
[3] => 98777666662110988873333322211
[4] => 98777655543332966665444322211
[5] => 88655533332110988876666444312
[6] => 97776643333210988766665332221
[7] => 98765554333331976666654443211
[8] => 88754333332110988876666654212
[9] => 97776654333320987666654332221
[10] => 98655543333320987666665444311
[11] => 98764333332110988876666653211
[12] => 98777654333331976666654322211
[13] => 88755543333320987666665444212
[14] => 97665433332110988876666543321
[15] => 98776543333320987666665432211
[16] => 98765543333320987666665443211
[17] => 98765433333210988766666543211
[18] => 98776543333320987666665432211=15
)
前回は計算できなかったこのくらい大きな桁の計算もできてしまいました。
このようにアルゴリズムを工夫することで、いろいろな場合において制限を回避することが出来るのですが、何故か工夫すればするほど人間にはわかりづらい表記になってしまうという不思議。
PR
トラックバック
トラックバックURL:
