作者sa072686 (小紅)
看板b98902HW
標題Re: [計程] TestGirl第51題
時間Thu Nov 19 17:45:16 2009
1F：→ Natsutaka:我仿照了樓上連結 寫了新的code:11/19 02:51
3F：→ Natsutaka:但一樣執行時間超過限制11/19 02:52
這樣比暴力解還慘烈，function call 次數上…
f(1) = 1
f(n) = n%2 ? f(n-1)+1 : f(n/2)+f(n/2)+1
姑且不論 function call 比迴圈花的時間多，光是寫個函數
return b ? f(b-1)*a%c : a%c;
可能都還比較快，重點是 f(n/2) 怎麼算結果都會一樣，所以不要呼叫兩次
要記住這是遞迴，你多 call 一次，展開成樹狀圖之後可是 exponential 成長的
自己畫一次就會懂了
只算一次 f(n/2) 的話，function call 的次數可以縮成
f(1) = 1
f(n) = n%2 ? f(n-1)+1 : f(n/2)+1
差不多就剩 O(log n) 了
※ 引述《Natsutaka (夏宇)》之銘言：
: 2007 Practice09 ( score: 5 )
: 題目如下:
: http://palcourse.csie.ntu.edu.tw/testgirl/problem/c2007/practice/pp8.txt
: 我的code如下:
: http://homepage.ntu.edu.tw/~b94202058/test51.c
: 其實我的code沒什麼好看的
: 想法就是先 A = A % C
: 再把A自乘B次
: 每自乘一次就對C求一次餘數
: 這樣寫是不會過的
: 因為執行時間過長
: 所以想請問有沒有較快的演算法
: 感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.248.145
4F：推 Natsutaka:謝謝 這次對了 真的是call太多次的問題 :) 11/20 10:25