從邏輯到軟件

邏輯與算法優(yōu)化——趙寶勝袁川昊紀(jì)楊算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。圍棋棋盤為19*19，暴力枚舉所有可能將會(huì)達(dá)到3^361,約等于2.08*10^170,如此大的計(jì)算量，現(xiàn)今的技術(shù)難以達(dá)成。而算法的魅力也在與此，通過優(yōu)化，可以大幅度降低時(shí)間與空間復(fù)雜度。請(qǐng)思考以下一道題.北京時(shí)間3月15日，谷歌AlphaGo與韓國棋手李世石的比賽落下帷幕，最終比分定格為4:1。獲勝后的AlphaGo也因此獲得它有生以來的第一個(gè)榮譽(yù)。在賽后的發(fā)布會(huì)上，韓國棋院已經(jīng)給“阿爾法圍棋”頒發(fā)名譽(yù)九段證書。圍棋,一直被認(rèn)為是人類對(duì)抗人工智能的最后防線。而今最后防線面臨崩盤，很多人發(fā)出人工智能終會(huì)取代人類的悲觀呼聲。然而,AlphaGo終究只是一段代碼而已，離真正的人工智能依舊相差甚遠(yuǎn)。從某種意義上說，AlphaGo的勝利，實(shí)際上是程序員的勝利。思考？有1000瓶水，已經(jīng)編號(hào)（0~999），其中一瓶含毒，可以自由混合，請(qǐng)問最少用多少只白鼠可以確定哪一瓶含毒？Ans:10現(xiàn)在只考慮8瓶水一瓶含毒的情況,只需三只老鼠即可確定，將1,3,5,7混合后給第一只老鼠，將2,3,6,7混合后給第二只老鼠，將4,5,6,7混合后給第三只老鼠.若老鼠死亡，記錄結(jié)果為1，否則為0，從右向左記數(shù)。觀察：若第零瓶有毒,實(shí)驗(yàn)結(jié)果為000,0*(4)+0*(2)+0*(1)=0;若第一瓶有毒,實(shí)驗(yàn)結(jié)果為001,0*(4)+0*(2)+1*(1)=1;若第二瓶有毒,實(shí)驗(yàn)結(jié)果為010,0*(4)+1*(2)+0*(1)=2;…………若第七瓶有毒,實(shí)驗(yàn)結(jié)果為111,1*(4)+1*(2)+1*(1)=7;用簡單的二分法即可得到答案,現(xiàn)介紹二進(jìn)制壓縮的方式。怎樣確定如何混合呢?觀察1001 2010 4100 3011 3011 51015101 6110 611071117111 7111第三位均為1第二位均為1第一位均為1

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

給定一個(gè)數(shù)字序列,長度為n，求其和最大的子序列。 (子序列:如1,2,3

其所有的子序列為1231,22,31,2,3)當(dāng)n較小時(shí),固然可以用筆算等,然而n>=100000時(shí),又該如何計(jì)算呢?(普通計(jì)算機(jī)一秒大約可以運(yùn)行出10^7次,當(dāng)n>=100000,計(jì)算次數(shù)約為10^10,需要1000s才能跑出結(jié)果,現(xiàn)在要求將時(shí)間控制在1s以內(nèi),可以做到嗎?)

給定的長度為3的序列,我們可以先寫出其6個(gè)子序列,然后進(jìn)行一一計(jì)算。用這種方法，計(jì)算長度為n的序列，計(jì)算次數(shù)數(shù)量級(jí)在O(n*n)左右.現(xiàn)介紹一種DP算法，即動(dòng)態(tài)規(guī)劃.DP的核心思想是動(dòng)態(tài)規(guī)劃整個(gè)問題.通過求解一個(gè)又一個(gè)局部的最優(yōu)解來獲得整體的最優(yōu)解.算法如下:定兩個(gè)量Sum和Max,均初始化其為第一個(gè)數(shù).從第二個(gè)數(shù)開始遍歷之后每一個(gè)數(shù),如果Sum>0,將Sum加上當(dāng)前位置的數(shù),將Sum與Max進(jìn)行比較，如果Sum>Max,則將Max刷新為Sum.如果Sum<=0,將Sum初始化當(dāng)前掃到的數(shù)。最后結(jié)果即為Max！這樣計(jì)算復(fù)雜度為O(N),僅需要計(jì)算100000次!大幅度節(jié)省了時(shí)間.

