美文网首页
Hailstone Sequence

Hailstone Sequence

作者: 徒步青云 | 来源:发表于2018-09-06 13:27 被阅读69次

    求解希尔顿序列(Hailstone Sequence),希尔顿序列问题是一个著名的数学问题,至今没有证明其正确性,也没证明其是错误的,即任何一个正整数N,如果是偶数的话就除以2,如果是奇数的话就乘以3再加上1,最后这个数都会变为1。其表达式如下:
    Hailstone(n) = \begin{cases} \{1\}, & \text{if n equal 1} \\ \{n\} \bigcup Hailstone(n/2), & \text{if n is even} \\ \{n\} \bigcup Hailstone(3n+1), & \text{if is odd} \end{cases}
    从中我们可以通过递归发现,每次对n这个数字进行判断奇偶性,采用不同的计算公式,举例说明:
    Hailstone(3) =\{3\} \bigcup Hailstone(3*3+1)\\ =\{3,10\} \bigcup Hailstone(10/2) \\ =\{3,10,5\} \bigcup Hailstone(5*3+1)\\ =\{3,10,5,16\} \bigcup Hailstone(16/2)\\ =\{3,10,5,16,8\} \bigcup Hailstone(8/2)\\ =\{3,10,5,16,8,4\} \bigcup Hailstone(4/2)\\ =\{3,10,5,16,8,4,2\} \bigcup Hailstone(2/2)\\ =\{3,10,5,16,8,4,2,1\}

    #include<iostream>
    
    using namespace std;
    
    int main(int argc,char* argv[])
    {
        int* hailstone = new int[100];
        int i;
        cin>>hailstone[0];
        for(i=1;i<100;i++){
            int prev = hailstone[i-1];
            if(prev==1)
                break;
            else if(prev%2==0)
                 hailstone[i]=prev/2;
            else
                 hailstone[i]=prev*3+1;
        }
    
        for(int j=0;j<i;j++)
            cout<<hailstone[j]<<" ";
    
        return 0;
    }
    
    

    有用不能证明这个程序的“有穷性”,故不能说该程序是一个算法。

    相关文章

      网友评论

          本文标题:Hailstone Sequence

          本文链接:https://www.haomeiwen.com/subject/rjqxgftx.html