从逻辑到软件

1、 算法（算法（Algorithm）是指解题方案的准确而完整的描述，）是指解题方案的准确而完整的描述， 是一系列解决问题的清晰指令，算法代表着用系统的是一系列解决问题的清晰指令，算法代表着用系统的 方法描述解决问题的策略机制。方法描述解决问题的策略机制。 北京时间北京时间3月月15日，谷歌日，谷歌AlphaGo与韩国棋手李世石的比赛落与韩国棋手李世石的比赛落 下帷幕，最终比分定格为下帷幕，最终比分定格为4:1。获胜后的。获胜后的AlphaGo也因此获得它也因此获得它 有生以来的第一个荣誉。在赛后的发布会上，韩国棋院已经有生以来的第一个荣誉。在赛后的发布会上，韩国棋院已经 给给“阿尔法围棋阿尔法围

2、棋”颁发名誉九段证书。颁发名誉九段证书。 现在只考虑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; 用简单的二分法即可得到答案,现介绍二

3、进制压缩的方式。 怎样确定如何混合呢? 观察 1 001 2 010 4 100 3 011 3 011 5 101 5 101 6 110 6 110 7 111 7 111 7 111 第三位均为1 第二位均为1 第一位均为1 其余位次均为01自由组合 给定一个数字序列,长度为n，求其和最大的子序列。 ( 子序列: 如1,2,3 其所有的子序列为 1 2 3 1,2 2,3 1,2,3 ) 当n较小时,固然可以用笔算等,然而n=100000时,又该如何计算呢? (普通计算机一秒大约可以运行出107次,当n=100000,计算次数约为1010,需 要1000s才能跑出结果,现在要求将时间控制

4、在1s以内,可以做到吗?) 给定的长度为3的序列,我们可以先写出其6个子序列,然后进行一一计算。 用这种方法，计算长度为n的序列，计算次数数量级在 O(n*n)左右. 现介绍一种现介绍一种DP算法，即动态规划算法，即动态规划. DP的核心思想是动态规划整个问题的核心思想是动态规划整个问题. 通过求解一个又一个局部的最优解来获得整体的最优解通过求解一个又一个局部的最优解来获得整体的最优解. 算法如下算法如下: 定两个量定两个量Sum和和Max,均初始化其为第一个数均初始化其为第一个数. 从第从第二二个数开始遍历之后每一个数个数开始遍历之后每一个数, 如果如果Sum0,将将Sum加上当前位置的数加

5、上当前位置的数,将将Sum与与Max进行比较，如果进行比较，如果 SumMax,则将则将Max刷新为刷新为Sum.如果如果Sum0?gcd(b,a%b):a; 证明过程： 逻辑，全都是逻辑惹的祸 套路，全tm是套路！ 证明： 最小公倍数 代码：int LCM(int a,int b)a/gcd(a,b)*b; 证明：这个是灰常复杂（jiandan）的（归纳） 首先得引入一个概念，同样也可以证明，在此我就不说了，有兴趣的可以百度百度或者问 老师也或者可以问同学。（数论里的一些破玩意） 引入概念：算术基本定理 内容：每个整数n=2可唯一分解成素数乘积 即n=p1*p2*p3pr;(这当中可以重复出现) 如果n isprime 那么有n=n；同样满足 BOSS2：Euler（欧拉） 对于他，大家肯定再熟悉不过了，我就不再 介绍了。反正这两位在数学全球红色通缉令 上都是名列前茅的恐怖分子了。 我今天要和大家介绍的是 欧拉回路和欧拉通 路（图论） 简介 定义：通过图（无向图或有向图）中所有边且每 边仅通过一次通路称为欧拉通路，相应的