题目:The following iterative sequence is defined for the set of positive integers:
n n/2 (n is even)
n 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
(克拉茨问题,求一百万内的一个数,使其经过克拉茨问题的运算后得到的序列最长)
public class Problem14 {
private int[] counts;
private int num;
public Problem14(int num){
this.num = num;
counts = new int[num];
}
public static void main(String[] args) {
int range = 1000000;
Problem14 p = new Problem14(range);
int cmp1 = 0;
int cmp2 = 0;
int r = 0;
int tmp = 0;
long st1 = System.nanoTime();
for(int i = 1; i<=range; i++){
tmp = p.comlen(i);
if(tmp>cmp1){
cmp1 = tmp;
r = i;
}
}
long et1= System.nanoTime();
System.out.println(r);
/*
long st2 = System.nanoTime();
for(int i = 1; i<=range; i++){
tmp = p.len(i);
if(tmp>cmp2){
cmp2 = tmp;
r = i;
}
}
long et2= System.nanoTime();
System.out.println(r);
*/
//System.out.println(p.getCounts(1000000));
System.out.println(et1-st1);
//System.out.println(et2-st2);
}
public int len(int n){
long copy = n;
int len = 1;
while(copy != 1){
if(copy%2==0){
copy /= 2;
if(copy<=num){
int flag = (int)copy;
if(counts[flag-1] != 0){
len += counts[flag-1];
break;
}
}
len++;
}else{
copy = 3*copy+1;
if(copy<=num){
int flag = (int)copy;
if(counts[flag-1] != 0){
len += counts[flag-1];
break;
}
}
len++;
}
}
counts[n-1] = len;
return len;
}
/*
public int comlen(int n){
long copy = n;
int len = 1;
while(copy != 1){
if(copy%2==0)
copy /= 2;
else
copy = 3*copy+1;
len++;
}
return len;
}
*/
}
我的想法是这样的:
按照常规做法,只需计算一百万内各个自然数的Collatz数列,然后比较即可。但这样其实重复了一些过程,比如题中例子:
13 40 20 10 5 16 8 4 2 1
自然数从13到20的运算是是之前没出现过的,但到了自然数10,不难发现在计算13之前是计算过10的Collatz数列的长度
的,所以这个数列计算到10其实可以不必计算了,只需把预先存储起来10的Collatz数列的长度加上13到20这过程中产生
自然数个数就可以了。
分享到:
相关推荐
Chapter 14. Web-Based Problem Solving Process Chapter 15. Software Tool Development Illustration Chapter 16. Software Tools for Correct Program Development Part 5 Computer Operation by Problem ...
13.Algorithm Gossip: 背包问题(Knapsack Problem 14.Algorithm Gossip: 蒙地卡罗法求 PI 15.Algorithm Gossip: Eratosthenes 筛选求质数 16.Algorithm Gossip: 超长整数运算(大数运算). 17.Algorithm Gossip: 长...
14. If the two ISPs do not peer with each other, then when they send traffic to each other they have to send the traffic through a provider ISP (intermediary), to which they have to pay for carrying ...
C++ Programming From Problem Analysis to Program Design 8th 最新版2018 涵盖最新C++ 14标准 高清PDF 1400多页
14 Map Coloring & Chromatic Number......Page 271 iLLusTrATinG The TheOrem......Page 273 eArLy ATTemPTs AT PrOOf......Page 275 summAry Of evenTs ThAT LeD TO The DefiniTiOn AnD sOLuTiOn TO The fOur ...
Benny Kjr Nielsen and Allan Odgaard fbenny, dug@diku.dk February 14, 2003 The main subject of this thesis is the so-called nesting problem, which (in short) is the problem of packing arbitrary two-...
机器学习基石10 - 1 - Logistic Regression Problem (14-33).mp4
C++ Recipes: A Problem-Solution Approach is a handy code cookbook reference guide that cover the latest C++ 14 as well as some of the code templates available in the latest Standard Template Library ...
0-1-knapsack-problem-master (14)c.zip
Chapter 14. Exception Handling. Chapter 15. Recursion. Chapter 16. Searching and Sorting. Chapter 17. Linked Lists. Chapter 18. Stacks and Queues. Appendix A. Reserved Words. Appendix B. Operator ...
by the standard IEEE benchmark systems with 14, 30, 57, 118, and 300 buses as well as several randomly generated systems. Since this condition is hard to study, a sufficient zero-duality-gap condition...
CHAPTER 14: STRING ALGORITHMS CHAPTER 15: ALGORITHM DESIGN TECHNIQUES CHAPTER 16: BRUTE FORCE ALGORITHM CHAPTER 17: GREEDY ALGORITHM CHAPTER 18: DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER CHAPTER 19: ...
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition) 3rd Edition ...14. Files, Streams, and Input/Output Techniques. 15. Sockets and Networking. 16. Data Structures: Lists, Stacks, and Queues.
C++ Programming: From Problem Analysis to Program Design By 作者: D. S. Malik ISBN-10 书号: 1337102083 ISBN-13 书号: 9781337102087 Edition 版本: 8 出版日期: 2017-02-13 pages 页数: 1491 Contents ...
Designing an efficient algorithm to solve a computer science problem is a skill of Computer programmer. This is the skill which tech companies like Google, Amazon, Microsoft, Adobe and many others ...
运行CATIA2018主程序setup.exe时,报错setup:Problem with VC11 Runtime installation
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition) 3rd Edition ...14. Files, Streams, and Input/Output Techniques. 15. Sockets and Networking. 16. Data Structures: Lists, Stacks, and Queues.
近似求pi
load shedding scheme for IEEE 14 and 118 bus test systems. In addition to having better solution, the global property of the proposed approach plays an important role in on-line applications. ...