第二章习题.docx

1、第二章习题讨论算法实现题 众数问题«问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=1，2，2，2，3，5。多重集S的众数是2，其重数为3。«编程任务：对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。«数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数。«结果输出:程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2 行，第1 行给出众数，第2 行是重

2、数。输入文件示例 输出文件示例input.txt 6122235output.txt23这是算法.但我还看不懂.我认为文件操作还好弄.就算法,它是用递归来做的.void mode(int LL,int RR)int L1,R1;int med=median(a,LL,RR);split(a,med,LL,RR,L1,R1);if(largestlargest) mode(LL,L1-1);if(RR-R1largest) mode(R1+1,RR);/median用于找中位数,split用中位数将数组分2为段.此问题还有待解决,谢谢各位的参与!/首先在此文件夹下建立名为qingsongin2.

3、txt的文件/其内容为6 1 2 2 2 3 5 之格式.其中第一的数为数组表长度#include#include#define MAXSIZE 20using namespace std;typedef int KeyLype;typedef int Status;typedef struct KeyLype key; RedType;typedef struct RedType rMAXSIZE + 1;int length; SqList;int SelectSort(SqList &L)int i,j,t;for(j=0;jL.length;j+)for(i=1;i=L.length-

4、j;i+)if(L.ri.key=1&med=1&med=L.length) if(L.rmed.key=L.rmed+1.key)med+;elsereturn med+1;void mode(SqList L,int a,int b,int &max_num,int &max_count) if(a=b) return ;else int l1,r1;int med,j,k;k=j=med=median(L,a,b);l1=L1(L,med);r1=R1(L,j);if(max_countmax_count)mode(L,a,l1,max_num,max_count);if(b-r1+1m

5、ax_count)mode(L,r1,b,max_num,max_count);int main() ifstream fin(qingsongin2.txt);ofstream fout(qingsongout2.txt);SqList L;int max_num;/众数int max_count;/众数的个数if (fin.fail() cout输入qingsongin2.txt文件出错!endl;return -1;if (fout.fail() coutfout(qingsongout2.txt);n;int i;for(i=1;iL.ri.key;finL.ri.key;L.leng

6、th=n;/coutendl;SelectSort(L);mode(L,1,L.length, max_num,max_count);/cout众数是:max_numendl;/cout重复次数是:max_numendl;fout众数是:max_numendl;fout它的个数是:max_countendl;cout请查看此文件夹下的qingsongout2.txt文件endl;return 0;但它的前提是已排好序的.算法第2章第11题 集合划分问题2009-11-02 17:37Description 问题描述： n个元素的集合1,2,?,n可以划分为若干个非空子集。例如，当n=4时，集合

7、1，2， 3，4可以划分为15个不同的非空子集如下： 1，2，3，4， 1，2，3，4， 1，3，2，4， 1，4，2，3， 2，3，1，4， 2，4，1，3， 3，4，1，2， 1，2，3，4， 1，3，2，4， 1，4，2，3， 1，2，3，4， 1，2，4，3， 1，3，4，2， 2，3，4，1， 1，2，3，4 其中，集合1，2，3，4由 1 个子集组成；集合1，2，3，4，1，3，2， 4，1，4，2，3，1，2，3，4，1，2，4，3，1，3，4，2，2， 3，4，1由2个子集组成；集合1，2，3，4，1，3，2，4，1，4， 2，3，2，3，1，4，2，4，1，3，3，4，1，2

8、由 3 个子集组 成；集合1，2，3，4由4个子集组成。 编程任务： 给定正整数n和m，计算出n个元素的集合1,2,?,n可以划分为多少个不同的由m 个 非空子集组成的集合。 Input 第 1 行是元素个数n和非空子集数mOutput 计算出的不同的由m个非空子集组成的集合数输出Sample Input Sample Output 6#includeint a10001000;int t(int n,int i) int m,pp=0; m=i-1;n-; if(m=n) pp+; else if(n=1) pp+; else if(m=1) pp+; else pp+=t(n,m); pp

9、+=i*t(n,i); return pp;int main() int n,m,sum; cinnm; sum=t(n,m); coutsumendl; return 0;4 3算法第2章第10题 集合划分问题2009-11-02 17:36Description 问题描述： n个元素的集合1,2,.,n可以划分为若干个非空子集。例如，当n=4时，集合1，2， 3，4可以划分为15个不同的非空子集如下： 1，2，3，4， 1，2，3，4， 1，3，2，4， 1，4，2，3， 2，3，1，4， 2，4，1，3， 3，4，1，2， 1，2，3，4， 1，3，2，4， 1，4，2，3， 1，2，3

10、，4， 1，2，4，3， 1，3，4，2， 2，3，4，1， 1，2，3，4 编程任务： 给定正整数n，计算出n个元素的集合1,2,.,n可以划分为多少个不同的非空子集。 Input 第1 行是元素个数nOutput 将计算出的不同的非空子集数输出Sample Input Sample Output 52#includeint a10001000;int t(int n,int i) int m,pp=0; m=i-1;n-; if(m=n) pp+; else if(n=1) pp+; else if(m=1) pp+; else pp+=t(n,m); pp+=i*t(n,i); /cou

11、tppn; for(i=1;i=n;i+) if(i=1|i=n) ani=1; else ani=t(n,i); sum+=ani; coutsumendl; return 0;5算法第2章第9题 排列的字典序问题2009-11-02 17:35Description 问题描述： n个元素1,2,.,n有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1， n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下： 字典序值 0 1 2 3 4 5 排列 123 132 213 231 312 321 编程任务： 给定 n 以及 n 个元素1,2,.,n

12、的一个排列，计算出这个排列的字典序值，以及按字 典序排列的下一个排列。 Input 第1 行是元素个数n。接下来的1 行是 n个元素1,2,.,n的一个排列。 Output 将计算出的排列的字典序值和按字典序排列的下一个排列输出.第一行是字典序值，第2行是按字典序排列的下一个排列。Sample Input Sample Output 8227 2 6 4 5 8 3 1 7#include #include void xiageshuzi(int n,int * Src,int *Des) int i,j,temp,min,mark; i=n-1; while (Srci0) i-; memc

13、py(Des,Src,n*sizeof(int); if (i=0) return; else temp = Desi-1; min = Desi; for (j=i;jtemp)&(Desj=min) mark=j; Desi-1=Desmark; Desmark=temp; for (;ii;j-) if (Desj=0;i-,j+) count=pi-1; for (m=0;mi;m+) if (pmpi) count-; if (j=0) k=1; else k*=j; ret+=count*k; return ret;int main() int n,i,sum; int a100=

14、0; int Des100=0; scanf(%d,&n); for (i=0;in;i+) scanf(%d,&ai); sum=PermToNum(n,a); printf(%dn,sum); xiageshuzi(n,a,Des); for (i=0;in;i+) printf(%d ,Desi); return 0;8 2 6 4 5 8 1 7 3算法第2章第6题 半数单集问题Description 给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。 (1) nset(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则

15、进行处理，直到不能再添加自然数为止。 例如，set(6)=6,16,26,126,36,136。半数集 set(6)中有6 个元素。 注意半数集不是多重集。集合中已经有的元素不再添加到集合中。 编程任务： 对于给定的自然数n，编程计算半数集set(n)中的元素个数。 Input 只有1行，给出整数n。(0n=200)Output 只有1 行，给出半数集set(n)中的元素个数。 Sample Input Sample Output 6#include int main() int n,N,p10000,count,i,k,j; count = 0; cinN; n = N/2; for(i=0

16、;i=n;i+) pi = 0; for(i=1;i=n;i+) k=i/2; for(j=1;j10)&(2*(i/10)=i%10) count-=pi/10; count+=1; coutcountendl;return 0;6#includeint a1000;int prog(int k) int i,s; if(k=1) return 1; else if(ak=0) s=1; for(i=1;i10&(i/10=(i%10)/2) s-=prog(i/10); ak=s; return ak; int main() int j,n;while(scanf(%d,&n),n) fo

17、r(j=0;j=n;j+) aj=0; printf(%dn,prog(n);return 0; 算法第2章第5题 半数集问题2009-11-02 17:31Description 给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。 (1) nset(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 例如，set(6)=6,16,26,126,36,136。半数集 set(6)中有6 个元素。 注意半数集是多重集。 编程任务： 对于给定的自然数n，编程计算半数集set(n)中的元素个数。 I

18、nput 有多行 每行为一个整数n (n大于0，且小于1000)Output 按行给出每行的结果（半数集set(n)中的元素个数）。 Sample Input Sample Output 6#include int main() int n,N,p10000,count,i,k,j; while(cinN) count = 0; n = N/2; for(i=0;i=n;i+) pi = 0; for(i=1;i=n;i+) k=i/2; for(j=1;j=k;j+) pi+=pj; pi+=1; count+=pi; count+=1; coutcountendl; return 0;6算

19、法第2章第3题 邮局选址问题2009-11-02 17:30Description 在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的 街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。 街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。 居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 给定n个居民点的位置,编程计算 n 个居民点到邮局的距离总和的最小值。Input 输入数据的第 1 行是居民点数 n，1=n=10000。接下来 n 行 是居民点的位置

20、，每行2个整数x和y，-10000=x，y=10000。 Output 输出的第 1 行中的数是 n 个居民点到邮局的距离总和的最小值Sample Input Sample Output 10#include#includeint cmp(const void *a,const void *b) return *(int *)a-*(int *)b;void main() int n,i=0,j,s,pp,qq,*x,*y; scanf(%d,&n); x=malloc(sizeof(int)*n); y=malloc(sizeof(int)*n); for(i=0;in;i+) scanf(

21、%d %d,x+i,y+i); qsort(x,n,sizeof(int),cmp); qsort(y,n,sizeof(int),cmp); for(i=0;in;i+) s=0; for(j=0;ji;j+) s+=(*(y+i)-*(y+j); j+; for(;jn;j+) s+=(*(y+j)-*(y+i); if(i=0) pp=s; if(spp) pp=s; for(i=0;in;i+) s=0; for(j=0;ji;j+) s+=(*(x+i)-*(x+j); j+; for(;jn;j+) s+=(*(x+j)-*(x+i); if(i=0) qq=s; if(sqq)

22、qq=s; printf(%dn,pp+qq);51 2 2 2 1 3 3 -2 3 3算法第2章第2题 众数问题2009-11-02 17:29Description 给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重 集S中重数最大的元素称为众数。 例如，S=1，2，2，2，3，5。 多重集S的众数是2，其重数为3。 编程任务： 对于给定的由n个自然数组成的多重集S，编程计算S 的众数及其重数。 Input 输入数据的第1行多重集S中元素个数n；接下来的 n 行中，每行有一个自然数。Output 输出有2 行，第1 行给出众数，第2行是重数。 Sample Input Sample Output Hint 2 3#include #include int cmp(const void *, const void *);int main() int n, i, *a, num, max = 0, t = 1; scanf(%d, &n); a = malloc(sizeof(int) * n); for(i = 0; i n; i+) scanf