還能更好嗎(C/C++)

c/c++演算法入門

起因

去年好像報名了一個比賽，藍橋杯，突然得知4.1就要開始省賽了，自己卻只學了些皮毛，之前參加了校級演算法實驗室，因為種種原因，現在已經退出了，只能靠自己的一雙勤勞的手和一些參考書開始系統的演算法學習。

還能更好嗎？

記得寒假的時候，群里有人問一個數組反轉的演算法怎麼寫的時候，他的大概思路是新開闢一個數組，原數組從後向前存到新數組裡，在輸出。可以說這也是大部分人想到的，解決了問題，止步於此。

但是，還能更好嗎？

因為學習了一些皮毛的數據結構，發現用一個類似隊列的數據結構（頭尾指針，但不是頭出尾進）頭指針向後走，尾指針向前走，每次走一步，交換一次頭尾指針指向的值。這樣運行時間就降低到到原來的一半，雖然優化不大，但是也要去盡量去想想看，還有更好的辦法嗎？

說點關於比賽的

黑盒競賽，我們甚至不需要寫逆序演算法，for循環從尾部列印到頭部即可??

備考第一天(18.3.15)

聊聊排序：

1. 冒泡
   相信大家應該不陌生這個演算法
   兩個for一個交換ab，灰常簡單有木有？
2. 快速（小到大）

   聽名字就很快

   左端找的基準數
   i，j為左右指針
   j-- 找一個小於基準數的數據
   i++ 找一個大於基準數的數據

   前提在i小於j的情況下

   交換ij數據
   ij相遇 遞歸排序(left,i-1)(i+1,right)
   不return條件 left小於right

備考第二天(18.3.16)

貪心演算法：

• 貪心演算法之前需注意的幾個問題

(1)確定初心，一旦堅定目標不要後悔

(2)可能沒有得到最優解，但是確實最優的近似解

(3)貪心策略決定演算法好壞

• 貪心知道

(1)貪心選擇：大問題要拆分成若干個小問題！去選擇最優解來解決小問題。

(2)最優子結構：一個問大題的最優解真好包含小問題最優解叫做最優子結構

• 貪心作弊秘籍

(1)一定要明確你的要的是大蘋果還是紅蘋果，求解目標不同，策略也會不同！

(2)一步一步得到局部最優解，把局部最優解合稱為原來的問題的最優解！

怎麼有點像冒泡排序呢？

實例：貪心演算法.加勒比海盜船

在北美洲東南部，有一片神秘的海域，那裡碧海藍天、陽光明媚，這正是傳說中海盜最活躍的加勒比海（Caribbean Sea）。17世紀時，這裡更是歐洲大陸的商旅艦隊到達美洲的必經之地，所以當時的海盜活動非常猖獗，海盜不僅攻擊過往商人，甚至攻擊英國皇家艦……

有一天，海盜們截獲了一艘裝滿各種各樣古董的貨船，每一件古董都價值連城，一旦打碎就失去了它的價值。雖然海盜船足夠大，但載重量為C，每件古董的重量為wi，海盜們該如何把儘可能多數量的寶貝裝上海盜船呢？

• 貪心秘籍.目的是什麼？

船的裝載量是一定的，我們需要依次找出最輕的古董！

• 貪心秘籍.可以拆成小問題嗎或者抽象成一類問題嗎？

排序，從小到大直到裝入最後一個物件後，載重量超過C。

符合最優子結構

備考第三天(18.3.17)

窮竭搜索：

又分為 DFS（深度優先）和 BFS（廣度優先）這兩種方式

學習之前需要明白這些：

• 遞歸：函數中再次點用自身的行為叫做遞歸

遞歸停止條件必須存在

//實例：階乘遞歸來實現long sum=1;long d(int k){ if(k<=1) return sum; sum=sum*k; d(k-1);}

• 棧：一種支持push和pop兩種操作的數據結構

特點：先進後出

//實例：迴文數 //可以自己實現一下

• 隊列：一種支持push和pop兩種操作的數據結構

特點：先進先出

備考第四天(18.3.18)

窮竭搜索：

又分為 DFS（深度優先）和 BFS（廣度優先）這兩種方式

• DFS - 當下如何做？（隱式用棧這種結構）

要是我會做Flash就好了，其實看一動畫明白的非常快！

//實例：部分和問題int a[MAX];int n,k;int dfs(int i,int sum){ if(i==n) return sum==k; //終止條件 //第一種，不加a[i]的情況 if(dfs(i+1,sum)) return 1; //第二種，加上a[i]的情況 if(dfs(i+1,sum+a[i])) return 1;}

• BFS - 能怎麼去做？（用隊列這種結構）

大概類似於遍歷頭指針指向點的所有情況

//實例：迷宮問題

盡然還有催更??

十分感謝 認真看 或者 指出小弟錯誤的大佬們??