从逻辑到软件

逻辑与算法优化——赵宝胜袁川昊纪杨算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。算法的优劣可以用空间复杂度与时间复杂度来衡量。围棋棋盘为19*19，暴力枚举所有可能将会达到3^361,约等于2.08*10^170,如此大的计算量，现今的技术难以达成。而算法的魅力也在与此，通过优化，可以大幅度降低时间与空间复杂度。请思考以下一道题.北京时间3月15日，谷歌AlphaGo与韩国棋手李世石的比赛落下帷幕，最终比分定格为4:1。获胜后的AlphaGo也因此获得它有生以来的第一个荣誉。在赛后的发布会上，韩国棋院已经给“阿尔法围棋”颁发名誉九段证书。围棋,一直被认为是人类对抗人工智能的最后防线。而今最后防线面临崩盘，很多人发出人工智能终会取代人类的悲观呼声。然而,AlphaGo终究只是一段代码而已，离真正的人工智能依旧相差甚远。从某种意义上说，AlphaGo的胜利，实际上是程序员的胜利。思考？有1000瓶水，已经编号（0~999），其中一瓶含毒，可以自由混合，请问最少用多少只白鼠可以确定哪一瓶含毒？Ans:10现在只考虑8瓶水一瓶含毒的情况,只需三只老鼠即可确定，将1,3,5,7混合后给第一只老鼠，将2,3,6,7混合后给第二只老鼠，将4,5,6,7混合后给第三只老鼠.若老鼠死亡，记录结果为1，否则为0，从右向左记数。观察：若第零瓶有毒,实验结果为000,0*(4)+0*(2)+0*(1)=0;若第一瓶有毒,实验结果为001,0*(4)+0*(2)+1*(1)=1;若第二瓶有毒,实验结果为010,0*(4)+1*(2)+0*(1)=2;…………若第七瓶有毒,实验结果为111,1*(4)+1*(2)+1*(1)=7;用简单的二分法即可得到答案,现介绍二进制压缩的方式。怎样确定如何混合呢?观察1001 2010 4100 3011 3011 51015101 6110 611071117111 7111第三位均为1第二位均为1第一位均为1

其余位次均为01自由组合同理即可得到原题答案为10！最大子序列和

给定一个数字序列,长度为n，求其和最大的子序列。 (子序列:如1,2,3

其所有的子序列为1231,22,31,2,3)当n较小时,固然可以用笔算等,然而n>=100000时,又该如何计算呢?(普通计算机一秒大约可以运行出10^7次,当n>=100000,计算次数约为10^10,需要1000s才能跑出结果,现在要求将时间控制在1s以内,可以做到吗?)

给定的长度为3的序列,我们可以先写出其6个子序列,然后进行一一计算。用这种方法，计算长度为n的序列，计算次数数量级在O(n*n)左右.现介绍一种DP算法，即动态规划.DP的核心思想是动态规划整个问题.通过求解一个又一个局部的最优解来获得整体的最优解.算法如下:定两个量Sum和Max,均初始化其为第一个数.从第二个数开始遍历之后每一个数,如果Sum>0,将Sum加上当前位置的数,将Sum与Max进行比较，如果Sum>Max,则将Max刷新为Sum.如果Sum<=0,将Sum初始化当前扫到的数。最后结果即为Max！这样计算复杂度为O(N),仅需要计算100000次!大幅度节省了时间.

逻辑与博弈逻辑指的是思维的规律和规则，是对思维过程的抽象。从狭义来讲，逻辑就是指形式逻辑或抽象逻辑，是指人的抽象思维的逻辑；广义来讲，逻辑还包括具象逻辑，即人的整体思维的逻辑。海盗分金币5个海盗抢得100枚金币后，讨论如何进行公正分配。他们商定的分配原则是：（1）抽签确定各人的分配顺序号码（1，2，3，4，5）；（2）由抽到1号签的海盗提出分配方案，然后5人进行表决，如果方案得到超过半数的人同意，就按照他的方案进行分配，否则就将1号扔进大海喂鲨鱼；（3）如果1号被扔进大海，则由2号提出分配方案，然后由剩余的4人进行表决，当且仅当超过半数的人同意时，才会按照他的提案进行分配，否则也将被扔入大海；（4）依此类推。这里假设每一个海盗都是绝顶聪明而理性，他们都能够进行严密的逻辑推理，并能很理智的判断自身的得失，即能够在保住性命的前提下得到最多的金币。同时还假设每一轮表决后的结果都能顺利得到执行，那么抽到1号的海盗应该提出怎样的分配方案才能使自己既不被扔进海里，又可以得到更多的金币呢？2号和3号有积极性让1号死，以便自己得到更多。所以，1号无奈之下，可能只有自己得0，而给2和3各50颗。但事实证明，这种做法依然不可行。为什么呢？

