#UVa:100-The 3n + 1 problem

灆洢 2011-11-24 07:48:54

題目大綱

題目表示有一個演算法在使用者給予一個數字n後,會進行下面的步驟:

  1. 輸入 n
  2. 印出 n
  3. 如果 n = 1,則循環結束。
  4. 如果 n 是奇數,那麼下一個循環的 n 就會是 3 * n + 1
  5. 否則下一個循環 n 就會是 n / 2
  6. 從第 2 步進入下一次循環。

例如:22,根據上述的演算法可得數列:22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

題目會給予ij兩個數字,想知道ij的區間中,誰代入上面的演算法後可以得到最長的數列。

測試資料

輸入資料

1 10
100 200
201 210
900 1000

輸出資料

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

題目網址

UVa Online Judge

解法思考

照著題目所說的去遞迴即可得解。

解法程式碼

C++ (0.310s)

/*******************************************************/
/* UVa 100 The 3n+1 problem                            */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2011/11/23                                 */
/* (Modified at 2020/08/27).                           */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int cyclelength(int n) {
  if (n == 1) {
    return 1;
  }
  else if (n % 2) {
    return 1 + cyclelength(3 * n + 1);
  }
  else {
    return 1 + cyclelength(n / 2);
  }
}

int main() {
  int i, j;
  while (scanf("%d%d", &i, &j) != EOF) {
    int maxLength = 0;
    int minValue = (i < j) ? i : j;
    int maxValue = (i > j) ? i : j;

    for (int value = minValue ; minValue <= maxValue; ++minValue) {
      int termLength = cyclelength(minValue);
      maxLength = (termLength > maxLength) ? termLength : maxLength;
    }

    printf("%d %d %d\n", i, j, maxLength);
  }
  return 0;
}

參考網址

Lucky貓的 UVA(ACM)園地

發表迴響

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