递归
通过LeetCode上【70. 爬楼梯】学习
class Solution {
public:
int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
回溯
利用回溯算法求解八皇后问题
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#define MAX 30
int check_pos(const int r[MAX],const int i,const int j);
void print(const int r[MAX],const int n);
int queen_place(int r[MAX],const int n);
int main(int argc,char *argv[]){
if(argc!=2){
fprintf(stderr,"Please input the number of queen!\n");
return 0;
}
int n=atoi(argv[1]);
if(n<4){
fprintf(stderr,"The number of queen must be larger than 4 !\n");
return 0;
}
int results[MAX]; // results[i]=j，表示把第i个皇后放在位置(i,j)上
int num = queen_place(results,n);
return 0;
}
int queen_place(int r[MAX],const int n){
int i,j,num;
i=0;j=0,num=0;
while(1){
int find=0;
while(j<n){
// 寻找第i个皇后放置的位置j
if(check_pos(r,i,j))
break;
j++;
}
if(j<n){
// 如果找到了记录该位置，继续放置第i个皇后
r[i++] = j;
j = 0;
}else{
// 如果没有找到合适的位置，回溯到第i-1个皇后，将其位置放在原来位置的下一个位置
j = r[--i] + 1 ;
}
if(i == n && r[i-1]<n){
//找到了一个合适的解
//print(r,n);
j=r[--i]+1; //继续寻找其他解
num++;
}else if(i<0) //已经找到了全部的解
break;
}
printf("num:%d\n",num);
return num;
}
//第i个皇后放在(i,j)位置是否合适
int check_pos(const int r[MAX],const int i,const int j){
int k;
for(k=0;k<i;k++){
if(r[k] == j) //是否在同列
return 0;
if(r[k]+k == i+j) //是否在45度对角线
return 0;
if(r[k]-k == j-i) //是否在135度对角线
return 0;
}
return 1;
}
//打印皇后放置的位置
void print(const int r[MAX],const int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(r[i]==j)
printf("1 ");
else
printf("0 ");
}
printf("\n");
}
printf("----------------------------\n");
}
利用回溯算法求解 0-1 背包问题
#include <iostream>
#include <stdio.h>
//#include <conio.h>
using namespace std;
int n;//物品数量
double c;//背包容量
double v[100];//各个物品的价值 value
double w[100];//各个物品的重量 weight
double cw = 0.0;//当前背包重量 current weight
double cp = 0.0;//当前背包中物品总价值 current value
double bestp = 0.0;//当前最优价值best price
double perp[100];//单位物品价值(排序后) per price
int order[100];//物品编号
int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
//按单位价值排序
void knapsack()
{
int i,j;
int temporder = 0;
double temp = 0.0;
for(i=1;i<=n;i++)
perp[i]=v[i]/w[i]; //计算单位价值（单位重量的物品价值）
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
{
temp = perp[i]; //冒泡对perp[]排序
perp[i]=perp[i];
perp[j]=temp;
temporder=order[i];//冒泡对order[]排序
order[i]=order[j];
order[j]=temporder;
temp = v[i];//冒泡对v[]排序
v[i]=v[j];
v[j]=temp;
temp=w[i];//冒泡对w[]排序
w[i]=w[j];
w[j]=temp;
}
}
}
//回溯函数
void backtrack(int i)
{
//i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品
double bound(int i);
if(i>n) //递归结束的判定条件
{
bestp = cp;
return;
}
//如若左子节点可行，则直接搜索左子树;
//对于右子树，先计算上界函数，以判断是否将其减去
if(cw+w[i]<=c)//将物品i放入背包,搜索左子树
{
cw+=w[i];//同步更新当前背包的重量
cp+=v[i];//同步更新当前背包的总价值
put[i]=1;
backtrack(i+1);//深度搜索进入下一层
cw-=w[i];//回溯复原
cp-=v[i];//回溯复原
}
if(bound(i+1)>bestp)//如若符合条件则搜索右子树
backtrack(i+1);
}
//计算上界函数，功能为剪枝
double bound(int i)
{
//判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
double leftw= c-cw;//剩余背包容量
double b = cp;//记录当前背包的总价值cp,最后求上界
//以物品单位重量价值递减次序装入物品
while(i<=n && w[i]<=leftw)
{
leftw-=w[i];
b+=v[i];
i++;
}
//装满背包
if(i<=n)
b+=v[i]/w[i]*leftw;
return b;//返回计算出的上界
}
int main()
{
int i;
printf("请输入物品的数量和背包的容量：");
scanf("%d %lf",&n,&c);
/*printf("请输入物品的重量和价值：\n"); for(i=1;i<=n;i++) { printf("第%d个物品的重量：",i); scanf("%lf",&w[i]); printf("第%d个物品的价值是：",i); scanf("%lf",&v[i]); order[i]=i; }*/
printf("请依次输入%d个物品的重量:\n",n);
for(i=1;i<=n;i++){
scanf("%lf",&w[i]);
order[i]=i;
}
printf("请依次输入%d个物品的价值:\n",n);
for(i=1;i<=n;i++){
scanf("%lf",&v[i]);
}
knapsack();
backtrack(1);
printf("最优价值为：%lf\n",bestp);
printf("需要装入的物品编号是：");
for(i=1;i<=n;i++)
{
if(put[i]==1)
printf("%d ",order[i]);
}
return 0;
}
分治
利用分治算法求一组数据的逆序对个数
#include<iostream>
#include<fstream>
using namespace std;
int reversePair(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);
int main(void) {
fstream f("test.txt", fstream::in | fstream::out);
int test[100];
int t[100];//临时数组用于合并步骤，不在递归函数中开启数组，防止递归过程内存中同时存在大量数组
int temp;
int i = 0;
while(f >> temp) {
test[i] = temp;
i++;
}
cout << reversePair(test, t, 0, i - 1) << endl;
f.close();
return 0;
}
int reversePair(int arr[], int temp[], int l, int r) {
if(l == r)
return 0;
int m = (l + r) / 2;
int ln = reversePair(arr, temp, l, m);//左序列逆序对数量
int rn = reversePair(arr, temp, m + 1, r);//右序列逆序对数量
int mn = merge(arr, temp, l, m, r);//左序列与右序列元素构成的逆序对数量
return ln + rn + mn;
}
int merge(int arr[], int temp[], int l, int m, int r) {
int count = 0, i, j;
for(i = l; i <= r; i++)
temp[i] = arr[i];
int k = l;
for(i = l, j = m + 1; i <= m && j <= r;k++) {
if(temp[i] > temp[j]) {
count += m - i + 1;//每次发现左序列元素比右序列元素大，逆序对数量增加，m-i+1即为该元素到左序列尾的元素数量
//其余代码为归并排序的步骤
arr[k] = temp[j];
j++;
}
else {
arr[k] = temp[i];
i++;
}
}
if(i > m) {
while(j <= r) {
arr[k] = temp[j];
j++;
k++;
}
}
else {
while(i <= m) {
arr[k] = temp[i];
i++;
k++;
}
}
return count;
}
动态规划
0-1 背包问题
#include <iostream>
using namespace std;
#define max(a,b) (((a) > (b)) ? (a) : (b))
int w[]={
0,3,6,3,8,6};//商品重量
int v[]={
0,4,6,6,12,10};//商品价值
int W = 10; //背包容量
int c[6][11]={
0};//c[i][j]表示在商品1到i中，背包容量为j时，最大价值
void Package0_1(int w[],int v[],int W,int n,int c[][11])//
{
for(int i=1;i<=n;i++) //逐行填表c[i][j]
{
for (int j=1;j<=W;j++)
{
if ( i == 1) //填写第1行时，不参考其他行
{
if (j < w[i])
c[i][j]=0;
else
c[i][j] = v[i];
}
else
{
if ( j < w[i]) //背包容量小于商品i的重量，商品i一定不选
{
c[i][j] = c[i-1][j];
}
else
{
c[i][j] = max(c[i-1][j],v[i]+c[i-1][j-w[i]]);//比较选与不选商品i的背包总价值大小
}
}
}
}
for(int m =1;m<6;m++)
{
for (int n=0;n<11;n++)
{
cout<<c[m][n]<<" ";
}
cout<<endl;
}
}
void Print_Package0_1(int c[][11]) //构造解
{
int i=5;
int j=10;
cout<<"总价值为"<<c[i][j]<<endl;
while(i!=1)
{
if ( c[i][j] == c[i-1][j] )
{
cout<<"商品"<<i<<"不选"<<endl;
}
else
{
cout<<"商品"<<i<<"选"<<endl;
j = j - w[i];
}
i--;
}
if ( c[i][j] == 0) //
{
cout<<"商品"<<i<<"不选"<<endl;
}
else
{
cout<<"商品"<<i<<"选"<<endl;
}
}
int main()
{
Package0_1(w,v,W,5,c);
Print_Package0_1(c);
return 0;
}
最小路径和（详细可看 Minimum Path Sum）
int minPathSum(vector<vector<int>>& grid) {
int m=(int)grid.size();
int n=(int)grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0]=grid[0][0];
for(int i=1;i<m;i++)
dp[i][0]=dp[i-1][0]+grid[i][0];
for(int i=1;i<n;i++)
dp[0][i]=dp[0][i-1]+grid[0][i];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
return dp[m-1][n-1];
}
编程实现莱文斯坦最短编辑距离
#include<bits/stdc++.h>
using namespace std;
int min(int a,int b,int c)
{
return (a<b)?(a<c?a:c):(b<c?b:c);
}
int main()
{
FILE * file;
freopen("input.txt", "r", stdin);
freopen("output.txt","w",stdout);
int d[6][8];
string a,b;
cin>>a>>b;
for (int i=0;i<=b.size()+1;i++)
{
for (int j=0; j<=a.size()+1;j++)
{
if (i==0&&j==0)
d[i][j]=0;
else if (i==0&& j > 0)
d[i][j]=j;
else if (i>0&&j==0)
d[i][j]=i;
else if(i>=1&&j>=1)
{
int k =((b[i-1]==a[j-1])?0:1);
d[i][j]=min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+k);
}
}
}
/* for(int i=0;i<b.size()+1;i++) { for(int j=0;j<a.size()+1;j++) { cout<<d[i][j]+" "; } cout<<endl; } */
cout<<d[b.size()+1][a.size()+1];
return 0;
}
编程实现查找两个字符串的最长公共子序列
#include <stdio.h>
#include <string.h>
#define MAXLEN 50
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
int i, j;
for(i = 0; i <= m; i++)
c[i][0] = 0;
for(j = 1; j <= n; j++)
c[0][j] = 0;
for(i = 1; i<= m; i++)
{
for(j = 1; j <= n; j++)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1; //如果使用'↖'、'↑'、'←'字符，会有警告，也能正确执行。
} //本算法采用1,3,2三个整形作为标记
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 3;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 2;
}
}
}
}
void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 1)
{
PrintLCS(b, x, i-1, j-1);
printf("%c ", x[i-1]);
}
else if(b[i][j] == 3)
PrintLCS(b, x, i-1, j);
else
PrintLCS(b, x, i, j-1);
}
int main()
{
char x[MAXLEN] = {
"ABCBDAB"};
char y[MAXLEN] = {
"BDCABA"};
int b[MAXLEN][MAXLEN]; //传递二维数组必须知道列数，所以使用MAXLEN这个确定的数
int c[MAXLEN][MAXLEN];
int m, n;
m = strlen(x);
n = strlen(y);
LCSLength(x, y, m, n, c, b);
PrintLCS(b, x, m, n);
return 0;
}
编程实现一个数据序列的最长递增子序列
#include <iostream>
using namespace std;
int lis(int A[], int n){
int *d = new int[n];
int len = 1;
for(int i=0; i<n; ++i){
d[i] = 1;
for(int j=0; j<i; ++j)
if(A[j]<=A[i] && d[j]+1>d[i])
d[i] = d[j] + 1;
if(d[i]>len) len = d[i];
}
delete[] d;
return len;
}
int main(){
int A[] = {
5, 3, 4, 8, 6, 7
};
cout<<lis(A, 6)<<endl;
return 0;
}
京公网安备 11010502036488号