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

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

（2014

湖南理工学院程序设计竞赛评析）

1．旅馆开关门

旅馆里有10000间房间，从1到10000编了号。第一位服务员把所有的房间门都打开了，第二位服务员把所有编号是2的倍数的房间进行“相反处理”，第三位服务员把所有编号是3的倍数的房间作“相反处理”，??， 第n(1<=n<=10000)位服务员把所有编号是n的倍数的房间作“相反处理”。问第n个服务员来过后，问共有多少张门是打开的(C)。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）

// 旅馆开关门 #include void main()

{ int j,k,n,s,a[10001];

printf(\请输入正整数n(n<=10000): \ scanf(\ // 输入n for(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(\输出结果 }

变通：求在这n个服务员中，哪一个服务员处理后门开的最少？

// 旅馆开关门 #include void main()

{ int j,k,n,s,km,min,a[10001];

printf(\请输入正整数n(n<=10000): \ scanf(\ // 输入n for(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

printf(\输出结果 }

请输入正整数n(n<=10000): 2014 82,3703

在2014个服务员中，第82个服务员处理后门开的最少：3703扇门打开！

思考：求在这n个服务员中，哪一个服务员处理后的开门数最接近某一指定整数m（例如2014）？

2．喝汽水

有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有1<=n<1012) 个空汽水瓶，最多可以换多少瓶（max）汽水喝？

解：设借m瓶，还空瓶至少为3m个，则有 n+m≥3m m≤n/2 max=[n/2]

n为偶数时取其一半；n为奇数时取其一半取整。 // 喝汽水

#include void main() { long n;

printf(\请输入正整数n: \

scanf(\ // 输入n printf(\输出结果 }

变通：

某学院有m个学生参加南湖春游，休息时喝汽水。南湖商家公告： 买1瓶汽水定价1.40元，喝1瓶汽水（瓶不带走）1元。 为节约资源，规定3个空瓶可换回1瓶汽水，或20个空瓶可换回7瓶汽水。 （3） 为方面顾客，可先借后还。例如借1瓶汽水，还3个空瓶；或借7瓶汽水，还20个空瓶。

问m个学生每人喝1瓶汽水（瓶不带走），至少需多少元？

输入正整数m(2

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.91<0.93<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()

{ long m,t,x,y;

printf(\请输入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人，每人花1元喝1瓶

printf(\喝%ld瓶汽水，需%.2f元。\\n\}

该算法有输入，即输入人数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（可达101位）能否被17整除：模拟整数的除法作！

// 判断长整数n（可达101位）能否被17整除 #include #include void main()

{ int a,c,k,m,d[101]; char n[101];

scanf(\以字符串方式输入长整数 for(m=0,k=0;n[k]!='\\0';k++)

{ m++; // m统计输入的整数n的位数 d[k]=n[k]-48; // 把数字字符变为数值 }

c=d[0]; // c为余数 for(k=1;k<=m-1;k++)

{a=c*10+d[k];c=a;} // a为模拟整除的被除数 if(c==0) printf(\输出结果 else printf(\ }

变通： 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(\

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\}

思考：对指定的正整数p，如何寻求最小的01串积？

4．解不等式

设n为正整数，解不等式

1?1/21?1/2?1/31?1/2?1/3?1/41?1/2??1/na?1??????b1?1/21?1/2?1/31?1/2?1/3?1/41?1/2??1/n（分母中各项符号“+”、“-”相间）

输入正整数a,b(1

样例输入 样例输出 3 8 2 3

解：上下限一般为键盘输入的a,b。

分两段求和：应用条件s #include void main() { long c,d,i;

double a,b,t,ts,s;

printf(\请输入a,b: \ scanf(\ i=0;t=ts=s=0; while(s

t=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(s

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(\}

测试输入 测试输出

10 1000 1000 2013 1000000 10000000

附： VFP程序清单 input \input \i=0 t=0 ts=0 s=0

do while s

ts=ts-1/i else

ts=ts+1/i endif s=s+t/ts enddo c=i

do while s

ts=ts-1/i else

ts=ts+1/i endif s=s+t/ts enddo d=i-1 ? c,d return

变通：分数不等式

试解以下关于正整数n的不等式

m?1?5 149 150 268 65024 542331 111111???????23456n

其中m为从键盘输入的正整数，式中符号为二个“+”号后一个“-”号，

即分母能被3整除时符号为“-”。

1. 枚举设计要点

式中出现减运算，导致不等式的解可能分段。 为叙述方便，记

s(n)?1?111111???????23456n

（1） 设置条件循环，每三项一组（包含二正一负）累加求和：

s=s+1.0/k+1.0/(k+1)-1.0/(k+2); (k=1,4,?)

若累加到某一组时s>m时退出循环，d=k+1, 可得区间解：n≥d. 因s(d+1)>m，显然s(d)>m； 而n=d+2时1.0/(n+3)为“+”，可得s(d+2)>m; 以后各项中，“-”项小于其前面的“+”项，可知对于n>d+2有s(n)>m成立。

（2）在n

因而有必要回过头来，在n=1——d中一项项求和，得个别离散解。这一步不能省，否则出现遗解。

2. 枚举描述

// 解不等式：m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n #include void main()

{ long d,m,k; double s;

printf(\请输入m: \ k=-2;s=0; while(s<=m)

{ k=k+3;s=s+1.0/k+1.0/(k+1)-1.0/(k+2); }

d=k+1; // 可确定区间解n≥d for(s=0,k=1;k<=d-1;k++)

{ if(k%3>0) s=s+1.0/k; // 逐项累加求和 else s=s-1.0/k; if(s>m)

printf(\逐个输出离散解 }

printf(\最后输出区间解 }

3. 算法测试与思考

请输入m: 4

n=10151, n=10153, n>=10154

注意：要特别注意，不要把前面的离散解遗失。

思考：如果把后一个离散解写入区间解中？能否简化逐项求和找出离散解？

4. 枚举改进

(1) 每三项一组（包含二正一负）累加求和： s=s+1.0/k+1.0/(k+1)-1.0/(k+2); (k=1,4,?)

若累加到某一组时s>m时退出循环，d=k+1, 可得区间解：n≥d.

此时，s(d-1)有可能大于m.

为得到s(d-1),在原s(d+1)基础上实施-1.0/d+1.0/(d+1)得s(d-1): 若s(d-1)>m,合并得区间解：n≥d-1； 若s(d-1)

（3） 当s(d-1)>m时，s(d-3)还有可能大于m.

因而在上s(d-1)的基础上实施s+1.0/(d-2)-1.0/(d-1),得s(d-3): 若s(d-3)>m, 得一个离散解：n＝d-3； 若s(d-3)

// 解不等式：m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n #include void main()

{ long d,k,t,m; double s;

printf(\请输入m: \ k=-2;s=0; while(s<=m)

{ k=k+3;s=s+1.0/k+1.0/(k+1)-1.0/(k+2); }

d=k+1; // 可确定区间解n≥d s=s-1.0/d+1.0/(d+1); // 得s(d-1) if(s>m) t=d-1;

else t=d; // 得区间解n≥t s=s+1.0/(d-2)-1.0/(d-1); // 得s(d-3)

if(s>m) printf(\输出一个离散解 printf(\≥%ld \\n\输出区间解 }

（5） 算法测试与分析

请输入m: 7

n=82273511, n≥82273513

原枚举设计与改进后的枚举设计的时间复杂度都是O(n)，深入分析可知改进后枚举所需时间只有原枚举时间的1/4。

5．拆分为连续正整数之和

一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8

请编写程序，根据输入的任何一个正整数n，找出符合这种要求的所有连续正整数序列的个数C。

如：对于15，其输出结果是3：对于16，其输出结果是：0。

设计1：基本设计

定义变量s求和，设计i（1——(n-1)/2）循环作为连续求和的起始项，j

（1——(n+1)/2）循环作为连续求和的累加项。

每加一项后检验：若s=n，则统计并输出一个连续序列“i?j”后退出求和的j循环。若不等，则继续求和。

// 基本设计程序1 #include void main()

{ long c,i,j,n,s;

printf(\请输入和数n：\ scanf(\ c=0;

for(i=1;i<=(n-1)/2;i++) {s=0;

for(j=i;j<=(n+1)/2;j++) {s+=j; if(s==n)

{c++;printf(\ } }

printf(\共有以上%d个解。\\n\输出拆分种数c }

2. 改进求和设计

在以上基本设计基础上改进： 每加一项后检验是否出现s≥n： 若未出现，所求和否定不足n，则继续求和；

若出现，所求和已达到或超过n，则后退出求和的j循环。退出之前还需进一步检验是否成立s=n,若有s=n则统计并输出一个连续序列“i?j”解。

这一改进，避免了当“和已达到或超过n”情形下“继续求和”的无效操作。

// 改进设计程序2 #include void main()

{ long c,i,j,n,s;

printf(\请输入和数n：\ scanf(\ c=0;

for(i=1;i<=(n-1)/2;i++) {s=0;

for(j=i;j<=(n+1)/2;j++) {s+=j;

if(s>=n) {if(s==n)

{c++;printf(\ break;

} } }

printf(\共有以上%d个解。\\n\输出拆分种数c }

3. 优化设计

设满足题意的连续正整数的个数最大为t，由 1+2+?+t=t(t+1)/2=n

显然有t≤sqrt(2*n)，可取t=sqrt(2*n)。 同时设起始数为m的连续k项之和为n，即有

k(2m?k?1)m?(m?1)??(m?k?1)??n2

解出m得

2n?k?1km?2

建立关于连续正整数个数k（2——t）循环，在循环中检验：

如果2n不能被k整除，或2n/k-k+1不能被2整除，则返回；否则得整数m=(2n/k+1-k)/2，即为一个解：m+?+（m+k-1）。

// 优化设计程序3 #include #include void main()

{ long c,k,m,n,t;

printf(\请输入和数n：\ scanf(\ t=sqrt(2*n); c=0;

for(k=2;k<=t;k++)

{if((2*n)%k>0 || (2*n/k+1-k)%2>0) continue; m=(2*n/k+1-k)/2; c++;

printf(\ }

printf(\共有以上%d个解。\\n\输出种数c }

数据测试：

请输入和数n：2015 1: 1007+...+1008 2: 401+...+405 3: 197+...+206 4: 149+...+161

5: 65+...+90 6: 50+...+80 7: 2+...+63

共有以上7个解。

以上3个程序的时间复杂度分析： 程序1为O(n^2)。

程序2的j循环平均值估值为n^(1/2)，因而其时间复杂度为O(n^(3/2))。 程序3的循环次数t为n^(1/2)，因而其时间复杂度为O(n^(1/2))。

变通：把“连续”去掉！

本节所探讨的整数拆分与上一章的整数划分都是把一个整数（和数）分解为若干个数（零数）之和，所不同的是：整数划分允许零数重复，而拆分不允许零数重复。整数划分未指定零数的范围（默认所有不大于和数的正整数），而本节探讨的整数拆分需指定零数的范围。

（1） 问题提出

给定正整数s（简称为和数），把s折分成为连续整数1—m（m≤s）（简称为零数或部分）之和，拆分式中不允许零数重复，且不记零数的次序。

例如，把s=9折分成为连续整数1—5的拆分式为： 9= 4+ 5；9= 1+ 3+ 5；9= 2+ 3+ 4。共3个。

输入正整数s,m（m≤s）,试求s共有多少个不同的拆分式？并展示出s的所有这些拆分式。

递归算法设计要点

我们在以上实现组合的基础上求解拆分式。

注意到拆分与式中各零数的排列顺序无关，我们考虑从连续整数1—m这m个数中取w（w

对于给定的和数s与最大零数m，首先计算拆分式中零数的最少个数wmin与零数的最多个数wmax，显然，拆分式中零数的个数w取值在区间[wmin，wmax]中。

建立组合递归函数c(k)，得到从1—m这m个数中取w(wmin≤w≤wmax)个数的所有组合{a(1),?,a(w)}，当这w个数之和a(1)+?+a(w)＝s时，输出s的一个拆分式，并用n统计拆分式的个数。

w在区间[wmin，wmax]中全部取完，则s的所有拆分式全部找到。 （3） 递归设计描述 #include void main()

// 和数s,零数取自1-m #include

int k,w,n,m,s,a[100]; void main()

{ int i,h,wmin,wmax; int c(int k);

printf(\请输入和数，最大零数：\ scanf(\

for(h=0,i=1;i<=m;i++) { h=h+i;

if(h>s) {wmax=i-1;break;} }

if(i>m) // 输入的最大零数太小，程序返回 { printf(\输入的最大零数太小！\\n\

for(h=0,i=m;i>=1;i--) { h=h+i;

if(h>s) {wmin=m-i;break;} }

for(w=wmin;w<=wmax;w++) // 从1--m中取w个数 c(1);

printf(\输出拆分种数n }

// 组合递归函数c(k) int c(int k) { int i,j,t; if(k<=w) { a[0]=0;

for(i=a[k-1]+1;i<=m+k-w;i++)

{ a[k]=i; // 探索第k个数赋值i

if(k==w) // 若已到w个数时，则检测其和 { for(t=0,j=w;j>0;j--) t=t+a[j];

if(t==s) // 满足条件时输出一个拆分式

{ n++;printf(\

for(j=1;j

printf(\ printf(\ }

}

else c(k+1); // 若没到w个数,则调用 c(k+1) } }

return n; }

（4） 数据测试与分析 请输入和数，最大零数：20,8 20= 5+ 7+ 8 20= 1+ 4+ 7+ 8 20= 1+ 5+ 6+ 8 20= 2+ 3+ 7+ 8 20= 2+ 4+ 6+ 8 20= 2+ 5+ 6+ 7

20= 3+ 4+ 5+ 8 20= 3+ 4+ 6+ 7 20= 1+ 2+ 3+ 6+ 8 20= 1+ 2+ 4+ 5+ 8 20= 1+ 2+ 4+ 6+ 7 20= 1+ 3+ 4+ 5+ 7 20= 2+ 3+ 4+ 5+ 6 n=13

以上递归设计具体说明了组合这一基础工具在实现整数拆分中的应用。

6．概率计算

概率论的起源与赌博问题有关。16世纪，意大利的学者吉罗拉莫·卡尔达诺（Girolamo Cardano，1501——1576）开始研究掷骰子等赌博中的一些简单问题。17世纪中叶，当时的法国宫廷贵族里盛行着掷骰子游戏，游戏规则是玩家连续掷 4 次骰子，如果其中没有 6 点出现，玩家赢，如果出现一次 6 点，则庄家（相当于现在的赌场）赢。按照这一游戏规则，从长期来看，庄家扮演赢家的角色，而玩家大部分时间是输家，因为庄家总是要靠此为生的，因此当时人们也就接受了这种现象。那么现在让我们来计算一个概率问题。

一个骰子有n（4≤n≤8）个面，随机投掷m（1≤m≤32）次，请计算出现连续最长x个相同面的概率(C)。（结果请四舍五入到小数点后第3位。）

如何理解“最长”？

例如x=3,连续出现4个相同面肯定排队在外，但连续出现2个相同面是否包含？不清楚！

变通：

骰子有n（4≤n≤8）个面，每个面上分别刻有1，2，?，n个点。投掷两个骰子出现正面点数之和为指定整数x（x≤n）的倍数的概率(C)。（结果请四舍五入到小数点后第3位。）

// 计算概率

#include void main()

{ int i,j,k,n,x; double y;

printf(\请输入整数n,x：\ scanf(\ k=0;

for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if((i+j)%x==0) k++; y=(double)k/n/n;

printf(\

}

拓展：

骰子有n（4≤n≤6）个面，每个面上分别刻有1，2，?，n个点。投掷m（1≤m≤8）个骰子出现正面点数之和为素数的概率(C)。（结果请四舍五入到小数点后第3位。）

#include #include void main()

{ int i,j,m,n,z,p[73];long b,c,d,k,s,t; double y;

printf(\请输入整数n,m: \scanf(\

for(i=1;i<=m*n;i++) p[i]=0; p[2]=1;

for(i=3;i<=m*n;i=i+2) { t=1;z=sqrt(i);

for(j=3;j<=z;j=j+2)

if(i%j==0) {t=0;break;}

if(t==1) p[i]=1; // i为素数时p[i]=1 } b=0;

for(i=1;i<=m;i++) b=b*10+1; // 计算b为m个1是循环起点 for(k=0,t=b;t<=n*b;t++) // m个n是循环终点 { d=t;z=s=0;

for(j=1;j<=m;j++) // 循环分离m位数的各个数字 { c=d; d=d/10; if(c==0 || c>n)

{z=1;break;} // 数字超范围退出 s=s+c; // 统计数字和

}

if(z==0 && p[s]==1) k++; // 统计个数 }

y=(double)k;

for(j=1;j<=m;j++) y=y/n; printf(\}

请输入整数n,m: 7 1 0.571

注： 前7个正整数中有2，3，5，7共4个素数，占4/7=0.571 请输入整数n,m: 6 8 0.236

思考：在标注编号分别为1，2，?，n的n张牌中抽取3张，其编号之和为素数的概率。

7．分数化小数

请写出一个程序，接受一个以N/D（0<=N<=65535，0<=D<=65535）的形式输入的分数，其中N为分子，D为分母，输出它的小数形式（运算结果小数点后最多保留100位）。假如它的小数形式存在循环节，要将其用括号括起来。例如：1/3=.33333...表示为.(3)，又如41/333=.123123123...表示为.(123)。输出11/59的小数：

（1）设计要点

模拟整数除法，重复地进行求商和余数的运算，直到余数为0或出现循环节为止。

设置a为被除数，d为除数，每一个商存放在b数组中，每一个余数存放在c数组中。

试商过程：a=c[k]*10；b[k]=a/d；c[k+1]=a%d。

我们应用余数相同来判断循环节。经k+1次试商的余数分别为c[1]，c[2]，?，c[k+1]。若c[k+1]=c[j](j=1，2，?，k)，则b[1]，?，b[j-1]为循环节前的小数；循环节为b[j]，?，b[k]。

注意：程序之所以把除数d的值作为试商次数k的上限是因为循环节长度与循环节前小数长度之和总是小于d。其实，也可以不设上限，直到得出循环节才终止程序。

（2）程序实现 // 分数化小数

#include void main() {

int a,d,n,r,i,j,k,t,u,c[200],b[200];

printf(\：\ a=n/d;c[1]=n%d;

printf(\

if(a!=0) printf(\输出整数部分 printf(\

for(k=1;k<=d;k++) {

a=c[k]*10;b[k]=a/d;c[k+1]=a%d;u=0; // 实施试商

if(c[k+1]==0) // 余数为零，打印小数 {

for(i=1;i<=k;i++) printf(\ break; }

for(j=1;j<=k;j++)

{

if(c[k+1]==c[j]) // 余数相同，有循环节 {

for(t=1;t

printf(\打印循环节前的小数 printf(\ for(t=j;t<=k;t++)

printf(\打印循环节 printf(\。\

printf(\循环节共%d位。\ u=1;break; } }

if(u==1) break; } }

（3）程序运行示例 input n,d：83,92

83/92=.90(2173913043478260869565)。 循环节共22位。 input n,d：11,59

11/59=.(1864406779661016949152542372881355932203389830508474576271)。

循环节共58位。

{

if(c[k+1]==c[j]) // 余数相同，有循环节 {

for(t=1;t

printf(\打印循环节前的小数 printf(\ for(t=j;t<=k;t++)

printf(\打印循环节 printf(\。\

printf(\循环节共%d位。\ u=1;break; } }

if(u==1) break; } }

（3）程序运行示例 input n,d：83,92

83/92=.90(2173913043478260869565)。 循环节共22位。 input n,d：11,59

11/59=.(1864406779661016949152542372881355932203389830508474576271)。

循环节共58位。