從邏輯到軟件

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

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

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

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

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

邏輯與博弈邏輯指的是思維的規(guī)律和規(guī)則，是對思維過程的抽象。從狹義來講，邏輯就是指形式邏輯或抽象邏輯，是指人的抽象思維的邏輯；廣義來講，邏輯還包括具象邏輯，即人的整體思維的邏輯。海盜分金幣5個海盜搶得100枚金幣后，討論如何進行公正分配。他們商定的分配原則是：（1）抽簽確定各人的分配順序號碼（1，2，3，4，5）；（2）由抽到1號簽的海盜提出分配方案，然后5人進行表決，如果方案得到超過半數(shù)的人同意，就按照他的方案進行分配，否則就將1號扔進大海喂鯊魚；（3）如果1號被扔進大海，則由2號提出分配方案，然后由剩余的4人進行表決，當且僅當超過半數(shù)的人同意時，才會按照他的提案進行分配，否則也將被扔入大海；（4）依此類推。這里假設每一個海盜都是絕頂聰明而理性，他們都能夠進行嚴密的邏輯推理，并能很理智的判斷自身的得失，即能夠在保住性命的前提下得到最多的金幣。同時還假設每一輪表決后的結果都能順利得到執(zhí)行，那么抽到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的方案絕對無法獲得半數(shù)以上通過，如果輪到4號分配，4號只有死，只有死！

由此可見，4號絕對不會允許自己來分。他注定是一個弱者中的弱者，他必須同意3號的任何方案！或者1號2號的合理方案?？梢姡绻?號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，還不如現(xiàn)在的1和2。

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

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