邏輯與博弈邏輯指的是思維的規(guī)律和規(guī)則，是對(duì)思維過程的抽象。從狹義來講，邏輯就是指形式邏輯或抽象邏輯，是指人的抽象思維的邏輯；廣義來講，邏輯還包括具象邏輯，即人的整體思維的邏輯。海盜分金幣5個(gè)海盜搶得100枚金幣后，討論如何進(jìn)行公正分配。他們商定的分配原則是：（1）抽簽確定各人的分配順序號(hào)碼（1，2，3，4，5）；（2）由抽到1號(hào)簽的海盜提出分配方案，然后5人進(jìn)行表決，如果方案得到超過半數(shù)的人同意，就按照他的方案進(jìn)行分配，否則就將1號(hào)扔進(jìn)大海喂鯊魚；（3）如果1號(hào)被扔進(jìn)大海，則由2號(hào)提出分配方案，然后由剩余的4人進(jìn)行表決，當(dāng)且僅當(dāng)超過半數(shù)的人同意時(shí)，才會(huì)按照他的提案進(jìn)行分配，否則也將被扔入大海；（4）依此類推。這里假設(shè)每一個(gè)海盜都是絕頂聰明而理性，他們都能夠進(jìn)行嚴(yán)密的邏輯推理，并能很理智的判斷自身的得失，即能夠在保住性命的前提下得到最多的金幣。同時(shí)還假設(shè)每一輪表決后的結(jié)果都能順利得到執(zhí)行，那么抽到1號(hào)的海盜應(yīng)該提出怎樣的分配方案才能使自己既不被扔進(jìn)海里，又可以得到更多的金幣呢？2號(hào)和3號(hào)有積極性讓1號(hào)死，以便自己得到更多。所以，1號(hào)無奈之下，可能只有自己得0，而給2和3各50顆。但事實(shí)證明，這種做法依然不可行。為什么呢？

因?yàn)槲覀円瓤?號(hào)和5號(hào)的反應(yīng)才行。很顯然，如果最后只剩下4和5，這無論4提出怎樣的方案，5號(hào)都會(huì)堅(jiān)決反對(duì)。即使4號(hào)提出自己要0，而把100顆鉆石都給5，5也不會(huì)答應(yīng)――因?yàn)?號(hào)愿意看到4號(hào)死掉。這樣，5號(hào)最后順利得到100顆鉆石——因此，4的方案絕對(duì)無法獲得半數(shù)以上通過，如果輪到4號(hào)分配，4號(hào)只有死，只有死！

由此可見，4號(hào)絕對(duì)不會(huì)允許自己來分。他注定是一個(gè)弱者中的弱者，他必須同意3號(hào)的任何方案！或者1號(hào)2號(hào)的合理方案。可見，如果1號(hào)2號(hào)死掉了，輪到3號(hào)分，3號(hào)可以說：我自己100顆，4號(hào)5號(hào)0顆，同意的請(qǐng)舉手！這時(shí)候，4號(hào)為了不死，只好舉手，而5號(hào)暴跳如雷地反對(duì)，但是沒有用。因?yàn)?個(gè)人里面有2個(gè)人同意啊，通過率66.7％，大于50％！

由此可見，當(dāng)輪到3號(hào)分配的時(shí)候，他自己100顆，4和5都是0。因此，4和5不會(huì)允許輪到3來分。如果2號(hào)能夠給4和5一些利益，他們是會(huì)同意的。

