题解 P5727 【【深基5.例3】冰雹猜想】

GaryH · 2020-01-01 22:15:40 · 题解

题解

给大家科普一下，就是main()函数是可以用来递归的。

那我们就可以这样做：

#include<bits/stdc++.h>
using namespace std;
int n,p,top,a[10001];
//p代表是否输入过
int main(){
    if(!p){
        cin>>n;p=1;
        a[++top]=n;
            //输入并存进第一次结果
    }
    if(n==1){
        for(int i=top;i>=1;--i){
            cout<<a[i]<<' ';
        }
            //输出结果
        return 0;
            //用main()函数递归一定要退出！！
    }
    if(n%2==1){
        n=n*3+1;
    }else{
        n/=2;
    }
    //判断是奇数还是偶数，并进行相应处理
    a[++top]=n;
    //存进结果
    main();//递归调用
}

当然，这样既费时间又费空间。

设 k = 该算法运算次数 ，则： (注意，k一般不等于n)

显而易见，此方法的时间复杂度为