存档

‘算法优化’ 分类的存档
3月
24

直方图下最大矩形面积问题【算法优化向】

histogram_area好像好久没写算法问题了。。。。上一次写好像是。。额。。大概是去年的事了吧。。。以前还兴致勃勃的狂写Euler Project的个人解答系列,但是后来发现官方有说,请不要在互联网上直接贴关于解答的代码,额,然后他这么一说,这个系列我就不怎么想弄了。。除了一方面不想做这些会被官方讨厌的事情外,其次是。。。懒。。。自己做完题还要花时间上来写思路,各种分析,敲数学公式什么的。。

唉,不管怎么说,研究算法和学习前端那些“不误正业”的东西的时候总是很“忘我”————忘记我™还要靠光子学和水声的东西毕业啊!!!!!然后这两天又跑到两个以前没去过的OJ网站上玩了,一个是51nod,还有一个leetcode OJ,昨晚就一直刷题玩到半夜三点多。。 阅读全文…

12月
08

Euler Project之Retraction【算法优化向】

pe_banner_light好吧,其实我是在新博客这边练习敲公式来着。。。

题目来源还是是Euler Project,之前官方连续公布了三道类似的题目,都是基于一种叫做Retraction数的东西,它的定义是:

对于所有整数\(n>1\),定义一族函数\(f_{n,a,b}(x)=mod(ax+b,n)\),\(x,a,b\)均为整数,且满足0<\(n\)<\(a\),\(0\leq b < n\),\(0\leq x < n\)
如果对所有\(x\)均有:

\(f_{n,a,b}(f_{n,a,b}(x))=mod(f_{n,a,b}(x),n)\)

那么,我们管\(f_{n,a,b}(x)=mod(ax+b,n)\)叫做一个Retraction;
我们需要计算的是\(R(n)\),定义为包含\(n\)的Retraction的个数。

阅读全文…

11月
22

互质数倒数乘积之和の研究【算法优化向】

pe_banner_light上周开始一直在Euler Project上面刷题,玩得不亦乐乎,那种面对千奇百怪的问题,可以用自己手边的各种工具来“玩弄”的感觉真是让人欲罢不能,其实手头上也就4套工具,C++,Python,Matlab,Mathematica,主要用得最多的也就Mathematica,Python。

好吧,讲正事,上周遇到一道题,可算把我两天给送进去了。。。。

题目链接可以参见这里,翻译过来是这样的:

对于任意整数M,我们定义R(M)是符合下面条件的整数p,q的乘积的倒数1/(p·q)的和,
1.1≤p<q≤M
2.p+q≥M
3.p和q互质
然后我们定义S(N)表示R(i)的和,2≤i<N

求:S(107)精确到小数点后4位

我开始用python试测了一下这个暴算的复杂度,直接跪了,所以我马上转战C++。。

首先我们可以根据题目表面要求写出第一套可以预知不可能成功的程序: 阅读全文…