参考了一些大佬的代码然后自己再写的一遍。
1、棋盘覆盖问题
在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
#include<stdio.h> #include <cstring> int board[50][50]; int Lnum=0; void chessplay(int tr,int tc,int dr,int dc,int size) { if(size==1) return; else { int n=++Lnum; int s=size/2; if(dr<tr+s&&dc<tc+s) //是否在左上角 { chessplay(tr,tc,dr,dc,s); } else { board[tr+s-1][tc+s-1]=n; chessplay(tr,tc,tr+s-1,tc+s-1,s); } if(dr<tr+s&&dc>=tc+s) //是否在右上角 { chessplay(tr,tc+s,dr,dc,s); } else { board[tr+s-1][tc+s]=n; chessplay(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s&&dc<tc+s) //是否在左下角 { chessplay(tr+s,tc,dr,dc,s); } else { board[tr+s][tc+s-1]=n; chessplay(tr+s,tc,tr+s,tc+s-1,s); } if(dr>=tr+s&&dc>=tc+s) //是否在右下角 { chessplay(tr+s,tc+s,dr,dc,s); } else { board[tr+s][tc+s]=n; chessplay(tr+s,tc+s,tr+s,tc+s,s); } } } int main() { memset(board,0,sizeof(board)); int x,y,size; scanf("%d",&size); scanf("%d",&x); scanf("%d",&y); chessplay(0,0,x-1,y-1,size); for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { printf(" %2d",board[i][j]); } printf("\n"); } return 0; }
2、合并排序问题
对n个元素组成的序列进行排序。
基本思想:将待排序元素分成大小大致相同的两个子集合,分别对两个集合进行排序,最终将排序好的子集合合并成所要求的排好序的集合。
#include<stdio.h> /* 5 220 10 30 50 40 */ int b[20]={0}; void hebing(int*a,int l,int mid,int r) { int i=l; int j=mid+1; int k=l; // while(i!=mid+1 && j!=r+1) // { // if(a[i]>a[j]) // b[k++]=a[j++]; // else // b[k++]=a[i++]; // // } while(i<=mid&&j<=r) { if(a[i]>a[j]) { b[k++]=a[j++]; } else { b[k++]=a[i++]; } } // while (i!=mid+1) // { // b[k++]=a[i++]; // } // while(j!=r+1) // { // b[k++]=a[j++]; // } // if(i==(mid+1)) { while(j<=r) { b[k++]=a[j++]; } } else if(j==(r+1)) //必须加else 因为上面让j变成了r+1 { while(i<=mid) { b[k++]=a[i++]; } } for(int i=l;i<=r;i++) /!!!!!必须把a排好了才能下一步归并,b是临时容器 { a[i]=b[i]; } } void paixu(int*a,int l,int r) { if(l<r) //! { int mid=(l+r)/2; paixu(a,l,mid); paixu(a,mid+1,r); hebing(a,l,mid,r); } } int main() { int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } paixu(a,0,n-1); for(int i=0;i<n;i++) { printf("%d ",a[i]); //不能是b } return 0; } /* 5 220 10 30 50 40 */
3、集合最大元问题
在规模为n的数据元素集合中找出最大元。当n=2时,一次比较就可以找出两个数据元素的最大元和最小元。当n>2时,可以把n个数据元素分为大致相等的两半,一半有n/2个数据元素,而另一半有n/2个数据元素。 先分别找出各自组中的最大元,然后将两个最大元进行比较,就可得n个元素的最大元
#include<stdio.h> int max(int x,int y) { return (x>y)?x:y; } int maxnum(int* a,int l,int r) { if(l==r) { return a[l]; } else { int mid=(l+r)/2; return max(maxnum(a,l,mid),maxnum(a,mid+1,r)); } } int main() { int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } printf("%d",maxnum(a,0,n-1)); return 0; }
4、循环赛日程表
2019年,德国甲级联赛刚刚落下帷幕。设有n支队伍参加循环赛,要求设计一个满足以下要求比赛日程表:
1)每支队伍必须与其它n-1支队伍各赛一次;
2)每支队伍一天只能赛一次。
输入:n=3
输出:
#include<stdio.h> #include<math.h> #define maxsize 64 int a[maxsize][maxsize]; //不定义在外面的话就要传进函数里去 void fenge(int n,int k) { if(n==2) { a[k][0]=k+1; a[k][1]=k+2; a[k+1][0]=k+2; a[k+1][1]=k+1; } else { fenge(n/2,k); fenge(n/2,k+n/2); for(int i=k;i<k+n/2;i++) //填右下角 { for(int j=0;j<n/2;j++) { a[i+n/2][j+n/2]=a[i][j]; } } for(int i=k+n/2;i<k+n;i++) //填右上角 { for(int j=0;j<n/2;j++) { a[i-n/2][j+n/2]=a[i][j]; } } } } int main() { printf("请输入k值:\n"); int k,n; scanf("%d",&k); n=pow(2,k); fenge(n,0); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf(" %d",a[i][j]); } printf("\n"); } return 0; }
1、 数字三角问题
问题描述:给定一个由n行数字组成的数字三角形,如下图所示
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
如上图最大值为30=7+3+8+7+5
#include<stdio.h> int max(int x,int y) { return (x>y)?x:y; } int main() { printf("请输入三角形行数n:\n"); int n; scanf("%d",&n); int a[n][n],m[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { scanf("%d",&a[i][j]); m[i][j]=-1; } } for(int i=n-1,j=0;j<=i;j++) { m[i][j]=a[i][j]; } for(int i=n-2;i>=0;i--) { for(int j=0;j<=i;j++) { m[i][j]=max(m[i+1][j],m[i+1][j+1])+a[i][j]; } } printf("\n数字总和最大为%d",m[0][0]); return 0; } /* 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 */
2、最长公共子序列问题
问题描述:给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
输入:
第1行:两个子序列的长度,m n
第2行:第1个子序列的各个元素(序列下标从1开始)
第3行:第2个子序列的各个元素(序列下标从1开始)
输出:
最长公共子序列
实例:
输入:
第1行:
4 5 //m和n的值
第2行
abad //输入4个字符,下标从1开始
第3行
baade //输入5个字符,下标从1开始
输出:
aad
#include<stdio.h> void LCSLength(int m,int n,char*x,char*y,int c[][10],int b[][10]) { int i,j; for(int i=1;i<=m;i++) { for(int 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; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } } int k=0; void LCS(int i,int j,char*x,int b[][10],char* ad) { if(i==0||j==0) return ; if(b[i][j]==1) { LCS(i-1,j-1,x,b,ad); ad[k++]=x[i-1]; //ad[0]是在最底层那一个赋的值,所以不用再逆序 } else if(b[i][j]==2) { LCS(i-1,j,x,b,ad); } else LCS(i,j-1,x,b,ad); } int main() { int m,n; scanf("%d%d",&m,&n); char x[m],y[n]; char ad[10]; scanf("%s",x); scanf("%s",y); int c[10][10],b[10][10]; for(int i=0;i<10;i++) { for(int j=0;j<10;j++) { c[i][j]=0; b[i][j]=0; } } LCSLength(m,n,x,y,c,b); LCS(m,n,x,b,ad); for(int i=0;i<10;i++) { printf("%c",ad[i]); } printf("\n") ; // for(int i=0;i<10;i++) //输出类型为1的走不通,因为这只找的共同有的没找有共同顺序的 // { // for(int j=0;j<10;j++) // { // // if(b[i][j]==1) // { // printf("%c",x[i-1]); // printf("%d|%d\n",i,j); // } // } // } return 0; } /* 4 5 abad baade */
3、日常购物
问题描述:小明今天很开心,因为在家买的新房子即将拿到钥匙。新房里面有一间他自己专用的、非常宽敞的房间。让他更高兴的是,他的母亲昨天对他说:“你的房间需要购买什么物品?怎么布置,你说了算,只要他们的价格总和不超过N元钱”。小明今天早上开始预算,但他想买太多的东西,肯定会超过母亲的N元限额。因此,他把对每件物品的渴望程度,分为5等级:用整数1->5表示,第5等表示最想要。他还从互联网上找到了每件商品(所有整数)的价格。他希望在不超过N元(可能等于N元)的情况下,将每件商品的价格与效益度的乘积的总和最大化.
设第j件物品的价格为p[j],重要度为w[j],其选中的k件商品,编号依次为j1,j2,……,jk,则所求的总和为:
p[j1]×w[j1]+p[j2]×w[j2]+ …+p[jk]×w[jk]。
请帮小明设计一个符合要求的购物清单。
其中N=2000,K=6
p[1]=200 w[1]=2
p[2]=300 w[2]=2
p[3]=600 w[3]=1
p[4]=400 w[4]=3
p[5]=1000 w[5]=4
p[6]=800 w[6]=5
4、台阶问题
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
实际情况:给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径1,3,1,0,6,1,0就是最小路径和,返回12.
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
#include<stdio.h> int minone(int x,int y) { return (x>y)?y:x; } int main() { int m[4][4]={ {1,3,5,9}, {8,1,3,4}, {5,0,6,1}, {8,8,4,0} }; int min[4][4]={0}; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { if(i==0) { if(j==0) min[i][j]=m[i][j]; else min[i][j]=min[i][j-1]+m[i][j]; } else if(j==0) { if(i!=0) min[i][j]=min[i-1][j]+m[i][j]; } else { min[i][j]=minone(min[i-1][j],min[i][j-1])+m[i][j]; } } } // for(int i=0;i<4;i++) // { // for(int j=0;j<4;j++) // { // printf("%d ",min[i][j]); // } // printf("\n"); // } printf("最小路径和为%d",min[3][3]); return 0; }
#include<stdio.h> int sum(int n) { if(n==1||n==2||n==3) { return n; } else { return sum(n-1)+sum(n-2); } } int main() { printf("请输入台阶数"); int n; scanf("%d",&n); printf("方法数为%d",sum(n)); return 0; }
1、最优服务次序问题
(1)问题描述:
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1<=i <= n 。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。
(2)编程任务:
对于给定的n个顾客需要的服务时间,编程计算最优服务次序。
(3)数据输入:
第一行是正整数n,表示有n 个顾客。接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。
(4)结果输出:
计算出的最小平均等待时间。
(5)输入示例
10
56 12 1 99 1000 234 33 55 99 812
(6)输出示例
532.00
#include<stdio.h> void bsort(int* time,int n) { int t; for(int i=0;i<n-1;i++) { for(int j=0;j<n-i-1;j++) { if(time[j]>time[j+1]) { t=time[j]; time[j]=time[j+1]; time[j+1]=t; } } } } int main() { printf("输入顾客数:\n"); int n,sum; scanf("%d",&n); int time[n]; printf("输入这n个顾客需要的服务时间\n"); for(int i=0;i<n;i++) { scanf("%d",&time[i]); } bsort(time,n); sum=time[0]; for(int i=1;i<n;i++) { time[i]+=time[i-1]; sum+=time[i]; } printf("\n最小平均等待时间为%.2lf",sum*1.0/n); return 0; } /* 10 56 12 1 99 1000 234 33 55 99 812 *(n-i-1) */
2、区间相交问题
(1)问题描述:
给定x 轴上n 个闭区间。去掉尽可能少的闭区间,使剩下的闭区间都不相交。
(2)编程任务:
给定n 个闭区间,编程计算去掉的最少闭区间数。
(3)数据输入:
第一行是正整数n,表示闭区间数。接下来的n行中,每行有2 个整数,分别表示闭区间的2个端点。
(4)结果输出:
计算出的去掉的最少闭区间数。
(5)输入示例
3
10 20
10 15
20 15
(6)输出文件示例
2
#include<stdio.h> int main() { printf("输入区间数n:\n"); int n,t,p,num; scanf("%d",&n); int s[n],e[n]; printf("输入区间:"); for(int i=0;i<n;i++) { scanf("%d %d",&t,&p); s[i]=(t>p?p:t); e[i]=(t>p?t:p); } for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) { if(e[j]>e[j+1]) { t=e[j]; e[j]=e[j+1]; e[j+1]=t; p=s[j]; s[j]=s[j+1]; s[j+1]=p; } } } num=1; int end=e[0]; for(int i=1;i<n;i++) { if(s[i]>end) { num++; end=e[i]; } } printf("去除区间数:%d",n-num); return 0; }
3、汽车加油问题
问题描述:一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。
算法设计:对于给定的n和k个加油站位置,计算最少加油次数。
数据输入:n:表示汽车加满油后可行驶nkm
k:旅途中有k个加油站
k+1个整数:表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。
数据输出:最少加油次数和具体在哪几个加油站加油。
例如: n=7 k=7
K+1个整数:1 2 3 4 5 1 6 6
最优值:4
#include<stdio.h> int main() { int n,k,num,sum; printf("输入n k:\n"); scanf("%d %d",&n,&k); printf("输入k+1个距离:\n"); int t[k+1]; int m[k]={0}; for(int i=0;i<=k;i++) { scanf("%d",&t[i]); } num=0; sum=t[0]; for(int i=0;i<k;i++) { if(t[i]>n) { printf("无解\n"); break; } if(sum+t[i+1]>n) { num++; sum=t[i+1]; m[i]=1; } else { sum=t[i]+t[i+1]; } } printf("\n加油次数为%d\n",num); printf("加油的站点为:") ; for(int i=0;i<k;i++) { if(m[i]!=0) printf("%d ",i+1); } printf("\n"); return 0; } /* 7 7 1 2 3 4 5 1 6 6 */
4、活动安排问题:考虑将一系列活动安排在科学会堂。假设有n个活动,每个活动需要花费一个单位时间。如果在时间T[i]或T[i]之前开始,则活动i将提供P[i]元的利润,其中T[i]是任意的数字。如果一个活动不是在T[i]或T[i]之前开始的,那么在安排过程中它根本不会带来任何利润。如果所有事件都可以在0时刻开始。
输入:n个活动的T[i]和P[i]
输出:活动安排顺序和获得的利润。
1、0-1背包问题
有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。要求每个物品要么放进背包,要么不放进背包。
#include<stdio.h> int w[10],v[10]; int n,pw; int ans=0; void df(int t,int ew,int ev) { if(t>n) { if(ev>ans) { ans=ev; } } else { int nw,nv; if(ew+w[t]<=pw) { nw=ew+w[t]; nv=ev+v[t]; df(t+1,nw,nv); //回溯 df(t+1,ew,ev); } else { df(t+1,ew,ev); } } } int main() { scanf("%d %d",&n,&pw); for(int i=1;i<=n;i++) { scanf("%d %d",&w[i],&v[i]); } df(1,0,0); //装第1个物品前已用的重量和已有的价值 printf("最大价值为%d",ans); return 0; }
2、旅行售货员问题
设有一个售货员从城市1出发,到城市2,3,…,n去推销货物,最后回到城市1。假定任意两个城市i,j间的距离dij(dij=dji)是已知的,问他应沿着什么样的路线走,才能使走过的路线最短。
#include<stdio.h> int bestr[10]={0}; int x[10]={0}; int g[10][10]; int ans=1000; int cost=0; int n; void swap(int* a,int* b) { int t; t=*a; *a=*b; *b=t; } void df(int t) //寻找第t个落脚点 { if(t>n) //n个点已选择完毕 { if(g[x[t-1]][x[1]]>0&&cost+g[x[t-1]][x[1]]<ans) { ans=cost+g[x[t-1]][x[1]]; for(int i=1;i<=n;i++) { bestr[i]=x[i]; } } } else { for(int i=t;i<=n;i++) { if(g[x[t-1]][x[i]]>0&&cost+g[x[t-1]][x[i]]<ans) { cost+=g[x[t-1]][x[i]]; swap(&x[t],&x[i]); df(t+1); //从下边两步回溯 cost-=g[x[t-1]][x[t]]; //这里不是x[i]!!! swap(&x[t],&x[i]); } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&g[i][j]); } } for(int i=1;i<=n;i++) { x[i]=i; } df(2); printf("最短路的长度为%d\n",ans); for(int i=1;i<=n;i++) { printf("%d->",bestr[i]); } printf("1\n"); return 0; }
3、图的m着色问题
(1)问题描述:给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。若这个图不是m可着色的,就输出no。若是则输出每种着色方案和可行方案数。
(2)样例1
输入:当输入如下图时
顶点数:6
边数:9
各边顶点:
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
输出:
样例2:
(3)实验步骤
(a)首先将给定的图利用抽象图表示出来
(b)判断该节点k当前的着色是否符合条件,需要判断x[k]与k结点其他相邻节点h的x[h]是否相等
(c)回溯过程,若此时的结点值已经大于结点总数,代表已经着色完成,并且找到了一种可行解,此时可以将可行解数+1
(d)回溯从最后一个结点往上回溯,并一层一层更改结点至其他可用着色,以此来找到所有的填色方案。
#include<stdio.h> int n,k,m; int g[10][10]={0}; int ncolor[10]={0}; int sum=0; bool check(int t,int mi) { for(int i=1;i<=n;i++) { if(g[t][i]==1&&ncolor[i]==mi) return false; //相邻且颜色相同就不能用这个颜色 } return true; } void df(int t) { if(t>n) { sum++; printf("方案%d为:",sum); for(int i=1;i<=n;i++) { printf("%d ",ncolor[i]); } printf("\n"); } else { for(int i=1;i<=m;i++) { if(check(t,i)) //封装,思路更清晰 { ncolor[t]=i; df(t+1); ncolor[t]=0; } } } } int main() { printf("输入n个点k条边m种颜色\n"); scanf("%d %d %d",&n,&k,&m); for(int i=1;i<=k;i++) { int x,y; scanf("%d %d",&x,&y); g[x][y]=1; g[y][x]=1; } df(1); printf("总方案数为%d种",sum); return 0; }