========================================================
1.自然数的平方和。
连续自然数的平方和,即f(N)=1*1+2*2+……+N*N。其结果f(N)=N*(N+1)*(2N+1)/6.
这个结果,验证还是比较容易验证的,采用数学归纳法即可。
但直接推导还是有些困难的,至少我自己想,费了半天时间没有推出来。
具体的多种推导过程,大家可自行百度,在百度百科【平方和公式】里面,提供了好几种自然数平方和的计算方法
-----------------------------------------------------------------
2.幻方的构造
N阶幻方是将1~N*N个自然数不重不漏的放到一个N行N列的方阵里面,使得每行、每列、以及主对角线上数字之和相同,如最简单的,三阶幻方,中国称为洛书的,“戴九履一,左三右七,二四为肩,六八为足,以五居中”,也就是
492
357
816
高阶幻方的构造,通用的方法是采用两个正交拉丁方来进行构造,只要有两个相互正交的拉丁方,就非常容易可以得到幻方的,但正交拉丁方应该不是唯一理论,至少,六阶正交拉丁方是不存在的,但六阶幻方却存在。我只了解通过正交拉丁方来构造幻方的过程了,在文中也只提及这种。
奇数阶幻方构造简单,非常容易就能拍得了,但偶数阶幻方构造很困难。
从原理上说,正交拉丁方的构造,需要借助模N整数域,N为奇数时,模N整数群就是个域,而偶数阶则不然,如模8整数群,2*4=0MOD8,两个不是0的数相乘得到0了。这时该怎么办?引入虚数单位i,然后用i来构造不可约多项式。具体过程不再论述了。
在组合数学这门数学课中,正交拉丁方的构造有详细论述。
可参考《组合数学》机械工业出版社的这个,说的很详细,不过需要一定数学功底
-----------------------------------------------------------------
3.称球问题----平衡三叉决策树
网上流传的经典问题:
问题1:有十二个外表相同的球,其中有一个坏球,它的重量和其它十一个有轻微的(但是可以测量出来的)差别。现在有一架没有砝码的很灵敏的天平,问至少几次才能找出那个坏球,并知道它比标准球重还是轻。
问题2:9个球,其中8个球质量一样,一个球质量偏重,问至少称几次,能找出偏重的球?
很多人应该见过这个题目,也曾经解过,不过如果不是相关专业的人,应该没有探究过原理吧?
N次称量能称几个小球,M个小球几次称量能找出有问题的小球?
理论与公式推导可参见这篇博客。
原理篇:/s/blog_l
公式篇:/s/blog_l
-----------------------------------------------------------------
4.魔方还原问题
对于魔方还原问题,大家了解的很可能比我多,我会还原魔方,不过我不会网上的边先法,我会的是角先法,是当年高中时我的一位同学告诉我的,不过只告诉了我一半,剩下的一半我自己补齐的,效率很低,五分钟才能还原回来。
当年尝试用群的思想来分析魔方的,结果水平不行。有本用群论来分析魔方的书,我大学时尝试看过没看懂。百度了一下没找到,以后找到了再补充。
-----------------------------------------------------------------
5.关联开关问题
这个是一道经典的算法题,按一个开关会导致其他开关状态改变,要采用异或矩阵来作为工具进行求解。
我做过这道题目,不过没有写博客啥的,在网上找一篇相关的文章吧
/qq_33879506/article/details/53192909
-----------------------------------------------------------------
问题与蚁群算法
TSP问题是最经典的NPC问题之一,相关的研究很多。
蚁群算法是一类群智能优化算法,文中将蚁群算法吹嘘到突破天际,其实不为过的,蚁群算法、粒子群算法、遗传算法、差分演化算法、分布估计算法,这一堆智能优化算法,统称演化算法。现代工程问题中面临的复杂的高维、多目标、多约束的问题,只能靠这类算法了。而且这类算法的普适性极高。
-----------------------------------------------------------------
后续还会出现一些算法,等写到再补充了58xs8.com