發表新討論
#26957: Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [36.238.37.191] | 發表日期 : 2021-09-04 23:10

往LRU Cache，把跑過的結果存起來，這樣的方向是對的嗎？

我一直Time out...

 
#26958: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-04 23:27

有動態儲存會比較快, 全部存起來不可能, 因為記憶體不夠, 我是把小於某值的結果才存起來。

 

 
#26959: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-04 23:28

這是我的秒數

通過檢測

#1: 25% AC (76ms, 14MB)

通過檢測

#2: 25% AC (2s, 19.1MB)

通過檢測

#3: 25% AC (3s, 24.6MB)

通過檢測

 

 
#26960: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [36.238.37.191] | 發表日期 : 2021-09-04 23:43

這是我的秒數

通過檢測

#1: 25% AC (76ms, 14MB)

通過檢測

#2: 25% AC (2s, 19.1MB)

通過檢測

#3: 25% AC (3s, 24.6MB)

通過檢測

 



 

你是使用遞迴的寫法嗎？還是使用迴圈呢？

我是使用遞迴，並且改成限制在n<10000，有50%!

但 #3 #4依然TLE，哈

 
#26961: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-04 23:51

我是遞迴設 1250000

 
#26962: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [36.238.37.191] | 發表日期 : 2021-09-05 00:18

我是遞迴設 1250000


對耶！我忘記 n 其實會超出10的6次方！

最後把範圍設125萬(驚人@@我不敢設這麼大)，然後使用array作為陣列索引就過了！

謝謝你，你真厲害！

 
#26963: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-05 00:24

我把 array改為 list 有快一點。

另外 oeis 有公式可查。

 
#26964: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-05 00:31

你也可以玩奇數才建表，也許更快。

 
#26965: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [36.238.37.191] | 發表日期 : 2021-09-05 00:32

我把 array改為 list 有快一點。

另外 oeis 有公式可查。


OEIS有公式 :O
我只有找到前10000項，原本想直接套，但是程式碼太大塞不下

https://oeis.org/A006577

 

list的部分改天來試試

 
#26966: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [36.238.37.191] | 發表日期 : 2021-09-05 00:33

你也可以玩奇數才建表，也許更快。



原本有嘗試這種作法

可是表不知道要建多大了，可能沒辦法陣列索引

使用dict應該會塞不下(或是我方法有用錯)

 
#26967: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.52.87] | 發表日期 : 2021-09-05 00:44

奇數除2的值當索引建表，表可以建2倍大。

偶數連除2到奇數，才進遞迴，想像會變快。晚安。

 
#26971: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [1.172.251.196] | 發表日期 : 2021-09-05 13:49

1.8s 的 Lanstar 大大，有打算現身說法一下嗎 XD

你使用的方法是什麼呢？分享一下哈

 
#26980: Re:Python


as95624268 (Lanstar)

學校 : 國立臺灣科技大學
編號 : 120749
來源 : [116.241.137.22]
最後登入時間 ：
2024-04-20 19:12:56
g256. 考拉茲猜想 | From: [116.241.137.244] | 發表日期 : 2021-09-06 01:43

我很少會點進討論區，一進來就看到我的名字 哈

 

我是用遞迴，陣列只開1000000

原本想說開大一點可以節省時間，但反而更慢了..

 

奇偶分開做會快很多

奇數：如果>333333，可以直接丟 (x*3+1)//2 進遞迴，次數要再加一

　　　否則，丟 x*3+1 進遞迴

偶數：丟 x//2 進遞迴

建表的時候也是。

 

因為我是由小到大建表，偶數的部分可以直接取 DP 中 x//2 的值

 

我也不知道還能不能再更快

 
#26981: Re:Python


as95624268 (Lanstar)

學校 : 國立臺灣科技大學
編號 : 120749
來源 : [116.241.137.22]
最後登入時間 ：
2024-04-20 19:12:56
g256. 考拉茲猜想 | From: [116.241.137.244] | 發表日期 : 2021-09-06 01:53

「奇偶分開做會快很多」打錯了 請無視xd

 
#26982: Re:Python


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.146.197]
最後登入時間 ：
2024-05-03 16:06:58
g256. 考拉茲猜想 | From: [61.223.53.203] | 發表日期 : 2021-09-06 01:55

我嘗試奇偶分開做, 腦袋打結了, 沒辦法 ~~~

 
#27046: Re:Python


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
g256. 考拉茲猜想 | From: [1.172.251.27] | 發表日期 : 2021-09-09 18:06

我很少會點進討論區，一進來就看到我的名字 哈

 

我是用遞迴，陣列只開1000000

原本想說開大一點可以節省時間，但反而更慢了..

 

奇偶分開做會快很多

奇數：如果>333333，可以直接丟 (x*3+1)//2 進遞迴，次數要再加一

　　　否則，丟 x*3+1 進遞迴

偶數：丟 x//2 進遞迴

建表的時候也是。

 

因為我是由小到大建表，偶數的部分可以直接取 DP 中 x//2 的值

 

我也不知道還能不能再更快



雖然認為陣列大小也會影響執行結果，但陣列太大反而索引效率差嗎？ :O

真是神奇的觀察

 
ZeroJudge Forum