Problem Solving►UVa

UVa 100 - The 3n + 1 problem

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

在每次查詢時一邊建表，為了加速，已經算出的長度就不重複計算，
並把過程中有出現過的數字，利用遞迴的概念(以stack去做)，其長度都一一找出。

1
2
3
4
5
6
7
8
int len = length[s.top()];
s.pop();
for (int j = 1; !s.empty(); j++, s.pop())
{
    now = s.top();
    if (now < N)
        length[now] = len + j;
}

Code

UVa 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <stack>
#define N 1000001
typedef long long LL;

int length[N] = {0, 1};
void build(int n)
{
    LL now = n, next;
    std::stack<LL> s;
    //for (int i = 2; i < N; i++) 也可以直接建完，速度較慢

    s.push(now);
    while (now != 1)
    {
        next = (now & 1) ? ((now << 1) + now + 1) : (now >> 1);
        s.push(next);

        if (next < N && length[next])
            break;

        now = next;
    }

    int len = length[s.top()];
    s.pop();
    for (int j = 1; !s.empty(); j++, s.pop())
    {
        now = s.top();
        if (now < N)
            length[now] = len + j;
    }
}

int main()
{
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);

    int i, j;
    while (scanf("%d%d", &i, &j) != EOF)
    {
        int max = 0, a, b;
        if (i < j)
            a = i, b = j;
        else
            a = j, b = i;

        for (; a <= b; a++)
        {
            //邊建邊查
            if (!length[a])
                build(a);
            if (length[a] > max)
                max = length[a];
        }

        printf("%d %d %d\n", i, j, max);
    }
    return 0;
}