POJ1207-The 3n plus 1 problem

[POJ] [INDEX] [1207] [The 3n + 1 problem]

[Time: 1000MS] [Memory: 10000K] [难度: 水题] [分类: 无]

---

问题描述

根据给定的算法，可以计算一个整数的循环数

现在给定一个区间，计算这个区间的所有数的循环数，把最大的循环数输出（输出的是整数 A 的循环数，而不是输出整数 A）

解题思路

注意的只有一点：

输入的两个区间端点不一定是从小到大输入的，因此要先对这两个数排一下序。

AC 源码

Download Link

/*
	Author:     Exp
	Date:       2017-11-29
	Code:       POJ 1207
	Problem:    The 3n plus 1 problem
	URL:		http://poj.org/problem?id=1207
*/

/*
	题意分析：
	 给定了计算整数n的所有循环数算法（循环数列包括n自身）：
	 1. 	 input n
	 2. 	 print n
	 3. 	 if n = 1 then STOP
	 4. 		 if n is 奇数 then   n = 3n+1
	 5. 		 else   n = n/2
	 6. 	 GOTO 2

	 再给定范围 [i, j] 且 i,j∈(0,10000)
	 求 [i, j] 之间拥有最多循环数的整数n的循环数的个数
*/

#include <iostream>
using namespace std;


/* 
 * 计算整数的循环数个数
 * @param num 整数
 * return 循环数个数
 */
int cycleCnt(int num);


int main(void) {
	int i, j;
	while(cin >> i >> j) {
		int min = (i <= j ? i : j);
		int max = (i > j ? i : j);

		int maxCnt = -1;
		for(int n = min; n <= max; n++) {
			int cnt = cycleCnt(n);
			maxCnt = (maxCnt < cnt ? cnt : maxCnt);
		}
		cout << i << " " << j << " " << maxCnt << endl;
	}

	//system("pause");
	return 0;
}


int cycleCnt(int num) {
	int cnt = 1;
	while(num > 1) {
		if(num % 2 == 1) {
			num = 3 * num + 1;

		} else {
			num /= 2;
		}
		cnt++;
	}
	return cnt;
}

---

版权声明

　　

• Site: http://exp-blog.com
• Mail: [email protected]

---