《程序设计竞赛题解、思考与变通.doc》由会员分享，可在线阅读，更多相关《程序设计竞赛题解、思考与变通.doc（16页珍藏版）》请在金锄头文库上搜索。
1、程序设计竞赛题解、思考与变通（2014湖南理工学院程序设计竞赛评析）1旅馆开关门旅馆里有10000间房间，从1到10000编了号。第一位服务员把所有的房间门都打开了，第二位服务员把所有编号是2的倍数的房间进行“相反处理”，第三位服务员把所有编号是3的倍数的房间作“相反处理”， 第n(1=n=10000)位服务员把所有编号是n的倍数的房间作“相反处理”。问第n个服务员来过后，问共有多少张门是打开的(C)。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）/ 旅馆开关门 #includevoid main() int j,k,n,s,a10001; printf( 请输入正整数n(n=1
2、0000): ); scanf(%d,&n); / 输入n for(j=1;j=10000;j+) aj=0; s=0; for(k=1;k=n;k+) for(j=1;j=10000;j+) if(j%k=0) aj=1-aj; /相反处理：也可aj=(aj+1)%2; for(j=1;j=10000;j+) s+=aj; printf(%dn,s); / 输出结果 变通：求在这n个服务员中，哪一个服务员处理后门开的最少？/ 旅馆开关门 #includevoid main() int j,k,n,s,km,min,a10001; printf( 请输入正整数n(n=10000): ); sc
3、anf(%d,&n); / 输入n for(j=1;j=10000;j+) aj=0; min=20000; for(k=1;k=n;k+) s=0; for(j=1;j=10000;j+) if(j%k=0) aj=1-aj; / j为k倍数时aj 施相反处理 s+=aj; if(smin)min=s;km=k; printf( %d,%dn,km,min); / 输出结果 请输入正整数n(n=10000): 2014 82,3703在2014个服务员中，第82个服务员处理后门开的最少：3703扇门打开！思考：求在这n个服务员中，哪一个服务员处理后的开门数最接近某一指定整数m（例如2014）
4、？2喝汽水 有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有1=n1012) 个空汽水瓶，最多可以换多少瓶（max）汽水喝？解：设借m瓶，还空瓶至少为3m个，则有n+m3mmn/2max=n/2n为偶数时取其一半；n为奇数时取其一半取整。/ 喝汽水#includevoid main() long n; p
5、rintf( 请输入正整数n: ); scanf(%ld,&n); / 输入n printf(%ldn,n/2); / 输出结果 变通：某学院有m个学生参加南湖春游，休息时喝汽水。南湖商家公告：买1瓶汽水定价1.40元，喝1瓶汽水（瓶不带走）1元。为节约资源，规定3个空瓶可换回1瓶汽水，或20个空瓶可换回7瓶汽水。 （3） 为方面顾客，可先借后还。例如借1瓶汽水，还3个空瓶；或借7瓶汽水，还20个空瓶。问m个学生每人喝1瓶汽水（瓶不带走），至少需多少元？输入正整数m(2m10000)，输出至少需多少元（精确到小数点后第2位）。解：注意到春游喝汽水无需带走空瓶，根据商家的规定作以下分析。 （1）
6、 如果人数为20人，买13瓶汽水，借7瓶汽水，饮完20瓶汽水后还20个空瓶（即相当于换回7瓶汽水还给商家），两清。此时每人花费为13/20*1.40=0.91元 （2） 如果人数为3人，买2瓶汽水，借1瓶汽水，饮完3瓶汽水后还3个空瓶（即相当于换回1瓶汽水还给商家），两清。此时每人花费为2/3*1.40=0.93元（3） 如果只有2人或1人，每人喝1瓶汽水（瓶不带走），此时每人花费1元。（4） 注意到0.910.931，因而有以下的最省钱算法：1） 把m人分为x=m/20个大组，每组20人。每组买13瓶汽水（借7瓶汽水），饮完后还20个空瓶（即相当于换回7瓶汽水还给商家），两清。2） 剩下t=
7、m-x*20人，分为y=t/3个小组，每组3人。每组买2瓶汽水（借1瓶汽水），饮完后还3个空瓶（即相当于换回1瓶汽水还给商家），两清。3） 剩下t=m-x*20-y*3人，每人花1元喝1瓶。该算法得所花费用最低为：(13*x+2*y)*1.40+t元。（5） 费用最低的算法描述/ 喝汽水 main() long m,t,x,y;printf( 请输入m：); scanf(%ld,&m);x=m/20; / 分x个大组，每组买13瓶汽水，借7瓶t=m-20*x; / 剩下大组外的t人y=t/3; / 剩下t人分y个小组，每组买2瓶汽水，借1瓶t=m-20*x-3*y; / 剩下大小组外的t人，每
8、人花1元喝1瓶printf( 喝%ld瓶汽水，需%.2f元。n,m,(13*x+2*y)*1.40+t); 该算法有输入，即输入人数m；有处理，即依次计算大组数x、小组数y与剩下的零散人数t；有输出，即输出最省费用。3长整数整除定理：把一个至少两位的正整数的个位数字去掉，再从余下的数中减去个位数的5倍。当且仅当差是17的倍数时，原数也是17的倍数 。例如，34是17的倍数，因为3-20=-17是17的倍数；201不是17的倍数，因为20-5=15不是17的倍数。输入一个正整数n（1=n=10100），你的任务是判断它是否是17的倍数。如果n是17的倍数则输出1，否则输出0。判断长整数n（可达1
9、01位）能否被17整除：模拟整数的除法作！/ 判断长整数n（可达101位）能否被17整除#include#includevoid main() int a,c,k,m,d101; char n101; scanf(%s,n); / 以字符串方式输入长整数 for(m=0,k=0;nk!=0;k+) m+; / m统计输入的整数n的位数 dk=nk-48; / 把数字字符变为数值 c=d0; / c为余数 for(k=1;k=m-1;k+) a=c*10+dk;c=a%17; / a为模拟整除的被除数if(c=0) printf( 1n); / 输出结果else printf( 0n); 变通：
10、 n个“1”组成的整数能被给定的正整数p（个位数字不为5 的奇数），求n至少为多大？解：写出求解n个“1”组成的整数能被整数p（个位数字不为5 的奇数），n至少为多大？。例如求出 n至少为多大时，n个“1”组成的整数能被2013整除？#include void main() int a,c,p,n; printf( 请输入p: ); scanf(%d,&p);c=1111;n=4; / 变量c与n赋初值 while(c!=0) / 循环模拟整数竖式除法 a=c*10+1;c=a%p;n=n+1; / 每试商一位n增1 printf( 由 %d 个1组成的整数能被 %d 整除。n,n,p);思考
11、：对指定的正整数p，如何寻求最小的01串积？4解不等式设n为正整数，解不等式（分母中各项符号“+”、“-”相间）输入正整数a,b(1ab10000000)，输出n满足的解区间c,d的上下限c,d。样例输入样例输出3 82 3解：上下限一般为键盘输入的a,b。分两段求和：应用条件sa实施循环段；应用条件sb实施循环段。/ 解分数不等式#include #includevoid main() long c,d,i; double a,b,t,ts,s; printf( 请输入a,b: ); scanf(%lf %lf,&a,&b); i=0;t=ts=s=0; while(sa) i=i+1; t
12、=t+(double)1/i; if(i%2=0) ts=ts-(double)1/i; else ts=ts+(double)1/i; s=s+t/ts; c=i; while(sb) i=i+1; t=t+(double)1/i; if(i%2=0) ts=ts-(double)1/i; else ts=ts+(double)1/i; s=s+t/ts; d=i-1; printf(%ld %ldn,c,d); 测试输入测试输出10 10005 1491000 2013150 2681000000 1000000065024 542331附： VFP程序清单input a= to ainput b= to bi=0t=0ts=0s=0do while sa i=i+1 t=t+1/i if i%2=0 ts=ts-1/i else ts=ts+1/i endif s=s+t/ts enddo c=i do while sb i=i+1 t=t+1/i if i%2=0 ts=ts-1/i else ts=ts+1/i endif s=s+t/ts enddo d=i-1 ? c,d return变通：分数不等式试解以下关于正整数n的不等式
