资源描述
桂 林 电 子 科 技 大 学 试 卷 年第 1 学期 课号 课程名称 网络与信息安全实验( B 卷 ,开卷)合用班级(或年级、专业) 13、14 考试时间 120 分钟 班级 学号 姓名 题 号一二三四五六七八九十成绩满 分20303020100得 分评卷人第一题、(20分)请编写一种函数fun(char *str),其功能是:鉴别字符串str与否是回文,若是,返回;否则返回。例如:“12321”,“adcdcba”;而“hello”,“123”就不是回文。部分源程序如下:#include #include #include intfun(char *str)intk;char*head,*rear;return!(*head-*rear);main() chars100;intflag;clrscr();printf(n please enter stringn);gets(s);flag=fun(s);printf(%d,flag);#include#include#includeintfun(char*str)intk;char*head,*rear;k=0;for(head=str;*head!=0;head+)k+;for(head=str,rear=head+k-1;headrear;head+,rear-)if(head=rear)continue;elsebreak;return!(*head-*rear);voidmain()chars100;intflag;/clrscr();printf(npleaseenterstringn);gets(s);flag=fun(s);printf(%d,flag);第二题、(30分)分别用动态规划法、递归算法法设计0-1背包问题。规定:阐明所使用的算法方略;写出算法实现的重要环节;分析算法的时间。动态规划法:#includeint V200200;/前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b) if(a=b) return a; else return b;int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+)for(int k=1;k=j/wi;k+) if(j=0;i-) if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选用状态 int n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d,&C); printf(输入物品数:n); scanf(%d,&n); printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d,&wi); printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); 时间复杂度为O(n3)递归算法:#include using namespace std; const int W = 150; const int number = 5; const int VALUE = 60, 20, 10, 60, 100; const int WEIGHT = 20, 30, 50, 60, 80; /function Make( i 解决到第i件物品 , j剩余的空间为j) :integer; int Make(int i, int j) int r1 = 0; int r2 = 0; int r = 0; if (i = -1) return 0; if(j = WEIGHTi) /背包剩余空间可以放下物品 i r1 = Make(i-1,j - WEIGHTi) + VALUEi; /第i件物品放入所能得到的价值 r2 = Make(i-1,j); /第i件物品不放所能得到的价值 r = (r1r2)?r1:r2; return r; void main() int maxValue = Make(number-1, W); coutmaxValue: maxValueendl; 第三题、(30分)通过键盘输入一种高精度的正整数n(n的有效位数240),去掉其中任意s个数字后,剩余的数字按原左右顺序将构成一种新的正整数。编程对给定的n和s,寻找一种方案,使得剩余的数字构成的新数最小。【样例输入】178543S=4【样例输出】13#includeint maxNum(char num240) int i,max=0,k; for(i=0;numi!=0;i+) if(max(int)numi) max=(int)numi; k=i; return k;void move(char num240,int n) int i;for(i=n;numi+1!=0;i+) numi=numi+1;numi=0;void fun(int s,char num240)while(s-)move(num,maxNum(num);void main() char num240; int s,i; printf(输入数字:); scanf(%s,num); printf(输入s的值:); scanf(%d,&s); fun(s,num); printf(%s,num);第四题(20分):截图在poj.org和上的个人信息。
展开阅读全文