The 3n + 1 problem
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 50648 | Accepted: 16059 |
Description
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.
Consider the following algorithm:
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
Consider the following algorithm:
1. input n 2. print n 3. if n = 1 then STOP 4. if n is odd then n <-- 3n+1 5. else n <-- n/2 6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).
Sample Input
1 10 100 200 201 210 900 1000
Sample Output
1 10 20 100 200 125 201 210 89 900 1000 174
Code:
import java.util.Arrays; import java.util.Scanner; public class Main { public static int Test(int n) { int count = 0; if (n == 1) { return 1; } count++; if (n % 2 == 0) { count += Test(n / 2); } else { count += Test(3 * n + 1); } return count; } public static void printNum(int m, int n) { int[] temp = new int[2]; temp[0] = m < n ? m : n; temp[1] = m > n ? m : n; int[] nums = new int[temp[1] - temp[0] + 1]; for (int i = temp[0]; i < temp[1] + 1; i++) { nums[i - temp[0]] = Test(i); } Arrays.sort(nums); System.out.print(m + " " + n + " " + nums[nums.length - 1]+"\n"); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { String str = cin.nextLine(); String[] str0 = str.split(" "); int m = Integer.parseInt(str0[0]); int n = Integer.parseInt(str0[1]); printNum(m, n); } cin.close(); } }
遇到了一个第一次看见的错误:Presentation Error
错误表示 运行结果正确,但是格式错误.
将该删的空格或者换行之类的去掉后就好了.
相关推荐
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
UVA 100题答案
如果 n 是奇数,把它乘 3 加1。 用新得到的值重复上述步骤,直到 n = 1 时停止。例如,n = 22 时该算法生成的序列是: 22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 人们猜想(没有得到证明)对于...
3N+1问题 c语言实现 挑战编程上的原题 考虑一下数列的生成办法.由n开始. 如果 n是偶数除以2. 如果是奇数, 除以3加1. 这样产生一个新的n, 长此以往,直到n = 1. 例如 n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8...
PAT 1001. 害死人不偿命的(3n+1)猜想 C实现
从键盘输入一个自然数n,将1至3n+2的自然数填入图2-1的圆框中,使得所有用线段相连的两个数之差的绝对值能产生数列1,2,…,3n+1。
将数论中3N+1猜想推广为3N+3k猜想。得到了3N+1猜想与3N+3k猜想的等价性。得到有关3N+3猜想的一些性质,3N+1猜想的推广、3N+3猜想的一些性质的建立对于研究4K+3型奇数在3N+3猜想压缩迭代中起到简化作用,同时也为3N+1...
叭啦 叭啦 巴拉 就是ACM100 3N+1 巴拉巴拉巴拉 叭啦 叭啦 巴拉 就是ACM100 3N+1 巴拉巴拉巴拉
继续(3n+1)猜想.sln
acm第100题 The 3n+1 problem #include <iostream> using namespace std; unsigned CyCle(unsigned m) { unsigned count = 1; while (m != 1) { if (m & 0x01) m = 3 * m + 1; else m = m / 2; ...
从键盘输入一个自然数n,将1至3n+2的自然数填入图2-1的圆框中,使得所有用线段相连的两个数之差的绝对值能产生数列1,2,…,3n+1。
C program that accepts the input of a positive integer m from the console and displays all all starting values n from 1 to m in tabular form
蛮力检查Collatz序列或3n + 1问题。 程序将查找具有最长Collatz序列的起始编号,直到指定的上限。 该代码有两种实现。 两者都是多线程的。 collatz.cpp使用共享内存库OpenMP,而mpi_collatz.cpp使用...
3n + 1 problem 151 - Power Crisis -> 约瑟夫问题DP 问题 10607 - Joseph's Cousin -> 约瑟夫问题变形 532 - Dungeon Master -> BFS类型的题目 299 - Train Swapping 10038 - Jolly Jumpers 10193 - All You Need ...
C实用代码
(3N+1 问题) 又名3N+1问题。 臭名昭著的 Collatz 猜想说,如果您从任何正整数开始,您将始终以这个循环结束。 结果,在某些时候,最终会出现在4,2,1的循环中。 这是如何运作的? 我建议您观看 Veritasium ...
3n+1个控制点 每四个点生成一条曲线 每条曲线分成200小段画出红色曲线 第二种随机曲线生成:随机三次Bezier曲线 3n+1个控制点 每四个点生成一条曲线 第三种随机曲线生成:随机三次B样条曲线 3n+1个控制点 每四个点...
The Generalized Petersen Graph P(n,7) is ((3n+6)/2,3)-Antimagic