重庆市大学生程序设计大赛习题资料集_图文.docxVIP

PAGE31 / NUMPAGES31 目录 0-1背包问题 ……2 表达式括号匹配问题……3 扫雷游戏……4 素数环……6 N皇后……8 迷宫……10 罗马数字求和……13 Tempter of the Bone……18 程序存储问题……21 二分查找……22 魔方矩阵……24 区间覆盖问题 ……25 数字三角……27 抓住那只牛……28 0-1背包问题 给定n种物品和一个背包，背包的最大承重为C 。已知物品i的重量是wi，其价值为pi。如何选择装入背包的物品，使得装入背包的物品重量不超出C，而总价值又最大？ 注意：对每种物品不能分割，只选择装入背包或不装入背包。 输入：第一行是两个整数，代表n和C，以空格分隔。第二行是n个物品的重量，以空格分隔。第三行是n个物品的价值，以空格分隔。 输出：第一行输出最大总价值。第二行输出背包方案，依次输出n个物品的装载情况，0表示不装入，1表示装入。 样例输入： 3 30 16 15 15 45 25 25 样例输出: 50 0 1 1 #includestdio.h int max(int a,int b) { if(ab)return a; return b; } int main() { int n,c; int s[100],v[100],m[100][100],route[100]; freopen(in.txt,r,stdin); freopen(out.txt,w,stdout); while(scanf(%d %d\n,n,c)!=EOF) { for(int i=0;in;i++) scanf(%d,s[i]); for(i=0;in;i++) scanf(%d,v[i]); for(i=0;in;i++) for(int j=0;j=c;j++) { if(i==0) { if(j=s[i])m[i][j]=v[i]; else m[i][j]=0; } else { m[i][j]=max(m[i-1][j],m[i-1][j-s[i]]+v[i]); } } printf(%d\n,m[n-1][c]); int j; for(i=n-1,j=c;i0;i--) { if(m[i][j]==m[i-1][j])route[i]=0; else { route[i]=1; j=j-s[i]; } } if(i==0 j=s[1])route[0]=1; if(i==0 js[1])route[0]=0; for(i=0;in;i++) printf(%d ,route[i]); } fclose(stdin); fclose(stdout); return 0; } 表达式括号匹配问题： 假设一个算术表达式中可以包含两种括号：圆括号“（”和“）”，方括号“[”和“]”，且这几种括号可以按任意次序嵌套使用。设计算法判断给定表达式中所含括号是???正确配对。 输入：一个表达式，长度不超过100 输出：如果匹配输出“匹配”，否则输出“不匹配” 输入样本1： (a*b[0]+(d+f)) 输出：匹配 输入样本2： (a*b(0]+(d+f)) 输出：不匹配 #includestdio.h int main() { char str[100]; freopen(in.txt,r,stdin); freopen(out.txt,w,stdout); while(scanf(%s\n,str)!=EOF) { char stack[100]; int top=0,i; for(i=0;str[i]!=\0;i++) { if(str[i]!=( str[i]!=) str[i]!=[ str[i]!=]) continue; else if(str[i]==( || str[i]==[) stack[top++]=str[i]; else if(str[i]==) || str[i]==]) { if(str[i]==) stack[top-1]==[) { printf(不匹配\n); break; } else if(str[i]==] stack[top-1]==() { printf(不匹配\n); break; } else {