作者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