搜索
ACM国际大学生程序设计竞赛--实验五集合划分问题2、题目分析：题目要求计算n个元素的集合共有多少个划分（其中每个划分都由不同的非空子集组成），n个元素的集合划分为m个块的划分数为F（n，m）=F（n-1，m-1）+m*F（n-1，m），m从1到n的划分个数相加即可求得总的划分数。3、算法设计：a.这一题的结果数很大，需要使用64位长整型：__int64；b.函数div（）采用递归的方式计算n个元素的集合划分为i个块的划分数：①div（n，1）=1，div（n，n）=1；②div（n，i）=div（n-1，i-1）+i*div（n-1，i）c.主函数采用for循环调用函数div（n，i）（1≤i≤n）对划分数进行累加统计。4、源程序：#includestdio.h__int64？div（__int64？n，__int64？i）{if（i==1||i==n）return？1；else？return？div（n-1，i-1）+i*div（n-1，i）；}main（）{__int64？i，n，s=0；scanf（%I64d，&n）；for（i=1；i=n；i++）s=s+div（n，i）；printf（%I64d，s）；return？0；}5、算法分析：函数div（）的时间复杂度为，主函数内for循环的时间复杂度为O（n），函数div（）嵌套在for循环内，故该算法的时间复杂度为。实验一统计数字问题1、问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。2、题目分析：考虑由0，1，2，…，9组成的所有n位数。从n个0到n个9共有个n位数，在这些n位数中，0，1，2，…，9每个数字使用次数相同，设为。满足如下递归式：由此可知，。据此，可从低位向高位进行统计，再减去多余的0的个数即可。3、算法设计：定义数组a[10]存放0到9这10个数出现的次数，个位为第0位，第j位的数字为r。采用while循环从低位向高位统计：a.统计从个位算起前j位0~9个数；b.如果j+1位为0，去掉第j+1位补0个数；c.统计第j+1位出现1~（r-1）个数；d.统计第j+1位出现r个数。4、源程序：#includeiostream.hintmain（）{longintsn[10]；inti，n，c，k，s，pown；for（i=0；i10；i++）sn[i]=0；cinn；for（k=s=0，pown=1；n0；k++，n/=10，pown*=10）{c=n%10；for（i=0；i10；i++）sn[i]+=c*k*（pown/10）；for（i=0；ic；i++）sn[i]+=pown；sn[c]+=1+s；sn[0]-=pown；s+=c*pown；}for（i=0；i10；i++）coutsn[i]'\n'；}5、算法分析：函数count（）的复杂度为O（1），主函数调用count（），故该算法的时间复杂度为O（1）。众数问题1、问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。对于给定的由n个自然数组成的多重集S，编程计算S的众数及其重数。2、题目分析：题目要求计算集合中重复出现最多的数以及该数出现的次数，若两个数出现的次数相同，则取较小的数。先对集合中的元素从小到大排序，再统计重数，找出最大的重数以及它对应的元素。3、算法设计：a.建立数组a[n]存储集合中的元素；b.调用库函数sort（a，a+n）对集合中的元素从小到大排序；c.采用for循环依次对排序后的元素进行重数统计：①用m标记元素，用s统计该元数的重数，分别用max和t标记出现的最大重数和该重数对应的元素。②若当前元素不同于前一个元素，且前一个元素的重数smax，更新max和t。4、源程序：#includeiostreamusing？namespace？std；#includealgorithmmain（）{int？n，i，t，m=0，s，max=0，*a；scanf（%d，&n）；a=new？int[n]；for（i=0；in；i++）scanf（%d，&a[i]）；sort（a，a+n）；for（i=0；in；i++）{if（m！=a[i]）s=1；elses++；m=a[i]；if（smax）{t=m；max=s；}}printf（%d\n%d\n，t，max）；return？0；}5、算法分析：主函数内调用的库函数sort（a，a+n）的时间复杂度为，for循环的时间杂度为Ο（n），故该算法的时间杂度为。ACM国际大学生程序设计竞赛--实验四半数集问题1、问题描述：？给定一个自然数n，由n开始可以依次产生半数集set（n）中的数如下：（1）n∈set（n）；（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；（3）按此规则进行处理，直到不能再添加自然数为止。例如：set（6）={6，16，26，126，36，136}，半数集set（6）中有6个元素。注意半数集是多重集，对于给定的自然数n，编程计算半数集set（n）中的元素个数。2、题目分析：题目要求输入有多行，每行给出一个整数n（0n1000），输入以文件结束标志EOF结束。半数集set（n）中的元素个数即为所有半数集set（j）（j=n/2）的元素个数之和加1（即将其自身添加到所求元素中）。3、算法设计：a.用数组count[i]计算set（i）中的元素个数，即计算所有j=i/2的set（j）中的元素加其自身的个数之和；b.用数组count_sum[i]计算所有j=i的set（j）中的元素个数之和；c.采用for循环分别对count[i]、count_sum[i]进行累加，即可求出半数集set（n）中的元素个数。4、源程序：#includestdio.hintset（intn）{inti，count[1001]，count_sum[1001]；count[1]=1；count_sum[1]=1；for（i=2；i=n；i++）{count[i]=count_sum[i/2]+1；count_sum[i]=count_sum[i-1]+count[i]；}returncount[n]；}main（）{intn；while（scanf（%d，&n）！=EOF）printf（%d\n，set（n））；return0；}5、算法分析：函数set（n）的时间复杂度为Ο（n），主函数调用函数set（n），故该算法的时间复杂度为Ο（n）。ACM国际大学生程序设计竞赛--实验五集合划分问题2、题目分析：题目要求计算n个元素的集合共有多少个划分（其中每个划分都由不同的非空子集组成），n个元素的集合划分为m个块的划分数为F（n，m）=F（n-1，m-1）+m*F（n-1，m），m从1到n的划分个数相加即可求得总的划分数。3、算法设计：a.这一题的结果数很大，需要使用64位长整型：__int64；b.函数div（）采用递归的方式计算n个元素的集合划分为i个块的划分数：①div（n，1）=1，div（n，n）=1；②div（n，i）=div（n-1，i-1）+i*div（n-1，i）c.主函数采用for循环调用函数div（n，i）（1≤i≤n）对划分数进行累加统计。4、源程序：#includestdio.h__int64？div（__int64？n，__int64？i）{if（i==1||i==n）return？1；else？return？div（n-1，i-1）+i*div（n-1，i）；}main（）{__int64？i，n，s=0；scanf（%I64d，&n）；for（i=1；i=n；i++）s=s+div（n，i）；printf（%I64d，s）；return？0；}5、算法分析：函数div（）的时间复杂度为，主函数内for循环的时间复杂度为O（n），函数div（）嵌套在for循环内，故该算法的时间复杂度为。ACM国际大学生程序设计竞赛--实验七编辑距离问题1、问题描述：？设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A，B）。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d（A，B）。2、题目分析：题目要求计算两字符串的编辑距离，可以采用动态规划算法求解，由最优子结构性质可建立递归关系如下：其中数组d[i][j]存储长度分别为i、j的两字符串的编辑距离；用edit标记所比较的字符是否相同，相同为0，不同为1；用m、n存储字符串a、b的长度。3、算法设计：a.函数min（）找出三个数中的最小值；b.函数d（）计算两字符串的编辑距离：①用edit标记所比较的字符是否相同，相同为0，不同为1；②分别用m、n存储字符串a、b的长度，用数组d[i][j]存储长度分别为i、j的两字符串的编辑距离，问题的最优值记录于d[n][m]中；③利用递归式写出计算d[i][j]的递归算法。4、源程序：#includeiostreamusingnamespacestd；intmin（inta，intb，intc）{inttemp=（ab？a：b）；return（tempc？temp：c）；}intd（char*a，char*b）{intm=strlen（a）；intn=strlen（b）；inti，j，temp；int**d；d=（int**）malloc（sizeof（int*）*（m+1））；for（i=0；i=m；i++）{d[i]=（int*）malloc（sizeof（int）*（n+1））；}d[0][0]=0；for（i=1；i=m；i++）d[i][0]=i；for（j=1；j=n；j++）d[0][j]=j；for（i=1；i=m；i++）{for（j=1；j=n；j++）{intedit=（a[i-1]==b[j-1]？0：1）；d[i][j]=min（（d[i-1][j-1]+edit），（d[i][j-1]+1），（d[i-1][j]+1））；}}temp=d[m][n]；free（d）；returntemp；}main（）{chara[10000]，b[10000]；scanf（%s\n%s，a，b）；printf（%d，d（a，b））；return0；}5、算法分析：函数d（）采用了双重循环，里层的for循环复杂度为O（n），外层的for循环复杂度为O（m），主函数调用了函数d（），故该算法的时间复杂度为O（mn）。ACM算法集锦--【题目】N皇后问题（含八皇后问题的扩展，规则同八皇后）：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。constmax=8；vari，j：integer；a：array[1..max]of0..max；{放皇后数组}b：array[2..2*max]ofboolean；{/对角线标志数组}c：array[-（max-1）..max-1]ofboolean；{\对角线标志数组}col：array[1..max]ofboolean；{列标志数组}total：integer；{统计总数}procedureoutput；{输出}vari：integer；beginwrite（'No.'：4，'['，total+1：2，']'）；fori：=1tomaxdowrite（a[i]：3）；w