題目:電腦科學的問題常被列為某一特定類的問題(如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(); } }
鏈結到這頁!