例题一 兔子繁殖问题
一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中指定月份有多少对兔子？
分析：
一月份有1对，二月份也是1对，三月份2对（新出生一对），四月份3对，五月份5对……
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | 1 | 2 | 3 | 5 | 8 | . | . | . | . | . | （n-1)+(n-2) |
即为斐波那锲数列求和问题。根据问题有迭代公式 f(n)=f(n-1)+f(n-2),初始条件 f(1)=1; f(2)=1;
第一种解决方法：
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int f[12];
f[0]=1;
f[1]=2;
if(n<2){
cout<<1<<endl;
return 0;
}
for(int i=2;i<n;i++){
f[i]=f[i-1]+f[i-2];
}
cout<<f[n-1]<<endl;
return 0;
}这种解决方法可以把n个月的结果都计算并保存下来，时间复杂度为O(n)，空间复杂度也为O(n）
第二种解决方法：
用A代替 f(n-1),B代替 f(n-2)，C代替 f(n)，可减少空间开销,空间复杂度为O(1),时间复杂度仍为O(n)
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int A=1,B=1;
int C;
if(n<3){
cout<<1<<endl;
return 0;
}
for(int i=3;i<=n;i++){
C=A+B;
A=B;
B=C;
}
cout<<C<<endl;
return 0;
}
例题二 数组a[n]构造b[n]
给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，
不允
许使用除法
；要求O(1) 空间复杂度和O(n) 的时间复杂度
假设N=5,即a[5]={a0,a1,a2,a3,a4}，根据题干中给出的b[n]的公式可得：
| i | 0 | 1 | 2 | 3 | 4 |
| b[i] | a1*a2*a3*a4 | a0*a2*a3*a4 | a0*a1*a3*a4 | a0*a1*a2*a4 | a0*a1*a2*a3 |
代码一：
#include<iostream>
#define MAX 1000
using namespace std;
int main(){
int a[MAX],b[MAX]={1};
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=i){
b[i]*=a[j];
}
}
}
for(int i=0;i<n;i++){
cout<<b[i]<<" ";
cout<<endl;
return 0;
}
虽然满足不使用除法，但算法中时间复杂度为O(
）空间复杂度为O(n)不符合题意；
改进1：由表格中的数据可知，每个b[i]都可以根据下标分为大于 i 和小于 i的两个部分，如：b[0]=
1
*
a[1]*a[2]*a[3]*a[4]
，b[2] =
a[0]*a[1]
*
a[3]*a[4]
, b[3]=
a[0]*a[1]*a[2]
*
a[4]
，
以此可将b[i]转换成两个部分的积：
left[i]=a[0]*a[1]*…*a[i-1];
right[i]=a[i+1]*a[i+2]*…*a[n];
b[i]=left[i]*right[i];
此时，计算left和right的时间复杂的均为O(n)，空间复杂度为O(n)，进一步可以将left[i]转化:
left[i]=a[i-1]*
left[i-1]
; 同理：right[i]=a[i-1]*
right[i+1]
;
#include<iostream>
#define MAX 1000
using namespace std;
int main(){
int n;
cin>>n;
int left[MAX],right[MAX],b[MAX],a[MAX];
for(int i=0;i<n;i++){
cin>>a[i];
}
left[0]=1;
right[n-1]=1;
for(int i=1;i<n;i++){
left[i]=a[i-1]*left[i-1];
}
for(int i=n-2;i>=0;i--){
right[i]=a[i-1]*right[i+1];
}
for(int i=0;i<n;i++){
b[i]=left[i]*right[i];
}
for(int i=0;i<n;i++)
cout<<b[i];
cout<<endl;
return 0;
}上述算法中空间复杂度为O(n),仍不满足题目的要求，降低空间复杂度：
b[i]=a[i+1]*b[i+1]; temp=a[i]; a[i]=temp*a[i-1]; b[i]=b[i]*a[i];
其中b[n-1]=1；此时空间复杂度满足条件为O(1)；
最终代码：
#include<iostream>
#define max 1000
using namespace std;
int main(){
int n,temp;
int a[max],b[max];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
b[n-1]=1;
for(int i=n-2;i>=0;i--){
b[i]=a[i+1]*b[i+1];
}
temp=a[0];
a[0]=1;
for(int i=1;i<n;i++){
a[i]=temp*a[i-1];
temp=a[i];
}
for(int i=0;i<n;i++){
b[i]=b[i]*a[i];
cout<<b[i];
}
cout<<endl;
return 0;
}
例三 求最大公约数
求两个数的最大公约数，给定两个整数a,b，求最大的正整数c，使得c|a，c|b
（c|a 表示c整除a）
辗转相除法
#include<iostream>
using namespace std;
int GCD(int a,int b){
int c;
if(a<b){
int temp;
temp=a;
a=b;
b=temp;
}
while(b!=0){
c=b;
b=a%b;
a=c;
}
return c;
}
int main(){
int a,b;
cin>>a,b;
int C;
C=GCD(a.b);
cout<<C<<endl;
return 0;
}