ACM第一次作业Word下载.docx
《ACM第一次作业Word下载.docx》由会员分享，可在线阅读，更多相关《ACM第一次作业Word下载.docx（20页珍藏版）》请在冰点文库上搜索。
2、LELE的RPG难题
有排成一行的ｎ个方格，用红（Red）、粉（Pink）、绿（Green）三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
6
递归分析：
从f（n-1）增加到f（n）分两种情况：
（1）一种是直接在所有已经排好了的f（n-1）序列中插入唯一一个第三色有f（n-1）种；
（2）另外是在已经排好了的f（n-2）序列中，插入与缝隙两边其中一个颜色相同的颜色，然后再插入第n个颜色且只需与第n-1种颜色不同有两种，故有2f（n-2）种；
递归关系：
f（n）=f（n-1）+2f（n-2），（n>
=2）
//
（2）LELE的RPG难题
intcountColor（intn）
if（n==2）
return6;
elseif（n==3）
returncountColor（n-1）+2*countColor（n-2）;
3、假设一个有序数组A[0],A[1],…,A[N-1]，编写一个函数intfind（intA[],intx），确定一个整数x是否在数组A中，如果在，则返回其位置，否则返回-1
//（3）
//有序数组元素查找-二分查找
intfind（intA[],intn）
{//sizeof（A）sizeof写进函数得不到数组所占的内存数，而仅是一个指针的内存大小
intlength=0;
//参数数组长度
for（inti=0;
A[i]!
=0;
i++）
{
length++;
}
intleft=0,mid,right=length-1;
while（left<
=right）
mid=（left+right）/2;
if（n<
A[mid]）
right=mid-1;
elseif（n>
{
left=mid+1;
}
else
returnmid;
return-1;
4、假设数组a中的元素是按从小到达顺序排列的，函数find（inta[],intn,int&
i,int&
j,intx）利用二分搜索法确定x是否在含有n个元素的数组a中，如果不在，则参数i为小于x的最大元素的下标，参数j为大于x的最小元素的下标。
如果x在数组a中，则i与j相等，都为等于x的元素的下标。
//（4）二分查找定位
voidfind2（inta[],intn,int&
i,int&
j,intx）
intleft=0,mid,right=n-1;
if（x>
a[mid]）
elseif（x<
i=mid;
j=mid;
if（x<
a[left]）//或者x<
a[right]
i=left-1;
j=left;
i=left;
j=left+1;
}}
5、百鸡问题：
有一个人有一百块钱，打算买一百只鸡。
到市场一看，公鸡三块钱一只，母鸡两块钱一个，小鸡一块钱三只。
现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？
//（5）百鸡问题-枚举法
voidcountChicken（）
inti,j;
doublek;
//公鸡、母鸡、小鸡
for（i=0;
i<
=33;
for（j=0;
j<
=50;
j++）
for（k=0;
k<
=300;
k++）
if（3*i+2*j+k/3.0==100）
cout<
<
"
公鸡"
'
\n'
母鸡：
小鸡：
endl;
6、水仙花数：
水仙花数是指一个3位数，其各位数字的立方和等于它本身。
例如：
153是水仙花数，因为153=13+53+33。
编程求所有的水仙花数。
//（6）三位水仙花数-枚举法
voidcountdaff（）
intl,m,r,temp;
for（inti=100;
=999;
r=i%10;
temp=i/10;
m=temp%10;
l=i/100;
if（i==pow（r,3）+pow（m,3）+pow（l,3））
cout<
7、给定一个矩形，在该矩形中有3个固定的点，以这3个点为中心的气球先后膨胀：
膨胀时触碰到矩形的边或其他气球时则停止膨胀。
编写程序求以何种顺序膨胀气球时，才能使气球的横切面面积之和为最大。
（1）以矩形左下角为原点，建立直角坐标系，程序输入的参数为：
三个固定点的坐标，矩形的长和宽，输出膨胀顺序；
（2）程序对参数的初步处理是算得三点相互之间的距离以及三点分别与矩形的最近距离，然后穷举法列举所有的膨胀顺序，找到使三个圆半径的平方和最小的膨胀顺序；
//（7）气球膨胀问题
doublemin（doublea,doubleb,doublec）
doublemin=a;
if（b<
min）
min=b;
if（c<
min=c;
returnmin;
voidsortBall（doublewidth,doubleheight,doublexA,doubleyA,doublexB,doubleyB,doublexC,doubleyC）
//点与点之间的距离
doubledistance[3];
distance[0]=sqrt（pow（（xA-xB）,2）+pow（（yA-yB）,2））;
distance[1]=sqrt（pow（（xA-xC）,2）+pow（（yA-yC）,2））;
distance[2]=sqrt（pow（（xC-xB）,2）+pow（（yC-yB）,2））;
//点与矩形的最近距离
doubleminRect[3];
doubleminA_x=xA>
width/2?
（width-xA）:
xA;
doubleminA_y=yA>
height/2?
（height-yA）:
yA;
minRect[0]=minA_x<
minA_y?
minA_x:
minA_y;
doubleminB_x=xB>
（width-xB）:
xB;
doubleminB_y=yB>
（height-yB）:
yB;
minRect[1]=minB_x<
minB_y?
minB_x:
minB_y;
doubleminC_x=xC>
（width-xC）:
xC;
doubleminC_y=yC>
（height-yC）:
yC;
minRect[2]=minC_x<
minC_y?
minC_x:
minC_y;
intrelative[3][2]={0,1,0,2,1,2};
boolstat[3]={true,true,true};
//初始化三个气球状态都未膨胀
intarray[3];
//临时顺序
intterarray[3];
//气球膨胀最终顺序
doublerad[3];
//膨胀后的气球半径
doublepowrad2=0;
//半径平方和
//开始穷举
3;
{//第一个膨胀的气球
stat[i]=false;
rad[i]=min（minRect[i],distance[relative[i][0]],distance[relative[i][1]]）;
//第一个膨胀的气球的半径
distance[relative[i][0]]-=rad[i];
distance[relative[i][1]]-=rad[i];
array[0]=i+1;
//第一个膨胀的气球编号
for（intj=0;
{//第二个膨胀的气球
if（stat[j]）
{
stat[j]=false;
rad[j]=min（minRect[j],distance[relative[j][0]],distance[relative[j][1]]）;
//第二个膨胀的气球的半径
distance[relative[j][0]]-=rad[j];
distance[relative[j][1]]-=rad[j];
array[1]=j+1;
//第二个膨胀的气球编号
for（intk=0;
{//第三个膨胀的气球
if（stat[k]）
{
rad[k]=min（minRect[k],distance[relative[k][0]],distance[relative[k][1]]）;
//第三个膨胀的气球的半径
array[2]=k+1;
//第三个膨胀的气球编号
if（（pow（rad[0],2）+pow（rad[1],2）+pow（rad[2],2））>
powrad2）
{
powrad2=（pow（rad[0],2）+pow（rad[1],2）+pow（rad[2],2））;
terarray[0]=array[0];
terarray[1]=array[1];
terarray[2]=array[2];
}
cout<
array[0]<
array[1]<
array[2]<
-------------------"
}
}//第三个膨胀的气球
//恢复第二个气球初始状态
//点与点之间的距离
distance[relative[j][0]]+=rad[j];
distance[relative[j][1]]+=rad[j];
stat[j]=true;
//恢复第二个气球状态都未膨胀
}
}//第二个膨胀的气球
//恢复初始状态
distance[0]=sqrt（pow（xA-xB,2）+pow（yA-yB,2））;
distance[1]=sqrt（pow（xA-xC,2）+pow（yA-yC,2））;
distance[2]=sqrt（pow（xC-xB,2）+pow（yC-yB,2））;
stat[0]=true;
//恢复三个气球状态都未膨胀
stat[1]=true;
stat[2]=true;
}//第一个膨胀的气球
cout<
最佳膨胀顺序为：
terarray[0]<
-"
terarray[1]<
terarray[2]<
//完整程序（+测试）：
#include<
iostream>
math.h>
usingnamespacestd;
{//cout<
sizeof（A）<
//sizeof写进函数得不到数组所占的内存数，而仅仅是一个指针的内存大小
intmain（）
/*//
（1）测试
请输入封闭分割线的个数：
intn;
cin>
>
n;
递归法算得分成平面的个数为：
countArea（n）<
通项法算得分成平面的个数为：
countArea2（n）<
*/
/*
//
（2）测试
请输入格子数：
//n>
=2
染色情况：
countColor（n）<
//（3）测试
intA[10]={1,2,3,4,5,6,7,8,9,0};
//令数组的最后一个元素为0，作为结束标志,不算为数组的元素
cout
升级会员 