回复 第8楼 的 doctorjxd:对这个嘛,其实复杂度可以更小,因为啊
<br />
f<-function(n) n^4/4 + n^3/2 + n^2/4</p>
<p>f.s<-function(m){#version 1<br />
if(m<=9) {<br />
if (f(1)==m) return (1);<br />
if (f(2)==m) return (2);<br />
}<br />
a=ceiling((4*m)^.5);<br />
b=ceiling((2*m)^.25);<br />
L=a:b<br />
val=f(L);<br />
tt=which(val==m);<br />
if (length(tt)==0) stop("No solution");<br />
print(length(a:b))<br />
L[tt]<br />
}</p>
<p>
</p>
那两个神奇的a/b的原理是高中数学就不写了。也就是查表配合二分法就很简单了。
不过R里有个类似的玩意儿: uniroot 用的就是二分法。于是不自己造轮子的话:
<br />
f<-function(n) n^4/4 + n^3/2 + n^2/4</p>
<p>f.s2<-function(m){#version 2<br />
if(m<=9) {<br />
if (f(1)==m) return (1);<br />
if (f(2)==m) return (2);<br />
}<br />
a=ceiling((4*m)^.5);<br />
b=ceiling((2*m)^.25);<br />
L=a:b<br />
uniroot(function(x){f(x)-m},range(b,a))<br />
}<br />
</p>
看个效果
<br />
> system.time(f.s(15687562500))<br />
[1] 250080<br />
user system elapsed<br />
0.11 0.03 0.14<br />
> system.time(f.s2(15687562500))<br />
user system elapsed<br />
0 0 0<br />
</p>