練習 - The 3n+1 problem

題目:電腦科學的問題常被列為某一特定類的問題(如NP,不可解,遞迴)。這個問題是請你分析演算法的一個特性:演算法的分類對所有可能的輸入是未知的。
考慮下述演算法:

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

列出輸入22,列印下述數字序列 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1。

人們推想,對於任何完整的輸入值,上述演算法將終止(當列印1時)。儘管這一演算法很簡單,但還不清楚這一猜想是否是正確的。然而,目前已經驗證,對所有的0 < n < 1,000,000的整數,該命題正確。

給定一個輸入n,確定在1被列印前列印數字的個數是可能的。這樣的個數稱為n的迴圈長度。在上述例子中,22的迴圈長度是16。

對於任意兩個整數 i 和 j,請你計算在 i 和 j 之間的整數中迴圈長度的最大值。

輸入:輸入是整數 i 和 j 組成的整數對序列,每對一行,所有整數小於 10,000,大於0。

輸出:對輸入的每對整數 i 和 j,請輸出 i、j 以及在 i 和 j 之間(包活 i 和 j )的所有整數中迴圈長度的最大值。這三個數字在一行輸出,彼此間至少用一個空格分開。在輸出中 i 和 j 按輸入的次序出現,然後是最大的迴圈長度。

import java.util.Scanner;

public class The3N1Problem {
	
	public The3N1Problem() {
			Scanner scanIn;
			int x, y, z, length, max = 0;
			scanIn = new Scanner(System.in);
			x = scanIn.nextInt();
			y = scanIn.nextInt();
			
			if(x > 0 && x < 10000 && y > 0 && y < 10000) {
				for(int i = Math.min(x, y); i <= Math.max(x, y); i++) {
					length = 1;
					z = i;
					while (true) {
						if(z == 1) break;
						length++;
						if(z % 2 == 1) {
							z = (3 * z) + 1;
						} else {
							z = z/2;
						}
					}
					max = Math.max(length, max);
				}
				
				System.out.printf("%d %d %d", x, y, max);
			} else {
				System.out.println("輸入的數值必須小於10,000和大於0");
			}
	}
	
	public static void main(String[] args) {
		The3N1Problem problem = new The3N1Problem();
	}

}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

*

驗證碼 * Time limit is exhausted. Please reload CAPTCHA.

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料