比如2的分配方案是：98，0，1，1，那么，3的反對(duì)無效。4和5都能得到1，比3號(hào)來分配的時(shí)候只能得到0要好得多，所以他們不得不同意。

由此看來，2號(hào)的最大利益是98。1號(hào)要收買2號(hào)，是不可能的。在這種情況下，1號(hào)可以給4號(hào)和5號(hào)每人2顆，自己收買他們。這樣，2號(hào)和3號(hào)反對(duì)是無效的。因此，1號(hào)的一種分配方案是：96，0，0，2，2。

這是不是最佳方案呢？再想一想，1號(hào)也可以不給4號(hào)和5號(hào)各2個(gè)，而只需要1個(gè)就搞定了3號(hào)，因?yàn)槿绻喌?號(hào)來分配，2號(hào)是可以不給3號(hào)的，3號(hào)的得益只有0。所以，能得到1個(gè)，3號(hào)也該很滿意了。所以，最后的解應(yīng)該是：97，0，1，2，0。

好，再倒推。假設(shè)1號(hào)提出了97，0，1，0，2的方案，1號(hào)自己贊成。2和4反對(duì)。3∶2，關(guān)鍵就在于3號(hào)和5號(hào)會(huì)不會(huì)反對(duì)。假設(shè)3號(hào)反對(duì)，殺掉1號(hào)，2號(hào)來分配，3自己只能得到0。顯然，3號(hào)不劃算，他不會(huì)反對(duì)。如果5號(hào)反對(duì)，輪到2號(hào)、3號(hào)、4號(hào)來分配，5號(hào)自己最多只能得到1。

所以，3號(hào)和5號(hào)與其各得到0和1，還不如現(xiàn)在的1和2。

正確的答案應(yīng)該是：1號(hào)分配，依次是：97，0，1，0，2;或者是：97，0，1，2，0。再見~歐幾里得話不多說，先來個(gè)自我介紹：大家好，我是歐幾里得。沒錯(cuò)，我就是那個(gè)擁有自己的一套幾何體系，害死一片考生的歐幾里得（數(shù)學(xué)不好的快膜，其實(shí)他只是在裝逼而已）。歐幾里得是古希臘最負(fù)盛名、最有影響的數(shù)學(xué)家之一。歐幾里得的《幾何原本》對(duì)于幾何學(xué)、數(shù)學(xué)和科學(xué)的未來發(fā)展，對(duì)于西方人的整個(gè)思維方法都有極大的影響。《幾何原本》是古希臘數(shù)學(xué)發(fā)展的頂峰。歐幾里得將公元前七世紀(jì)以來希臘幾何積累起來的豐富成果，整理在嚴(yán)密的邏輯系統(tǒng)運(yùn)算之中，使幾何學(xué)成為一門獨(dú)立的、演繹的科學(xué)。今天我要向大家介紹的是

歐幾里得算法歐幾里得算法名字很高大上其實(shí)就是用來求最大公因數(shù)和最小公倍數(shù)的一個(gè)很實(shí)用的算法。intgcd(inta,intb){returnb>0?gcd(b,a%b):a;}證明過程：邏輯，全都是邏輯惹的禍套路，全tm是套路！證明：最小公倍數(shù)代碼：intLCM(inta,intb){a/gcd(a,b)*b;}證明：這個(gè)是灰常復(fù)雜（jiandan）的（歸納）首先得引入一個(gè)概念，同樣也可以證明，在此我就不說了，有興趣的可以百度百度或者問老師也或者可以問同學(xué)。（數(shù)論里的一些破玩意）引入概念：算術(shù)基本定理內(nèi)容：每個(gè)整數(shù)n>=2可唯一分解成素?cái)?shù)乘積即n=p1*p2*p3……pr;(這當(dāng)中可以重復(fù)出現(xiàn))如果nisprime那么有n=n；同樣滿足BOSS2