ลำดับ Collatz สามารถสร้างได้โดย 3 เงื่อนใข 1.ถ้า n = 1 ให้ หยุด
2.ถ้า n เป็นเลขคู่ ให้ n/23.ถ้า n เป็นเลขคี่ ให้ 3n+1
เช่น n = 13 ลำดับก็จะเป็น 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 เมื่อ n = 13 ลำดับนี้จะมีความยาว = 10 โจทย์ข้อนี้ต้องการให้เราหาความยาวของลำดับที่มากที่สุด ที่ถูกสร้างโดยเลขที่ <= n
นั่นหมายความว่า ถ้า n เป็น 13 เราจะต้องไล่หาลำดับของ 13 , 12 , 11 ,10 ,...,1 แล้วดูว่าลำดับไหนมีความยาวมากที่สุด
แนวคิด ถ้ามองโจทย์ดีๆแล้วเมื่อเราสร้าง Collatz ของ 13 เราจะสร้างของ 40,20,10,5,16,8,2,1 เช่นเดียวกัน เพราะฉะนั้นเราสามารถใช้เทคนิคการ Memoization เข้ามาช่วยได้ จะทำให้เราสามารถหาลำดับ Collatz ได้ไวขึ้นมาก เมื่อเราหาได้แล้วเราจะต้องไล่ตั้ง 1 จนถึง n เพื่อหาว่าตัวไหนมากสุด แต่ถ้าหากคิดดีๆแล้ว
ถ้าเราจำค่าความยาวที่มากสุดแล้วนำไปเปรียบเทียบกับตัวถัดไปเรื่อยๆ เราก็สามารถทำการ precompute ทุกคำตอบได้เหมือนกัน
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| #include <cmath> | |
| #include <cstdio> | |
| #include <cstring> | |
| using namespace std; | |
| static int cnt[10000000]; | |
| int collatz(long long n) | |
| { | |
| if(n < 10000000 && cnt[n] != 0) | |
| return cnt[n]; | |
| int result; | |
| if(n%2 == 0) | |
| result = 1+collatz(n/2); | |
| else | |
| result = 1+collatz(3*n+1); | |
| if(n < 10000000) | |
| cnt[n] = result; | |
| return result; | |
| } | |
| int main() | |
| { | |
| static long long ans[5000007]; | |
| int highest = 0; | |
| cnt[1] = 1; | |
| for(int i = 1;i <= 5000000;i++) | |
| { | |
| int k = collatz(i); | |
| if(k >= highest) | |
| { | |
| highest = k; | |
| ans[i] = i; | |
| } | |
| else | |
| ans[i] = ans[i-1]; | |
| } | |
| int tc; | |
| cin >> tc; | |
| while(tc--) | |
| { | |
| int n; | |
| cin >> n; | |
| cout << ans[n] << endl; | |
| } | |
| } |
ไม่มีความคิดเห็น:
แสดงความคิดเห็น