首页 > ACM题库 > HDU-杭电 > HDU 4484-Hailstone HOTPO-记忆化搜索-[解题报告]HOJ
2015
07-16

HDU 4484-Hailstone HOTPO-记忆化搜索-[解题报告]HOJ

Hailstone HOTPO

问题描述 :

The hailstone sequence is formed in the following way:

(1) If n is even, divide it by 2 to get n’
(2) If n is odd, multiply it by 3 and add 1 to get n’

It is conjectured that for any positive integer number n, the sequence will always end in the repeating cycle: 4, 2, 1, 4, 2, 1,… Suffice to say , when n == 1, we will say the sequence has ended.

Write a program to determine the largest value in the sequence for a given n.

输入:

The first line of input contains a single integer P, (1<= P <= 100000), which is the number of data set s that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of two space separated decimal integers. The first integer is the data set number. The second integer is n, (1 <= n <= 100,000), which is the starting value.

输出:

The first line of input contains a single integer P, (1<= P <= 100000), which is the number of data set s that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of two space separated decimal integers. The first integer is the data set number. The second integer is n, (1 <= n <= 100,000), which is the starting value.

样例输入:

4
1 1
2 3
3 9999
4 100000

样例输出:

1 1
2 16
3 101248
4 100000

题意:

给定一个数a,如果是奇数则 a=a×3+1 偶数 a=a/2 ; 直到a==1为止,问a的最大值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

using namespace std;
const int N = 50000009;
int ans[N];
int find(int n)
{
    if(n<N)
    {
        if(n==1) return 1;
        if(ans[n]) return ans[n];
        if(n&1) ans[n] = find(n*3+1);
        else
        {
            int t = find(n>>1);
            ans[n] = max(n,t);
            return ans[n];
        }
        return ans[n];
    }else
    {
        if(n&1) return find(n*3+1);
        else return max(n,find(n>>1));
    }
    return n;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    ans[1] = 1;
    int cas,n,a;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&a,&n);
        printf("%d %d\n",a,find(n));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/binwin20/article/details/8454843