UVa 100 : 3n+1

Posted on | In |  
Symbols : 671 字

題目 : UVa

對一個整數 k，利用以下 2 個規則
可以得出一個特定的序列 Sk : A1、A2 . . . An，其中 An = 1

規則

  1. 當 Ak 是偶數 : Ak = Ak-1 / 2
  2. 當 Ak 是奇數 : Ak = 3 * Ak-1 + 1

本題目會輸入 2 個正整數 a 、 b，並求出在 [ a , b ] 區間中，序列長度最長者

例如 : 以下列舉出前幾個數的序列長度

Sk 1 2 3 4 5 6 7 8 9 10
長度 1 2 8 3 6 9 17 4 20 7

因此若輸入 1 10
答案就是 20 ( S7 )

測資
Input :

1 10
100 200
201 210
900 1000

Output :

1 10 20
100 200 125
201 210 89
900 1000 174


解法

很簡單的算術題，但是如果真的傻傻的每次都從 a “ 重新 “ 算到 b，會浪費掉很多時間
因為題目會給很多組測資，裡面一定會有大量重複的區間

因此，我們可以用空間換取時間，把算過的 Sk 給記錄下來
這邊我選擇只記錄到 S10000，因為題目給定的輸入範圍就是 ( 0, 10000 )
但是我們有可能會遇到超過 10000 的數字，比如 9999 -> 29998 (爆了)
所以超出 10000 的數字我們還是必須要土法煉鋼
但在 10000 內的數字我們可以很快的就得到答案

例如 :
上面我們已經紀錄了 1 ~ 10 的長度了
現在要計算 64
S64 : 64 -> 32 -> 16 -> 8
在這裡遇到 8 ( 已經紀錄過 )，因此剩下的部分就會跟 S8 重疊
所以長度就是 S64 = 3 + S8 = 7


程式碼

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
	Solution() : length(MAX_SIZE + 1, 0)
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);

		buffer.reserve(1000);
	}

	int calculate(int n)
	{
		int len = 0;
		int k;

		buffer.clear();

		for (k = n; k != 1; ++len)
		{
			// 如果遇到記錄過的點，恭喜你，剩下的部分就可以不用計算了
			if (k <= MAX_SIZE && length[k] != 0)
			{
				len = len + length[k] - 1;
				break;
			}

			if (k & 0x01)
				k = 3 * k + 1;
			else
				k >>= 1;

			// 將過程中經過的點記錄下來
			buffer.push_back(k);
		}

		length[n] = ++len;

		for (k = 0; k < buffer.size(); ++k)
			if (buffer[k] <= MAX_SIZE)
				length[buffer[k]] = len - k - 1;
		
		return len;
	}

private:
	const int MAX_SIZE = 1000000;
	vector<int> length;
	vector<int> buffer;
};

int main(void)
{
	Solution s;

	int l, r;
	int max;
	int tem;

	int sm, b;

	while (cin >> l)
	{
		cin >> r;

		max = 0;

		// 確保 sm 是小的， b 是大的
		if (l > r)
		{
			sm = r;
			b = l;
		}
		else
		{
			sm = l;
			b = r;
		}

		for (auto k = sm; k <= b; ++k)
		{
			// 得到 "每一個" 數字的序列長度
			tem = s.calculate(k);

			// 記錄最大的
			if (tem > max)
				max = tem;
		}

		cout << l << " " << r << " " << max << endl;
	}

	return 0;
}
0%