您所在位置：网站首页 > 高等教育 > 大学课件算法与分析作业

算法与分析作业

14页

卖家[上传人]：jay****li

文档编号：207913881

上传时间：2021-11-05

文档格式：DOC

文档大小：163KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

1.88 金贝

/ 14 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、算法与分析作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。 a) int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x = l) int m = (l+r)/2; if (x = am) return m; if (x l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 2、O(1)空间子数组环卫算法：设a0:n-1是一个n维数组，k（1 k n-1）是一个非负整数。试设计一个算法将子数组a0 : k-1与ak+1 : n-1换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。 #include /交换数组的两段大小相等的范围的对应数据 /alow1alow2alow1+1alow2+1.ahigh1ahigh2 voidswap(inta,intlow1,i

2、nthigh1,intlow2,inthigh2) inttemp; while(low1=high1) temp=alow1; alow1=alow2; alow2=temp; low1+; low2+; /利用分治算法，每次选择最小的数组进行换位 voidpatition(inta,intlow,intk,inthigh) if(lowhigh) if(k-low+1)=(high-k) swap(a,low,k,k+1,high); elseif(k-low+1)(high-k) swap(a,low,k,low+high-k,high); patition(a,low,k,low+high-k-1); else swap(a,low,high+low-k-1,k+1,high); patition(a,high+low-k,k,high); /测试 intmain() inta=0,1,2,3,4,5,6,7,8,9,10,11,12,13; patition(a,0,4,13); for(inti=0;i14;i+) printf(%d,ai); return0; 3、定义：

3、给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下： 1）； 2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； 3）按此规则进行处理，直至不能再添加新的自然数为止。例如。其中共有6个元素。半数集问题：对于给定的n，求半数集set(n) 中元素的个数。#include#include#defineMAX1000/函数声明intHalfSet(intn);/声明全局变量intarraysMAX=0;intmain()intn=6;intsum=HalfSet(n);printf(%d,sum);getch();intHalfSet(intn)if(arraysn0)returnarraysn;elsearraysn=1;for(inti=1;i=n/2;i+)arraysn+=HalfSet(i);returnarraysn; 4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。#include main() int a10; int i,c,j; for(i=0;i10;i+) printf(请输入十个数,这是第%d个:,i+1)

4、; scanf(%d,&ai); for(i=0;ii+1;j-) if(aj-1aj-2) c=aj-1; aj-1=aj-2; aj-2=c; printf(从小到大的顺序是:); for(i=0;i10;i+) printf(n%d,ai); getch(); 5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。 publicstaticintgreedySelector(ints,intf,booleana)intn=s.length-1;a1=true;intj=1;intcount=1;for(inti=2;i=fj)ai=true;j=i;count+;elseai=false;returncount;6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。分析：我们知道如果a+b=常数，则|a-b|越小，a*b

5、越大。贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。7、子集和问题：设是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即。 #include#include#defineMAX1000/globalvariablesintn=0;/thenumberofnumbersintc=0;/thesumofthesubsetintnumMAX=0;intcount=1;/thenumberoftheelementinasubsetintresultMAX=0;/theanswerofthisquestionintc_sum=0;/currentsum/prototypesvoidswap(int&a,int&b);voidback_subset(inti);intmain()/declarationinti=0;printf(Pleaseinputthenumberofthenumbers:;scanf(%d,&n);printf(Pleaseinputthesum:);scanf(%d,&c);for(i=1;i=n;i+)scanf(%d,&numi);back_subset(1);getch();voidback_subset(inti)if(c_sum+numi=c)resultcount=numi;for(inttemp=1;tempn)return;if(c_sum+numic)return;for(intj=i;j=n;j+)resultcount+=numj;c_sum+=numj;swap(numi,numj);

《算法与分析作业》由会员jay****li分享，可在线阅读，更多相关《算法与分析作业》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源