第一章：分治算法——分而治之

  把一个复杂的问题分成2个或多个相似或相同的子问题，再把子问题分成更多的小的子问题......直到最后小问题可以简单的求解，原问题的解即子问题的解的合并。基于这个原理的高效算法有：快速，归并排序，傅立叶变换。

  比如：你要折断一个木头这个木头由10个小木头组成，那么你会怎么做？ 答：分成5个，再分成1个   

            （8+9）*6=？ 运算步骤

---

  折半查找法

  问题1：在一排（10000以内）已按编号大小排好序的图书中，快速按编号查找到某本书所在的位置（数组2，4，6）

              输入格式：输入要查找的数

              输出格式：一个数，否则输出-1

            输入样例： 4

            输出样例：1

  作业1：在数组 （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] 已经发现，退出查找

    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++ 算法第二天

 

C++ 算法竞赛宝典2019.7.2

第二部分  算法

  递归算法：

        递归函数即自调用函数，在函数内部直接的或者间接地调用自己。在求解某些具有随意性的复杂问题时经常使用递归，如要求编写一个函数，将输入的任意长度的字符串反向输出。普通做法是将字符串放入数组中然后将数组元素反向输出即可，然而这里的要求是输入是任意长度的，总不能开辟一个很大的空间保存字符串吧？这时候递归就起作用了。递归采用了分治的思想，将整体分割成部分，从最小的基本部分入手，逐一解决，其中部分通常和整体具有相同的结构，这样部分可以继续分割，直到最后分割成基本部分。

递归函数必须定义一个终止条件，即什么情况下终止递归，终止继续调用自己，如果没有终止条件，那么函数将一直调用自己，知道程序栈耗尽，这时候等于是写了一个Bug!

总结递归的特点：

（1） 使用递归时，一定要有明确的终止条件！

（2） 递归算法解题通常代码比较简洁，但不是很容易读懂。

（3） 递归的调用需要建立大量的函数的副本，尤其是函数的参数，每一层递归调用时参数都是单独的占据内存空间，他们的地址是不同的，因此递归会消耗大量的时间和内存。而非递归函数虽然效率高，但相对比较难编程。

（4） 递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

---

1.例子：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时总共赶了多少只鸭子？经过每个村子卖出多少只鸭子？

题目分析：经过7个村子后他还剩2只鸭子，而每经过一个村子卖出所赶鸭子的一半多一只，所以在经过第七个村子前他所赶的鸭子数为（2+1）*2=6只，经过第7个村子时卖出6/2+1=4只。设经过7个村子之后，即在经过第8个村子之前，village=7,duck=2,即f(7)=2。f(6)=(f(7)+1)*2，卖出f(6)/2+1只。以此类推，可得出他出发时的鸭子数以及经过每个村子卖出鸭子数。

算法分析：

数学公式

C++ 算法竞赛宝典2019.7.2

                              f(x)表示经过x村子后剩余的鸭子数，出发前的总数count=((f(1)+1)*2)。

算法实现：

for  (village = 0; village<7; village++)//经过7个村庄

count = (duck + 1) * 2;//每经过一个村庄之前剩余的鸭子数量

duck = count;//将值传给dcuck,获得最终鸭子数，实现递归

当village=7时是递归出口

完整代码：

#include<iostream>

using namespace std;

int main()

{

int village;//村庄

int duck = 2;//经过7个村子之后的鸭子剩余数

int count = 0;//鸭子总数

cout << "经过第7个村庄后，鸭子剩余" << duck << "只" << endl;

for (village = 0; village<7; village++)//经过7个村庄

{

count = (duck + 1) * 2;//每经过一个村庄之前剩余的鸭子数量

duck = count;//将值传给duck,获得最终鸭子数，实现递归

/*剩余的鸭子数+1才是卖出之前总鸭子数的一半，例如：

经过第7个村庄后剩余2只鸭子，那么经过第7个村庄之前的总鸭子数为：duck=(2+1)*2

在第7个村庄卖出count/2+1只鸭子，剩余duck-((count+1)/2+1)只

*/

cout << "经过第" << 7 - village << "个村庄时卖出" << (count + 1) / 2 + 1 << "只，"

<< "剩余" << duck - ((count + 1) / 2 + 1) << "只" << endl;

}

cout << "出发前的鸭子总数为" << count << "只" << endl;

//返回鸭子总数

return count;

}