529 . 考拉茲猜想

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dbGIs
這題出的好!唐可可給你一個讚

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

100.0% (6/6)

Tags

apcsc apcsc-loop

Description

未解決的數學問題：對所有自然數，如果它是奇數，則對它乘 3 再加 1，如果它是偶數，則對它除以 2，如此循環，最終都能夠得到 1。

考拉茲猜想（英語：Collatz conjecture），又稱為奇偶歸一猜想、3n+1 猜想、冰雹猜想、角谷猜想、哈塞猜想、烏拉姆猜想或敘拉古猜想，是指對於每一個正整數，如果它是奇數，則對它乘 $3$ 再加 $1$，如果它是偶數，則對它除以 $2$，如此循環，最終都能夠得到 $1$。

以上取自於維基百科。

為了驗證考拉茲猜想的正確性，請你寫出一個程式使其可以輸入一個數字，輸出考拉茲猜想的過程直到 $1$ 為止。

Input Format

輸入只有一行，裡面只有一個數字 $x$，表示請你驗證考拉茲猜想的起始數字。

  • $1 \le x \le 1000$，且 $x$ 為整數。

Output Format

輸出過程的格式，請參照以下格式
x -> 下一步的x -> ... -> 1 -> end，所有的數字以及箭頭都有空格，最後以換行結尾。
舉例來說，如果輸入為 $1$，則你該輸出一行 1 -> end。
如果輸入為 $18$，則你該輸出以下一行：
18 -> 9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end。

Sample Input 1

1

Sample Output 1

1 -> end

Sample Input 2

18

Sample Output 2

18 -> 9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
Submit
Back to Top