第二章习题.docx

第二章习题.docx

《第二章习题.docx》由会员分享，可在线阅读，更多相关《第二章习题.docx（23页珍藏版）》请在冰点文库上搜索。

第二章习题

[讨论]算法实现题众数问题

«问题描述：

给定含有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行是重数。

输入文件示例输出文件示例

input.txt

6

1

2

2

2

3

5

output.txt

2

3

这是算法...

但我还看不懂...

我认为文件操作还好弄.就算法,它是用递归来做的.

voidmode（intLL,intRR）

{

intL1,R1;

intmed=median（a,LL,RR）;

split（a,med,LL,RR,L1,R1）;

if（largest

if（L1-LL>largest）mode（LL,L1-1）;

if（RR-R1>largest）mode（R1+1,RR）;

}

//median用于找中位数,split用中位数将数组分2为段.

[此问题还有待解决,谢谢各位的参与!

]

//首先在此文件夹下建立名为qingsongin2.txt的文件

//其内容为6122235之格式.其中第一的数为数组表长度

#include

#include

#defineMAXSIZE20

usingnamespacestd;

typedefintKeyLype;

typedefintStatus;

typedefstruct{

KeyLypekey;

}RedType;

typedefstruct{

RedTyper[MAXSIZE+1];

intlength;

}SqList;

intSelectSort（SqList&L）

{

inti,j,t;

for（j=0;j

for（i=1;i<=L.length-j;i++）

if（L.r[i].key

{

t=L.r[i].key;

L.r[i].key=L.r[i-1].key;

L.r[i-1].key=t;

}

return0;

}//简单选择排序

intmedian（SqListL,inta,intb）

{

intmed;

if（（a+b）%2==0）

med=（a+b）/2;

else

med=（a+b-1）/2;

returnmed;

}

intL1（SqListL,intmed）

{

while（med>=1&&med<=L.length）

{if（L.r[med].key==L.r[med-1].key）

med--;

else

returnmed-1;

}

}

intR1（SqListL,intmed）

{

while（med>=1&&med<=L.length）

{if（L.r[med].key==L.r[med+1].key）

med++;

else

returnmed+1;

}

}

voidmode（SqListL,inta,intb,int&max_num,int&max_count）

{

if（a==b）

return;

else

{

intl1,r1;

intmed,j,k;

k=j=med=median（L,a,b）;

l1=L1（L,med）;

r1=R1（L,j）;

if（max_count

{

max_count=r1-l1-1;

max_num=L.r[k].key;

}

if（l1-a+1>max_count）

mode（L,a,l1,max_num,max_count）;

if（b-r1+1>max_count）

mode（L,r1,b,max_num,max_count）;

}

}

intmain（）

{

ifstreamfin（"qingsongin2.txt"）;

ofstreamfout（"qingsongout2.txt"）;

SqListL;

intmax_num;//众数

intmax_count;//众数的个数

if（fin.fail（））

{

cout<<"输入qingsongin2.txt文件出错!

"<

return-1;

}

if（fout.fail（））

{

cout<<"fout（\"qingsongout2.txt\"）;"<

return-2;

}

intn;//n是数组表的长度

fin>>n;

inti;

for（i=1;i<=n;i++）

//cin>>L.r[i].key;

fin>>L.r[i].key;

L.length=n;

//cout<

SelectSort（L）;

mode（L,1,L.length,max_num,max_count）;

//cout<<"众数是:

"<

//cout<<"重复次数是:

"<

fout<<"众数是:

"<

fout<<"它的个数是:

"<

cout<<"请查看此文件夹下的qingsongout2.txt文件"<

return0;

}

但它的前提是已排好序的.

算法第2章第11题集合划分问题

2009-11-0217:

37

Description

问题描述：

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}，{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}}由3个子集组

成；集合{{1}，{2}，{3}，{4}}由4个子集组成。

编程任务：

