递归与搜索部分知识点小结
搜索部分学习小结
背包问题知识总结
动态规划部分知识点总结
贪心算法部分知识点
贪心算法部分题目及知识点总结
知识补充：
递归：
循环，迭代，递推，递归的区别：
循环：不断重复进行某一运算、操作。
迭代（A重复调用B）：不断对前一旧值运算得到新值直到达到精度。一般用于得到近似目标值，反复循环同一运算式（函数），并且总是把前一 次运算结果反代会运算式进行下一次运算
递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）
回溯：递归时经历的一个过程。
递归（A调用A）：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大(你想进bat，那么编程就的牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。
递归的三大元素（思路步骤）：
1、明确函数想要干什么
2、寻找递归结束条件
3、找出函数的等价关系式
注意：当我们第三步找出等价函数之后，还得再返回去第二步，根据第三步函数的调用关系，看看会不会出现一些漏掉的结束条件（避免出错或者死循环等问题（递归结束条件考虑的少，循环一直无法结束））。
递归的优化思路：
1.考虑是否有重复计算：当一个递归调用开始时，可能存在很多子问题的重复计算，这样在做这些重复计算时会花费更多的时间，造成不必要的时间浪费，当然一个程序想要做到完美是非常困难的，我们也不可能超越程序应该有的时间复杂度和空间复杂度去直接给出结果，这里对于时间的优化，我们给出以空间换取时间的思路，用备忘录的方式去记录那些可能存在重复计算的子问题的结果，当遇到已经计算出结果的子问题时，我们采取直接取出结果代替重复计算的方式去进行优化。
//设这里递归函数的等价关系为f(n)=f(n-1)+f(n-2)
int f(int n){
if(n <= 1){
return n;
}
//先判断有没计算过（假定初始数组元素为-1）
if(arr[n] != -1){
//计算过，直接返回
return arr[n];
}else{
// 没有计算过，递归计算,并且把结果保存到 arr数组里
arr[n] = f(n-1) + f(n-2);
reutrn arr[n];
}
}
递归转迭代：
理论上递归和迭代可以相互转换，但实际从算法结构来说，递归声明的结构并不总能转换为迭代结构，即迭代可以转换为递归，但递归不一定能转换为迭代。一般来说能用迭代的就不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出（尾递归可以解决堆栈的溢出，但是仍然避免不了函数调用的开销）。
将递归算法转换为非递归算法有两种方法，一种是直接求值（迭代），不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法，后者使用栈保存中间结果，称为间接转换法。
直接转换法：
直接转换法通常用来消除尾递归（tail recursion）和单向递归，将递归结构用迭代结构来替代。（单向递归 → 尾递归 → 迭代）
间接转换法：
递归实际上利用了系统堆栈实现自身调用，我们通过使用栈保存中间结果模拟递归过程，将其转为非递归形式。
尾递归函数递归调用返回时正好是函数的结尾，因此递归调用时就不需要保留当前栈帧，可以直接将当前栈帧覆盖掉。
//这是递归
int funcA(int n)
{
if(n > 1)
return n+funcA(n-1);
else
return 1;
}
//这是迭代
int funcB(int n)
{
int i,s=0;
for(i=1;i<n;i++)
s+=i;
return s;
}
对于尾调用、尾递归等概念可以参考以下文章：
动态规划：
介绍动态规划之前先介绍一下分治策略。
分治策略：
将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。
因为在求解大问题时，需要递归的求小问题，因此一般用「递归」的方法实现，即自顶向下。
动态规划：
动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
将「动态规划」的概念关键点抽离出来描述就是这样的：
-
1.动态规划法试图只解决每个子问题一次
-
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
动态规划的三大步骤：
动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤：
第一步：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
第二步： 找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。
第三步： 找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这就是所谓的初始值。
有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。
参考文章：
为什么你学不会递归？告别递归，谈谈我的一些经验
再谈循环&迭代&回溯&递归&递推这些基本概念
递归与迭代的区别
尾递归
尾调用优化
为什么你学不过动态规划？告别动态规划，谈谈我的经验
作业一：
数字三角形算法：
#include<iostream>
int a[1001][1001];
using namespace std;
int main()
{
int n,i,j;
//int a[1001][1001]; //得出一个结论：当数组在主函数内部时不宜开太大，否则导致程序崩溃（这里a[1001][1001]太大，a[101][101]OK）
cin>>n;
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
cin>>a[i][j];
for (i=n-1; i>=1; i--){
for (j=1; j<=i; j++)
{
if (a[i+1][j]>=a[i+1][j+1])
a[i][j]+=a[i+1][j];
else
a[i][j]+=a[i+1][j+1];
}
}
cout<<a[1][1]<<endl;
return 0;
}
小朋友上台阶（斐波那契数列）：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int f1=1,f2=2,f;
int n;
cin>>n;
for (int i=3; i<=n; ++i)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(n==1) cout<<1<<endl;
else if(n==2) cout<<2<<endl;
else cout<<f<<endl;
return 0;
}
输油管道问题：
#include<stdio.h>
#include<stdlib.h> //abs函数对浮点数操作会报错
#include<math.h>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000]; //记录y坐标
int select(int left, int right, int k)
{
//找到了第k小的元素：
if (left >= right) return a[left];
int i = left;
int j = right+1;
int pivot = a[left];
while (true)
{
do {
i = i+1; //从第i+1位置向右扫描，找出a[i]>pivot的值停止
} while (a[i] < pivot);
do {
j = j-1; //从第j-1位置向左扫描（实际第一次是原来位置的right（right+1-1），直到a[j]<pivot停止
} while (a[j] > pivot);
if (i >= j) break; //表示没有可交换的对象了
swap(a[i], a[j]); //交换完毕后指针i继续从i+1位置继续向右扫描，指针j继续从j+1位置向左扫描
}
if (j-left+1 == k) return pivot;
//此时的a[j]比a[left](pivot)小，因此互相交换一下，此时a[j]左边比a[j]小，右边比a[j]大，完成一次排序划分
//对于a[j]左边的数据进行二次划分则以第一次的a[j]为pivot(a[left])
//这样数组的数据没有丢失且完成了对pivot的一次划分
a[left] = a[j];
a[j] = pivot;
if (j-left+1 < k)
return select(j+1, right, k-j+left-1);
else return select(left, j-1, k);
}
int main()
{
int n; //油井的数量
int x; //x坐标，读取后丢弃
cin>>n;
for(int k=0; k<n; k++)
cin>>x>>a[k];
sort(a,a+n); //按升序排序
//计算各油井到主管道之间的输油管道最小长度总和
int min=0;
for(int i=0; i<n; i++)
min += (int)fabs(a[i]-a[n/2]); //abs函数与fabs函数区别
cout<<"采用对数组a排序，取中间的元素的算法求解： "<<min<<endl;
//abs函数与fabs函数区别：
//C语言中：
//abs函数包含在<stdlib.h>头文件中，只对整型求绝对值，对浮点数求整会报错
//fabs函数包含在<math.h>头文件中，对浮点数求绝对值，对整数求绝对值会出现问题
//因此在C语言中一定要选对函数
/*
// 使用fabs求一个整数的绝对值
printf("fabs(-3)(%%d): %d\n", fabs(-3));
printf("fabs(-3)(%%f): %f\n\n", fabs(-3));
// 使用abs求一个浮点数的绝对值
printf("abs(-3.14)(%%d): %d\n", abs(-3.14));
printf("abs(-3.14)(%%f): %f\n", abs(-3.14));
*/
//C++中二者没有区别，都包含在<cmath>头文件中，都可以对浮点数进行操作
/*
double a=10;
double b=-90;
cout<<abs(a)<<" "<<fabs(b)<<endl;
*/
// int n; //油井的数量
// int x; //x坐标，读取后丢弃
cin>>n;
for (int i=0; i<n; i++)
cin>>x>>a[i];
int y = select(0, n-1, n/2); //采用分治算法计算中位数（选择数组中第n/2小的数，即中位数）
//计算各油井到主管道之间的输油管道最小长度总和
min=0;
for(int i=0; i<n; i++)
min += (int)fabs(a[i]-y);
cout<<"采用分治策略求中位数的算法求解： "<<min<<endl;
/*
快速排序算法是分治策略的典型应用，不过不是对问题进行等份分解（二分法），
而是通过分界数据（支点）将问题分解成独立的子问题。
记一趟快速排序后，分解出左子集中元素个数为 nleft,则选择问题可能是以下几种情况之一：
nleft ＝k﹣1，则分界数据就是选择问题的答案。
nleft ＞k﹣1，则选择问题的答案继续在左子集中找，问题规模变小了。
nleft ＜k﹣1，则选择问题的答案继续在右子集中找，问题变为选择第k-nleft-1 小的数，问题的规模变小了。
此算法在最坏情况时间复杂度为 O(n2) ，此时nleft总是为0，左子集为空，即第k小元素总是位于right子集中。
平均时间复杂度为 O(n )。
*/
/*
result:
5
1 2
2 2
1 3
3 -2
3 3
采用对数组a排序，取中间的元素的算法求解： 6
5
1 2
2 2
1 3
3 -2
3 3
采用分治策略求中位数的算法求解： 6
*/
}
最大子段和问题：
#include<iostream>
using namespace std;
#define NUM 1001
int a[NUM];
int MaxSum(int n, int &besti, int &bestj)
{
int sum=0;
int b=0;
int begin=0;
for(int i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else{
b=a[i];
begin = i;
}
if (b>sum) //得到新的最优值时，更新最优解
{
sum = b;
besti = begin;
bestj = i;
}
}
return sum;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int besti=0;
int bestj=0;
int sum=MaxSum(n,besti,bestj);
cout<<sum<<" "<<"首地址："<<besti<<" 尾地址:"<<bestj<<endl;
return 0;
}
0-1背包动态规划：
#include <iostream>
using namespace std;
int w[105], val[105]; //用w[]和val[]数组分别表示每件物品的重量和价值
int dp[105][1005]; //利用dp[][]来记录输入m项物品和t容量时的最大价值
int main()
{
int m, t;
cin >> m >> t;
for(int i=1; i<=m; i++)
cin >> w[i] >> val[i];
/*
//初始化或者置零等操作（这里无需初始化，数组默认值为零）
for(int i=1; i<=m; i++) //物品
{
for(int j=t; j>=0; j--) //容量
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1; i<=m; i++) //物品
for(int j=t; j>=0; j--) //容量
{
if(j >= w[i]) //容量大于物品质量的时候，表示物品可以装，这时候选择装或者不装两个状态
dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);
else //容量小于物品质量的时候，装不下
dp[i][j] = dp[i-1][j];
}
cout << dp[m][t] << endl;
/*
//test_cout
for(int i=1; i<=m; i++) //物品
{
for(int j=t; j>=0; j--) //容量
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
*/
return 0;
}
//优化（将二维数组转换成一维数组实现空间优化）：
//f[j]=max(f[j-w[i]]+v[i],f[j]);
/*
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include <stdio.h>
#include <string.h>
int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
int max(int x,int y){//返回x,y的最大值
if(x>y) return x;
return y;
}
int main(){
int t,m,i,j;
memset(f,0,sizeof(f)); //总价值初始化为0
scanf("%d %d",&t,&m); //输入背包承重量t、物品的数目m
for(i=1;i<=m;i++)
scanf("%d %d",&w[i],&v[i]); //输入m组物品的重量w[i]和价值v[i]
for(i=1;i<=m;i++){ //尝试放置每一个物品
for(j=t;j>=w[i];j--){//倒叙是为了保证每个物品都使用一次
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
}
}
printf("%d\n",f[t]); //输出承重量为t的背包的总价值
return 0;
}
*/
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出：
8
*/
背包问题的贪心算法：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Pair{ //每个物品的单位价值（单位价值如果没说的话，可以采用总价值除以总质量获取单位价值）和总重量
int cost;
int weight;
};
bool cmp( const Pair &x,const Pair &y) //默认排序方式是按单位质量的价值高低进行排序，价值高者优先放（贪心策略）
{
return x.cost > y.cost;
}
int n, s, m, v, w; //s件物品，v和m表示输入的价值和质量，n表示执行n次
const int maxn=100001;
Pair pack[maxn];
int sum=0;
int main()
{
cin>>n; //表示执行次数
while(n--)
{
scanf("%d%d",&s,&m);
sum=0;
for(int i=1;i<=s;i++)
{
pack[i].cost=0;
pack[i].weight=0;
}
for(int i=1;i<=s;i++)
{
scanf("%d%d",&v,&w);
pack[i].cost=v;
pack[i].weight=w;
}
sort( pack+1,pack+s+1,cmp);
//开时装包
int i;
for(i=1;i<=s;i++) //从第一件物品（价值高者）开始装，这样按照价值高者的优先策略依次装入背包
{
//如果某一件物品的总量超过了该背包的剩余总量，
//也就是可以按照将该物品瓜分的策略进行装取：
//sum+=pack[i].cost*m;方式进行，然后跳出循环（背包已满）
if(pack[i].weight > m)
{
sum+=pack[i].cost*m;
break;
}
else //全装下背包也不满，那就全装下，然后总价值增加，容量减少
{
sum+=pack[i].cost*pack[i].weight;
m-=pack[i].weight;
}
}
printf("%d\n",sum);
}
return 0;
}
/*
//test:
//输入：
1
3 15
5 10
2 8
3 9
//输出：
65
*/
木棒的加工：
//每一次加工，开头第一个长度序列的先加工完，之后，再在长度不同的序列，
//找出重量比最后加工的木棒重量还要大的木棒，进行加工，直至找不到为止。
//（这就变成了长度比较确定后寻找质量最长单调递增子序列的个数。）
#include<bits/stdc++.h>
using namespace std;
#define maxN 5001
struct stick
{
int l; //木棒的长度
int w; //木棒的重量
}data[maxN]; //所存放的木棒
int cmp(stick a,stick b)
{
if(a.l==b.l)return a.w<b.w; //长度相同时，按重量排序
else if(a.l<b.l)return true; //优先按长度排序
return false;
}
int LIS(int n,stick a[])//木棒数量 木棒参数的数组
{
int b[maxN];//木棒分组的序号
memset(b,0,sizeof(b));//给b赋初值为0，长度为maxN
int i,j,k;
b[0]=1; //边界条件
for(i=1;i<n;i++)
{//计算第i个木棒的分组序号
k=0;
for(j=0;j<i;j++)
if(a[i].w<a[j].w&&k<b[j])k=b[j]; //关系式
b[i]=k+1;
}
//查找最大的分组序号（数组b中的最大值）
int max=0;
for(i=0;i<n;i++)
if(b[i]>max)max=b[i];
return max;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>data[i].l>>data[i].w;//4 9 5 2 2 1 3 5 1 4
}
sort(data,data+n,cmp);
int bb=LIS(n,data);
cout<<bb;
}
鱼塘钓鱼问题：
#include <cstdio>
using namespace std;
int t[101],f[101],d[101],f1[101],la,n,m,max;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&f[i]);
for (int i=1;i<=n;i++) scanf("%d",&d[i]);
for (int i=1;i<n;i++) scanf("%d",&t[i]);
scanf("%d",&m);
for (int k=1;k<=n;k++){
int ti=m-la,ans=0,j=0;
for (int i=1;i<=k;i++) f1[i]=f[i];
for (int i=1;i<=k;i++) if (f1[i]>f1[j]) j=i;//找最大值
while (ti>0&&f1[j]>0){
if (f1[j]>0) ans+=f1[j];
f1[j]-=d[j];
for (int i=1;i<=k;i++) if (f1[i]>f1[j]) j=i;//更新
ti--;
}
max=(max>ans)?max:ans;
la+=t[k];
}
printf("%d",max);
return 0;
}
/*
test：
输入：
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
输出：
76
*/
实验一：
杨辉三角形：
#include <stdio.h>
int main()
{
int i, j, n, a[34][34];
scanf("%d", &n);
for (i = 0; i < n; i++)
{
a[i][0] = 1;
a[i][i] = 1;
for (j = 1; j < i; j++)
a[i][j] = a[i-1][j-1] + a[i-1][j];
}
for (i = 0; i < n; i++)
{
for (j = 0; j <= i; j++)
printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
字符串对比：
#include<stdio.h>
#include<string.h>
int main()
{
int len1,len2;
char ch1[10],ch2[10];//定义字符串数组
scanf("%s%s",ch1,ch2);
len1=strlen(ch1);//求字符串长度
len2=strlen(ch2);
if(len1==len2)//判断字符串长度是否相等
{
int flag=1;//定义一个标识符
for(int i=0;i<len1;i++)
if(ch1[i]!=ch2[i])//判断如果不相同
flag=0;//使标识符变化
if(flag) printf("2");//判断，如果标识符没有改变，则符合条件2
else
{
flag=1;//重新定义标识符
for(int i=0;i<len1;i++)//判断，如果在忽略大小写的情况下是否还是不同
if(ch1[i]+32!=ch2[i]&&ch1[i]-32!=ch2[i]&&ch1[i]!=ch2[i])
flag=0;//使标识符改变
if(flag) printf("3");//如果标识符没有改变 ，则符合条件3
else printf("4");//否则符合条件4
}
}
else printf("1");//否则符合条件1
}
拦截导弹（LIS，贪心，动态规划）：
//LIS解法，将导弹拦截问题转化为最长上升子序列问题（最长不递增子序列）
#include<stdio.h>
#include<string.h>
int Height[101]; //发射过来的导弹高度
int MaxLen[101]; //发射第i颗导弹处记录的最大不上升子序列的个数
int Maxint[101]; //用来记录发射第i颗导弹需要的最大拦截导弹系统的个数
void LIS(int k){ //拦截导弹问题即找出最长不上升子序列问题
memset(MaxLen,0,sizeof(MaxLen));
memset(Maxint,0,sizeof(Maxint));
for(int i = 1;i <= k; i++){
MaxLen[i] = 1;
Maxint[i]=1;
//遍历其前所有导弹高度
for(int j = 1;j < i;j++){
//如果当前导弹高度小于等于j号导弹
if(Height[i] <= Height[j]){
//把当前导弹放在j号导弹后，其最长不增子序列长度为j号导弹结尾的最长不增子序列长度 + 1
int preMax = MaxLen[j] + 1;
if(preMax > MaxLen[i]){
MaxLen[i] = preMax;
}
}
else{ //如果当前导弹高度大于j号导弹高度，那么我们就需要增加导弹系统拦截
int preMaxint = Maxint[j] + 1;
if(preMaxint > Maxint[i]){
Maxint[i] = preMaxint;
}
}
}
}
}
int main()
{
int N,i; //N表示发射过来的导弹数量
while(scanf("%d",&N)!=EOF){
//输入导弹高度
for(i = 1;i <= N;i++){
scanf("%d",&Height[i]);
}
LIS(N);
int Max = -1;
int ans = -1;
//输出最长不增子序列的长度即能拦截的导弹数
for(i = 1;i <= N;i++){
if(Max < MaxLen[i]){
Max = MaxLen[i];
}
if(ans < Maxint[i]){
ans = Maxint[i];
}
}
if(N != 0){
printf("%d %d\n",Max,ans);
}
}
return 0;
}
/*
//用于解此题的还有动态规划和贪心算法求解：
//动态规划求解：
for(int i=1; i<=n; i++)
{
for(int j=0; j<i; j++) //与前面每一个比较一次
{
if(a[j]<a[i]) //需要多加1个系统 （a[]数组用于存放导弹高度）
dp[i]=max(dp[i],dp[j]+1); //选出需要最少系统的最大值 （dp[]初始值为1）
//将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（体现了动态规划的思想）
}
}
sort(dp,dp+n);
cout<<dp[n-1]<<endl;
//贪心算法求解：
while(~scanf("%d",&n)) //n表示导弹个数
{
int x,sum=0;
dp[maxn]={0};
for(int i=0;i<n;i++)
{
cin>>x;int j; //x表示导弹高度
//利用sum表示当前至少有多少系统，并在每次导弹发射时遍历这些系统所能拦截的最大高度，
//进行比较后如果能拦截，即x<=dp[j]则更新该系统的最大拦截高度值，否则则遍历下一个最大拦截高度值，
//如果都没有，那么就是遍历到了最后，此时j=sum+1>sum，则增加一个新系统去拦截该导弹
//这里每次都拿已有的最大高度值去和新发射的导弹高度值进行比较，
//即从问题的初始状态出发，直接去求每一步的最优解，
//通过若干次的贪心选择，最终得出整个问题的最优解（体现了贪心算法的思想）
for(j=1;j<=sum;j++)
{
if(x<=dp[j]) //这里的dp[j]表示该系统在j处能拦截的最大高度
{
dp[j]=x; //更新该系统下一个能拦截的最大高度
break;
}
}
if(j>sum) //前面的系统不能拦截
{
dp[++sum]=x;//新加一个系统并且赋值下一次能拦截的高度
}
}
cout<<sum<<endl;
}
*/
/*
//test:
//输入：
8
389 207 155 300 299 170 158 65
//输出：
6 2
*/
八（n）（2n）皇后问题：
#include<iostream>
#include <cstdio>
using namespace std;
int arry[10][10];
int count=0; //存储方案结果数量
bool check(int k,int j){ //判断节点是否合适（k代表行，j代表列）
for(int i=0;i<8;i++){ //检查行列冲突（其实这里只检查列冲突即可，行是遍历来的，是不会产生冲突的）
if(arry[i][j]==1){
return false;
}
}
for(int i=k-1,m=j-1; i>=0 && m>=0; i--,m--){ //检查左对角线
if(arry[i][m]==1){
return false;
}
}
for(int i=k-1,m=j+1; i>=0 && m<=7; i--,m++){ //检查右对角线
if(arry[i][m]==1){
return false;
}
}
return true;
}
void print(){ //打印结果
cout<<"方案"<<count<<":"<<endl;
for(int i=0;i<8;i++){
for(int m=0;m<8;m++){
if(arry[i][m]==1){
cout<<"o ";
}
else{
cout<<"+ ";
}
}
cout<<endl;
}
cout<<endl;
}
void findQueen(int i){//寻找皇后节点
if(i>7){//八皇后的解
count++;
print();//打印八皇后的解
return;
}
for(int m=0;m<8;m++){ //深度回溯,递归算法
if(check(i,m)){ //检查皇后摆放是否合适
arry[i][m]=1;
findQueen(i+1); //合适则置一，并往下递归调用求解
arry[i][m]=0; //清零，以免回溯的时候出现脏数据（这一步是找到结果之后进行的操作，防止影响下一个结果，恢复到上一步的初始状态）
}
}
}
int main() {
findQueen(0); //从第0行开始，如果是i，则表示前i行没有摆放的皇后，不会影响后面的排列，变成8-i个皇后在没有限制的8-i行寻找位置
cout<<"八皇后问题共有："<<count<<"种可能"<<endl;
}
实验二：
Fibonacci数列：
#include <stdio.h>
int F(int n)
{
int i, s1 = 1, s2 = 1, s3 = 1;
for (i = 3; i <= n; i++)
{
s3 = s1 + s2;
if (s3 > 10007)
s3 -= 10007;
s1 = s2;
s2 = s3;
}
return s3;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", F(n));
return 0;
}
校门外的树：
#include <iostream>
using namespace std;
int main()
{
int L,M;
int num[10001]={0};
int n=0;
cin>>L>>M;
int a[100],b[100];
for(int i=0;i<M;i++)
{
cin>>a[i]>>b[i];
for(int j=a[i];j<=b[i];j++)
{
num[j]=1;
}
}
for(int i=0;i<=L;i++)
{
if(num[i]==0)
{
n++;
}
}
cout<<n;
return 0;
}
夺宝奇兵：
#include <iostream>
#include<algorithm>
using namespace std;
int arr[101][101], dp[101][101];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
cin >> arr[i][j];
for (int i = n - 1; i >= 0; i--)
for (int j = 0; j <= i; j++)
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + arr[i][j]; //动态规划，状态转移方程
//dp[0][0]位置缩小正好是[0][0]位置，从底部回溯到顶部结果
cout << dp[0][0];
/*
从顶部推到底部（结果在底部位置，但是不能确定，要通过比较筛选确定）
int maxnum=0;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+mountain[i-1][j-1];
if(maxnum<dp[i][j])
maxnum=dp[i][j];
}
}
cout <<maxnum<<endl;
*/
return 0;
}
/*
test:
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
30
*/
分解质因数：
#include<stdio.h>
int main()
{
int a,b,i,d,c,j;
scanf("%d%d",&a,&b);
if(a<=b&&a>=2&&a<=10000&&b<=10000)
{
for(i=a;i<=b;i++)
{
d=1;
for(j=2;j<i;j++)
if(i%j==0)
{
d=0;
break;
}
if(d==1)
printf("%d=%d\n",i,i);
else if(d==0)
{
printf("%d=",i);
j=2;
c=i;
while(1)
{
while(c%j==0)
{
printf("%d",j);
c=c/j;
if(c!=1)
printf("*");
}
if(c==1)
{
printf("\n");
break;
}
j++;
}
}
}
}
return 0;
}
写在最后：
算法的学习有两个困难的地方（参考文章：算法之美（豆瓣读书））：
其一，我们学习了那些经典的算法，除了赞叹一下设计的巧思，但总难免问上一句：怎么想到的？对学生来说，这可能是最费解、也最让人窝火的地方。我们下再多的功夫去记忆书上的算法、去分析这些算法的效率，却终究不能理喻得到这些算法的过程。心理盘算着：给我一个新问题，让我设计个算法出来，我能行吗？答案是：不知道。
可这偏偏又是极重要的，无论作研究还是实际工作，一个计算机专业人士最重要的能力，就是解决问题——解决那些不断从理论模型、或者从实际应用中冒出来的新问题。
其二，算法作为一门学问，有两条正交的线索。一个是算法处理的对象：数、矩阵、集合、串(strings)、排列(permutations)、图(graphs)、表达式(formula)、分布(distributions)，等等。另一个是算法的设计思想：贪婪、分治、动态规划、线性规划、局部搜索(local search)，等等。这两条线索几乎是相互独立的：同一个离散对象，例如图，稍有不同的问题，例如single-source shortest path和all-pair shortest path，就可以用到不同的设计思想，如贪婪和动态规划；而完全不同的离散对象上的问题，例如排序和整数乘法，也许就会用到相同的思想，例如分治。
两条线索交织在一起，该如何表述。对学生而言，不同离散对象的差别是直观的——我们已经惯于在一章里面完全讲排序、而在另一章里面完全讲图论算法；可是对算法而言，设计思想的差别是根本的，因为这是从问题的结构来的：不同离散对象上面定义的问题，可以展现出类似的结构，而这结构特征，就是支持一类算法的根本，也是我们设计算法的依据。
很多时候我们会为算法的复杂难想或者满满套路而烦恼，但是在思考过后又会觉得还蛮有意思，学到了很多，很有成就感，或许这就是算法的魅力吧。
京公网安备 11010502036488号