ACM第一次作业.doc

第一次作业1、平面分割方法设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。输入示例：3输出示例：8要求：用两种方法：（1） 得到第n项与其之前已知项之间的关系，程序用递归实现（2） 得到第n项的通项公式，程序直接实现。解：（1） 递归关系：f(n)=f(n-1)+2(n-1)(增加几个交点就增加几个平面)（2） 通项公式：f(n)=n(n-1)+2/(1)/平面分割方法int countArea(int n)/递归法if(n=1)return 2;elsereturn countArea(n-1)+2*(n-1);/通项公式法an=2+n(n-1)int countArea2(int n)return 2+n*(n-1);2、LELE的RPG难题有排成一行的个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求的涂法.输入示例：3输出示例：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难题int countColor(int n)if(n=2)return 6;else if(n=3)return 6;elsereturn countColor(n-1)+2*countColor(n-2);3、 假设一个有序数组A0, A1, , AN-1，编写一个函数int find(int A, int x)，确定一个整数x是否在数组A中，如果在，则返回其位置，否则返回-1/(3)/有序数组元素查找-二分查找int find(int A,int n)/sizeof(A)sizeof写进函数得不到数组所占的内存数，而仅是一个指针的内存大小 int length=0;/参数数组长度for(int i=0;Ai!=0;i+)length+;int left=0,mid,right=length-1;while(left=right)mid=(left+right)/2;if(nAmid)left=mid+1;elsereturn mid;return -1;4、假设数组a中的元素是按从小到达顺序排列的，函数find(int a, int n, int &i, int &j, int x)利用二分搜索法确定x是否在含有n个元素的数组a中，如果不在，则参数i为小于x的最大元素的下标，参数j为大于x的最小元素的下标。如果x在数组a中，则i与j相等，都为等于x的元素的下标。/(4)二分查找定位void find2(int a,int n,int &i,int &j,int x)int left=0,mid,right=n-1;while(leftamid)left=mid+1;else if(xamid)right=mid-1;elsei=mid;j=mid;if(xaleft)/或者xarighti=left-1;j=left;elsei=left;j=left+1;5、百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡三块钱一只，母鸡两块钱一个，小鸡一块钱三只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？/(5)百鸡问题-枚举法void countChicken()int i,j;double k;/公鸡、母鸡、小鸡for(i=0;i=33;i+)for(j=0;j=50;j+)for(k=0;k=300;k+)if(3*i+2*j+k/3.0=100)cout公鸡in母鸡：jn小鸡：knendl;6、水仙花数：水仙花数是指一个3位数，其各位数字的立方和等于它本身。例如：153是水仙花数，因为153=13+53+33。编程求所有的水仙花数。/(6)三位水仙花数-枚举法void countdaff()int l,m,r,temp;for(int i=100;i=999;i+)r=i%10;temp=i/10;m=temp%10;l=i/100;if(i=pow(r,3)+pow(m,3)+pow(l,3)coutiendl;7、 给定一个矩形，在该矩形中有3个固定的点，以这3个点为中心的气球先后膨胀：膨胀时触碰到矩形的边或其他气球时则停止膨胀。编写程序求以何种顺序膨胀气球时，才能使气球的横切面面积之和为最大。解：（1）以矩形左下角为原点，建立直角坐标系，程序输入的参数为：三个固定点的坐标，矩形的长和宽，输出膨胀顺序；（2）程序对参数的初步处理是算得三点相互之间的距离以及三点分别与矩形的最近距离，然后穷举法列举所有的膨胀顺序，找到使三个圆半径的平方和最小的膨胀顺序；/(7)气球膨胀问题double min(double a,double b,double c)double min=a;if(bmin)min=b;if(cwidth/2?(width-xA):xA;double minA_y=yAheight/2?(height-yA):yA;minRect0=minA_xwidth/2?(width-xB):xB;double minB_y=yBheight/2?(height-yB):yB;minRect1=minB_xwidth/2?(width-xC):xC;double minC_y=yCheight/2?(height-yC):yC;minRect2=minC_xminC_y?minC_x:minC_y;int relative32=0,1,0,2,1,2;bool stat3=true,true,true;/初始化三个气球状态都未膨胀int array3;/临时顺序int terarray3;/气球膨胀最终顺序double rad3;/膨胀后的气球半径double powrad2=0;/半径平方和/开始穷举for(int i=0;i3;i+)/第一个膨胀的气球stati=false;radi=min(minRecti,distancerelativei0,distancerelativei1);/第一个膨胀的气球的半径distancerelativei0-=radi;distancerelativei1-=radi;array0=i+1;/第一个膨胀的气球编号for(int j=0;j3;j+)/第二个膨胀的气球if(statj)statj=false;radj=min(minRectj,distancerelativej0,distancerelativej1);/第二个膨胀的气球的半径distancerelativej0-=radj;distancerelativej1-=radj;array1=j+1;/第二个膨胀的气球编号for(int k=0;kpowrad2)powrad2=(pow(rad0,2)+pow(rad1,2)+pow(rad2,2);terarray0=array0;terarray1=array1;terarray2=array2;coutarray0endl;coutarray1endl;coutarray2endl;cout-endl;/第三个膨胀的气球/恢复第二个气球初始状态/点与点之间的距离distancerelativej0+=radj;distancerelativej1+=radj;statj=true;/恢复第二个气球状态都未膨胀/第二个膨胀的气球/恢复初始状态/点与点之间的距离distance0=sqrt(pow(xA-xB,2)+pow(yA-yB,2);distance1=sqrt(pow(xA-xC,2)+pow(yA-yC,2);distance2=sqrt(pow(xC-xB,2)+pow(yC-yB,2);stat0=true;/恢复三个气球状态都未膨胀stat1=true;stat2=true;/第一个膨胀的气球cout最佳膨胀顺序为：terarray0-terarray1-terarray2endl;/完整程序（+测试）：#include#includeusing namespace std;/(1)/平面分割方法int countArea(int n)/递归法if(n=1)return 2;elsereturn countArea(n-1)+2*(n-1);/通项公式法an=2+n(n-1)int countArea2(int n)return 2+n*(n-1);/(2)LELE的RPG难题int countColor(int n)if(n=2)return 6;else if(n=3)return 6;elsereturn countColor(n-1)+2*countColor(n-2);/(3)/有序数组元素查找-二分查找int find(int A,int n)/coutsizeof(A)endl;/sizeof写进函数得不到数组所占的内存数，而仅仅是一个指针的内存大小 int length=0;/参数数组长度for(int i=0;Ai!=0;i+)length+;int left=0,mid,right=length-1;while(left=right)mid=(left+right)/2;if(nAmid)left=mid+1;elsereturn mid;return -1;/(4)二分查找定位void find2(int a,int n,int &i,int &j,int x)int left=0,mid,right=n-1;while(leftamid)left=mid+1;else if(xamid)right=mid-1;elsei=mid;j=mid;if(xaleft)/或者xarighti=left-1;j=left;elsei=left;j=left+1;/(5)百鸡问题-枚举法void countChicken()int i,j;double k;/公鸡、母鸡、小鸡for(i=0;i=33;i+)for(j=0;j=50;j+)for(k=0;k=300;k+)if(3*i+2*j+k/3.0=100)cout公鸡in母鸡：jn小鸡：knendl;/(6)三位水仙花数-枚举法void countdaff()int l,m,r,temp;for(int i=100;i=999;i+)r=i%10;temp=i/10;m=temp%10;l=i/100;if(i=pow(r,3)+pow(m,3)+pow(l,3)coutiendl;/(7)气球膨胀问题double min(double a,double b,double c)double min=a;if(bmin)min=b;if(cwidth/2?(width-xA):xA;double minA_y=yAheight/2?(height-yA):yA;minRect0=minA_xwidth/2?(width-xB):xB;double minB_y=yBheight/2?(height-yB):yB;minRect1=minB_xwidth/2?(width-xC):xC;double minC_y=yCheight/2?(height-yC):yC;minRect2=minC_xminC_y?minC_x:minC_y;int relative32=0,1,0,2,1,2;bool stat3=true,true,true;/初始化三个气球状态都未膨胀int array3;/临时顺序int terarray3;/气球膨胀最终顺序double rad3;/膨胀后的气球半径double powrad2=0;/半径平方和/开始穷举for(int i=0;i3;i+)/第一个膨胀的气球stati=false;radi=min(minRecti,distancerelativei0,distancerelativei1);/第一个膨胀的气球的半径distancerelativei0-=radi;distancerelativei1-=radi;array0=i+1;/第一个膨胀的气球编号for(int j=0;j3;j+)/第二个膨胀的气球if(statj)statj=false;radj=min(minRectj,distancerelativej0,distancerelativej1);/第二个膨胀的气球的半径distancerelativej0-=radj;distancerelativej1-=radj;array1=j+1;/第二个膨胀的气球编号for(int k=0;kpowrad2)powrad2=(pow(rad0,2)+pow(rad1,2)+pow(rad2,2);terarray0=array0;terarray1=array1;terarray2=array2;coutarray0endl;coutarray1endl;coutarray2endl;cout-endl;/第三个膨胀的气球/恢复第二个气球初始状态/点与点之间的距离distancerelativej0+=radj;distancerelativej1+=radj;statj=true;/恢复第二个气球状态都未膨胀/第二个膨胀的气球/恢复初始状态/点与点之间的距离distance0=sqrt(pow(xA-xB,2)+pow(yA-yB,2);distance1=sqrt(pow(xA-xC,2)+pow(yA-yC,2);distance2=sqrt(pow(xC-xB,2)+pow(yC-yB,2);stat0=true;/恢复三个气球状态都未膨胀stat1=true;stat2=true;/第一个膨胀的气球cout最佳膨胀顺序为：terarray0-terarray1-t