湖南理工学院2011程序设计竞赛参考答案 1. 解不等式
设n为正整数，求n至少为多大，满足以下不等式 a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n
输入正整数a,输出满足不等式的n的最小值。 输入a=100 输出： 输入a=2011 输出： (1) 应用一重循环求解
// 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include
printf(\请输入a: \i=0;ts=0;s=0; while(s<=a) { i=i+1;
ts=ts+(double)1/i; // ts为各项的分母 s=s+1/ts; }
printf(\满足不等式的正整数n至少为: %ld \\n\}
输入a: 100，输出满足不等式的正整数n至少为： 566 输入a: 2011,输出满足不等式的正整数n至少为: 18622 (2) 应用二重循环求解
// 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include
printf(\请输入a: \i=0;ts=0;s=0; while(s<=a) { i=i+1;ts=0;
for(k=1;k<=i;k++)
ts=ts+(double)1/k; // ts为各项的分母 s=s+1/ts; }
printf(\满足不等式的正整数n至少为: %ld \\n\}
注：当a非常大时，程序运行时间可能比较长（时间复杂度为O(n)）。 (3) 验证程序
// 求和: s=1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include
printf(\请输入n: \ts=0;s=0;
for(i=1;i<=n;i++)
{ ts=ts+(double)1/i; // ts为各项的分母 s=s+1/ts; }
printf(\}
验证：
请输入n: 565, s=99.87895 请输入n: 566, s=100.02353 请输入n: 18621, s=2010.99170 请输入n: 18622, s=2011.08777 （4）不等式拓广
// 解不等式: 2011<1+1/(1+1/2)+...+1/(1+1/2+...+1/n)<2012 #include
ts=ts+(double)1/i; // ts为各项的分母 s=s+1/ts; } c=i; 2
while(s<=2012) { i=i+1;
ts=ts+(double)1/i; // ts为各项的分母 s=s+1/ts; }
d=i-1; // 注意：上限为i-1,而不是i
printf(\满足不等式的正整数n: %ld≤n≤%ld \\n\}
满足不等式的正整数n: 18622≤n≤18631
2. 统计
试求恰含有k个数字7且不能被7整除的7位整数的个数s。 输入k,输出s。 k=1, 输出： k=3, 输出： (1) 设计要点
设置t循环穷举所有7位数。
为了检测7位数t含有多少个数字7，每个7位整数t赋给d(以保持t不变)，然后通过7次求余先后分离出t的7个数字c，if(c==7) f++;用变量f统计数字7的个数。 例如f=2，说明整数t中恰含2个数字7。
据f==k && k%7>0检测t恰含有k个数字7且不能被7整除，s作相应统计。 （2）程序设计
// 恰含k个数字7且不能被7整除的7位整数的个数 #include
printf(\请输入整数k(1<=k<=6): \s=0;
for(t=1000000;t<=9999999;t++) // 枚举每一个7位数 { d=t; f=0;
for(j=1;j<=7;j++) { c=d; d=d/10;
if(c==7) f++; // 统计7位整数中各数字的个数 }
if(f==k && t%7>0) // 统计含k个数字7且不能被7整除数的个数 s++; }
printf(\恰含%d个数字7且不能被7整除的7位整数的个数s=%ld \\n\（3）程序运行示例
请输入整数k(1<=k<=6): 1
恰含1个数字7且不能被7整除的7位整数的个数s=2884960 请输入整数k(1<=k<=6): 3
恰含3个数字7且不能被7整除的7位整数的个数s=184316 (4) 问题拓广
// 恰含k个数字7且不能被7整除的m位整数的个数 #include
printf(\请输入整数m(2<=m<=9): \printf(\请输入整数k(1<=k for(j=2;j<=m;j++) x=x*10; // x=10^(m-1) 为最小的m位数 s=0; for(t=x;t<=10*x-1;t++) // 枚举每一个m位数 { d=t; f=0; for(j=1;j<=m;j++) { c=d; d=d/10; if(c==7) f++; // 统计m位整数中各数字的个数 } if(f==k && t%7>0) // 统计含k个数字7且不能被7整除数的个数 s++; } printf(\恰含%d个数字7且不能被7整除的%d位整数的个数s=%ld \\n\} 3. 求最值 设整数a的所有因数（含1与本身）之和为s，定义 p(a)=s/a 为整数a的因数比。 例如，6的因数有1,2,3,6,s=1+2+3+6=12，p(6)=12/6=2。 试求指定区间[x,y]中整数的因数比的最大值（精确到小数点后4位）。 输入x,y, 输出最大因数比的整数a及其因数比p(a)。 输入x=1000,y=2011, 输出： 输入x=10000,y=100000, 输出： （1）设计要点 设置a循环穷举区间[x,y]中的所有整数。可在整数范围内操作。 为了求整数a的因数和s,显然1与a是因数。设置k(2——sqrt(a))循环枚举，如果k是a的因数，则a/k也是a的因数，约定k≤a/k。 如果a=b*b，显然k=b,a/k=b，此时k=a/k。而因数b只有一个，所以此时必须从和s中减去一个b，这样处理以避免重复。 通过比较求s/a的最大值s1/a1。 （2）程序设计 // 求[x,y]范围内整数的因数比最大值 #include { long a,s,a1,s1,b,k,x,y; printf(\请输入区间x,y: \a1=1;s1=1; for(a=x;a<=y;a++) // 枚举区间内的所有整数a {s=1+a;b=(long)sqrt(a); for(k=2;k<=b;k++) // 试商寻求a的因数k if(a%k==0)s=s+k+a/k; // k与a/k是a的因数，求和 if(a==b*b) s=s-b; // 如果a=b^2,因k=a/k,需去掉重复因数b if((double)s/a>(double)s1/a1) {a1=a;s1=s; } // 比较求s/a的最大值s1/a1 } printf(\整数%ld的因数比最大：%.4f\\n\} （3）程序运行示例 求区间[x,y]中整数的因数比最大值. 请输入整数x,y:1000,2011 整数1680的因数比最大：3.5429 求区间[x,y]中整数的因数比最大值. 请输入整数x,y:10000,100000 整数55440的因数比最大：4.1870 (4) 试商求因数的范围选择 // 求[x,y]范围内整数的因数比最大值 #include { long a,s,a1,s1,b,k,x,y; printf(\请输入区间x,y: \a1=1;s1=1; for(a=x;a<=y;a++) // 枚举区间内的所有整数a {s=1+a;b=a/2; for(k=2;k<=b;k++) // 试商寻求a的因数k if(a%k==0) s=s+k; // k是a的因数，求和 if((double)s/a>(double)s1/a1) {a1=a;s1=s; } // 比较求s/a的最大值s1/a1 } printf(\整数%ld的因数比最大：%.4f\\n\} 2说明：试商从2至a/2, 其时间复杂度为O(n)；而试商从2至sqrt(a)，其时间复杂度为O(nn)。 当参数y非常大时，程序运行时间太长，可能得不到相应的解。 （5）应用双精度变量且带验证的程序设计 设置a循环穷举区间[x,y]中的所有整数。可在双精范围内操作。 为了求整数a的因数和s,显然1与a是因数。设置k(2——sqrt(a))循环枚举，如果k是a的因数，则a/k也是a的因数，约定k≤a/k。 如果a=b*b，显然k=b,a/k=b，此时k=a/k。而因数b只有一个，所以此时必须从和s中减去一个b，这样处理以避免重复。 设置max存储因数比最大值。枚举区间内每一整数a，求得其因数和s。通过s/a与max比较求取因数比最大值。 对比较所得因数比最大的整数，通过试商输出其因数和式。 // 求[x,y]范围内整数的因数比最大值(带验证) #include { double a,s,a1,s1,s2,b,k,t,x,y,max=0; printf(\求区间[x,y]中整数的因数比最大值.\printf(\请输入整数x,y:\scanf(\ for(a=x;a<=y;a++) // 枚举区间内的所有整数a