第一章：分治算法——分而治之
? 把一個復雜的問題分成2個或多個相似或相同的子問題，再把子問題分成更多的小的子問題......直到最后小問題可以簡單的求解冕碟，原問題的解即子問題的解的合并拦惋。基于這個原理的高效算法有：快速鸣哀，歸并排序架忌，傅立葉變換。
? 比如：你要折斷一個木頭這個木頭由10個小木頭組成我衬，那么你會怎么做叹放？ 答：分成5個，再分成1個? ?
? ? ? ? ? ? （8+9）*6=挠羔？ 運算步驟
? 折半查找法
? 問題1：在一排（10000以內(nèi)）已按編號大小排好序的圖書中井仰，快速按編號查找到某本書所在的位置（數(shù)組2，4破加，6）
? ? ? ? ? ? ? 輸入格式：輸入要查找的數(shù)
? ? ? ? ? ? ? 輸出格式：一個數(shù)俱恶，否則輸出-1
? ? ? ? ? ? 輸入樣例： 4
? ? ? ? ? ? 輸出樣例：1
? 作業(yè)1：在數(shù)組 （15，24范舀，33合是，42，65锭环，71）
? ? ? ? ? ? 輸入樣例：33
? ? ? ? ? ? 輸出樣例：2
? 遞歸二分法原理
? a[]——> 1 2 3 4 5
? ? X? ? ? ? ? I? ? K? ? J
? J>I? ? X與a[k]有三種情況
? ? 1. x=a[k] 已經(jīng)發(fā)現(xiàn)聪全，退出查找
? ? 2.x<a[k]? 在前半部分查找，i不變辅辩，j=> k-1
? ? 3.x>a[k]? 在后半部分查找难礼，j不變，i=> k+1
代碼：
#include<iostream>
#include<assert.h>
using namespace std;
int Search(int ar[], int low, int high, int key)
{
? ? if(low > high)//查找不到
? ? ? ? return -1;
? ? int mid = (low+high)/2;
? ? if(key == ar[mid])//查找到
? ? ? ? return mid;
? ? else if(key < ar[mid])
? ? ? ? return Search(ar,low,mid-1,key);
? ? else
? ? ? ? return Search(ar,mid+1,high,key);
}
int main()
{
? ? int ar[3] = {2玫锋，4蛾茉，6};
? ? int n = sizeof(ar)/sizeof(int);
? ? int key;
? ? cout<<"請輸入要查找的key值:>";
? ? cin>>key;
? ? cout<<"pos :> "<<Search(ar,0,n-1,key)<<endl;
}
2019.07.03? C++ 算法第二天
?
第二部分? 算法
? 遞歸算法：
? ? ? ? 遞歸函數(shù)即自調(diào)用函數(shù)，在函數(shù)內(nèi)部直接的或者間接地調(diào)用自己撩鹿。在求解某些具有隨意性的復雜問題時經(jīng)常使用遞歸谦炬，如要求編寫一個函數(shù)，將輸入的任意長度的字符串反向輸出节沦。普通做法是將字符串放入數(shù)組中然后將數(shù)組元素反向輸出即可吧寺，然而這里的要求是輸入是任意長度的窜管，總不能開辟一個很大的空間保存字符串吧？這時候遞歸就起作用了稚机。遞歸采用了分治的思想，將整體分割成部分获搏，從最小的基本部分入手赖条，逐一解決，其中部分通常和整體具有相同的結(jié)構(gòu)常熙，這樣部分可以繼續(xù)分割纬乍，直到最后分割成基本部分。
遞歸函數(shù)必須定義一個終止條件裸卫，即什么情況下終止遞歸仿贬，終止繼續(xù)調(diào)用自己，如果沒有終止條件墓贿，那么函數(shù)將一直調(diào)用自己茧泪，知道程序棧耗盡，這時候等于是寫了一個Bug!
總結(jié)遞歸的特點：
（1） 使用遞歸時聋袋，一定要有明確的終止條件队伟！
（2） 遞歸算法解題通常代碼比較簡潔，但不是很容易讀懂幽勒。
（3） 遞歸的調(diào)用需要建立大量的函數(shù)的副本嗜侮，尤其是函數(shù)的參數(shù)，每一層遞歸調(diào)用時參數(shù)都是單獨的占據(jù)內(nèi)存空間啥容，他們的地址是不同的锈颗，因此遞歸會消耗大量的時間和內(nèi)存。而非遞歸函數(shù)雖然效率高咪惠，但相對比較難編程击吱。
（4） 遞歸函數(shù)分為調(diào)用和回退階段，遞歸的回退順序是它調(diào)用順序的逆序硝逢。
1.例子：一個人趕著鴨子去每個村莊賣姨拥，每經(jīng)過一個村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了七個村子后還剩兩只鴨子渠鸽，問他出發(fā)時總共趕了多少只鴨子叫乌？經(jīng)過每個村子賣出多少只鴨子？
題目分析：經(jīng)過7個村子后他還剩2只鴨子徽缚，而每經(jīng)過一個村子賣出所趕鴨子的一半多一只憨奸，所以在經(jīng)過第七個村子前他所趕的鴨子數(shù)為（2+1）*2=6只，經(jīng)過第7個村子時賣出6/2+1=4只凿试。設經(jīng)過7個村子之后排宰，即在經(jīng)過第8個村子之前似芝，village=7,duck=2,即f(7)=2。f(6)=(f(7)+1)*2板甘，賣出f(6)/2+1只党瓮。以此類推，可得出他出發(fā)時的鴨子數(shù)以及經(jīng)過每個村子賣出鴨子數(shù)盐类。
算法分析：
數(shù)學公式
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f(x)表示經(jīng)過x村子后剩余的鴨子數(shù)寞奸，出發(fā)前的總數(shù)count=((f(1)+1)*2)。
算法實現(xiàn)：
for? (village = 0; village<7; village++)//經(jīng)過7個村莊
count = (duck + 1) * 2;//每經(jīng)過一個村莊之前剩余的鴨子數(shù)量
duck = count;//將值傳給dcuck,獲得最終鴨子數(shù)在跳，實現(xiàn)遞歸
當village=7時是遞歸出口
完整代碼：
#include<iostream>
using namespace std;
int main()
{
int village;//村莊
int duck = 2;//經(jīng)過7個村子之后的鴨子剩余數(shù)
int count = 0;//鴨子總數(shù)
cout << "經(jīng)過第7個村莊后枪萄，鴨子剩余" << duck << "只" << endl;
for (village = 0; village<7; village++)//經(jīng)過7個村莊
{
count = (duck + 1) * 2;//每經(jīng)過一個村莊之前剩余的鴨子數(shù)量
duck = count;//將值傳給duck,獲得最終鴨子數(shù)，實現(xiàn)遞歸
/*剩余的鴨子數(shù)+1才是賣出之前總鴨子數(shù)的一半猫妙，例如：
經(jīng)過第7個村莊后剩余2只鴨子瓷翻，那么經(jīng)過第7個村莊之前的總鴨子數(shù)為：duck=(2+1)*2
在第7個村莊賣出count/2+1只鴨子，剩余duck-((count+1)/2+1)只
*/
cout << "經(jīng)過第" << 7 - village << "個村莊時賣出" << (count + 1) / 2 + 1 << "只割坠，"
<< "剩余" << duck - ((count + 1) / 2 + 1) << "只" << endl;
}
cout << "出發(fā)前的鴨子總數(shù)為" << count << "只" << endl;
//返回鴨子總數(shù)
return count;
}
? ?