因为我们要先看4号和5号的反应才行。很显然，如果最后只剩下4和5，这无论4提出怎样的方案，5号都会坚决反对。即使4号提出自己要0，而把100颗钻石都给5，5也不会答应――因为5号愿意看到4号死掉。这样，5号最后顺利得到100颗钻石——因此，4的方案绝对无法获得半数以上通过，如果轮到4号分配，4号只有死，只有死！

由此可见，4号绝对不会允许自己来分。他注定是一个弱者中的弱者，他必须同意3号的任何方案！或者1号2号的合理方案。可见，如果1号2号死掉了，轮到3号分，3号可以说：我自己100颗，4号5号0颗，同意的请举手！这时候，4号为了不死，只好举手，而5号暴跳如雷地反对，但是没有用。因为3个人里面有2个人同意啊，通过率66.7％，大于50％！

由此可见，当轮到3号分配的时候，他自己100颗，4和5都是0。因此，4和5不会允许轮到3来分。如果2号能够给4和5一些利益，他们是会同意的。

比如2的分配方案是：98，0，1，1，那么，3的反对无效。4和5都能得到1，比3号来分配的时候只能得到0要好得多，所以他们不得不同意。

由此看来，2号的最大利益是98。1号要收买2号，是不可能的。在这种情况下，1号可以给4号和5号每人2颗，自己收买他们。这样，2号和3号反对是无效的。因此，1号的一种分配方案是：96，0，0，2，2。

这是不是最佳方案呢？再想一想，1号也可以不给4号和5号各2个，而只需要1个就搞定了3号，因为如果轮到2号来分配，2号是可以不给3号的，3号的得益只有0。所以，能得到1个，3号也该很满意了。所以，最后的解应该是：97，0，1，2，0。

好，再倒推。假设1号提出了97，0，1，0，2的方案，1号自己赞成。2和4反对。3∶2，关键就在于3号和5号会不会反对。假设3号反对，杀掉1号，2号来分配，3自己只能得到0。显然，3号不划算，他不会反对。如果5号反对，轮到2号、3号、4号来分配，5号自己最多只能得到1。

所以，3号和5号与其各得到0和1，还不如现在的1和2。

正确的答案应该是：1号分配，依次是：97，0，1，0，2;或者是：97，0，1，2，0。再见~欧几里得话不多说，先来个自我介绍：大家好，我是欧几里得。没错，我就是那个拥有自己的一套几何体系，害死一片考生的欧几里得（数学不好的快膜，其实他只是在装逼而已）。欧几里得是古希腊最负盛名、最有影响的数学家之一。欧几里得的《几何原本》对于几何学、数学和科学的未来发展，对于西方人的整个思维方法都有极大的影响。《几何原本》是古希腊数学发展的顶峰。欧几里得将公元前七世纪以来希腊几何积累起来的丰富成果，整理在严密的逻辑系统运算之中，使几何学成为一门独立的、演绎的科学。今天我要向大家介绍的是

欧几里得算法欧几里得算法名字很高大上其实就是用来求最大公因数和最小公倍数的一个很实用的算法。intgcd(inta,intb){returnb>0?gcd(b,a%b):a;}证明过程：逻辑，全都是逻辑惹的祸套路，全tm是套路！证明：最小公倍数代码：intLCM(inta,intb){a/gcd(a,b)*b;}证明：这个是灰常复杂（jiandan）的（归纳）首先得引入一个概念，同样也可以证明，在此我就不说了，有兴趣的可以百度百度或者问老师也或者可以问同学。（数论里的一些破玩意）引入概念：算术基本定理内容：每个整数n>=2可唯一分解成素数乘积即n=p1*p2*p3……pr;(这当中可以重复出现)如果nisprime那么有n=n；同样满足BOSS2