问题重述：
1.一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
代码：
题目分析：
设在经过n
个村子时有xn
只鸭子，根据题意可以得到如下递推公式：
则在第n+1
个村子时有xn-xn2+1=xn2-1
只鸭子，即
xn+1=xn2-1
，所以xn-1=xn+1×2
在经过第7个村子书还剩下2只鸭子，即
x7=2
算法构造：
根据上述公式可以看出：
函数出口为： x7=2
函数体为：xn-1=xn+1×2
用最后的鸭子数倒推上一步的鸭子数，再以此类推，在经过最后一个村子时只剩下2两只鸭子，每递归一次经过的村次数就减少一个，直到最后为0即跳出函数
算法实现：
#include
using namespace std;
/*
Auther:Qiaoxue Zheng
Date:2018/11/15
Discribtion:To calculate how many duck the man have
when he sold hal of ducks and one more acrosss a village
and he only have two ducks when across 7 villages
*/
/*
Function:get the number of ducks when he passed count villages
Parameter:
count: the number of villages
*/
int saleDuck(int count) {
if (count == 0) {//exit,only two ducks left at last
return 2;
}
else {//body,get the number of ducks at the last time
count--;
return (saleDuck(count) + 1) * 2;
}
}
//Main function
int main() {
int acount_duck = 0;
int acount_village = 7;
acount_duck = saleDuck(acount_village);
cout <<"一共赶了"<
int all = 0;//the number of all ducks
int sale = 0;//the number of sold ducks
int rest = 0;//the number of rest ducks
//get the numbe of ducks when the man passed every village
for (int count = 7; count >= 1; count--) {
all = saleDuck(count);
sale = all / 2 + 1;
rest = all - sale;
cout << "经过第" << 8 - count << "个村庄时卖了" << sale << "只鸭子，还剩" << rest << "只鸭子" << endl;
}
system("pause");
return 0;
}
运行结果：
