算法设计与分析——第二章_递推算法
递归算法
（Recursion）。
¢一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
¢递归需要有边界条件、递归前进段和递归返回段。
在递归调用过程中，系统为每一层的返回点、局部变量等开辟了堆栈来存储。递归次数过多容易造成堆栈溢出等。
int fib[50]; //采用数组保存中间结果
void fibonacci(int n)
{
fib[0] = 1;
fib[1] = 1;
for (int i=2; i<=n; i++)
fib[i] = fib[i-1]+fib[i-2];
}
集合的全排列问题
//产生从元素k～m的全排列，作为前k—1个元素的后缀
void Perm(int list[], int k, int m)
{
//构成了一次全排列，输出结果
if(k==m)
{
for(int i=0;i<=m;i++)
cout<<list[i]<<" ";
cout<<endl;
}
else
//在数组list中，产生从元素k～m的全排列
for(int j=k;j<=m;j++)
{
swap(list[k],list[j]);
Perm(list,k+1,m);
swap(list[k],list[j]);
}
}
//产生从元素k～m的全排列，作为前k—1个元素的后缀
void Perm(int list[], int k, int m)
{
if(k==m) //构成了一次全排列，输出结果
{
for(int i=0;i<=m;i++)
cout<<list[i]<<" ";
cout<<endl;
}
else
//在数组list中，产生从元素k～m的全排列
for(int j=k;j<=m;j++)
{
swap(list[k],list[j]);
Perm(list,k+1,m);
swap(list[k],list[j]);
}
}
整数划分问题
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1
分治策略
二分搜索技术
3.6 二分搜索算法
//数组a[]中有n个元素，已经按升序排序，待查找的元素x
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0; //左边界
int right=n-1; //右边界
while(left<=right)
{
int middle=(left+right)/2; //中点
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
} return -1; //未找到x
}
循环赛日程表
void Table(int k)
{
int i, r;
int n = 1 << k;
//构造正方形表格的第一行数据
for (i=0; i<n; i++)
a[0][i] = i + 1;
//采用分治算法，构造整个循环赛日程表
for (r=1; r<n; r<<=1)
for (i=0; i<n; i+=2*r)
{
Copy(r, r + i, 0, i, r); //①
Copy(r, i, 0, r + i, r); //②
}
}
实现方阵的拷贝
//源方阵的左上角顶点坐标（fromx, fromy），行列数为r
//目标方阵的左上角顶点坐标（tox, toy），行列数为r
void Copy(int tox, int toy, int fromx, int fromy, int r)
{
for (int i=0; i<r; i++)
for (int j=0; j<r; j++)
a[tox+i][toy+j] = a[fromx+i][fromy+j];
}
输油管道问题
采用分治策略求中位数
int n; //油井的数量
int x; //x坐标，读取后丢弃
int a[1000]; //y坐标
cin>>n;
for (int i=0; i<n; i++)
cin>>x>>a[i];
int y = select(0, n-1, n/2); //采用分治算法计算中位数
//计算各油井到主管道之间的输油管道最小长度总和
int min=0;
for(int i=0;i<n;i++)
min += (int)fabs(a[i]-y);
cout<<min<<endl;
半数集问题
(1) n set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6，16，26，126，36，136}。
半数集set(6)中有6个元素。
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
计算半数集问题的递归算法—记忆式搜索
int a[1001];
int comp(int n)
{
int ans=1;
if(a[n]>0)return a[n]; //已经计算
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans; //保存结果
return ans;
}
整数因子分解
int total; //定义为全局变量
void solve(int n)
{
if (n==1) total++; //获得一个分解
else for (int i=2; i<=n; i++)
if (n%i==0) solve(n/i);
}
//主函数main()中数据的读取与调用
int n;
while( scanf("%d",&n)!=EOF)
{
total = 0;
solve(n);
printf("%d\n",total);
}
取余运算
int mod(__int64 a, __int64 p, __int64 k)
{
if (p == 1) return a%k;
if (p%2) return mod(a%k, p-1, k)*a%k; //p是奇数
else return mod((a*a)%k, p/2, k); //p是偶数
}
//主函数main()中数据的读取与调用
unsigned a, p, k;
while (scanf("%u%u%u",&a,&p,&k)!=EOF)
printf("%d\n", mod(a, p, k));