PHP奇怪的问题与工作代码 [英] PHP Strange issue with working code

问题描述

有一种技术可以从(N)位代码中生成(N + 1)位代码的列表.

There is a technique by which the list of (N+1) bit codes can be generated from (N)-bit codes.

1. 以给定的顺序获取N位代码的列表，并将其命名为List-N
2. 逆转上述列表(List-N)，并命名新的反射列表:Reflected-List-N
3. 在原始列表(列表N)的每个成员前面加上0，然后将此新列表称为"A"
4. 在新列表(Reflected-List-N)的每个成员前面加上1，然后将此新列表称为"B"
5. 具有N + 1位的代码列表是列表A和B的串联.

上述步骤的演示:从2位神秘代码生成3位神秘代码列表

A Demonstration of the above steps: Generating the list of 3-bit Mystery Codes from 2-Bit Mystery Codes

1. 2位代码列表:00、01、11、10
2. 撤消/反映上面的列表:10、11、01、00
3. 为旧条目添加0:000、001、011、010前缀
4. 带有1、110、111、101、100的前缀反映列表
5. 连接在最后两个步骤中获得的列表:000、001、011、010、110、111、101、100

我找到了解决方法，但是当我输入65时出现错误

I found solution but when I enter 65 for example getting error

PHP Fatal error: Out of memory (allocated 538968064) (tried to allocate 20 bytes) in /home/pLR62k/prog.php on line 27

在Ideone上 http://goo.gl/WB3DKh

我在做什么错了?

<?php
function MysteryCodes($input){
    $initArr=array(0,1);
    if($input==1){
        return $initArr;
    }
    else {
        $list=array();
        $list[0]=$initArr;
        for ($i=1; $i<$input; $i++)
            {   
                $prevIndex=$i-1;
                $reflectedListN = array_reverse($list[$prevIndex]);
                $listA=prefixR($list[$prevIndex], '0');
                $listB=prefixR($reflectedListN, '1');
                $list[$i]=array_merge($listA, $listB);
            }
    }
    return array_slice($list[$input-1], -$input);
}



function prefixR($input, $prefix){
    $result=array();
    foreach($input as $value){
        $result[]=$prefix.$value;
    }
    return $result;
}

fscanf(STDIN, "%d", $inp);
if($inp>=1 && $inp<=65){
$result=MysteryCodes($inp);
$output="";
foreach($result as $key=>$value)
    $output.="$value\n";

fwrite(STDOUT, $output);
}   

推荐答案

您正在使用wayyyy的内存过多.创建一个包含所有元素的数组仅适用于小型N.

You're using wayyyy too much memory. Creating an array which holds all elements is only going to work for small N.

您在问题中说"2位神秘码" 是所有可能的2位组合.然后，您的算法将成为一种生成所有可能的N位组合的方法.对于N=65，组合的数量(因此是您要存储的元素的数量)为

You stated in your question that the "2-Bit Mystery Codes" are all four possible two-bit combinations. Your algorithm then becomes a method that generates all possible N bit combinations. For N=65, the number of combinations (and therefore, of elements you're trying to store) is

2^65 = 36893488147419103232 ≈ 3 * 10^19

很多.而且它甚至不算您正在执行的所有中间步骤.假设没有开销，您的列表将占用约30艾字节的内存.如果要生成这些数字，则必须将自己限制为较小的N，或者寻找另一种无需全部保存即可即时计算它们的方法.

That quite a lot. And it doesn't even count all the intermediate steps you're taking. Assuming no overhead, your list would take up about 30 Exabytes of memory. If you want to generate these numbers, you'll have to restrict yourself to smaller N or find another method of calculating them on the fly without saving them all.

这篇关于PHP奇怪的问题与工作代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！