给定正整数n和m，计算出n个元素的集合{1,2,?

n}可以划分为多少个不同的由m个

非空子集组成的集合。

Input

第1行是元素个数n和非空子集数m

Output

计算出的不同的由m个非空子集组成的集合数输出

SampleInput

SampleOutput

6

#include

inta[1000][1000];

intt（intn,inti）

{

intm,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）;

}

}

returnpp;

}

intmain（）

{

intn,m,sum;

cin>>n>>m;

sum=t（n,m）;

cout<

return0;

}

43

算法第2章第10题集合划分问题

2009-11-0217:

36

Description

问题描述：

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}，{4}}，

{{1，2，4}，{3}}，

{{1，3，4}，{2}}，

{{2，3，4}，{1}}，

{{1，2，3，4}}

编程任务：

给定正整数n，计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的非空子集。

Input

第1行是元素个数n

Output

将计算出的不同的非空子集数输出

SampleInput

SampleOutput

52

#include

inta[1000][1000];

intt（intn,inti）

{

intm,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）;

}

}

//cout<

returnpp;

}

intmain（）

{

inti,j,n,sum=0;

cin>>n;

for（i=1;i<=n;i++）

{

if（i==1||i==n）

a[n][i]=1;

else

a[n][i]=t（n,i）;

sum+=a[n][i];

}

cout<

return0;

}

5

算法第2章第9题排列的字典序问题

2009-11-0217:

35

Description

问题描述：

n个元素{1,2,...,n}有n!

个不同的排列。

将这n!

个排列按字典序排列，并编号为0，1，…，

n!

-1。

每个排列的编号为其字典序值。

例如，当n=3时，6个不同排列的字典序值如下：

字典序值012345

排列123132213231312321

编程任务：

给定n以及n个元素{1,2,...,n}的一个排列，计算出这个排列的字典序值，以及按字

典序排列的下一个排列。

Input

第1行是元素个数n。

接下来的1行是n个元素{1,2,...,n}的一个排列。

Output

将计算出的排列的字典序值和按字典序排列的下一个排列输出.第一行是字典序值，第2行是按字典序排列的下一个排列。

SampleInput

SampleOutput

8227

26458317

#include

#include

voidxiageshuzi（intn,int*Src,int*Des）

{

inti,j,temp,min,mark;

i=n-1;

while（（Src[i]0））

i--;

memcpy（Des,Src,n*sizeof（int））;

if（i==0）

return;

else

{

temp=Des[i-1];

min=Des[i];

for（j=i;j

{

if（（Des[j]>temp）&&（Des[j]<=min））

mark=j;

}

Des[i-1]=Des[mark];

Des[mark]=temp;

for（;i

for（j=n-1;j>i;j--）

{

if（Des[j]

{

temp=Des[j];

Des[j]=Des[j-1];

Des[j-1]=temp;

}

}

}

}

intPermToNum（intn,int*p）

{

inti,j,count,k,ret,m;

k=1;

ret=0;

for（i=n-1,j=0;i>=0;i--,j++）

{

count=p[i]-1;

for（m=0;m

if（p[m]

count--;

if（j==0）

k=1;

else

k*=j;

ret+=count*k;

}

returnret;

}

intmain（）

{

intn,i,sum;

inta[100]={0};

intDes[100]={0};

scanf（"%d",&n）;

for（i=0;i

scanf（"%d",&a[i]）;

sum=PermToNum（n,a）;

printf（"%d\n",sum）;

xiageshuzi（n,a,Des）;

for（i=0;i

printf（"%d",Des[i]）;

return0;

}

8

26458173

算法第2章第6题半数单集问题

Description

给定一个自然数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）中的元素个数。

Input

只有1行，给出整数n。

（0

Output

只有1行，给出半数集set（n）中的元素个数。

SampleInput

SampleOutput

6

#include

intmain（）

