chapter1 算法问题求解基础
1.1算法概述
1.什么是算法
- 算法—用计算机实现的问题求解方法。
- 5个特征
（1）输入：0或多个
（2）输出：至少一个
（3）确定性：算法每一条指令都有明确的定义
（4）能行性：算法每一条指令必须足够基本，可以用=已实现的基本运算执行有限次来实现。
（5）有穷性：有限步骤后终止 - 描述方法
大白话、流程图、伪代码、程序设计语言
例1 计算两个整数的最大公约数（辗转相除法==欧几里得算法、连续整数检测算法）
用于计算两个整数m和n（0<=m<n)的最大公约数gcd(m,n).其计算过程是重复下列等式，直到n mod m=0.
gcd(m,n)=gcd(n mod m,m)
例如gcd(24，60)=gcd(12,24)=gcd(0,12)=12
程序1-1 欧几里得递归算法 (递归调用函数)
#include<iostream>
#include<algorithm>
using namespace std;
//欧几里得递归算法
void Swap(int &a,int &b)//用于交换两个数的函数，其实有内置的swap函数，注意要变量的引用
{
int c=a;
a=b;
b=c;
}
int RGcd(int m,int n)//0<=m<n
{
if(m==0)return n;
return RGcd(n%m,m);
}
int Gcd(int m,int n)
{
if(m>n)Swap(m,n);
return RGcd(m,n);
}
int main()
{
int m,n;
cin>>m>>n;
cout<<Gcd(m,n);
return 0;
}
程序1-2 欧几里得迭代算法(循环）
#include<bits/stdc++.h>
using namespace std;
int Gcd(int m,int n)
{
if(m==0)return n;
if(n==0)return m;
if(m>n)swap(m,n);//n中保存大的数
while(m>0)
{
int rem=n%m;
n=m;
m=rem;
}
return n;
}
int main()
{
int m,n;
cin>>m>>n;
cout<<Gcd(m,n);
return 0;
}
连续整数检测算法
最大公约数定义：能够同时整除它们的最大正整数。因此最大公约数小于或等于两数中的较小者。t=min{m,n},然后检查t能否整除m和n ,若能，即为解；否则t–，继续检测
#include<bits/stdc++.h>
using namespace std;
int Gcd(int m,int n)
{
if(m==0)return n;
if(n==0)return m;
int t=m>n?n:m;
while(m%t ||n%t)
t--;
return t;
}
int main()
{
int m,n;
cin>>m>>n;
cout<<Gcd(m,n);
return 0;
}
2.为什么学习算法
重要重要重要
一个受过良好的计算机科学知识训练的人知道如何处理算法，即构造算法、操纵算法、理解算法和分析算法。算法远不只是为了编写好的计算程序，它是一种具有一般意义的智能工具，必定有助于对其他学科的理解。
1.2 问题求解方法
软件开发的过程----使用计算机求解问题的过程。
计算机解题的核心任务----设计算法
1.问题和问题求解
问题----与希望的目标不一致
2.问题求解过程
- 理解问题
- 设计方案
- 何处着手，类似问题
- 一些特殊示例进行分析
- 实现方案
- 回顾复查
- 评估：改进、简化和推广
3.系统生命周期
系统生命周期：软件工程将软件开发和维护过程分成若干阶段。分析（做什么）、设计（如何做）、编码、测试和维护
1.3 算法设计和分析
1.算法问题求解过程
精确算法、启发式算法（可能更有效，但未必是最优解）
2.如何设计算法
学习基本算法。
如合并排序和快速排序都可以视为分治法产生的排序算法，但二者是不同的算法。
3.如何表示算法
自然语言、流程图、伪代码、程序设计语言等，（下面主要用c/c++来描述）
4.如何确认算法
算法确认：对于所有的合法术后如，都能在有限时间输出预期结果。
算法证明：使用数学方法
5.如何分析算法
执行时间和所需空间
1.4 递归和归纳
重复性计算
（1）递归
（2）迭代
归纳法和递归关系密切，可以用归纳法证明递归算法的正确性。
1.递归
递归定义：直接或间接引用自身的定义方法。包括基础情况和递归部分
例1-1 斐波那契数列
F0=0,F1=1;
Fn=Fn-1+Fn-2;
需要注意的是，递归实现的斐波那契数列在计算过程中会存在大量的重复计算，效率较低。如果需要计算较大的斐波那契数列，建议使用迭代或动态规划的方法，可以避免重复计算，提高效率。
long Fib(int n)
{
if(n<=1)return n;
else return Fib(n-1)+Fib(n-2);
}
2.递归算法示例
例1-2 逆序输出整数的各位数 设有正整数n=12345,现希望逆序输出54321.
设k位整数为d1d2…dk,要得到dkdk-1…d1可以分两步：
（1）首先输出dk
（2）然后输出由前k-1位组成的正整数d1d2…dk-1
得到下面的递归程序
#include<bits/stdc++.h>
using namespace std;
void PrintDigit(unsigned int n)
{
cout<<n%10;
if(n>=10)PrintDigit(n/10);
}
int main()
{
unsigned int n;
cin>>n;
PrintDigit(n);
return 0;
}
例1-3 汉诺塔问题
假定有三个塔座：x,y,z,在塔座上有n个直径不同的圆盘，它们按直径大小从小到大编号为1，2，…，n。现要求将x塔座上的n个圆盘移动到y上，并按相同的顺序叠排。移动时：
（1）每次只能移动一个圆盘
（2）圆盘可以加到塔座x、y、z中任意一个之上
（3）任何时刻都不能将一个较大的圆盘放在较小的圆盘之上
假定圆盘从小到大编号为1-n，移动圆盘的算法可以粗略地描述如下：
（1）以y为中介，将前n-1个圆盘从x移到z上
（2）将第n个圆盘移到y上
（3）以x为中介，将z上的n-1个圆盘移到y上
#include<bits/stdc++.h>
using namespace std;
enum tower{A='X',B='Y',C='Z'};
void Move(int n,tower x,tower y)
{
//将第n个圆盘从x移到y的顶部
cout<<"The disk "<<n<<" is moved from "<<char(x)<<" to top of tower "<<char(y)<<endl;
}
void Hanoi(int n,tower x,tower y,tower z)//将n个圆盘从x->y,z作为中介
{
if(n){
Hanoi(n-1,x,z,y);
Move(n,x,y);
Hanoi(n-1,z,y,x);
}
}
int main()
{
Hanoi(3,A,B,C);
return 0;
}
输出如下
The disk 1 is moved from X to top of tower Y
The disk 2 is moved from X to top of tower Z
The disk 1 is moved from Y to top of tower Z
The disk 3 is moved from X to top of tower Y
The disk 1 is moved from Z to top of tower X
The disk 2 is moved from Z to top of tower Y
The disk 1 is moved from X to top of tower Y
例1-4 产生各种可能的排列
给定n个自然数，{0，1，2，…n-1}的集合。设计一个算法，输出该集合所有可能的排列（permutation).n个自然数的集合有n!个不同的排列。
介绍一种求此问题的简单递归算法。
由四个自然数组成的排列通过以下方式构造:
（1）以0 开头，紧随其后为{1，2，3}的各种排列
（2）以1 开头，紧随其后为{0，2，3}的各种排列
（3）以2 开头，紧随其后为{0，1，3}的各种排列
（4）以3 开头，紧随其后为{0，1，2}的各种排列
语句（1）中“紧随其后为{1，2，3}的各种排列”实质上是求比原始问题少一个数的排列生成问题。相当于原题目，这是一个同类子问题，但规模小一些。意味着可用递归求解
template <class T>
void Perm(T a[],int k,int n)
{
if(k=n-1)
{
for(int i=0;i<n;i++)//输出一种排列
cout<<a[i]<<" ";
}
else
for(int i=k;i<n;i++)
{
T t=a[k];a[k]=a[i];a[i]=t;//产生{a[k],...a[n-1]}各种排列
Perm(a,k+1,n);
t=a[k];a[k]=a[i];s[i]=t;//产生{a[k+1],...a[n-1]}各种排列
}
}
本章小结
递归是强有力的算法算法结构。
习题
1.写一个递归算法和一个迭代算法计算二项式系数。 Cnm=Cn-1m+Cn-1m-1=n!/m!(n-m)!
递归法
#include<bits/stdc++.h>
using namespace std;
int Combine(int m,int n)
{
if(m==0||m==n)return 1;//注意递归出口，是一个确定的值
else return Combine(m,n-1)+Combine(m-1,n-1);
}
int main()
{
int m,n;
cin>>m>>n;
cout<<Combine(m,n);
return 0;
}
迭代法是不是用一个数组保存结果呀，然后依次计算。
2.S是有n个元素的集合，S的幂集是S的所有可能的子集组成的集合。例如，S={a,b,c},S的幂集={{}，{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.写一个递归函数，以S为输入，输出S的幂集。
