程序设计竞赛题解、思考与变通

《程序设计竞赛题解、思考与变通》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序设计竞赛题解、思考与变通（2014湖南理工学院程序设计竞赛评析）1．旅馆开关门旅馆里有10000间房间，从1到10000编了号。第一位服务员把所有的房间门都打开了，第二位服务员把所有编号是2的倍数的房间进行“相反处理”，第三位服务员把所有编号是3的倍数的房间作“相反处理”，……，第n(1<=n<=10000)位服务员把所有编号是n的倍数的房间作“相反处理”。问第n个服务员来过后，问共有多少张门是打开的(C)。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）//旅馆开关门#includevoidmain(){intj,k,n,s,a[10001];p

2、rintf("请输入正整数n(n<=10000):");scanf("%d",&n);//输入nfor(j=1;j<=10000;j++)a[j]=0;s=0;for(k=1;k<=n;k++)for(j=1;j<=10000;j++)if(j%k==0)a[j]=1-a[j];//相反处理：也可a[j]=(a[j]+1)%2;for(j=1;j<=10000;j++)s+=a[j];printf("%d",s);//输出结果}变通：求在这n个服务员中，哪一个服务员处理后门开的最少？//旅馆开关门#includevoidmain(){intj,k,n,s,km

3、,min,a[10001];printf("请输入正整数n(n<=10000):");scanf("%d",&n);//输入nfor(j=1;j<=10000;j++)a[j]=0;min=20000;for(k=1;k<=n;k++){s=0;for(j=1;j<=10000;j++){if(j%k==0)a[j]=1-a[j];//j为k倍数时a[j]施相反处理s+=a[j];}if(s

4、员处理后门开的最少：3703扇门打开！思考：求在这n个服务员中，哪一个服务员处理后的开门数最接近某一指定整数m（例如2014）？2．喝汽水有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有1<=n<1012)个空汽水瓶，最多可以换多少瓶（max）汽水喝？解：设借m瓶，还空瓶至少为3m个，则有n+

5、m≥3mm≤n/2max=[n/2]n为偶数时取其一半；n为奇数时取其一半取整。//喝汽水#includevoidmain(){longn;printf("请输入正整数n:");scanf("%ld",&n);//输入nprintf("%ld",n/2);//输出结果}变通：某学院有m个学生参加南湖春游，休息时喝汽水。南湖商家公告：买1瓶汽水定价1.40元，喝1瓶汽水（瓶不带走）1元。为节约资源，规定3个空瓶可换回1瓶汽水，或20个空瓶可换回7瓶汽水。（3）为方面顾客，可先借后还。例如借1瓶汽水，还3个空瓶；或借7瓶汽水，还20个空瓶。问m个学生每人喝1瓶汽水

6、（瓶不带走），至少需多少元？输入正整数m(2

7、1，因而有以下的最省钱算法：1）把m人分为x=m/20个大组，每组20人。每组买13瓶汽水（借7瓶汽水），饮完后还20个空瓶（即相当于换回7瓶汽水还给商家），两清。2）剩下t=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()