学步园

有这样一道题：

初始时，给定任意一N，对任意大于0的数n，
①：若其为偶数，n=n/2；
②：若其为奇数，则n=n*3+1；
重复该过程，直到N==1；在该过程中所产生的序列：N……1 的长度即为所求。例如，当N=22时，所产生序列为：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1。长度为16，即是所求。该题假设所有的关于该N的数字均会以1结束。

这里是我的算法，求出1~100之内所有数字的该序列长度。对i，其序列长度为A[i]。因为对数字99，其3N+1为298，所以声明数组长度为300。结果为：打印1到100的序列的长度值。这样的算法好像被称为动态规划……
算法的正确性暂且不论。使我惊奇的是：

第一个MARK处的for并没有如我所想的那样做够MAXSIZE此，通过测试，只做了2次……Why？

最神奇的是：第二个MARK处的for，一次都没有做……在VC中运行是空白……点击运行出来的并不是如我所想那样，打印100个数字，而是什么都没有，直接是press any key to continue……测试了下，给我感觉就是，在第一个MARK处的for完以后程序就直接退出了，没有做到第二个MARK处……第一个MARK处的for完就再也没有做什么了……

开始以为是数组开辟的有问题，测试了下，完全OK。后来以为是第一个MARK的for将MAXSIZE改变了，但测试了并没有改变……最无语的是，我不能测试第一个for完成后发生了什么……所有的位于第一个for 之后的代码全部不会运行……

以下为先前错误的代码：

#include <stdio.h><br /> #include <stdlib.h><br /> #define MAXSIZE 100</p> <p>int main(void){<br /> //本算法用于……<br /> int A[3*MAXSIZE]={0};<br /> int i,j;<br /> int pa;</p> <p> for(A[1]=1,i=1;i<=MAXSIZE;i++){ //MARK!!<br /> j=i; pa=j;<br /> while(A[j]==0){<br /> A[j]=pa; pa=j;<br /> if(j%2==0) j/=2;<br /> else j=j*3+1;<br /> }//while<br /> while(pa!=j){<br /> A[pa]=A[j]+1;<br /> j=pa; pa=A[pa];<br /> }//while<br /> while(j<=MAXSIZE&&A[2*j]==0){<br /> A[2*j]=A[j]+1;<br /> j*=2;<br /> }//while<br /> }//for</p> <p> for(i=1;i<=MAXSIZE;i++) printf("%d ",A[i]); //MARK!!!</p> <p> return EXIT_SUCCESS;<br /> }//main

修改后的代码如下：

#include <stdio.h><br /> #include <stdlib.h><br /> #define MAXARRAYSIZE 10000<br /> #define MAXLENGTH 100</p> <p>int main(void){<br /> //本算法用于……<br /> int A[MAXARRAYSIZE]={0};<br /> int i,j;<br /> int pa;<br /> int tmp;<br /> int cnt=0;</p> <p> for(A[1]=1,i=1;i<=MAXLENGTH;i++){<br /> j=i; pa=j;<br /> while(A[j]==0){ //while-1<br /> A[j]=pa; pa=j;<br /> if(j%2==0) j/=2;<br /> else j=j*3+1;<br /> cnt++;<br /> }//while<br /> while(pa!=j){ //while-2<br /> tmp=A[pa];<br /> A[pa]=A[j]+1;<br /> j=pa; pa=tmp;<br /> }//while<br /> while((j<=MAXARRAYSIZE)&&(2*j<MAXARRAYSIZE)&&(A[2*j]==0)){ //while-3<br /> A[2*j]=A[j]+1;<br /> j*=2;<br /> }//while<br /> }//for</p> <p> for(i=1;i<=MAXLENGTH;i++) printf("%d ",A[i]);</p> <p> return EXIT_SUCCESS;<br /> }//main

测试了一上午，终于找到了问题：

问题在于：
①：while-2中
在while-1中，我本来想要用pa和j来共同虚拟成栈的结构，以便在while-2中使用。while-2很OK，完全没问题。但是在while-2中，使用该虚拟栈进行回溯时，出了问题。在我原来的代码中，我在进行A[pa]=A[j]+1;之前并没有保存A[pa]的值，而A[pa]正是虚拟栈中回溯不可缺少的。在没有保存A[pa]的情况下进行A[pa]=A[j]+1，而后又执行pa=A[pa]进行回溯。出错！

②：while-3中
在while-3中，本意是凭借偶数这一链进行上寻，以尽可能减少while-2的循环量。但很不幸的是，数组越界。忘了加条件(2*j <MAXARRAYSIZE)。数组越界，C中很常见的错误，我却没有想到……汗啊~

③：临时数组A[]的大小问题
开始我以为所使用的元素的下标不会超过298，因为99*3+1=298，所以只使用了300大小的临时数组。后来看到所说，临时数组太小，数组所用元素应该在4000~5000，于是使用重新使用了5000大小的数组。运行，成功！但仔细一看，发现，大约有10多个数字的数据有问题，比如，27的长度达到了好几百万……于是另编写了一超级简单的测试程序，使用最笨的办法进行计算发现27的长度只不过100多，但在求其长度的过程中，所使用的临时元素达到了9232……很显然临时数组的大小还是不够……于是使用那个最笨的算法，将所用出错的数字重新算了遍，以期找到所需要的数组的最大元素数。结果发现……很神奇，在100之内，所有的那些我先去的算法中出错的，将长度错误的计算做好几万好几十万的数字在计算中，所使用的最大数组元素的下标皆是9232……好神奇……为什么？巧合？或者是有什么定理？
于是将临时数组大小重设为10000……运行，OK，没问题！

另，有人可能会说，用10000个单元的临时数组来，实际上所要求的不过是1~100共100个数组而已，为求这100个数字却要多用9900个单元，是不是有点得不偿失……
我觉得这很值得!
我使用我这个麻烦的，逻辑晦涩的，浪费了9900个数组单元的程序，计算1~100这一百个数字的长度时，while-2，也就是判断奇数偶数并作出相应的计算的核心循环的循环次数只有198次。
而我使用那个超级简单的，逻辑简洁的，没有用到一个数组空间的程序，计算1~100这一百个数字的长度时，while-2的循环次数是3167次……
而如果是计算1~1000之内的数字呢？1~10000之内的数组呢？……我相信3167次的那个算法至少应该是以O(N)增长的。而我的算法，貌似应该是O(N)……
基于此，我觉得，这9900个数组单元浪费的值得……

下面是我的用于测试的代码（因为用于测试所以没有写多规范，已经被我改的面目全非了……）

#include <stdio.h><br /> int cnt=0;</p> <p>void func(int i){<br /> while(i!=1){<br /> printf("%d ",i);<br /> if(i%2==0) i/=2;<br /> else i=i*3+1;<br /> cnt++;<br /> }//while<br /> }//func</p> <p>void main(){<br /> int i=1;<br /> while(i++<=100) func(i);<br /> printf("/n%d",cnt);<br /> }//main<br />

我相信还有更好的代码，可以将那9900个单元减少或者不使用……期待ing……

要小心呐~做事太马虎了……为了找到这些错误，愣是把30多句语句增加到了40多句……太菜了我……

另，补充一点，关于题目中所说，这样的序列都会以1结尾，是一个数学界的假设，还没有得到证实……