Hailstone Sequence

2018-09-06  本文已影响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;
}

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

上一篇下一篇

猜你喜欢

热点阅读