POJ 1207 - The 3n + 1 problem


问题描述

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

现在给定一个区间,计算这个区间的所有数的循环数,把最大的循环数输出(输出的是整数 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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1260 - Pearls POJ 1260 - Pearls
POJ 1260 - Pearls Time: 1000MS Memory: 10000K 难度: 初级 分类: 动态规划 问题描述给出几类珍珠,以及它们的单价,要求用最少的钱就可以买到相同数量的,相同(或更高)质量的珍珠。 【规定买任
2011-11-16
下一篇 
POJ 1321 - Chess Problem POJ 1321 - Chess Problem
POJ 1321 - Chess Problem Time: 1000MS Memory: 10000K 难度: 初级 分类: DFS 问题描述无。 解题思路DFS,没想法就很难很难,有想法就很容易的题。 棋盘规则与否不是难点,无论规则
2011-11-13
  目录