{

intn,N,p[10000],count,i,k,j;

count=0;

cin>>N;

n=N/2;

for（i=0;i<=n;i++）

p[i]=0;

for（i=1;i<=n;i++）

{

k=i/2;

for（j=1;j<=k;j++）

p[i]+=p[j];

p[i]+=1;

count+=p[i];

if（（i>10）&&（2*（i/10）<=i%10））

count-=p[i/10];

}

count+=1;

cout<

return0;

}

6

#include

inta[1000];

intprog（intk）  

{  

   inti,s;  

   if（k==1）  

       return1;  

   else  

   {  

       if（a[k]==0）  

       {  

           s=1;  

           for（i=1;i<=k/2;i++）  

           {  

               s+=prog（i）;  

if（i>10&&（i/10<=（i%10）/2））  

                   s-=prog（i/10）;   

           }  

           a[k]=s;  

       }  

       returna[k];  

   }  

}  

intmain（）     

{

   intj,n;

while（scanf（"%d",&n）,n）

{

  for（j=0;j<=n;j++）  

   a[j]=0;    

  printf（"%d\n",prog（n））;

}

return0;

}

算法第2章第5题半数集问题

2009-11-0217:

31

Description

给定一个自然数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）中的元素个数。

Input

有多行

每行为一个整数n

（n大于0，且小于1000）

Output

按行给出每行的结果（半数集set（n）中的元素个数）。

SampleInput

SampleOutput

6

#include

intmain（）

{

intn,N,p[10000],count,i,k,j;

while（cin>>N）

{

count=0;

n=N/2;

for（i=0;i<=n;i++）

p[i]=0;

for（i=1;i<=n;i++）

{

k=i/2;

for（j=1;j<=k;j++）

p[i]+=p[j];

p[i]+=1;

count+=p[i];

}

count+=1;

cout<

}

return0;

}

6

算法第2章第3题邮局选址问题

2009-11-0217:

30

Description

在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的

街区中。

用x坐标表示东西向，用y坐标表示南北向。

各居民点的位置可以由坐标（x,y）表示。

街区中任意2点（x1,y1）和（x2,y2）之间的距离可以用数值|x1-x2|+|y1-y2|度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

给定n个居民点的位置,编程计算n个居民点到邮局的距离总和的最小值。

Input

输入数据的第1行是居民点数n，1<=n<=10000。

接下来n行

是居民点的位置，每行2个整数x和y，-10000<=x，y<=10000。

Output

输出的第1行中的数是n个居民点到邮局的距离总和的最小值

SampleInput

SampleOutput

10

#include

#include

intcmp（constvoid*a,constvoid*b）

{

return*（int*）a-*（int*）b;

}

voidmain（）

{

intn,i=0,j,s,pp,qq,*x,*y;

scanf（"%d",&n）;

x=malloc（sizeof（int）*n）;

y=malloc（sizeof（int）*n）;

for（i=0;i

scanf（"%d%d",x+i,y+i）;

qsort（x,n,sizeof（int）,cmp）;

qsort（y,n,sizeof（int）,cmp）;

for（i=0;i

{

s=0;

for（j=0;j

s+=（*（y+i）-*（y+j））;

j++;

for（;j

s+=（*（y+j）-*（y+i））;

if（i==0）

pp=s;

if（s

pp=s;

}

for（i=0;i

{

s=0;

for（j=0;j

s+=（*（x+i）-*（x+j））;

j++;

for（;j

s+=（*（x+j）-*（x+i））;

if（i==0）

qq=s;

if（s

qq=s;

}

printf（"%d\n",pp+qq）;

}

5

12

22

13

3-2

33

算法第2章第2题众数问题

2009-11-0217:

29

Description

给定含有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行是重数。

SampleInput

SampleOutput

Hint

2

3

#include

#include

intcmp（constvoid*,constvoid*）;

intmain（）

{

intn,i,*a,num,max=0,t=1;

scanf（"%d",&n）;

a=malloc（sizeof（int）*n）;

for（i=0;i

scanf