20CN网络安全小组论坛 - 编程破解

论坛: 编程破解标题: ACM试题

作者: kert_t8 [kert_t8]

论坛用户

The 3n + 1 problem

Background
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.

The Problem
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then
5. else
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 (including the 1). 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.

The 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 1,000,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.

The 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

地主发表时间: 04-12-10 16:58

回复: kert_t8 [kert_t8]

论坛用户

3n+1问题
背景：
计算科学的问题通常被分为好几类（例如：NP，不可解，递归等等），但在这个题目里有一个不知道属于哪一类的算法，你需要对他的所有可能的输入进行分析

以下是给出的算法：
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then
5. else
6. GOTO 2

给定输入22，将会产生下面的输出序列 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
猜想这个算法是对于所有输入都是可以中止的（当1打印出来的时候）（译者注：不会出现死循环）。尽管算法有所简化，但是这个猜想是否正确还没有定论。然而，有一点是可以肯定的，那就是对于所有的输入n， 0<n<1,000,000 ，以上猜想是正确的。（事实上的数字远远超过了此限制）

给定输入n，我们可以计算出输出数列的长度（包括1），这个长度称为n的 [black]周期[\black],对于22来说，他的[black]周期[\black]是16

下面你将要编程实现的是：任意给出两个数i,j，计算出包括i,j在内的i,j之间所有数的[black]周期[\black]的最大值。

输入：
输入将是一系列的(i,j)有序数对。一对一行。所有的整数将在 0到1,000,000之间。
你应该读入每一对数，然后计算出[black]最大周期[\black]

输出：
对于每一对数（i,j），你应该输出 i,j 以及你所计算出来的对应的[black]最大周期[\black]。这三个数应该至少是用一个空格分隔，三个数应该在同一行（因为）。i,j的顺序应该和它们出现在输入中的顺序一样，[black]最大周期[\black]应该跟在他们后面

外国人说话真他妈罗嗦，我都受不了了

例子：

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

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

B1层发表时间: 04-12-10 17:16

回复: kert_t8 [kert_t8]

论坛用户

我的 Possible Solution:
没有严格按照他的输入输出格式来写，但是主要问题的解决做出来了，从键盘输入i,j，然后打印出最大周期。上面的代码应该放在getter.java的文件里，下面的放在pson.java里

基本思想：
数组Data存放周期.n对应的周期就在Data[n]里面。如果发现周期是0，那么就相当于不知道，就计算。每次计算的中间步奏也放到Data里面保存。数组的大小是1000000，如果要计算的数超过这个大小，就抛开Data不管，直接进行计算。
maxLength使用一个循环，找出最大的周期，circleLength使用第归，找出具体每一个属对应的周期。

import java.io.*;

class getter {

public static void main(String[] args) {

}

public static String getString(InputStream in){
String retString;
try{
InputStreamReader streamRead = new InputStreamReader(in);
BufferedReader stringReader= new BufferedReader(streamRead);
retString = stringReader.readLine();
}
catch(IOException e){
System.out.println("String error");
retString="ERROR";
}
return retString;
}

public static int getInt(InputStream in){
int retInt;
Integer holdInt;
try{
String intStr = getter.getString(in);
holdInt = Integer.valueOf(intStr);
retInt = holdInt.intValue();
}
catch(NumberFormatException e){
System.out.println("WARNING:not valid integer");
retInt = 0;
}
return retInt;
}
}

//////////////////////////////////////////////////////////////////////////

public class pson {
public static void main(String arg[]) {
int[] Data = new int[1000001];
int i = getter.getInt(System.in);
int j = getter.getInt(System.in);
pson vec = new pson();
int max = vec.maxLength(i,j,Data);
System.out.println(max);
}

public pson(){}

public int maxLength(int i, int j, int[] Data) {
int Max=0;
for (int x=i;x<=j;x++) {
System.out.println(x);
if (Data[x]==0)
Data[x]=circleLength((double)x,Data);
if (Data[x]>Max)
Max=Data[x];
}
return Max;
}

public int circleLength(double n, int[] Data) {
double x = n;
if (x % 2 == 0)
x=x/2;
else
x=3*x+1;
if (x==1)
Data[(int)x]=1;
if (x>1000000)
return circleLength(x,Data)+1;
if (Data[(int)x]==0)
Data[(int)x]=circleLength(x,Data);
if (n>1000000)
return Data[(int)x]+1;
Data[(int)n]=Data[(int)x]+1;
return Data[(int)n];
}
}

�

B2层发表时间: 04-12-10 17:25

回复: kert_t8 [kert_t8]

论坛用户

1，有没有更快的方法？
2，用什么样的方法，才可以把字体加黑！！！我faint

决定以后要多多练习，争取能把ACM的题都做一边，因为今天早上醒来的时候，莫名其妙的突然觉得自己的水平好低，真得觉得要是再不努力，将来就没有前途了，现在IT竞争那么激烈.....
谁能告诉我一个本科生，水平一般，在中关村当个小程序员一个月能拿多少钱？养得起自己么？我突然觉得好怕

算了算了，半夜两点了，睡觉，困~~~~~~~~~~~~~

B3层发表时间: 04-12-10 17:30

回复: virgoshaka [virgoshaka]

论坛用户

先问一下哦，这是几几年的题目阿？

B4层发表时间: 04-12-11 23:05

回复: kert_t8 [kert_t8]

论坛用户

不知道，我到网上下了一个ACM题库全集，然后从头开始做

管它呢，有些东西是不会变的，陈而弥久

B5层发表时间: 04-12-12 04:20

论坛: 编程破解