最省納智捷1年新車83萬起直擊★美車模手癢不小心...法人:14檔今年本業虧定了色令人昏 喜會女網友悲...
2012-03-05 18:59:37 人氣(173) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][JAVA][Sanner] 371 - Ackermann Functions

0
收藏
0
推薦

Ackermann Functions 

An Ackermann function has the characteristic that the length of the sequence of numbers generated by the function cannot be computed directly from the input value. One particular integer Ackermann function is the following:

displaymath32

This Ackermann has the characteristic that it eventually converges on 1. A few examples follow in which the starting value is shown in square brackets followed by the sequence of values that are generated, followed by the length of the sequence in curly braces:

     [10] 5 16 8 4 2 1 {6}
     [13] 40 20 10 5 16 8 4 2 1 {9}
     [14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}
     [19] 58 29 88 44 22 ... 2 1 {20}
     [32] 16 8 4 2 1 {5}
     [1] 4 2 1 {3}

Input and Output

Your program is to read in a series of pairs of values that represent the first and last numbers in a closed sequence. For each closed sequence pair determine which value generates the longest series of values before it converges to 1. The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long. The last pair of values will be 0, 0. The output from your program should be as follows:

Between L and H, V generates the longest sequence of S values.

Where:

L = the lower boundary value in the sequence

H = the upper boundary value in the sequence

V = the first value that generates the longest sequence, (if two or more values generate the longest sequence then only show the lower value) S = the length of the generated sequence.

In the event that two numbers in the interval should both produce equally long sequences, report the first.

Sample Input

  1 20
 35 55
  0 0

Sample Output

Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.


import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int L, H, i, tmp;
while(keyboard.hasNext()) {
L = keyboard.nextInt();
H = keyboard.nextInt();
if(L > H) {
tmp = L;
L = H;
H = tmp;
}
if(L == 0 && H == 0)
break;
int longest = 0, v = 0;
for(i = L; i <= H; i++) {
tmp = function((long)i);
if(tmp > longest) {
longest = tmp;
v = i;
}
}
System.out.printf("Between %d and %d, %d generates the longest sequence of %d values.\n",
L, H, v, longest);
}
}
public static int function(long n) {
int length = 0;
do {
if((n&1) != 0)
n = n*3+1;
else
n /= 2;
length++;
} while(n != 1);
return length;
}
}

371Ackermann Functions
台長:Morris
人氣(173) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][JAVA][System.in.read] 371 - Ackermann Functions
此分類上一篇:[UVA][JAVA][Biginteger] 619 - Numerically Speaking

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文