从一段Py到思考人生

0x00

从个人习惯来说写程序会先想的事情:

  1. 如何把实际问题转换为可以描述给程序的问题。
  2. 能不能把一个未知问题转换为若干个可知解法的问题。

也和平时所思考问题的特点有关,一般会关注 如何最直接的把漏洞用代码表达 和 如何最快写出Exp。除了上面务实的两点,还有一个更加深邃的问题,如何更加巧妙地解决一个问题。思考这个问题可能是无限次覆盖第二条的痛苦过程,但是这是成长的必经之路嘛。

研究应用安全同时如果能熟悉数据结构和算法和语言底层,大概就像小前锋能突能投能抢板一样恐怖(我是詹皇脑残粉~)。

还是拿这两天偶然遇到的一道编程题的Python解来做例子吧,问题本身并不是什么难题,但是觉得思考过程比较有趣。

0x01

问题:给定一个正整数N,求不大于N的所有正整数的最大奇约数的和。(N的范围是0到10E,时间限定是1秒。)

按上面的常规思路,首先想成这样:

定义函数a,求一个数的约数,然后找到其中最大的奇数返回。函数main写一个循环,累加函数a。

数Num的最大奇约数方法,用最朴实思路去想的话,可以从0开始输入给定整数i,如果能够整除则判断Num/i是否是奇数,如果不是则继续,如果是则返回。

qq%e6%88%aa%e5%9b%be20160914163203

程序非常的简陋,当然发现无法做到1s内计算出结果。输出的第二行是程序的运行时间,千万级就已经达不到要求了。想象一下如果数Num是2的10次方,getnum要尝试1024次才能得到最大奇约数1。

qq%e6%88%aa%e5%9b%be20160914170528

0x02

如果没有时间要求,或者N比较小,这样的笨办法是可以达到目。然而有了限定,那就要思考文章开始提到的,如何更加巧妙的计算这个值。

刚刚说到2的n次方极大的影响了程序的效率,先判断log2 N是不是整数,如果是的话直接返回1,不是的话则放入函数a求解。后来发现速度提升不是很大。

重新规划方法:发现如果一个数是奇数的话,则最大奇约数是自己本身,如果一个数是偶数则反复除以2直到一个奇数就是他的最大奇约数。

qq%e6%88%aa%e5%9b%be20160914170258

qq%e6%88%aa%e5%9b%be20160914170528

快了一些,不过还是感觉比较慢,忽然想到一个很奇怪的事情,即使是不做任何判断,从1加到10E就已经超过1秒了。

0x03

所以当你顺着题目想求和的时候已经输了。正好是笔试题,所以在讨论区看到一个算法牛的解法。从算法角度来说这个可能是一个典型问题吧,所以时间开销不允许是开始的O(N^2),也不允许是O(N)。

第二种解法的时候已经接近真相了,不过,累加是不够聪明,因为把不大于N的所有的数字的奇约数加在一起,可以转换为log2 N个等差数列求和。
是不是想到了中学时期的数学证明题对左边数列分组求和。。。

重新规划方法:求小于等于N的所有奇数的和,然后剩下的偶数除以2取出所有奇数的和再加进去,依次类推直到没有偶数。
转换为程序角度就是求小于N的所有奇数和小于N/2的所有奇数…一直累加到小于等于2或小于等于1的所有奇数的和.

开始写程序的时候觉得N是奇数还是偶数的时候计算小于N的所有奇数的和时不一样,但是可以pythonic的用((N+1)/2)**2来求(N为int型时,8/2=9/2),这里仔细想想就知道项数永远是(N+1)/2。

OK,万事具备,用一个递归就可以计算出结果了。

qq%e6%88%aa%e5%9b%be20160914172919

0x04

是不是想起了小时候听的高斯的故事,老师布置计算算1累加到100的和,勤奋的小朋友们在一个一个数字算,而高斯小朋友非常快的计算出了结果。。。

为什么会有人跑的比自己快呢,因为你在做加法的时候,别人在做乘法啊。

共勉~

发表评论

电子邮件地址不会被公开。