2012程序设计竞赛基础实训题详解

a6432943 贡献于2012-08-15

作者 X  创建于2012-05-14 02:39:00   修改者X  修改于2012-06-07 07:19:00字数76455

文档摘要:2012程序设计竞赛基础实训题详解
关键词:

 2012年程序设计竞赛基础实训详解 试1 不等式 对指定的正整数m,试求满足不等式 的正整数n。 输入正整数m(1 #include void main() { long c,d,i,m; double s; printf(" 请输入m: ");scanf("%ld",&m); i=0;s=0; while(s #include void main() {long a,b,n,x,y,z,w; printf(" 请输入区间[a,b]的上下限a,b: "); scanf("%ld,%ld",&a,&b); n=0; for(x=a;x<=b-3;x++) for(y=x+1;y<=b-2;y++) for(z=y+1;z<=b-1;z++) for(w=z+1;w<=b;w++) if(x*x+y*y+z*z==w*w) // 满足不定方程式时统计 n++; if(n==0) printf(" 方程在该区间内没有解。\n"); else printf(" 方程在[%ld,%ld]内有%ld组解。 \n",a,b,n); } 优化循环参数: // 求指定区间内不定方程解的组数 t22 #include #include void main() {long a,b,n,x,y,z,w; printf(" 请输入区间[a,b]的上下限a,b: "); scanf("%ld,%ld",&a,&b); n=0; for(x=a;x<=sqrt(b*b/3);x++) for(y=x+1;y<=sqrt((b*b-x*x)/2);y++) for(z=y+1;z<=sqrt(b*b-x*x-y*y);z++) for(w=z+1;w<=b;w++) if(x*x+y*y+z*z==w*w) // 满足不定方程式时统计 n++; if(n==0) printf(" 方程在该区间内没有解。\n"); else printf(" 方程在[%ld,%ld]内有%ld组解。 \n",a,b,n); } 数据测试: 请输入区间[a,b]的上下限a,b: 500,1000 方程在[500,1000]内有131组解。 请输入区间[a,b]的上下限a,b: 1000,2012 方程在[1000,2012]内有617组解。 精简循环设计: 设指定区间为[a,b],精简w循环,设置3重循环在指定区间内穷举x,y,z(xb或w不满足方程,返回;否则用n统计级数。 // 求指定区间内不定方程解的组数t23 #include #include void main() {long a,b,d,n,x,y,z,w; printf(" 请输入区间[a,b]的上下限a,b: "); scanf("%ld,%ld",&a,&b); n=0; for(x=a;x<=sqrt(b*b/3);x++) for(y=x+1;y<=sqrt((b*b-x*x)/2);y++) for(z=y+1;z<=sqrt(b*b-x*x-y*y);z++) { d=x*x+y*y+z*z; w=(int)sqrt(d); // w为x,y,z的平方和开平方 if(w>b) break; if(w*w==d) n++; // 满足方程式时统计 } if(n==0) printf(" 区间内没有勾股数组。\n"); else printf(" 方程在[%ld,%ld]内有%ld组解。 \n",a,b,n); } 变通: 可把要求统计解数变为输出某些解,或输出某些量。 实训2:求最大值 设指定区间[a,b]内的正整数x,y,z,w满足 其中a≤x void main() { long m,t,x,y;double p,mi; printf(" 请输入m:"); scanf("%ld",&m); p=1.40;mi=2*m; // 最小值mi赋初值 for(x=0;x<=m/20;x++) // 分x个大组,每组买13瓶汽水,借7瓶 { t=m-20*x; // 剩下大组外的t人 y=t/3; // 剩下t人分y个小组,每组买2瓶汽水,借1瓶 t=m-20*x-3*y; // 剩下大小组外的t人,每人花1元喝1瓶 if ((13*x+2*y)*p+t void main() { long m,x,y,z; printf(" 请输入m:"); scanf("%ld",&m); x=m/20; // 分x个大组,每组买13瓶汽水,借7瓶 y=(m-20*x)/3; // 剩下人分y个小组,每组买2瓶汽水,借1瓶 z=m-20*x-3*y; // 剩下零散z人,每人花1元喝1瓶 printf(" 喝%ld瓶汽水,需%.2f元。\n",m,(x*13+y*2)*1.40+z); } 试4 交通网 岳阳新城区的方格交通网如图1所示,其中金鹗山占据了交通网中(3,2)、(4,2)与(4,3)这三个交叉点尚未开通,另有从(2,3)至(2,4)与(6,4)至(7,4)的两条打“×”路段正在维护,禁止通行。 试统计从始点(0,0)到终点(m,n)的不同最短路线(路线中各段只能从左至右、从下至上)的条数。 图1 交通网格示意图 输入正整数m,n(7 void main() { int m,n,x,y,f[50][50]; printf(" 请输入正整数m,n: "); scanf("%d,%d",&m,&n); for(x=1;x<=m;x++) f[x][0]=1; for(y=1;y<=n;y++) f[0][y]=1; // 确定边界条件 for(x=1;x<=m;x++) for(y=1;y<=n;y++) // 实施递推得目标值f(m,n) if(x==3 && y==2 || x==4 && y==2 || x==4 && y==3) f[x][y]=0; else if(x==2 && y==4) f[x][y]=f[x-1][y]; else if(x==7 && y==4) f[x][y]=f[x][y-1]; else f[x][y]=f[x-1][y]+f[x][y-1]; printf(" 不同最短路线条数为: %d \n",f[m][n]); } 数据测试: 请输入正整数m,n: 10,8 不同最短路线条数为: 11008 请输入正整数m,n: 20,12 不同最短路线条数为: 70679215 附无障碍交通路线问题程序 // 无障碍完整交通路线问题t42 #include void main() { int k,m,n,x,y,z,f[50][50]; printf(" 请输入正整数m,n: "); scanf("%d,%d",&m,&n); for(x=1;x<=m;x++) f[x][0]=1; for(y=1;y<=n;y++) f[0][y]=1; // 确定边界条件 for(x=1;x<=m;x++) for(y=1;y<=n;y++) // 实施递推得目标值f(m,n) f[x][y]=f[x-1][y]+f[x][y-1]; printf(" 不同最短路线条数为: %d \n",f[m][n]); z=1; for(k=1;k<=m;k++) z=z*(n+k)/k; printf(" 不同最短路线组合数为: %d \n",z); } 请输入正整数m,n: 7,10 不同最短路线条数为: 19448 实训3 带中转站的交通路线 在某城区的完整方格交通网中,中转站(a,b)与终点(m,n)为交通网中的任意两交叉点,这里a,b,m,n为非负整数。 试统计从始点(0,0)经中转点(a,b)到终点(m,n)的不同最短路线(路线中各段只能靠近目标点而不能远离目标点)的条数。(注:若a>m且b>n时,从(0,0)点至中转站(a,b)这一段允许经过终点(m,n)点) 交通网格示意图 输入非负整数a,b,m,n,输出从始点(0,0)经中转站(a,b)到终点(m,n)的最短路线的条数。 测试数据: (1) a=9,b=7,m=20,n=12 (2) a=20,b=12,m=9,n=7 试5 三角网格 把一个正三角形的三边n等分,分别与各边平行连接各分点,得n-三角网格。例如n=6时6-三角网格如图2所示。 对指定正整数n,试求n-三角网格中不同三角形(大小不同或方位不同)的个数,以及所有这些三角形的面积之和(设网格中最小的单位三角形的面积为1)。 图2 6-三角网格 输入整数n(1 void main() { int k,m,n,u,p[1000]; long t,t1,t2,s1,s2,ss1,ss2; printf(" 请输入正整数n: "); scanf("%d",&n); for(t=0,k=1;k<=n;k++) {t=t+(2*k-1);p[k]=t;} t1=t2=s1=s2=ss1=ss2=0; for(k=1;k<=n;k++) // 求正立三角形个数及其面积之和 { t1=t1+k; s1=s1+t1;ss1=ss1+t1*p[n+1-k]; } m=(n%2==0?1:2); for(k=m;k<=n-1;k=k+2) // 求倒立三角形个数及其面积之和 { t2=t2+(k-1)+k;u=(n+1-k)/2; s2=s2+t2;ss2=ss2+t2*p[u]; } printf(" 三角网格中共有三角形个数为:%ld \n",s1+s2); printf(" 三角网格中所有三角形面积之和为:%ld \n",ss1+ss2); } 数据测试: 请输入正整数n: 25 三角网格中共有三角形个数为:4303 三角网格中所有三角形面积之和为:244153 请输入正整数n: 100 三角网格中共有三角形个数为:256275 三角网格中所有三角形面积之和为: 201941895 点评: 难点在于统计“倒立”三角形时,需对k分奇数与偶数两种情形分别总结规律。 另外,求三角形面积之和时,p数组的建立大大简化了计算。 试6 双码二部数 双码二部数定义:由两个不同数码组成,每个数码多于1位时相连而不分开的正整数称为双码二部数。显然,10是最小双码二部数,3335是一个4位双码二部数,477是一个3位双码二部数;而333只有一个数码,4474的数码4呈分开状态,都不是双码二部数。 对指定的正整数n,探求出n位双码二部数从小到大排序的序列中第m项。 依次输入n,m(2 #include void main() { int a,b,a0,b0,i,n,m,la,lb,la0,lb0,s; printf(" 请依次输入整数n,m: "); scanf("%d,%d",&n,&m); s=0; for(a=1;a<=9;a++) // 高部数字a从小到大枚举 { for(la=1;la<=n-2;la++) // 高部位数la分3步骤枚举 { lb=n-la; for(b=0;b<=a-1;b++) { s++; // 变量s统计个数 if(s==m) // 记录第m个数的信息 { a0=a;b0=b;la0=la;lb0=lb;} } } la=n-1;lb=1; for(b=0;b<=9;b++) { if(a!=b) // 当a=b时跳过 { s++; if(s==m){ a0=a;b0=b;la0=la;lb0=lb;} } } for(la=n-2;la>=1;la--) { lb=n-la; for(b=a+1;b<=9;b++) { s++; if(s==m){ a0=a;b0=b;la0=la;lb0=lb;} } } } if(m<=s) { printf(" %d位双码二部数从小到大第%d个数为:", n,m); for(i=1;i<=la0;i++) printf("%d",a0); for(i=1;i<=lb0;i++) printf("%d",b0); printf(" \n"); } else printf(" %d位双码二部数的个数不到%d个。\n",n,m); } 数据测试: 请依次输入整数n,m: 10,500 10位双码二部数从小到大第500个数为:7766666666 请依次输入整数n,m: 30,2012 30位双码二部数从小到大第2012个数为:888888888888888888888888000000 设计改进: // 探求n位双码二部数从小到大排序的第m个t62 #include #include void main() { int a,b,a0,b0,i,n,m,la,la0,lb0,s; printf(" 请依次输入整数n,m: "); scanf("%d,%d",&n,&m); a=1;b=0;la=1; s=1; while(lam,且n=d+1为“-”,可得n=d为一个解; 而n=d+2时1.0/(n+3)为“+”,可得s(d+2)>m;以后各项中,“-”项小于其前面的“+”项,可知对于n>d+2有s(n)>m成立。 因而有区间解:n≥d (2) 在n void main() { long d,n,m,k; double s; printf("\n 请输入m: "); scanf("%d",&m); n=-2;s=0; while(s<=m) { n=n+3;s=s+1.0/n+1.0/(n+1)-1.0/(n+2); } d=n+1; s=0; // 可确定区间解n≥d(1) for(k=1;k<=n;k++) { if(k%3>0) s=s+1.0/k; else s=s-1.0/k; if(s>m) printf(" n=%ld, ",k); // 逐个得离散解 } printf("n>=%ld \n",d); } 程序运行示例: 请输入m: 4 n=10151, n=10153, n>=10154 请输入m: 7 n=82273511, n=82273513, n>=82273514 注意:要特别注意,不要把离散解遗失。 思考:如果把后一个离散解写入区间解中? 设计要点2: 为叙述方便,记 (1) 通过循环累加,当加到s=s+1.0/n+1.0/(n+1)-1.0/(n+2);得s(n+2)>m,令d=n+1,可知:n≥d为解; (2) 此时,s(n)有可能大于m,因而在原s基础上s-1.0/d+1.0/(d+1)得s(n): 若s(n)>m,合并得区间解:n≥d-1; 若s(n)m, 得一个离散解:n=d-3; 若s(n-2) void main() { long d,n,m; double s; printf("\n 请输入m: "); scanf("%d",&m); n=-2;s=0; while(s<=m) { n=n+3;s=s+1.0/n+1.0/(n+1)-1.0/(n+2); } d=n+1; // 可确定区间解n≥d(1) s=s-1.0/d+1.0/(d+1); // 得s(n) if(s>m) printf(" n>=%ld \n",d-1); // 输出区间解 else printf(" n>=%ld \n",d); s=s+1.0/(d-2)-1.0/(d-1); // 得s(n-2) if(s>m) printf(" n=%ld \n",d-3); // 输出一个离散解 } 数据测试: 请输入m: 4 n>=10153 n=10151 请输入m: 7 n>=82273513 n=82273511 程序设计3:请判断以下程序是否正确? // 解不等式:m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n #include void main() { double n,m,s; printf("\n 请输入m: "); scanf("%lf",&m); n=0;s=3.0/2; while(s<=m) { n=n+3;s=s-1.0/n+1.0/(n+1)+1.0/(n+2); } d=n+2; printf(" n=%.0f,",d); // 得一个离散解(1) s=s-1.0/(n+3)+1.0/(n+4);d=n+4; if(s>m) printf(" n>=%.0f\n",d); // 可确定区间解n≥d(2) else printf(" n>=%.0f\n",d+1); // ?? } (1) 首先s(d)>m,n=d为一个解; 而s(d-3)<=m,n=d-2为“-”项,其绝对值大于n=d-1的“+”项,可得s(d-1)m时,以后的“-”项绝对值小于其前面的“+”项,故得区间解n≥d; 当s(n+4)<=m时,因可知s(n+5)>m;但不能确定s(n+6)>0,因而不能确定n≥d+1为区间解! 2 求最大值 设指定区间[a,b]内的正整数x,y,z,w满足 其中a≤x #include void main() {long a,b,d,s,x,y,z,w,max; printf(" 请输入区间[a,b]的上下限a,b: "); scanf("%ld,%ld",&a,&b); max=0; for(x=a;x<=sqrt(b*b/3);x++) for(y=x+1;y<=sqrt((b*b-x*x)/2);y++) for(z=y+1;z<=sqrt(b*b-x*x-y*y);z++) { d=x*x+y*y+z*z; w=(int)sqrt(d); // w为x,y,z的平方和开平方 if(w>b) break; if(w*w==d) // 满足条件时统计 { s=x+y+z+w; if(s>max) max=s; } } printf(" s的最大值为:%ld \n",max); } 数据测试: 请输入区间[a,b]的上下限a,b: 500,1000 s的最大值为:2728 请输入区间[a,b]的上下限a,b: 1000,2012 s的最大值为:5496 3 带中转站的交通路线 在某城区的完整方格交通网中,中转站(a,b)与终点(m,n)为交通网中的任意两交叉点,这里a,b,m,n为非负整数。 试统计从始点(0,0)经中转点(a,b)到终点(m,n)的不同最短路线(路线中各段只能靠近目标点而不能远离目标点)的条数。(注:若a>m且b>n时,从(0,0)点至(a,b)点这一段允许经过(m,n)点) 交通网格示意图 输入非负整数a,b,m,n,输出从始点(0,0)经(a,b)到终点(m,n)的最短路线的条数。 测试数据: (3) a=9,b=7,m=20,n=12 (4) a=20,b=12,m=9,n=7 设计要点: 如果路线中没有设指定的必经点,从始点(0,0)到终点(m,n)每一条路线共m+n段,其中横向m段,纵向n段,每一条不同路线对应从m+n个元素中取m个元素(以放置横向段)的组合数,不同路线条数为 今设置了路线中的必经点(a,b),须分以下两步统计。设从始点(0,0)到交叉点(a,b)的不同路线条数为y, 从交叉点(a,b)到终点(m,n)的不同路线条数为z。据乘法原理,从始点(0,0)经(a,b)到终点(m,n)的最短路线的条数为yz。 为了求y,分以下两种情形计算: 1) 若a=0或b=0,即必经点与起点在横向或纵向同线,y=1。 2) 若a>0且b>0,即a,b为正整数时,y=。 为了求z,分以下两种情形计算: 1) 若m=a或n=b,即必经点与终点在横向或纵向同线,z=1。 2) 若m≠a且n≠b,必经点与终点在横向相差,在纵向相差,z=。 程序设计: // 带中转站的最短路线 #include #include void main() { double a,b,c,d,m,n,k,y,z; printf(" 请输入正整数a,b: "); scanf("%lf,%lf",&a,&b); printf(" 请输入正整数m,n: "); scanf("%lf,%lf",&m,&n); y=1; if(a*b>0) for(k=1;k<=a;k++) y=y*(b+k)/k; // 计算C(a+b,a) z=1; if((m-a)*(n-b)!=0) { c=fabs(m-a);d=fabs(n-b); for(k=1;k<=c;k++) z=z*(d+k)/k; // 计算C(|m-a|+|n-b|,|m-a|) } printf(" 不同最短路线条数为: %.0f \n",y*z); } 数据测试: 请输入正整数a,b: 9,7 请输入正整数m,n: 20,12 不同最短路线条数为: 49969920 请输入正整数a,b: 20,12 请输入正整数m,n: 9,7 不同最短路线条数为: 986263125120 附无障碍无中转站的交通路线问题程序: // 无障碍完整交通路线问题 #include void main() { int k,m,n,x,y,z,f[50][50]; printf(" 请输入正整数m,n: "); scanf("%d,%d",&m,&n); for(x=1;x<=m;x++) f[x][0]=1; for(y=1;y<=n;y++) f[0][y]=1; // 确定边界条件 for(x=1;x<=m;x++) for(y=1;y<=n;y++) // 实施递推得目标值f(m,n) f[x][y]=f[x-1][y]+f[x][y-1]; printf(" 不同最短路线条数为: %d \n",f[m][n]); z=1; for(k=1;k<=m;k++) z=z*(n+k)/k; printf(" 不同最短路线组合数为: %d \n",z); } 请输入正整数m,n: 7,10 不同最短路线条数为: 19448 4 双码二部数序列 试求双码二部数升序序列的第m项。 测试数据:m=2012;m=20124 设计1: 把双码二部数升序序列的第m项换算为n位的第m0项。 注意到2位双码二部数共9*9=81个;3位双码二部数共2*9*9=2*81个;…… // 求双码二部数升序序列的第m项 #include #include void main() { int a,b,a0,b0,i,n,m,m0,la,lb,la0,lb0,s; printf(" 请依次输入整数m: "); scanf("%d",&m); s=0;n=0; while(s=1;la--) { lb=n-la; for(b=a+1;b<=9;b++) { s++; if(s==m0){ a0=a;b0=b;la0=la;lb0=lb;} } } } printf(" 双码二部数升序序列的第%d个数为:",m); for(i=1;i<=la0;i++) printf("%d",a0); for(i=1;i<=lb0;i++) printf("%d",b0); printf(" \n"); printf(" (式中%d个%d,%d个%d)\n", la0,a0,lb0,b0); } 设计2: 从n=2位开始统计 // 求双码二部数从小到大排列的第m个数 #include void main() { int a,b,a0,b0,i,m,n,p,la,la0,lb0; printf(" 请输入整数m: "); scanf("%d",&m); n=1;p=0; while(1) { n++;p++;a=1;b=0;la=1; // 默认n位第1个为1后n-1个0 if(p==m) {a0=a;b0=b;la0=la;lb0=n-la0;break;} while(la #include void main() { long j,n; double ts,s; printf(" 请输入n: "); scanf("%d",&n); j=0;ts=0;s=0; while(j #include void main() { double j,n,ts,s; printf(" 请输入n: "); scanf("%lfd",&n); j=0;ts=0;s=0; while(j #include void main() {long a,b,k; int m,n,s,x; printf(" 请确定m: "); scanf("%d",&m); a=1;n=0; while (1) {a++;s=0; // 检验a世纪 for(b=a*100-99;b<=a*100-1;b+=2) // 穷举a世纪奇数年号b {x=0; for(k=3;k<=sqrt(b);k+=2) if(b%k==0) {x=1;break;} if(x==0)break; // 当前为非合数世纪时,跳出循环进行下一个世纪的探求 s=s+x; // 年号b为合数时,x=1,s增1 } if(s==50) // s=50,即50个奇数均为合数 { n++; if(n==m) printf(" 第%d个合数世纪为:%ld 世纪。\n",n,a); } if(n==m) break; } } 4. 程序运行示例 请确定m: 10 第1个合数世纪为: 16719世纪。 第10个合数世纪为: 58453世纪。 16719 世纪尽管是最早的合数世纪,它的100个年号为[1671801,1671900]全为合数。这是一个非常漫长的年代,可谓天长地久,地老天荒! 7 分解质因数 整数分解质因数是最基本的分解。例如,90=2*3*3*5, 1960=2^3*5*7^2,前者为质因数乘积形式,后者为质因数的指数形式。 把指定区间上的所有整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数,则注明为素数。 例如, 92=2*2*23, 91(素数!)。 分解: 1671861= 5845271= (1) 设计要点 对每一个被分解的整数i,赋值给b(以保持判别运算过程中i不变),用k(从2开始递增取值)试商: 若不能整除,说明该数k不是b的因数,k增1后继续试商。 若能整除,说明该数k是b的因数,打印输出"k*";b除以k的商赋给b(b=b/k)后继续用k试商(注意,可能有多个k因数),直至不能整除,k增1后继续试商。 按上述从小至大试商确定的因数显然为质因数。 循环取值k的终值如何确定,一定程度上决定了程序的效率。终值定为i-1或i/2,无效循环太多。循环终值定为i的平方根sqrt(i)可大大精简试商次数,此时如果有大于sqrt(i)的因数(至多一个!),在试商循环结束后要注意补上,不要遗失。 如果整个试商后b的值没有任何缩减,仍为原待分解数i,说明i是素数,作素数说明标记。 (2) 质因数分解乘积形式程序设计 // 质因数分解乘积形式 #include"math.h" #include void main() {long int b,i,k,m,n,w=0; printf("[m,n]中整数分解质因数(乘积形式).\n"); printf("请输入m,n:"); scanf("%ld,%ld",&m,&n); for(i=m;i<=n;i++) // i为待分解的整数 { printf("%ld=",i); b=i;k=2; while(k<=sqrt(i)) // k为试商因数 {if(b%k==0) {b=b/k; if(b>1) {printf("%ld*",k); continue; // k为质因数,返回再试 } if(b==1) printf("%ld\n",k); } k++; } if(b>1 && b0,说明整数t中含有数字7。如果g=0,说明整数t中不含数字4。 对每一个m位整数,据f>0 && t%7>0, s1作相应统计。据f>0 && t%7>0 && g==0, s2作相应统计。 (2) 程序设计 // 统计含数字7且不能被7整除的m位整数的个数s1,其中不含数字4的个数s2 #include void main() { int c,f,g,i,j,m; long b,d,s1,s2,t; printf(" 请输入位数m (2<=m<=9): "); scanf("%d",&m); b=1; s1=0;s2=0; for(i=2;i<=m;i++) b=b*10; // 计算m位数的起点 for(t=b;t<=10*b-1;t++) // 枚举每一个m位数 { d=t; f=0;g=0; for(j=1;j<=m;j++) { c=d%10; d=d/10; if(c==7) f++; // 统计数字7的个数 if(c==4) g++; // 统计数字4的个数 } if(f>0 && t%7>0) s1++; // 统计含数字7且不能被7整除数的个数 if(f>0 && t%7>0 && g==0) s2++; // 统计其中不含数字4的个数 } printf(" s1=%ld ,s2=%ld \n",s1,s2); } (3) 程序运行示例 请输入位数m (2<=k<=9): 5 s1=32152 ,s2=20412 请输入位数m (2<=k<=9): 6 s1=366522 ,s2=208300 变通1:试统计含有数字7且能被7整除的没有重复数字的m位整数的个数s1,并指出其中最大的一个数。 为了比较是否存在重复数字,设置f数组,f[3]=2为2个数字“3”。 #include void main() { int c,e,g,i,j,m,f[10]; long b,d,s1,t; printf(" 请输入位数m (2<=m<=9): "); scanf("%d",&m); b=1; s1=0; for(i=2;i<=m;i++) b=b*10; // 计算m位数的起点 for(t=b;t<=10*b-1;t++) // 枚举每一个m位数 { d=t; for(j=0;j<=9;j++) f[j]=0; // 数组清零 for(j=1;j<=m;j++) { c=d%10; d=d/10; f[c]++; // 统计数字c的个数 } for(g=0,j=0;j<=9;j++) if(f[j]>1) g=1; // 存在重复数字标注g=1 if(f[7]>0 && t%7==0 && g==0) {s1++; e=t;} // 统计个数,并把满足条件的数赋值给e } printf(" s1=%ld ,e=%d \n",s1,e); } 请输入位数m (2<=m<=9): 5 s1=1978 ,e=98763 请输入位数m (2<=m<=9): 6 s1=11704 ,e=987651 变通2:试统计恰含一个数字7与2个数字4且能被7整除的m(m>3)位整数的个数s1,并指出其中从小到大排序的第n个数。 #include void main() { int c,e,i,j,m,n,f[10]; long b,d,s1,t; printf(" 请输入m,n: "); scanf("%d,%d",&m,&n); b=1; s1=0; for(i=2;i<=m;i++) b=b*10; // 计算m位数的起点 for(t=b;t<=10*b-1;t++) // 枚举每一个m位数 { d=t; for(j=0;j<=9;j++) f[j]=0; // 数组清零 for(j=1;j<=m;j++) { c=d%10; d=d/10; f[c]++; // 统计数字c的个数 } if(f[7]==1 && f[4]==2 && t%7==0) {s1++; if(s1==n) e=t; // 统计个数,并把第n个数赋值给e } } printf(" s1=%ld ,e=%d \n",s1,e); } 请输入m,n: 6,1000 s1=4096 ,e=417242 9 真分数最值 统计分母在指定区间[a,b]的最简真分数(分子小于分母,且分子分母无公因数)共有多少个,并求其中最接近指定分数x/y的最简真分数。 输入a,b, 输出[a,b]中最简真分数的个数、指出最接近417/2011的最简真分数。 测试数据: a=10,b=99, 输出: a=100,b=999, 输出: (1)设计要点 设计求解一般情形:统计分母在指定区间[a,b]的最简真分数的个数,并求这些最简真分数的和(正整数a,b从键盘输入)。 设分数分子为i,分母为j,最简真分数的个数为n,其和为s。 在指定范围[a,b]内枚举分数的分母j:a——b; 同时对每一个分母j枚举分子i:1——j-1。 对每一分数i/j,置标志t=0,然后进行是否存在公因数的检测。 如果分子i与分母j存在大于1的公因数u,说明i/j非最简真分数,应予舍略。因为分子分母同时约去u后,分母可能不在[a,b],即使在[a,b]时前面已作了统计求和。 注意到公因数u的取值范围为[2,i],因而设置u循环在[2,i]中枚举,若满足条件 j%u==0 && i%u==0 说明分子分母存在公因数,标记t=1后退出,不予统计与求和。 否则保持原t=0,说明分子分母无公因数,用n实施迭代“n=n+1”统计个数。 为了求最接近s=x/y的最简真分数,设双精度型变量smin存储|i/j-x/y|的最小值,把分数i/j转变为double型减去s并求绝对值与smin比较,若fabs((double)i/j-s) #include void main() {int a,b,i,j,i1,j1,t,u,x,y;long n; double s,smin; printf(" 最简真分数分母在[a,b]内,请确定a,b: "); scanf("%d,%d",&a,&b); // 输入区间的上下限 printf(" 指定分数为x/y,请确定x,y: "); scanf("%d,%d",&x,&y); // 输入指定分数 n=0;s=(double)x/y;smin=10; for(j=a;j<=b;j++) // 枚举最简真分数的分母 for(i=1;i<=j-1;i++) // 枚举最简真分数的分子 { for(t=0,u=2;u<=i;u++) // 枚举因数 if(j%u==0 && i%u==0) { t=1;break;} // 分子分母有公因数,则舍去 if(t==0) { n++; // 统计最简真分数个数 if(fabs((double)i/j-s)1(k=0——9),说明d中存在有重复数字,返回。 在不存在重复数字的情形下,检测若f[0]+f[1]+f[4]=0,说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求,打印输出。 // 组成没有重复数字的7位平方数 #include #include void main() {int k,m,n,t,f[10]; long a,b,c,d,w; n=0; b=sqrt(2356789);c=sqrt(9876532); for(a=b;a<=c;a++) {d=a*a; w=d; // 确保d为平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { m=w%10;f[m]++;w=w/10;} for(t=0,k=1;k<=9;k++) if(f[k]>1) t=1; // 测试平方数是否有重复数字 if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4 {n++; printf(" %2d: ",n); printf(" %ld=%ld^2 \n",d,a); } } printf(" 共可组成%d个没有重复数字的7位平方数.\n",n); } 1: 3297856=1816^2 2: 3857296=1964^2 3: 5827396=2414^2 4: 6385729=2527^2 5: 8567329=2927^2 6: 9572836=3094^2 共可组成6个没有重复数字的7位平方数. 变通1: 用1,2,…,9这9 个数字可以组成多少个没有重复数字的9位平方数? // 组成没有重复数字的9位平方数 #include #include void main() {int k,m,n,t,f[10]; long a,b,c,d,w; n=0; b=(int)sqrt(123456789);c=(int)sqrt(987654321); for(a=b;a<=c;a++) {d=a*a; w=d; // 确保d为平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { m=w%10;f[m]++;w=w/10;} for(t=0,k=1;k<=9;k++) if(f[k]>1) t=1; // 测试平方数是否有重复数字 if(t==0 && f[0]==0) // 测试平方数中没有重复数字,也没有数字0 {n++; printf(" %2d: ",n); printf(" %ld=%ld^2 \n",d,a); } } printf(" 共可组成%d个没有重复数字的9位平方数.\n",n); } 1: 139854276=11826^2 2: 152843769=12363^2 3: 157326849=12543^2 4: 215384976=14676^2 5: 245893761=15681^2 6: 254817369=15963^2 7: 326597184=18072^2 8: 361874529=19023^2 9: 375468129=19377^2 10: 382945761=19569^2 11: 385297641=19629^2 12: 412739856=20316^2 13: 523814769=22887^2 14: 529874361=23019^2 15: 537219684=23178^2 16: 549386721=23439^2 17: 587432169=24237^2 18: 589324176=24276^2 19: 597362481=24441^2 20: 615387249=24807^2 21: 627953481=25059^2 22: 653927184=25572^2 23: 672935481=25941^2 24: 697435281=26409^2 25: 714653289=26733^2 26: 735982641=27129^2 27: 743816529=27273^2 28: 842973156=29034^2 29: 847159236=29106^2 30: 923187456=30384^2 共可组成30个没有重复数字的9位平方数. 11 构建横竖折对称方阵 试观察图所示的横竖折对称方阵的构造特点,总结归纳其构造规律,设计并输出n(奇数)阶对称方阵。 图 7阶横竖对称方阵 输出15阶、19阶横竖折对称方阵。 解: 这是一道培养与锻炼观察能力、归纳能力与设计能力的有趣案例。 设置2维数组a[n][n]存储n阶方阵的元素,数组a[n][n]就是数据结构。本案例求解算法主要是给a数组赋值与输出。一个一个元素赋值显然行不通,必须根据方阵的构造特点,归纳其构建规律,分区域给各元素赋值。 (1) 构造规律与赋值要点 观察横竖折对称方阵的构造特点,方阵横向与纵向正中有一对称轴。两对称轴所分4个小矩形区域表现为同数字横竖折递减,至4顶角元素为1。 设阶数n(奇数)从键盘输入,对称轴为m=(n+1)/2。 设置2维a数组存储方阵中元素,行号为i,列号为j,a[i][j]为第i行第j列元素。 可知主对角线(从左上至右下)有:i=j; 次对角线(从右上至左下)有:i+j=n+1。 按两条对角线把方阵分成上部、左部、右部与下部4个区,如图所示。 图 对角线分成的4个区 对角线上元素可归纳到上、下部,即上、下部区域带等号即可。 上、下部按列号j的函数m-abs(m-j)赋值: if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j) a[i][j]=m-abs(m-j); 左、右部按行号i的函数m-abs(m-i)赋值: if(i+jj || i+j>n+1 && i // 调用2个头文件 #include void main() {int i,j,m,n,a[30][30]; // 定义数据结构 printf(" 请确定方阵阶数(奇数)n: "); scanf("%d",&n); if(n%2==0) {printf(" 请输入奇数!");return;} m=(n+1)/2; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j) a[i][j]=m-abs(m-j); // 方阵上、下部元素赋值 if(i+jj || i+j>n+1 && iz。为避免重复,不妨设x>y>z。 在指定区间[a,b]上根据x,y,z的大小关系设置循环:z从a至b-2,y从z+1至b-1,x从y+1至b。 对每一组x,y,z,如果直接应用条件式 1/(x*x)+1/(y*y)=1/(z*z) 作判别,因分数计算的不可避免的误差,有可能把一些成立的倒立勾股数组解遗失,即造成遗漏。 注意到上述分数条件式作通分整理得到的下面的正整数条件式 z*z*(x*x+y*y)=x*x*y*y 程序中为防止发生解的遗漏,应用上述整数条件作判别是适宜的。 (2) 求区间内倒立勾股数程序设计 // 求指定区间内倒立勾股数组 #include #include void main() {int a,b,n; long x,y,z; printf(" 求指定区间[a,b]内倒立的勾股数组."); printf("\n 请输入区间[a,b]的上下限a,b: "); scanf("%d,%d",&a,&b); printf("\n 区间[%d,%d]中倒立的勾股数组有:\n",a,b); n=0; for(z=a;z<=b-2;z++) for(y=z+1;y<=b-1;y++) for(x=y+1;x<=b;x++) if(z*z*(x*x+y*y)==x*x*y*y) // 满足倒立勾股数条件时输出 {n++; printf(" 1/%ld^2+1/%ld^2=1/%ld^2 \n",x,y,z); } printf("共%d组勾股数.",n); } (3) 程序运行示例 区间[30,100]中倒立的勾股数组有: 1/60^2+1/45^2=1/36^2 1/80^2+1/60^2=1/48^2 1/100^2+1/75^2=1/60^2 共3组勾股数. 区间[100,200]中倒立的勾股数组有: 1/180^2+1/135^2=1/108^2 1/200^2+1/150^2=1/120^2 共2组勾股数. 13 基于素数的代数和 定义s(n)=1*3-3*5-5*7+7*9+9*11±…-25*27±…±(2n-1)*(2n+1) (一般项(2k-1)*(2k+1)的符号识别:当(2k-1)与(2k+1)中有且只有一个素数,取“+”;其余取“-”。) 1) 求s(1000)。 2) 设1<=n<=1000,当n为多大时,s(n)最大。 3) 设1<=n<=1000,当n为多大时,s(n)最小。 (1) C程序设计 // 基于素数的整数和 #include #include void main() { int t,j,n,k,k1,k2,a[3000]; long s,smax,smin; printf(" 请输入整数n: "); scanf("%d",&n); for(k=1;k<=n+1;k++) a[k]=0; for(k=2;k<=n+1;k++) {for(t=0,j=3;j<=sqrt(2*k-1);j+=2) if((2*k-1)%j==0) {t=1;break;} if(t==0) a[k]=1; // 标记第k个奇数2k-1为素数 } s=0;smax=0;smin=10000; for(k=1;k<=n;k++) {if(a[k]+a[k+1]==1) s+=(2*k-1)*(2*k+1); // 实施代数和 else s-=(2*k-1)*(2*k+1); if(s>smax){smax=s;k1=k;} // 比较求最大值smax if(sb时,由赋值f(k)=b确定为序列的第k项;然后b=b*3,即b按递推规律乘3,为后一轮比较作准备。 每计算一项f(k),通过累加实现求和:s=s+f(k)。 3. 幂序列程序实现 // 幂序列求解 #include void main() {int k,n,t,p2,p3; long a,b,s,f[100]; printf("求数列的第n项与前n项和,请输入n:"); scanf("%d",&n); a=2;b=3;s=0;p2=0;p3=0; for(k=1;k<=n;k++) { if(a10000000时结束循环,输出“未求出该方程的基本解!”而结束。 3. 程序设计 // 解 PELL方程: x^2-ny^2=1, c231 #include #include void main() {double a,m,n,x,y; printf(" 解PELL方程: x^2-ny^2=1.\n"); printf(" 请输入非平方整数 n:"); scanf("%lf",&n); m=floor(sqrt(n+1)); if(m*m==n) { printf(" n为平方数,方程无正整数解!\n"); return; } y=1; while(y<=10000000) { y++; // 设置y从1开始递增1枚举 a=n*y*y;x=floor(sqrt(a+1)); if(x*x==a+1) // 检测是否满足方程 { printf(" 方程x^2-%.0fy^2=1的基本解为:\n",n); printf(" x=%.0f, y=%.0f\n",x,y); break; } } if(y>10000000) printf(" 未求出该方程的基本解!"); } 4. 程序运行示例与说明 解PELL方程: x^2-ny^2=1. 请输入非平方整数 n:73 方程x^2-73y^2=1的基本解为: x=2281249, y=267000 为了提高求解方程的范围,数据结构设置为双精度(double)型。如果设置为整形或长整形,方程的求解范围比设置为双精度型要小。例如n=73时,设置整形或长整形就不可能求出相应方程的解。可见,数据结构的设置对程序的应用范围有着直接的影响。 对某些n,相应佩尔方程解的位数太大。例如当n=991时,相应佩尔方程的基本解达30位。此时只有通过某些专业算法(例如连分数法)才能进行求解。 16 数列中的素数 已知数列a(1)=2,a(k)=a(k-1)+k (k>1).试求该数列的前m项中的素数个数及最大素数。 输入m,输出前m项中的素数个数及最大素数。 测试数据: m=50; m=100 // 数列中的素数 #define N 30000 #include #include void main() {int m,n,k,j,t,a[N]; long s; printf(" 请输入m: "); scanf("%d",&m); a[1]=2;s=1; for(k=2;k<=m;k++) { a[k]=a[k-1]+k; for(t=0,j=2;j<=sqrt(a[k]);j++) if(a[k]%j==0) {t=1;break;} if(t==0) {s++;n=a[k];} // a[k]为素数,用s统计个数 } printf(" 前%d项中素数个数为:%ld \n",m,s); printf(" 最大素数为:%d \n",n); } 请输入m: 50 前50项中素数个数为:17 最大素数为:1129 请输入m: 100 前100项中素数个数为:32 最大素数为:5051 17 3x+1转化 在美国曾流行以下数学游戏:从任意奇数开始,反复作以下运算 (1) 若为奇数,则乘以3后加1。 (2) 若为偶数,则除以2。 最后总可以得到数1。 这一论断既不能证明是正确的,也不能举出反例说明是错误的。 这一问题称为“3x+1问题”或“Carlitz问题”。日本角谷静夫教授把这一游戏介绍到日本,又称为角谷猜想。 例如,奇数13的转化步骤为:13->40->20->10->5->16->8->4->2->1共进行9步完成. 设计程序,输入指定奇数m,输出转化为1的转化次数。 测试数据:(1) m=71 (2) m=2011 (1) 算法设计 对输入的整数m,赋给c后,设置嵌套的条件循环实施上述(1)(2)操作: 若c为奇数,则c=3*c+1. 若c为偶数,则c=c/2. 直至c=1时结束。同时用变量n统计推导的步骤数。 指定区间[a,b]内的所有整数,可求解出完成3x+1转化步骤数n最多的整数m及其完成3x+1转化的步骤数。 (2) 求整数m的转化过程的C程序设计 // 3x+1转化 #include void main() {int m,n,c; printf("input m:"); scanf("%d",&m); n=0; c=m; printf("\n %d",m); while(c!=1) {if(c%2==1) //奇数时,乘以3后加1 {c=3*c+1;n++; printf("->%d",c); } else {c=c/2;n++; // 偶数时,除以2 printf("->%d",c); } } printf("\n 共进行%d步完成.",n); } input m:71 71->214->107->322->161->484->242->121->364->182->91->274->137->412->206->103->310->155->466->233->700->350->175->526->263->790->395->1186->593-> 1780->890->445->1336->668->334->167->502->251->754->377->1132->566->283->850->425->1276->638->319->958->479->1438->719->2158->1079->3238->1619->4858->2429->7288->3644->1822->911->2734->1367->4102->2051->6154->3077->9232->4616->2308->1154->577->1732->866->433->1300->650->325->976->488->244->122->61->184->92->46->23->70->35->106->53->160->80->40->20->10->5->16->8->4->2->1 共进行102步完成. input m:2011 2011->6034->3017->9052->4526->2263->6790->3395->10186->5093->15280->7640 ->3820->1910->955->2866->1433->4300->2150->1075->3226->1613->4840->2420->1210->605->1816->908->454->227->682->341->1024->512->256->128->64->32->16->8->4->2->1 共进行42步完成. 18 分数化小数 1.问题提出 设计程序,接受一个N/D形式的分数,其中N为分子,D为分母(约定N,D<200),输出它的小数形式。如果它的小数形式存在循环节,要将其用括号括起来,并计算输出循环节的位数。 例如:1/3=.(3);3/8=.375; 45/56=.803(571428) 输出83/92的小数: 输出11/59的小数: 2.设计要点 模拟整数除法,重复地进行求商和余数的运算,直到余数为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。其实,也可以不设上限,直到得出循环节才终止程序。 3.程序实现 // 分数化小数 #include void main() { int a,d,n,r,i,j,k,t,u,c[200],b[200]; printf("input n,d:");scanf("%d,%d",&n,&d); a=n/d;c[1]=n%d; printf(" %d/%d=",n,d); if(a!=0) printf("%d",a); // 输出整数部分 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("%d",b[i]); break; } for(j=1;j<=k;j++) { if(c[k+1]==c[j]) // 余数相同,有循环节 { for(t=1;t void main() { int c,f,g,h,i,j,k; long b,d,s,t; printf(" 请输入数字3的个数k (1≤k≤6): "); scanf("%d",&k); b=1; s=0; for(i=1;i<=k+2;i++) b=b*10; // 计算k+3位数的起点 for(t=b;t<=4*b-1;t++) // 枚举首位为3的k+3位数 { d=t;f=0;g=0;h=0; for(j=1;j<=k+3;j++) { c=d%10; d=d/10; if(c==1) f++; // 统计数字1的个数 if(c==2) g++; // 统计数字2的个数 if(c==3) h++; // 统计数字3的个数 } if(f==1 && g==2 && h==k) s++; // 统计个数s } printf(" s=%ld \n",s); } (3) 程序运行示例 请输入数字3的个数k (1≤k≤6): 4 s=105 请输入数字3的个数k (1≤k≤6): 5 s=168 (4) 拓广 若需求k=100时的排列数,如何求? 1) 注意到一排k个“3”的空位共k+1个。 这k+1个选2个空位共C(k+1,2)种组合,每一空位放置1个“2”。 这k+1个选1个空位共C(k+1,1)种组合,空位中放置2个“2”。 2) 注意到一排k个“3”与2个“2”的空位共k+3个。 这k+3个选1个空位共C(k+3,1)种组合,空位中放置1个“1”。 3) 因而得不同的排列数为: (C(k+1,2)+C(k+1,1))*C(k+3,1)=(k+1)*(k+2)*(k+3)/2 // 排列数 #include void main() { int k;long s; printf(" 请输入数字3的个数k: "); scanf("%d",&k); s=(k+1)*(k+2)*(k+3)/2; printf(" s=%ld \n",s); } 请输入数字3的个数k: 100 s=530553 (5) 进一步拓广 计算由2个“1”、2个“2”、k个“3”的排列数。 20 幂积序列 设x,y为非负整数,试计算集合 的元素不大于指定整数n的个数k,并求这些元素从小到大排序的第m项f。 输入n,m, 输出k,f。 测试数据: n=10000,m=50 输出: n=10000000,m=100 输出: 解:幂积序列复杂在“积”字上,即幂积序列的项既可以是2的幂,3的幂,也可以是这双幂的乘积。 1. 枚举求解 (1)设计要点 集合元素由2的幂与3的幂及其乘积组成,设元素从小到大排序的第k项为f(k)。显然,f(1)=1,f(2)=2。 设置a循环,a从3开始递增1至n,对每一个a(赋值给j),逐次试用2试商,然后逐次试用3试商。 试商后若j>1,说明原a有2,3以外的因数,不属于该序列。 若j=1,说明原a只有2,3的因数,属于该序列,把a赋值给序列第k项。 由于实施从小到大测试赋值,所得项无疑是从小到大的序列。 当a达到指定的n,退出循环,输出指定项f(m)。 (2) 枚举程序设计 // 幂序列2^x*3^y枚举求解 #include void main() {int k,m; long a,j,n,f[1000]; printf(" 计算不大于n的项数,请指定n: "); scanf("%ld",&n); printf(" 输出序列的第m项,请指定m: "); scanf("%d",&m); f[1]=1;f[2]=2;k=2; for(a=3;a<=n;a++) { j=a; while(j%2==0) j=j/2; // 反复用2试商 while(j%3==0) j=j/3; // 反复用3试商 if(j==1) { k++;f[k]=a;} // 用a给f[k]赋值 } printf(" 幂序列中不大于%ld的项数为:%d\n",n,k); if(m<=k) printf(" 从小到大排序的第%d项为:%ld\n",m,f[m]); else printf(" 所输序号m大于序列的项数!\n"); } (3) 程序运行示例 n=10000,m=50 输出: 67, 2304 n=10000000,m=100 输出:190, 93312 2. 按指数穷举排序求解 // 按指数穷举排序求解 #include void main() {int i,j,k,m,p2,p3; double d,n,t,t2[100],t3[100],f[1000]; printf(" 计算小于n的项数,请指定n: "); scanf("%lf",&n); printf(" 输出序列的第m项,请指定m: "); scanf("%d",&m); t=1;p2=0; while(tf[j]) { d=f[i];f[i]=f[j];f[j]=d;} printf(" 幂序列中小于%.0f的项数为:%d\n",n,k); printf(" 从小到大排序的第%d项为:%.0f\n",m,f[m]); } else printf(" 所输入的m大于序列的项数!\n"); } (3)程序运行示例 计算小于n的项数,请指定n: 10000000000000 输出序列的第m项,请指定m: 600 幂序列中小于10000000000000的项数为:624 从小到大排序的第600项为:5355700839936 计算小于n的项数,请指定n: 100000000000000 输出序列的第m项,请指定m: 700 幂序列中小于100000000000000的项数为:720 从小到大排序的第700项为:61004779879896 变通:如何求从小到大排序的幂积序列前m项之和? 3. 递推算法设计 (1) 确定递推关系 为探索x+y=i时各项与x+y=i-1时各项之间的递推规律,剖析x+y的前几个值情形: x+y=0时,元素为1(初始条件); x+y=1时,元素为2*1=2,3*1=3,共2项; x+y=2时,元素有2*2=4,2*3=6,3*3=9,共3项; x+y=3时,元素有2*4=8,2*6=12,2*9=18,3*3*3=27,共4项; …… 可归纳出以下递推关系: x+y=i时,序列共i+1项,其中前i项是x+y=i-1时的所有i项分别乘2所得;最后一项为x+y=i-1时的最后一项乘3所得(即t=3^i)。 注意,对x+y=i-1的所有i项分别乘2,设为f[h]*2,必须检测是否小于n而大于0。同样,对t也必须检测是否小于n而大于0。只有小于n且大于0时才能赋值。 这里要指出,最后若干行可能不是完整的,即可能只有前若干项能递推出新项。为此设置变量u: 当一行有递推项时u=1;否则u=0。只有当u=0时停止,否则会影响序列的项数。 (2) 以n=1000为例具体说明递推的实施: f( 1)=1 i= 1: f( 2)=2 f( 3)=3 i= 2: f( 4)=4 f( 5)=6 f( 6)=9 i= 3: f( 7)=8 f( 8)=12 f( 9)=18 f(10)=27 i= 4: f(11)=16 f(12)=24 f(13)=36 f(14)=54 f(15)=81 i= 5: f(16)=32 f(17)=48 f(18)=72 f(19)=108 f(20)=162 f(21)=243 i= 6:f(22)=64 f(23)=96 f(24)=144 f(25)=216 f(26)=324 f(27)=486 f(28)=729 i= 7: f(29)=128 f(30)=192 f(31)=288 f(32)=432 f(33)=648 f(34)=972 i= 8: f(35)=256 f(36)=384 f(37)=576 f(38)=864 i= 9: f(39)=512 f(40)=768 每一列的下一个数是上一个数的2倍。而每一行的最后一数为3的幂。 当所有递推项完成后,对所有k项应用逐项比较进行从小到大排序。 排序后输出指定的第m项。 (3)递推排序程序实现 // 递推排序求解 #include void main() {int i,j,h,k,m,u,c[100]; double d,n,t,f[1000]; printf(" 计算小于n的项数,请指定n: "); scanf("%lf",&n); printf(" 输出序列的第m项,请指定m: "); scanf("%d",&m); k=1;t=1.0; i=1; c[0]=1; f[1]=1.0; while(1) { u=0; for(j=0;j<=i-1;j++) { h=c[i-1]+j; if(f[h]*20) // 第i行各项为前一行各项乘2 { k++;f[k]=f[h]*2;u=1; if(j==0) c[i]=k; // 该行的第1项的项数值赋给c(i) } else break; } t=t*3; // 最后一项为3的幂 if(t0) { k++;f[k]=t; } // 用t给f[k]赋值 if(u==0) break; i++; } for(i=1;if[j]) { d=f[i];f[i]=f[j];f[j]=d;} printf(" 幂序列中小于%f的项数为:%d\n",n,k); if(m<=k) printf(" 从小到大排序的第%d项为:%.0f\n",m,f[m]); else printf(" 所输入的m大于序列的项数!\n"); } (4)程序运行示例 计算小于n的项数,请指定n: 1000000000 输出序列的第m项,请指定m: 300 幂序列中小于1000000000的项数为:306 从小到大排序的第300项为:774840978 4. 进一步推广至3个幂积: 设x,y,z为非负整数,试计算集合 的元素不大于指定整数n的个数,并求这些元素从小到大排序的第m项。 // 3幂积按指数穷举排序求解 #include void main() {int i,j,u,k,m,p2,p3,p5; double d,n,t,t2[100],t3[100],t5[1000],f[1000]; printf(" 计算小于n的项数,请指定n: "); scanf("%lf",&n); printf(" 输出序列的第m项,请指定m: "); scanf("%d",&m); t=1;p2=0; while(tf[j]) { d=f[i];f[i]=f[j];f[j]=d;} printf(" 幂序列中小于%.0f的项数为:%d\n",n,k); if(m<=k) printf(" 从小到大排序的第%d项为:%.0f\n",m,f[m]); else printf(" 所输入的m大于序列的项数!\n"); } 计算小于n的项数,请指定n: 100000000000000 输出序列的第m项,请指定m: 1000 幂序列中小于100000000000000的项数为:1263 从小到大排序的第1000项为:10089075234375 21 构建斜折对称方阵 试观察图所示的斜折对称方阵的构造特点,总结归纳其构造规律,设计并输出n(奇数)阶斜折对称方阵。 图 7阶斜折对称方阵 输出15阶、19阶斜折对称方阵。 (1) 构造规律与赋值要点 斜折对称方阵的构造特点:两对角线上均为“0”,依两对角线把方阵分为4个区域,每一区域表现为同数字依附两对角线折叠对称,至上下左右正中元素为n/2。 同样设置2维a[n][n]数组存储方阵中元素,行号为i,列号为j,a[i][j]为第i行第j列元素。 令m=(n+1)/2, 按m把方阵分成的4个小矩形区如图所示。 图 按m分成的4个小矩形 注意到方阵的主对角线(从左上至右下)上元素为:i=j,则左上区与右下区依主对角线赋值:a[i][j]=abs(i-j); 注意到方阵的次对角线(从右上至左下)上元素为:i+j=n+1,则右上区与左下区依次对角线赋值:a[i][j]=abs(i+j-n-1); (2) 程序设计 // 斜折对称方阵 #include #include void main() {int i,j,m,n,a[30][30]; printf(" 请确定方阵阶数(奇数)n: "); scanf("%d",&n); if(n%2==0) { printf(" 请输入奇数!");return;} m=(n+1)/2; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i<=m && j<=m || i>m && j>m) a[i][j]=abs(i-j); // 方阵左上部与右下部元素赋值 if(i<=m && j>m || i>m && j<=m) a[i][j]=abs(i+j-n-1); // 方阵右上部与左下部元素赋值 } printf(" %d阶对称方阵为:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) // 输出对称方阵 printf("%3d",a[i][j]); printf("\n"); } } 运行以上两个程序,可以在欣赏各个具体的对称方阵中,感受从特例到一般的神奇。 22 n个1 整除 一个整数为n个1,它能被指定正整数p(约定为个位数字非5的奇数)整除,问n至少为多大? 输入p,输出n。 p=57, n= p=2013, n= 设计1: 模拟竖式除法 // n个1 被p 整除 #include void main() { int a,c,n,p; printf(" 请输入整数p: "); scanf("%d",&p); n=4; c=1111; // 确定初始值 while(c!=0) { a=c*10+1; c=a%p; n++; // 实施除乘竖式计算模拟 } printf(" 至少%d个1才能初被%d整除.\n",n,p); } 设计2: 余数统计法 // n个1 被2011 整除 #include void main() { int c,n,s,p; printf(" 请输入整数p: "); scanf("%d",&p); n=1; c=1; s=1; // 确定初始值 while(s!=0) { n++; c=c*10%p; // c为第n位除以p的余数 s=(s+c)%p; // 统计n个1险乎以p的余数 } printf(" 至少%d个1才能初被%d整除.\n",n,p); } 请输入整数p: 57 至少18个1才能初被57整除. 请输入整数p: 2013 至少60个1才能初被2013整除. 23 逆序乘积式 1. 案例提出 选择数字完成以下逆序乘积式: DE×FG=ED×GF 式中的每一个字母代表一个数字,不同的字母代表不同的数字。 逆序乘积式表述为:用4个不同的数字组成两个2位数,这两个2位数的乘积等于这两个2位数的逆序数的乘积。 试找出所有符合要求的逆序乘积式。 2. 求解要点 求所有逆序乘积式,要求既不重复,也不遗漏。后者通过枚举所有二位数并不难实现,关键是如何确保不重复,包括一边两个乘数交换的重复,等号两边交换的重复。为此,约定式中的4个数字中D为最小。 设置a,b(a #include void main() {int a,b,a1,b1,i,j,n,t,c[5]; printf(" 逆序式:DE*FG=ED*GF \n"); n=0; for(a=10;a<=98;a++) // 枚举二位数 for(b=a+1;b<=99;b++) { c[1]=a/10; c[2]=a%10; c[3]=b/10; c[4]=b%10; t=0; for(i=1;i<=3;i++) for(j=i+1;j<=4;j++) if(c[i]==c[j]) // 存在相同数字时返回 {t=1;break;} if(t==1) continue; a1=c[2]*10+c[1]; // 产生逆序数 b1=c[4]*10+c[3]; if(a*b==a1*b1 && c[1] #include void main() { int a,b,a1,b1,i,j,n,t,c[7]; printf(" 三位逆序乘积式:DEF*GHK=FED*KHG \n"); n=0; for(a=102;a<=987;a++) for(b=a+1;b<=999;b++) { c[1]=a/100; c[2]=(a/10)%10; c[3]=a%10; c[4]=b/100; c[5]=(b/10)%10; c[6]=b%10; a1=c[3]*100+c[2]*10+c[1]; // 产生逆序数 b1=c[6]*100+c[5]*10+c[4]; if(a*b!=a1*b1||c[1]>c[4]||c[1]>c[3]||c[1]>c[6]) continue; // 乘积不等返回 t=0; for(i=1;i<=5;i++) for(j=i+1;j<=6;j++) if(c[i]==c[j]) {t=1;break;} if(t==0) // 没有相同数字时打印结果 { n=n+1; printf(" %2d: %3d*%3d=%3d*%3d \n",n,a,b,a1,b1); } } } (3)程序运行结果。 三位逆序乘积式:DEF*GHK=FED*KHG 1: 134*862=431*268 2: 143*682=341*286 3: 314*826=413*628 24 方阵压缩 在 n*n个整数组成的n 行n列组成的 n阶方阵中,共有(n-1)*(n-1)个2*2个子方阵,定义方阵一次压缩:以每一个2*2子方阵的4个元素之和为压缩后的方阵的一个元素。 可知每一次压缩,方阵的阶数减1。经n-1次压缩后,n阶方阵变为一个整数。 例如: 2 5 1 4 6 7 17 19 1 3 2 14 18 68 (1) 求9阶行列号和方阵(方阵的每一个元素为其行号与列号之和,1≤行号≤9, 1≤列号≤9)压缩后的结果。 (2) 求8阶行列号积方阵(方阵的每一个元素为其行号与列号之积,1≤行号≤8, 1≤列号≤8)压缩后的结果。 // 方阵压缩 #include void main() { int n,i,j,k,x,y;long a[50][50]; printf(" 请确定方阵阶数n: "); scanf("%d",&n); printf(" 已知%d阶方阵为:\n",n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=i+j; // 行列号积方阵,改为i*j for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%4ld ",a[i][j]); // 输出已知矩阵 printf("\n"); } for(k=1;k<=n-1;k++) // 经n-1次压缩 for(x=1;x<=n-k;x++) for(y=1;y<=n-k;y++) a[x][y]=a[x][y]+a[x+1][y]+a[x][y+1]+a[x+1][y+1]; printf(" 方阵压缩结果为: %ld. \n",a[1][1]); } 请确定方阵阶数n: 9 已知9阶方阵为: 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 4 5 6 7 8 9 10 11 12 5 6 7 8 9 10 11 12 13 6 7 8 9 10 11 12 13 14 7 8 9 10 11 12 13 14 15 8 9 10 11 12 13 14 15 16 9 10 11 12 13 14 15 16 17 10 11 12 13 14 15 16 17 18 方阵压缩结果为: 655360. 请确定方阵阶数n: 8 已知8阶方阵为: 1 2 3 4 5 6 7 8 2 4 6 8 10 12 14 16 3 6 9 12 15 18 21 24 4 8 12 16 20 24 28 32 5 10 15 20 25 30 35 40 6 12 18 24 30 36 42 48 7 14 21 28 35 42 49 56 8 16 24 32 40 48 56 64 方阵压缩结果为: 331776. 25 没有重复数字的正整数 在p(2≤p≤16)进制中共有p个数码:0,1,…,p-1,记p进制中没有重复数字的正整数为f(p)个。 例如p=2,2进制中有0,1两个数码,2进制中没有重复数字的正整数只有1,10,即 f(2)=2。 输入p,输出f(p). 测试数据: 10 15 解: 不妨分析10进制的没有重复数字的正整数情形。 1位: 9个 2位: 9*A(9,1) ( 十位数字9个,个位数字从不同于十位数字的余下9个数码中选1个) 3位: 9*A(9,2) ( 百位数字9个,个、十位数字从不同于百位数字的余下9个数码中选2个排列) 十进制k位: 共9*A(9,k-1)个没有重复数字的正整数。(k=2,3,…,10) 一般地在p(2≤p≤10)进制中: 1位:共p-1个; k位:共(p-1)*A(p-1,k-1)个没有重复数字的正整数。(k=2,3,…,p) 统计: 程序设计: // p进制中没有重复数字的正整数统计 #include #include void main() { int k,p; double t,s; printf(" 请输入进制数p: ");scanf("%d",&p); t=1;s=1; for(k=p-1;k>=1;k--) {t=t*k; s=s+t; } printf(" 共有%.0f个没有重复数字的正整数。\n",(p-1)*s); } 请输入进制数p: 10 共有8877690个没有重复数字的正整数。 请输入进制数p: 15 共有3317652307270个没有重复数字的正整数。 26 求指定区间内连续合数最多的子区间 输入: 键盘输入区间范围c,d。 输出: 最多连续合数的个数,连续合数的起始与终止数。 例如输入 c,d:10,100 最多连续合数的个数为:7 连续合数区间为:[90,96] 测试数据: 100,10000 10,10000000 程序设计1: //求指定区间内最多有多少个连续合数 #include #include void main() { long c,d,i,j,f,t,f1,i1,max; printf(" 请输入 c,d:"); scanf("%ld,%ld",&c,&d); f=c;max=0; if(c%2==0) c++; i=c; for(i=c;i<=d;i+=2) {t=0; for(j=3;j<=sqrt(i);j+=2) // 试商判别素数 if(i%j==0) {t=1;break;} if(t==0) // t为0表明i为素数 { if(i-f>max) {max=i-f;f1=f+1;i1=i-1;} f=i; // f为i的前一个素数 } } printf(" 最多连续合数的个数为:%ld\n",max-1); printf(" 连续合数区间为:[%ld,%ld]\n",f1,i1); } 请输入 c,d:100,10000 最多连续合数的个数为:35 连续合数区间为:[9552,9586] 请输入 c,d:10000,1000000 最多连续合数的个数为:113 连续合数区间为:[492114,492226] 程序设计2: 求出区间[c,d]内的所有相邻素数对f,m,求取m-f的最大值max。 注意到本题的搜索范围较大,采用效率较高的筛法求素数是适宜的。 求素数的筛法是公元前三世纪的厄拉多塞(Eratosthenes)提出来的:对于一个大整数x,只要知道不超过sqrt(x)的所有素数p,划去所有p的倍数2p,3p,...,剩下的整数就是不超过x的全部素数。 应用筛法求素数,为了方便实施"划去"操作,设置数组。 考虑到有时待测区间[c,d]比较大,为不使数组下标超维,或把[c,d]分割为若干子区间[cs,ds],确保在子区间中操作不超维。 每一数组元素对应一个待判别的奇数,并赋初值0。如果该奇数为p的倍数则应划去,对应元素加一个划去标记,通常给该元素赋值-1。最后,打印元素值不是-1(即没有划去)的元素对应的奇数即所求素数。 在实际应用筛法的过程中,p通常不限于取不超过sqrt(x)的素数,而是适当放宽取不超过sqrt(x)的奇数(从3开始)。这样做尽管多了一些重复划去操作,但程序实现要简便些。 在指定区间[cs,ds](约定cs为奇数)上所有奇数表示为j=cs+2k,(k=0,1,...,e,这里e=(ds-cs)/2)。于是k=(j-cs)/2是奇数j在数组中的序号(下标)。如果j为奇数的倍数时,对应数组元素作划去标记,即a[(j-cs)/2]=-1。 根据cs与奇数i,确定 g=2*int(cs/(2*i))+1,使得gi接近区间下限cs,从而使划去的gi,(g+2)i,...在[cs,ds]中,减少无效操作,以提高对大区间的筛选效率。 最后,凡数组元素a[k]≠-1,对应的奇数j=cs+2k则为素数。  2) C程序设计与运行示例 // 求指定区间内最多有多少个连续合数 #include #include void main() { long c,d,cs,ds,ct,dt,f,g,i,j,k,m,max,a[11000]; int e,u,x,y; printf(" 请输入 c,d:"); scanf("%ld,%ld",&c,&d); if(d-c<=20000) {cs=c;ds=d;x=0;} else {x=(d-c)/20000;cs=c;ds=d-20000*x;} f=cs;max=0; for(y=1;y<=x+1;y++) // 把[c,d]中分x+1个子区间筛选素数 { if(cs%2==0) cs++; for(i=0;i<=10999;i++) a[i]=0; e=(ds-cs)/2;i=1; while (i<=sqrt(ds)) {i=i+2;g=2*(cs/(2*i))+1; if(g*i>ds) continue; if(g==1) g=3; j=i*g; while (j<=ds) { if(j>=cs) a[(j-cs)/2]=-1; // 筛去标记-1 j=j+2*i; } } for(u=1,k=0;k<=e;k++) { if(a[k]!=-1) { m=cs+2*k; // m即筛选所得素数 if(m-f>max) // 寻求两相邻素数间距的最大值 { max=m-f;ct=f+1;dt=cs+2*k-1;} f=m; } } cs=ds+1;ds=ds+20000; // cs与ds增长后继续探求 } printf(" 最多连续合数的个数为:%ld\n",max-1); printf(" 连续合数区间为:[%ld,%ld]\n",ct,dt); } 请输入 c,d:10,20000 最多连续合数的个数为:51 连续合数区间为:[19610,19660] 请输入 c,d:100000,2000000 最多连续合数的个数为:131 连续合数区间为:[1357202,1357332] 请输入 c,d:10,10000000 最多连续合数的个数为:153 连续合数区间为:[4652354,4652506] 请输入 c,d:1000,100000000 最多连续合数的个数为:219 连续合数区间为:[47326694,47326912] 27 完美综合运算式 以下含乘方(a^b即为a的b次幂)、加、减、乘、除的综合运算式的右边为一位非负整数f,请把数字0,1,2,...,9这10个数字中不同于数字 f 的 9个数字不能重复填入式左边的9个□中,(约定数字“1”、“0”不出现在式左边的一位数中,“0”不为首位),使得该完美综合运算式成立 □^□+□□÷□-□□□×□=f 输入整数f(0≤f≤9),输出对应的所有综合运算式。 测试数据: f=5, f=7 (1) 设计要点 所有量设置在整数范围内取值,其中a^b用a自乘b次实现。 即要求的综合运算式为 a^b+z/c-d*e=f 设置f,a,b,c,d,e循环,因式右的一位数f可取0,则f循环从0至9取值,其他一位数从2至9取值。 对每一组f,a,b,c,d,e,计算z=(d*e+f-a^b)*c。同样是枚举,这样处理,可省略z循环,同时省略z是否能被c整除,省略等式是否成立的检测。 计算z后,检测z是否为二位数。若计算所得z非二位数,则返回。 然后分别对7个整数进行数字分离,设置g数组对7个整数分离的共10个数字进行统计,g(x)即为数字x(0—9)的个数。 若某一g(x)不为1,不满足数字0,1,2,...,9这10个数字都出现一次且只出现一次,标记t=1. 若所有g(x)全为1,满足数字0,1,2,...,9这10个数字都出现一次且只出现一次,保持标记t=0, 则输出所得的完美综合运算式。 (2) 程序清单 // 把0,1,2,...,9不重复填入,□^□+□□/□-□□□*□=□ // 式左的一位数不能为0或1, 式左的二位数首位不能为0 #include #include void main() {int a,b,c,d,e,f,k,t,n,x,y,z,m[7],g[10]; n=0; for(f=0;f<=9;f++) for(a=2;a<=9;a++) for(b=2;b<=9;b++) for(c=2;c<=9;c++) for(d=102;d<=987;d++) // 实施枚举 for(e=2;e<=9;e++) { for(t=1,k=1;k<=b;k++) t=t*a; // 计算乘方a^b z=(d*e+f-t)*c; if(z<10 || z>98) continue; m[1]=a;m[2]=b;m[3]=c;m[4]=d;m[5]=e;m[6]=z; for(x=0;x<=9;x++) g[x]=0; g[f]=1; // 因f 可取0,单独给g数组赋值 for(k=1;k<=6;k++) { y=m[k]; while(y>0) { x=y%10;g[x]++; // 分离数字给g数组统计 y=y/10; } } for(t=0,x=0;x<=9;x++) if(g[x]!=1) {t=1;break;} // 检验数字0-9各出现一次 if(t==0) // 输出一个解 { n++; printf("%2d: %d^%d+%d/%d",n,a,b,z,c); printf("-%d*%d=%d \n",d,e,f); } } } (3) 运行结果 1: 4^6+72/9-513*8=0 2: 5^4+78/6-319*2=0 3: 9^3+48/6-105*7=2 4: 9^3+64/8-105*7=2 5: 2^9+78/6-130*4=5 6: 9^3+64/2-108*7=5 7: 2^9+80/5-174*3=6 8: 5^4+18/9-207*3=6 9: 9^3+50/2-187*4=6 10: 5^4+96/8-210*3=7 11: 6^3+54/9-107*2=8 12: 8^3+64/2-107*5=9 (4) 也可以按双精度型设计 对每一组f,a,b,c,d,e,计算z=(d*e+f-a^b)*c。 // 把0,1,2,...,9不重复填入,□^□+□□/□-□□□*□=□ // 式左的一位数不能为0或1, 式左的二位数首位不能为0 #include #include void main() {int c,d,e,f,k,t,n,x,y,z,m[7],g[10];double a,b; n=0; for(f=0;f<=9;f++) for(a=2;a<=9;a++) for(b=2;b<=9;b++) for(c=2;c<=9;c++) for(d=102;d<=987;d++) // 实施枚举 for(e=2;e<=9;e++) { z=(d*e+f-(int)pow(a,b))*c; if(z<10 || z>98) continue; m[1]=(int)a;m[2]=(int)b;m[3]=c;m[4]=d;m[5]=e;m[6]=z; for(x=0;x<=9;x++) g[x]=0; g[f]=1; // 因f 可取0,单独给g数组赋值 for(k=1;k<=6;k++) { y=m[k]; while(y>0) { x=y%10;g[x]++; // 分离数字给g数组统计 y=y/10; } } for(t=0,x=0;x<=9;x++) if(g[x]!=1) {t=1;break;} // 检验数字0-9各出现一次 if(t==0) // 输出一个解 { n++; printf("%2d: %.0f^%.0f+%d/%d",n,a,b,z,c); printf("-%d*%d=%d \n",d,e,f); } } } 28 构建圈号对称方阵 图 6阶与7阶圈号对称方阵 请观察图所示的6阶与7阶圈号对称方阵的构造特点,归纳其构成规律,设计并输出指定的n阶圈号对称方阵。 输出18阶、19阶圈号对称方阵。 (1) 构造特点 值得注意的是,这里的n阶,n可为奇数,也可为偶数。一个一个元素通过枚举赋值是行不通的,必须根据其构造特点,把方阵分成若干区,在各区用统一表达式赋值。 设a[i][j]存储方阵中元素,行号为i,列号为j。 可知主对角线:i=j;次对角线:i+j=n+1。 按两条对角线把方阵分成上部、左部、右部与下部4个区,如图所示。 图 对角线分成的4个区 上、下部可带等号,把对角线上的元素划归该区。 上部按行号i的函数赋值,因为同行上的元素的值相同;注意到n可为奇数,也可为偶数,赋值函数取为 (n+1)/2-i+1; 同理,下部按行号函数i-n/2赋值。 左部按列号j的函数赋值,因为同列上的元素的值相同;注意到n可为奇数,也可为偶数,赋值函数取为 (n+1)/2-j+1; 同理,右部按列号函数j-n/2赋值。 (2) 程序设计 // 圈号对称方阵 #include #include void main() {int i,j,n,a[30][30]; printf(" 请确定方阵阶数n: "); scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) {if(i+j<=n+1 && i<=j) a[i][j]=(n+1)/2-i+1; // 方阵上部元素赋值 if(i+jj) a[i][j]=(n+1)/2-j+1; // 方阵左部元素赋值 if(i+j>=n+1 && i>=j) a[i][j]=i-n/2; // 方阵下部元素赋值 if(i+j>n+1 && i #include void main() { int a,b,c,g,i,j,w,h[10]; long m,mx,n,d,t; printf(" 请输入位数: ");scanf("%d",&w); n=0;t=1;a=w/2; for(j=1;j<=w-1;j++) t=t*10; // 计算最小的w位整数t for(m=t;m<=(10*t-1);m++) // 枚举所有的w位数 { d=m;b=0; for(j=0;j<=9;j++) h[j]=0; for(j=1;j<=w;j++) {c=d%10;h[j]=c;d=d/10;} for(j=1;j<=a;j++) if(h[j]!=h[w-j+1]){b=1;break;} if(b==0) // b=0时m为回文数 { for(g=0,i=2;i<=sqrt(m);i++) if(m%i==0){g=1;break;} if(g==0) { n++; // t=0时m为回文素数,n统计 mx=m; } } } printf(" %d位回文素数共有%ld个。\n",w,n); printf(" 其中最大的回文素数为:ld\n",mx); } 请输入位数: 5 5位回文素数共有93个。 其中最大的回文素数为:98689 请输入位数: 7 7位回文素数共有668个。 其中最大的回文素数为:9989899 30 求最值 设n为正整数,,式中各项符号为二正一负。求当n为多大时,s(n)最接近指定的正整数a? 输入a, 输出s(n)最接近a的n,s(n)。 (1) 输入a=1000,输出: (2) 输入a=2012,输出: 解: 一般地求当n为多大时,s(n)最接近正整数a?其中a从键盘输入a。 // s(n)=1+1/(1+1/2)-1/(1+1/2+1/3)+...+1/(1+1/2+...+1/n) #include #include void main() { long a,n,n1; double m,ts,s,s1; printf(" 请输入a: "); scanf("%d",&a); n=0;ts=0;s=0;m=100000.0; while(s #define s 1000 void main() {int m[s],n,p2,p3,i; m[1]=p2=p3=1; // 排头p2,p3赋初值 printf("n="); scanf("%d",&n); for(i=2;i<=n;i++) if(2*m[p2]+1<3*m[p3]+1) {m[i]=2*m[p2]+1; p2++;} else {m[i]=3*m[p3]+1; if(2*m[p2]==3*m[p3]) p2++; // 为避免重复项,P2须增1 p3++;} printf("m(%d)=%5d\n",n,m[n]); } 运行程序,输入n=100, 输出 m(100)=418 输入n=500, 输出 m(500)=3351 注: 有资料对本题设计程序,省去了注释所在的程序行if(2*m[p2]==3*m[p3]) p2++;,即忽略了两队列相等的情形,因而导致数组m中出现重复项(例如出现两项31等),这与集合元素的互异性相违。 3. 递推设计 由初始条件m(1)开始,经两递推式递推得m(2),m(3);这两者比较,较小者确定为m(2),另一个为m(3)。然后由m(2)递推得m(4),m(5);m(3)逐个与m(4),m(5)比较:若m(3)大,则交换,确保m(3)最小。若出现m(3)与某一数相等,为避免重复,另一数置为一个出界的“大数”。 一般地,已得m(i)后,递推得m(2i),m(2i+1); m(i+1)与m(j)(j=i+2,i+3,…,2i+1)逐个比较:若m(i+1)>m(j),则m(i+1)与m(j)交换,确保m(i+1)最小。若出现m(i+1)=m(j),为避免重复,则置m(j)为一个出界的“大数”。 设置i(从1至n)循环,由m(1)开始递推得m(2),m(3),至推得m(n)结束。 递推求解的C程序设计: // 双关系2x+1,3x+1递推 #include void main() {int n,i,j,h,m[1500]; m[1]=1; scanf("%d",&n); for(i=1;i<=n;i++) {m[2*i]=2*m[i]+1;m[2*i+1]=3*m[i]+1; for(j=i+2;j<=2*i+1;j++) {if(m[i+1]>m[j]) // m(i+1)与m(j)比较 {h=m[j]; m[j]=m[i+1];m[i+1]=h;} // 交换,使m(i+1)最小 if(m[i+1]==m[j]) m[j]=20000+j;}} // 置m(j)为一出界大数,以避免重复 for(i=1;i<=n;i++) {printf(" %4d",m[i]); if(!(i%10)) printf("\n");} } 运行程序,依次打印出数列的前n项。 4. 穷举判别的C程序设计 设置变量i: i从2开始递增1取值,若i可由已有的项m(j)推得,即满足条件i=2*m(j)+1 或 i=3*m(j)+1,说明i是m数列中的一项,赋值给m(k)。 程序设计与运行示例: // 2x+1,3x+1穷举判别 #include void main() {int n,k,j;long i,m[1000]; scanf("%d",&n); m[1]=1;k=1;i=1; while(k #include void main() {int k,m,n,t,f[10]; double a,b,c,d,w,x,a1,d1; printf(" 请确定整数m: "); scanf("%d",&m); x=1.0; for(k=2;k<=m;k++) x=x*10; // 确定m位数的起点x n=0; b=(int)pow(x,0.5);c=pow(10*x-1,0.5); for(a=b+1;a<=c;a++) {d=a*a; w=d; // 确保d为m位平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { t=(int)fmod(w,10);f[t]=f[t]+1;w=floor(w/10);} for(t=0,k=0;k<=9;k++) if(f[k]>1) {t=1; break;} // 测试平方数是否有重复数字 if(t==0 ) // 测试平方数中没有重复数字 {n++;d1=d;a1=a;} } printf(" 共可组成%d个没有重复数字的%d位平方数.",n,m); printf(" 其中最大的为:%.0f=%.0f^2 \n",d1,a1); } 请确定整数m: 7 共可组成123个没有重复数字的7位平方数. 其中最大的为:9872164=3142^2 请确定整数m: 10 共可组成87个没有重复数字的10位平方数. 其中最大的为:9814072356=99066^2 变通: 用0,1,2,...,9能组成没有重复数字的m(1 #include void main() {int k,m,n,n1,t,max,f[10]; double a,b,c,d,w,x; max=0; for(m=2;m<=10;m++) {x=1.0; for(k=2;k<=m;k++) x=x*10; // 确定m位数的起点x n=0; b=(int)pow(x,0.5);c=pow(10*x-1,0.5); for(a=b+1;a<=c;a++) {d=a*a; w=d; // 确保d为m位平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { t=(int)fmod(w,10);f[t]=f[t]+1;w=floor(w/10);} for(t=0,k=0;k<=9;k++) if(f[k]>1) {t=1; break;} // 测试平方数是否有重复数字 if(t==0 ) n++; // 测试平方数中没有重复数字 } if(n>max) {max=n;n1=m;} } printf(" 没有重复数字的10位平方数有%d个。\n",n); printf(" 当m=%d时,没有重复数字的%d位平方数最多,有%d个。\n",n1,n1,max); } 没有重复数字的10位平方数有87个。 当m=7时,没有重复数字的7位平方数最多,有123个。 33 抽水站选址与输水管道设计 在一河流的一侧有A,B两个村,A距离河边1000米, B距离河边4000米,A与B相距6000米,如图所示. 6000 B A 1000 C(x,y) 4000 (0,0) D(x,0) x 今要在河边修一抽水站D,向A、B两村供水。已知单独向A供水管道费用为a=90元/米, 单独向B供水管道费用为b=70元/米,而同时满足A、B两村用水的大管道费用c正在调查市场价格。 试请根据c的值设计抽水站的地址D与输水管道布局,达到供水管线费用最省。 输入c, 输出D的位置与安装输水管道的最小费用(精确到整数米或元)。 测试数据: (1) c=100 (2) c=110 (3) c=120 解:设A到河岸的垂足为坐标原点(0,0),抽水站 D(x,0),管线分叉点C(x,y)。 设A、B的纵坐标为ya,yb,A、B的距离为l. 则A、B到河岸的垂足之间的距离g=sqrt(l*l-(yb-ya)*(yb-ya)) AC=ea=sqrt(x*x+(ya-y)*(ya-y)) CB=eb=sqrt((g-x)*(g-x)+(yb-y)*(yb-y)) 费用:f=c*y+90*ea+70*eb 设计x(0——g),y(0——yd)循环,其中yd为ya与yb中的较小者。 比较得f的最小值。 // 抽水站选址与输水管道设计 #include #include void main() { double c,ea,eb,f,g,l,x,y,ya,yb,yd,x1,y1,min; printf(" 请输入大管道费用c: ");scanf("%lf",&c); ya=1000;yb=4000;l=6000; g=sqrt(l*l-(yb-ya)*(yb-ya)); yd=(yb>=ya?ya:yb); // yd为ya与yb较小者 min=100000000; for(x=0;x<=g;x=x+0.5) for(y=0;y<=yd;y=y+0.5) { ea=sqrt(x*x+(ya-y)*(ya-y)); eb=sqrt((g-x)*(g-x)+(yb-y)*(yb-y)); f=c*y+90*ea+70*eb; if(f 2x+3y∈A (3)再无其他数属于A。 试求集合A中元素从小到大排列序列的第n项。 n=500, 输出: n=2012, 输出: 2. 设计要点 设置a数组存储序列各项,a(t)为序列的第t项。显然a(1)=1,a(2)=2。 设t为项数,在t void main() { int n,t,k,i,h,j,a[30000]; printf("请输入n: "); scanf("%d",&n); a[1]=1;a[2]=2; t=2;k=2; while(t1) z[x][--y]=++m; } 奇数层另赋值描述: x=i;y=1;m++; z[x][y]=m; while(y1) z[--x][y]=++m; 赋值完成,用二重循环打印输出所选择的折叠方阵。 (2) 折叠方阵程序设计 //折叠方阵 #include void main() { int i,m,n,x,y,z[20][20]; printf(" n阶折叠方阵,请确定n:"); scanf("%d",&n); m=1;z[1][1]=m; // m与数组z赋初值 for(i=2;i<=n;i++) //方阵n-1层赋值 if(i%2==0) { x=1;y=i;m++; //偶数层赋值 z[x][y]=m; while(x1) z[x][--y]=++m; } else //奇数层赋值 { x=i;y=1;m++; z[x][y]=m; while(y1) z[--x][y]=++m; } printf(" %d阶折叠方阵:\n",n); for(x=1;x<=n;x++) // 打印n阶折叠方阵 { for(y=1;y<=n;y++) printf("%4d",z[x][y]); printf("\n"); } } (3) 程序变通 如果以上两种方阵起始不是1,而是某一指定的整数a,只须把变量m赋初值1改成赋初值a,即m=a即可。 试把输出方阵的语句修改为:printf("%4d",z[y][x]); 即x,y互换,请观察输出的折叠方阵有什么改变? 试把输出方阵的语句修改为:printf("%4d",n*n+1-z[x][y]); 观察输出的折叠方阵有什么改变? 36 n位超级素数 定义n位超级素数: (1) n(n>1)位整数x为素数; (2) 从高位开始,去掉1位后为n-1位素数;去掉2位后为n-2位素数;…;去掉n-1位后为1位素数。 测试数据: n=5 n=7 设计1: // 枚举求指定n位超级素数 #include void main() {int i,n; long c,d,e,f,k,s,t; int p(long f); printf(" 请确定n(n>1): "); scanf("%d",&n); for(c=1,i=1;i<=n-1;i++) c=c*10; s=0; for(f=c+1;f<=10*c-1;f=f+2) { if(p(f)==0 || !(f%10==3 || f%10==7)) continue; for(t=1,d=f/10,i=1;i<=n-2;i++) { if(d%10==0) t=0; d=d/10; } if(t==0) continue; for(t=1,k=10,i=1;i<=n-2;i++) {k=k*10;t=t*p(f%k);} if(t==0) continue; s++;e=f; // 统计并赋值 } printf(" 共%ld个%d位超级素数.\n",s,n); printf(" 其中最大数为%ld.\n",e); } #include int p(long k) {int j,h,z; z=0; if(k==2) z=1; if(k>=3 && k%2==1) {for(h=0,j=3;j<=sqrt(k);j+=2) if(k%j==0) {h=1;break;} if(h==0) z=1; } return z; } 请确定n(n>1): 5 共192个5位超级素数. 其中最大数为99643. 请确定n(n>1): 7 共429个7位超级素数. 其中最大数为9986113. 设计2: // 递推求指定n位超级素数 #include void main() {int g,i,j,k,m,n; long d,f,s,a[20000],b[20000],e[20]; int p(long f); printf(" 请确定n(n>1): "); scanf("%d",&n); g=2;s=0; a[1]=3;a[2]=7;e[1]=1; for(k=2;k<=n;k++) { e[k]=e[k-1]*10;m=0; for(j=1;j<=9;j++) for(i=1;i<=g;i++) { f=j*e[k]+a[i]; if(p(f)==1) { m++;b[m]=f; if(k==n) {s++;d=f; } // 统计并超级素数赋值 } } g=m; for(i=1;i<=g;i++) a[i]=b[i]; } printf(" 共%ld个%d位超级素数.\n",s,n); printf(" 其中最大数为%ld.\n",d); } #include int p(long k) {int j,h,z; z=0; if(k==2) z=1; if(k>=3 && k%2==1) {for(h=0,j=3;j<=sqrt(k);j+=2) if(k%j==0) {h=1;break;} if(h==0) z=1; } return z; } 请确定n(n>1): 6 共326个6位超级素数,最大数为998443 37 串立方体统计 一个长,宽,高分别为给定正整数a,b,c的长方体是由a*b*c个边长为1的小立方体组合而成,试求长方体的一条对角线穿过的小立方体的个数。(正整数a,b,c值从键盘输入)。 输入正整数a,b,c, 输出一条对角线穿过的小立方体的个数。 测试数据: (1) 91,72,37 (2) 201,101,73 (1) 串正方形 一个长,宽分别为正整数a,b的长方形是由a*b个边长为1的小正方形组合而成,试求长方形的一条对角线穿过的小正方形的个数。(正整数a,b从键盘输入)。 1) 算法设计 应用对角线微量增长是否穿过小正方形来统计小正方形的个数。 设对角线长为le,长、宽两方向上变化比例分别为ca=a/le,cb=b/le。同时设置a2,b2分别为长、宽两方向上的量,a1,b1分别为长、宽两方向上已统计过的整数。 对角线长从0开始,以微量0.0001增长。每一个微量增长点,凡长a或宽b方向量达到或超过一个新的整数,即接触或进入一个新的小正方形,则统计量n增1。 初始值:当le=0(a1=b1=c1=0),n=1(因已进入到第一个小正方形)。 2) 串正方形 C程序设计 // 串正方形 #include #include void main() {int n,t; double a,b,a1,b1,a2,b2,x,le,ca,cb; printf("请输入长方形的长,宽:"); scanf("%lf,%lf",&a,&b); le=sqrt(a*a+b*b); // 计算对角线长 ca=a/le;cb=b/le; // 计算长、宽两个方向的斜率 a1=0;b1=0;n=1; for(x=0;x=a1+1) {t=1;a1=a2;} // 长a方向增量达1,标识符t=1 if(b2>=b1+1) {t=1;b1=b2;} // 宽b方向类似处理 if(t==1) n++; // a,b方向只要有一个增量达1,统计量n增1 } printf("对角线串正方形个数为: %d个.\n",n); } 运行程序,输入a=42,b=27,输出 对角线串正方形个数为: 66个。 (2) 串立方体 一个长,宽,高分别为给定正整数a,b,c的长方体是由a*b*c个边长为1的小立方体组合而成,试求长方体的一条对角线穿过的小立方体的个数。 (正整数a,b,c值从键盘输入)。 1) 算法设计 应用对角线微量增长是否穿过小立方体统计小立方体的个数。 设对角线长为le,长宽高三方向上变化比例分别为ca=a/le,cb=b/le,cc=c/le。同时设置a2,b2,c2分别为长宽高三方向上的量,a1,b1,c1分别为长宽高三方向上已统计过的整数。 对角线长从0开始,以微量0.0001增长。每一个微量增长点,凡长a或宽b或高c方向量达到或超过一个新的整数,即接触或进入一个新的小立方体,则统计量n增1。 初始值:当le=0(a1=b1=c1=0),n=1(因已进入到第一个小立方体)。 2) 串立方体 C程序设计 // 串立方体 #include #include void main() { int n,t; double a,b,c,a1,b1,c1,a2,b2,c2,x,le,ca,cb,cc; printf("请输入长方体的长,宽,高:"); scanf("%lf,%lf,%lf",&a,&b,&c); le=sqrt(a*a+b*b+c*c); // 计算对角线长 ca=a/le;cb=b/le;cc=c/le; // 计算长、宽、高三个方向的斜率 a1=0;b1=0;c1=0;n=1; for(x=0;x=a1+1) {t=1;a1=a2;} // 长a方向增量达1,标识符t=1 if(b2>=b1+1) {t=1;b1=b2;} if(c2>=c1+1) {t=1;c1=c2;} // 宽b,高c方向类似处理 if(t==1) n++; // a,b,c方向只要有一个增量达1,统计量n增1 } printf("对角线串立方体个数为:"); printf("%d个.\n",n); } 程序运行示例: 请输入长方体的长,宽,高:91,72,37 对角线串立方体个数为:198个. 请输入长方体的长,宽,高:201,101,73 对角线串立方体个数为:373个. 38 整数的因数比 设整数a的小于其本身的因数之和为s,定义 p(a)=s/a 为整数a的因数比。 事实上,a为完全数时,p(a)=1。例如,p(6)=1。 有些资料还介绍了因数之和为数本身2倍的整数,例如p(120)=2。 试求指定区间[1,2011]中整数的因数比的最大值。 设计要点: 一般地,求指定区间[x,y]中整数的因数比最大值。 为了求整数a的因数和s,显然1是因数。设置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 #include void main() { double a,s,a1,s1,b,k,t,x,y,max=0; printf(" 求区间[x,y]中整数的因数比最大值."); printf(" 请输入整数x,y:"); scanf("%lf,%lf",&x,&y); for(a=x;a<=y;a++) // 枚举区间内的所有整数a {s=1;b=sqrt(a); for(k=2;k<=b;k++) // 试商寻求a的因数k if(fmod(a,k)==0) s=s+k+a/k; // k与a/k是a的因数,求和 if(a==b*b) s=s-b; // 如果a=b^2,去掉重复因数b t=s/a; if(max #include void main() { double l,w,r,a,v,s,x,y,x1,x2,y1,y2; printf(" 请确定球台边框(l,w): "); scanf("%lf,%lf",&l,&w); printf(" 请确定球心开始位置(x,y): "); scanf("%lf,%lf",&x,&y); printf(" 请确定球半径r: "); scanf("%lf",&r); printf(" 请确定射击角度a: "); scanf("%lf",&a); printf(" 请确定射击速度v: "); scanf("%lf",&v); printf(" 请确定时间s: "); scanf("%lf",&s); x1=r;x2=l-r;y1=r;y2=w-r; x=x+v*s*cos(a*3.1415926/180); y=y+v*s*sin(a*3.1415926/180); while(xx2 || yy2) {if(x>x2) x=2*x2-x; if(xy2) y=2*y2-y; if(y #include void main() { double l,w,r,a,b,v,s,x,y,x1,x2,y1,y2; printf(" 请确定球台边框(l,w): "); scanf("%lf,%lf",&l,&w); printf(" 请确定球心开始位置(x,y): "); scanf("%lf,%lf",&x,&y); printf(" 请确定球半径r: "); scanf("%lf",&r); printf(" 请确定射击角度b: "); scanf("%lf",&b); printf(" 请确定射击初速度v: "); scanf("%lf",&v); printf(" 请确定匀减速的加速度a: "); scanf("%lf",&a); x1=r;x2=l-r;y1=r;y2=w-r; s= v*v/2/a; x=x+s*cos(b*3.1415926/180); y=y+s*sin(b*3.1415926/180); while(xx2 || yy2) {if(x>x2) x=2*x2-x; if(xy2) y=2*y2-y; if(y1),求出其平方数s; 计算a的位数w,同时计算b=10^w,a的平方s的尾部c=s%b; 比较a,c,若a=c则输出守形数。 (2) 程序实现 // 求[x,y]内的守形数 #include void main() {long int a,b,c,k,s,x,y; printf(" 求区间[x,y]中的守形数."); printf(" 请输入整数x,y:"); scanf("%ld,%ld",&x,&y); for(a=x;a<=y;a++) { s=a*a; // 计算a的平方数s b=1;k=a; while(k>0) {b=b*10;k=k/10;} c=s%b; // c为a的平方数s的尾部 if(a==c) printf("%ld^2=%ld \n",a,s); } } (3) 程序运行结果 求区间[x,y]中的守形数.请输入整数x,y:10,10000 25^2=625 76^2=5776 376^2=141376 625^2=390625 9376^2=87909376 2. 探索n位守形数 (1) 求解要点 为了求更多位数的守形数,可应用守形数的性质:一个m位守形数的尾部m-1位数也是一个守形数。 道理很简单,a是一个m位数,a的平方数尾部的m-1位仅由a的尾部m-1位决定而与a的其他位无关。 实施易知一位守形数有三个:1,5,6。则二位守形数的个位数字只可能是1,5,6这三个数字。根据这一思路,我们可应用递推求出多位守形数。 (2) 程序设计 // 求n位守形数 #include void main() { int n,d,k,j,i,t,m,w,z,u,v,a[500],b[500],c[500]; printf("n=");scanf("%d",&n); for(d=1;d<=9;d++) {for(k=1;k<=500;k++) {a[k]=0;b[k]=0;c[k]=0;} a[1]=d; // 给个位数赋值 for(k=2;k<=n;k++) {for(j=0;j<=9;j++) {a[k]=j;v=0; for(i=1;i<=k;i++) c[i]=0; // 探索a(k) for(i=1;i<=k;i++) {for(z=0,t=1;t<=k;t++) {u=a[i]*a[t]+z;z=u/10; b[i+t-1]=u%10; // 计算平方 } for(w=0,m=i;m<=k;m++) {u=c[m]+b[m]+w; w=u/10;c[m]=u%10; } } for(i=1;i<=k;i++) if(a[i]!=c[i]) v=1; if(v==0) break; } } if(v==0 && a[n]!=0) // 输出n位守形数结果 {printf(" %d结尾的%d守形数: ",a[1],n); for(k=n;k>=1;k--) printf("%d",a[k]); printf("\n"); } } } (3) 程序运行示例 运行程序, 输入n=30,得30位守形数 5结尾的30守形数: 106619977392256259918212890625 6结尾的30守形数: 893380022607743740081787109376 41 奇数序列运算式 在由指定相连奇数组成的序列的每相邻两项中插入运算符号: 若相邻两项都是合数,则两项中插入“-”号; 若相邻两项一项合数一项素数,则两项中插入“+”号; 若相邻两项都是素数,则两项中插入乘号“*”号; 输入奇数b,c(b #include void main() {int b,c,f,m,n,k,i,j,a[N]; long t,s; printf(" 请输入首尾奇数b,c(b #include void main() {int i,j,m,n,t,s,z,a[20][20]; printf(" 输入方阵阶n:"); scanf("%d",&n); printf(" 方阵有以下两种旋转方式:\n"); printf(" 1: 逆时针转 2: 顺时针转\n"); printf(" 选择旋转方式代码: "); scanf("%d",&z); m=n/2;t=0; a[m+1][m+1]=n*n; for(i=1;i<=m;i++) // 按规律给a数组赋值 {s=n+1-2*i; for(j=i;j<=n-i;j++) {a[i][j]=t+1-i+j; a[j][n+1-i]=t+s+1+j-i; a[n+1-i][j+1]=t+3*s-j+i; a[j+1][i]=t+4*s-j+i; } t=t+4*s; } printf(" 所求旋转方阵为:"); for(i=1;i<=n;i++) {printf("\n"); for(j=1;j<=n;j++) // 按座标输出方阵 if(z%2==0) printf("%4d",a[i][j]); else printf("%4d",a[j][i]); } } (3) 程序运行示例与变通 输入方阵阶n:7 方阵有以下两种旋转方式: 1: 逆时针转 2: 顺时针转 选择旋转方式代码: 1 所求旋转方阵为: 1 24 23 22 21 20 19 2 25 40 39 38 37 18 3 26 41 48 47 36 17 4 27 42 49 46 35 16 5 28 43 44 45 34 15 6 29 30 31 32 33 14 7 8 9 10 11 12 13 输入方阵阶n:8 方阵有以下两种旋转方式: 1: 逆时针转 2: 顺时针转 选择旋转方式代码: 2 所求旋转方阵为: 1 2 3 4 5 6 7 8 28 29 30 31 32 33 34 9 27 48 49 50 51 52 35 10 26 47 60 61 62 53 36 11 25 46 59 64 63 54 37 12 24 45 58 57 56 55 38 13 23 44 43 42 41 40 39 14 22 21 20 19 18 17 16 15 程序变通:把程序中的输出量a[i][j] 改变为n*n-a[i][j]+1,可输出由内到外的旋转方阵。 43 n!计算 定义n!=1*2*3*…*n 输入正整数n(<=100),计算并输出n!(若大于10位时输出其高10位)及其位数。 测试数据: n=30 n=100 设计要点: 设置s存储n!的连乘积,当其位数超过10位时,s中的高10位是准确的。 设置条件循环实施连除求得s的位数w. 当位数w大于10时,设置条件循环实施连除求得s的高10位. #include"stdio.h" void main() { double s=1,k; int i,n,w=0,m; printf(" 请输入一个正整数n:"); scanf("%d",&n); for(i=1;i<=n;i++) s=s*i; // 计算n! k=s; while(k>=1) { w++;k=k/10;} // 计算n!的位数w m=w; while(w>10) { s=s/10;w--;} // 若超过10位计算其高10位 if(w!=10) printf(" %d!=%.lf,共%d位\n",n,s,w); else printf(" %d!=%.lf...共%d位\n",n,s,m); } 请输入一个正整数n:30 30!=2652528598...,共33位 请输入一个正整数n:100 100!=9332621544...,共158位 变通:输入正整数n(<=100),精确计算并输出n!及其位数。 设计要点: 设置s数组,s[1]为阶乘的个位数字,s[2]为阶乘的十位数字,类推。 模拟竖式乘法,要注意每次乘时需进位。 // 模拟竖式乘法求n!的精确值 #include void main() { int i,j,m,n,s[1000]; printf(" 请输入整数n(n>2): "); scanf("%d",&n); for(j=1;j<=2*n;j++) s[j]=0; s[1]=1; for(i=2;i<=n;i++) { m=0; // 乘i前进位数m清零 for(j=1;j<=2*n;j++) { s[j]=s[j]*i+m; // 从个位开始,第j位乘i m=s[j]/10; // 十位以上为进位数 s[j]=s[j]%10; // 个位数字存储到本位 } } i=2*n; while(s[i]==0) i--; // 去高位零 printf(" %d!=",n); for(j=i;j>=1;j--) // 从高位开始逐位输出 printf("%d",s[j]); printf("\n 共%d位。 \n",i); } 请输入整数n(n>2): 30 30!=265252859812191058636308480000000 共33位。 请输入整数n(n>2): 100 100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 共158位。 44 分数数列 老师为了检测学生的观察分析能力与程序设计水平,写出一个递推分数数列的前6项: 1/2, 3/5, 4/7, 6/10, 8/13, 9/15, ...,引导学生注意观察数列的构成规律:第i项的分母d与分子c存在以下关系:d=c+i.而c为与前i-1项中的所有分子、分母均不相同的最小正整数。 试求出该数列的第n项,并求出前n项中的最大项。 测试数据: (1) n=1000 (2) n=2012 1. 设计要点 注意到递推需用到前面的所有项,必须设置数组:c(i)表第i项的分子,d(i)表第i项的分母(均表现为整数)。 显然,初始值为:c(1)=1,d(1)=2。 已知前i-1项,如何确定c(i)? 显然c(i)>c(i-1),同时可证当i>2时,第i个分数的分子c(i)总小于第i-1个分数的分母d(i-1)。置k在区间(c(i-1),d(i-1))取值,k分别与d(1),d(2),...d(i-1)比较,若有相同,则k增1后再比较;若没有相同的,则产生第i项,作赋值:c(i)=k,d(i)=k+i。 为了准确求出数列前n项中的最大项,设最大项为第x项(x赋初值1),每产生一项(第i项),如果有 c(i)/d(i)>c(x)/d(x) <=> c(i)*d(x)>c(x)*d(i) 即第i项要比原最大项第x项还大,则作赋值x=i,把产生的第i项确定为最大。前n产生完毕,最大项也比较出来了。 在程序设计中作最大项的比较,用后一个整数不等式是适宜的,准确的。如果用前一个分数不等式比较因误差的存在可能导致最大项结果的失误。 2. 分数数列C程序设计 // 分数递推数列 #include void main() { int n,i,k,t,j,kmax; static long c[3001],d[3001]; printf("请输入整数n(1--3000):"); // 键盘输入确定整数n scanf("%d",&n); c[1]=1; d[1]=2; c[2]=3;d[2]=5; kmax=1; // 数组与最大项序号赋初值 for(i=3;i<=n;i++) {for(k=c[i-1]+1;kc[kmax]*d[i]) kmax=i;} // 比较得最大项的序号kmax printf("数列的第%d项为: %ld/%ld.\n",n,c[n],d[n]); printf("数列前%d项中最大项为: ",n); for(i=1;i<=n;i++) // 检查有多个最大项时输出 if(c[i]*d[kmax]==c[kmax]*d[i]) printf(" 第%d项: %ld/%ld.\n",i,c[i],d[i]); } 3. 数据测试 请输入整数n(1--3000):1000 数列的第1000项为: 1618/2618. 数列前1000项中最大项为: 第610项, 987/1597. 请输入整数n(1--3000):2012 数列的第2012项为: 3255/5267. 数列前2012项中最大项为: 第1597项, 2584/4181. 顺便指出,上述分数的分子和分母构成的数对(1,2),(3,5),(4,7),(6,10),...常称为Wythoff对。Wythoff对在数论和对策论中应用较广。 45 双和数组 把一个偶数2s分解为6个互不相等的正整数a,b,c,d,e,f,然后把这6个正整数分成(a,b,c)与(d,e,f)两个组,若这两组数具有以下两个相等特性: 则把数组(a,b,c)与(d,e,f)称为基于s 的双和数组(约定aa,因而d起点为a+1。 把比较倒数和相等1/a+1/b+1/c=1/d+1/e+1/f转化为比较整数相等 d*e*f*(b*c+c*a+a*b)=a*b*c*(e*f+f*d+d*e) (*) 若上式不成立,即倒数和不相等,则返回。 同时注意到两个3元组中若部分相同部分不同,不能有倒数和相等,因而可省略排除以上6个正整数中是否存在相等的检测。 若式(*)成立,打印输出和为s的双和数组,并用x统计解的个数。 (2) C程序设计 // 双和数组探索 #include #include void main() {int a,b,c,d,e,f,x,s; for(s=21;s<=100;s++) { printf(" s=%d: \n",s); x=0; for(a=1;a<=(s-3)/3;a++) for(b=a+1;b<=(s-a-1)/2;b++) for(d=a+1;d<=(s-3)/3;d++) for(e=d+1;e<=(s-d-1)/2;e++) { c=s-a-b; f=s-d-e; if(a*b*c*(e*f+f*d+d*e)!=d*e*f*(b*c+c*a+a*b)) continue; // 排除倒数和不相等 x++; printf("%3d: (%2d,%2d,%2d) ",x,a,b,c); printf("(%2d,%2d,%2d)\n",d,e,f); } if(x==0) printf(" 无解!\n"); } } (3) 程序运行结果与讨论 s=26: 1: ( 4,10,12) ( 5, 6,15) s=98: 1: ( 2,36,60) ( 3, 5,90) 2: ( 7,28,63) ( 8,18,72) 3: ( 7,35,56) ( 8,20,70) 4: (10,33,55) (12,20,66) 46 素数和序列 把前8个正整数排成一个序列,如果序列中所有相邻的两项之和都是一个素数,该序列称为一个8项素数和序列。 构造并输出所有不同的8项素数和序列(约定序列左瑞小于右瑞)。 (1) 设计要点 为避免重复,约定首项小于尾项。 环中的每一项为一个数字,相连的8项构成一个8位数。因而设置a循环,在12345678——87654321中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数,该数也为9的倍数,为此,枚举循环步长可取9,以精简枚举次数。 为操作与判断方便,设置3个数组: f数组统计8位数a中各个数字的频数。如f[3]=2,即a中有2个数字“3”。 g数组表示8位数a中每位数的数字。如g[4]=6,即a的从高位开始第4位数为数字“6”。 b数组标记整数x是否为素数。如b[13]=1,标识“1”表示13为素数,标识“0”为非素数。 枚举实施: 1) 注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。 2) 在8位数的a 循环中,对a实施8次求余分离出各个数字x,应用f[x]++统计数字x的频数,应用g[9-k]=x记录a的各位数字。 3) 设置k(1——8)判断循环: 若f[k]!=1 ,表明数字k出现重复或遗漏,返回。 若 b[g[k]+g[k+1]]!=1,表明相邻的第k项与第k+1项之和不是素数,返回。 (2) 程序设计 // 8项素数序列枚举求解 #include #include void main() { int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; s=0; b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(" 8项素数序列:\n"); for(a=12345678;a<=78654321;a+=9) // 步长为9枚举8位数 {t=0;y=a; for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++) {x=y%10;f[x]++; // 分离a的8数字,用f数组统计x的个数 y=y/10;g[9-k]=x; // 用g数组记录a的第k位数字 } for(k=1;k<=7;k++) if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1; if(f[8]!=1 || t==1 || g[1]>g[8]) continue; // 有相同数字或相邻和非素或左大于右,返回 s++; printf(" %d: %d",s,g[1]); // 输出8项素数和环 for(k=2;k<=8;k++) printf(",%d",g[k]); printf("\n"); } } (3) 程序运行示例 8项素数序列: 1: 1,2,3,4,7,6,5,8 2: 1,2,3,8,5,6,7,4 …… 30: 7,6,5,2,1,4,3,8 (4) 拓广到8项素数和环 把前8个正整数摆成一个环,如果环中所有相邻的两个数之和都是一个素数,该环称为一个8项素数和环。 构造并输出所有不同的8项素数和环。 1) 设计要点 为简化输出,环序列简化为一般序列输出,为避免重复,约定首项为“1”。 环中的每一项为一个数字,相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数12345678——18765432中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数,该数也为9的倍数,为此,枚举循环步长可取9,以精简枚举次数。 若 b[g[k]+g[k+1]]!=1,表明相邻的第k项与第k+1项之和不是素数,返回。顺便说明,为判断方便,首项“1”先行赋值给g[9],以与g[8]相邻,在k循环中一道进行判别。 通过以上判断筛选的a,其各个数字即为所求的8项素数环的各项,打印输出。 2) 枚举实现8项素数和环 // 8项素数和环枚举求解 #include #include void main() { int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; g[9]=1;s=0; b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(" 8项素数和环:\n"); for(a=12345678;a<=18765432;a+=9) // 步长为9枚举8位数 {t=0;y=a; for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++) {x=y%10;f[x]++; // 分离a的8个数字,用f数组统计x的个数 g[9-k]=x; // 用g数组记录a的第k位数字 y=y/10; } for(k=1;k<=8;k++) if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1; if(t==1) continue; // 有相同数字或相邻和非素,返回 s++; printf(" %d: 1",s); // 输出8项素数和环 for(k=2;k<=8;k++) printf(",%d",g[k]); printf("\n"); } } 3) 程序运行示例 8项素数和环: 1: 1,2,3,8,5,6,7,4 2: 1,2,5,8,3,4,7,6 3: 1,4,7,6,5,8,3,2 4: 1,6,7,4,3,8,5,2 容易验证,所得素数和环中每相邻两项(包括首尾两项)之和均为素数。 如果求解素数和序列,只要把环中的首尾相接的条件“b[a[n]+1]==1”去除即可。 (5) 探索首项为1的10项素数序列 // 10项素数序列枚举求解 #include #include void main() { int t,k,s,x,g[11],f[11],b[20];double a,y; for(k=1;k<=18;k++) b[k]=0; s=0; b[3]=b[5]=b[7]=b[11]=b[13]=b[17]=b[19]=1; // 7个奇素数标记 printf(" 10项素数序列:\n"); for(a=1023456789;a<=1987654320;a=a+9) // 步长为9枚举10位数 {t=0;y=a; for(k=0;k<=10;k++) f[k]=0; for(k=1;k<=10;k++) { x=(int)fmod(y,10); if(x==0) x=10; f[x]++; // 分离a的10个数字,用f数组统计x的个数 y=floor(y/10.0);g[11-k]=x; // 用g数组记录a的第k位数字 } for(k=1;k<=9;k++) if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1; if(f[10]!=1 || t==1) continue; // 有相同数字或相邻和非素或左大于右,返回 s++; printf(" %d: %d",s,g[1]); // 输出10项素数和环 for(k=2;k<=10;k++) printf(",%d",g[k]); printf("\n"); } } 10项素数序列: 1: 1,10,3,2,5,6,7,4,9,8 2: 1,10,3,2,5,8,9,4,7,6 3: 1,10,3,2,9,4,7,6,5,8 …… 128: 1,6,7,4,9,8,5,2,3,10 47 6 顺数 定义排列数:整数m的排列数为m的各位数字的不同排列产生的整数。例如123的排列数有132,213,231,312,321等。 定义6顺数:一个w(5 void main() { int b,c,j,k,w,f[10],h[10]; long m,n,d,t; printf(" 请输入位数: ");scanf("%d",&w); t=1; for(k=1;k<=w-1;k++) t=t*10; // 计算最小的w位整数t for(m=t;m<(10*t-1)/(w-1);m++) // 枚举所有的w位数 { d=m;b=0; for(j=0;j<=9;j++) f[j]=0; for(j=1;j<=w;j++) {c=d%10;f[c]++;d=d/10;} for(k=2;k<=6;k++) { n=m*k;d=n; for(j=0;j<=9;j++) h[j]=0; for(j=1;j<=w;j++) {c=d%10;h[c]++;d=d/10;} for(j=0;j<=9;j++) if(f[j]!=h[j]){b=1;k=w;break;} } if(b==0) { printf(" %ld:",m); for(j=2;j<=6;j++) {printf(" %ld*%d=%ld",m,j,j*m); if(j%3==0) printf("\n"); } printf("\n"); } } } 请输入位数: 6 142857: 142857*2=285714 142857*3=428571 142857*4=571428 142857*5=714285 142857*6=857142 请输入位数: 7 1428570: 1428570*2=2857140 1428570*3=4285710 1428570*4=5714280 1428570*5=7142850 1428570*6=8571420 1429857: 1429857*2=2859714 1429857*3=4289571 1429857*4=5719428 1429857*5=7149285 1429857*6=8579142 48 连写数 连写数:按正整数的顺序不间断写下的整数称为连写数。 例如一直写到15的连写数为123456789101112131415,其中15为该连写数的结束数。 探求能被指定正整数n整除的最小连写数,并指出该连写数的位数。 例如,n=7, 能被7整除的最小连写数为1234567891011,该连写数共13位. 输入n,输出能被n整除的最小连写数的结束数,并输出该连写数的位数。 测试数据: (1) n=73 (2) n=2012 // 被n整除的连写数探求 #include #include void main() { int a,c,j,k,m,n,t;long s; printf(" 请输入正整数n:");scanf("%d",&n); c=1;m=1;s=1; while(c!=0) {m++;j=m;t=1;k=0; while(j>0) {j=j/10;t=t*10;k++;} a=c*t+m; c=a%n; s=s+k; } printf(" 连写数1234...一直写到%d,能被%d整除。\n",m,n); printf(" 1234...一直写到%d的连写数共%ld位。\n",m,s); } 请输入正整数n:73 连写数1234...一直写到79,能被73整除。 1234...一直写到79的连写数共149位。 请输入正整数n:2012 连写数1234...一直写到2348,能被2012整除。 1234...一直写到2348的连写数共8285位。 48 49 方阵与菱形转换 输入一个n阶方阵,把它顺时针旋转45度后成为一个2n-1行的菱形,然后把菱形顺时针再旋转45度后成为一个n阶方阵,…。 构建一个方阵,依次输出转换后的数阵。 例如,n=5阶方阵及其前两次转换为: 4 2 2 5 6 4 6 2 2 4 1 8 8 9 1 2 9 1 9 7 9 7 5 6 6    方阵旋转45度转换为菱阵:  4 4 2 1 6 2 2 8 2 5 9 9 8 2 6 7 1 9 4 5 9 1 6 7 6    菱阵旋转45度转换为方阵:  9 2 1 4 4 7 9 8 6 2 5 1 8 2 2 6 9 9 2 5 6 7 1 4 6 设计要点: 设方阵的数据存储的a数组,菱形的数据存储在b数组。 (1) 方阵旋转45度转换成为菱形,a数组向b数组赋值。 设方阵的行号为i,列号为j, 以对角线i+j=n+1为界分为上下两个区域。通过归纳,上下两个区分别进行赋值。 上区: i+j<=n+1,方阵的a[i][j]为菱形的b[i+j-1][j]。 下区: i+j>=n+2,方阵的a[i][j]为菱形的b[i+j-1][n+1-i]。 (2) 菱形旋转45度转换成方阵,b数组向a数组赋值。 设菱形的行号为i(1≤i≤2n-1),对菱形分上下两个区域。通过归纳,上下两个区分别进行赋值。 上区: i<=n,菱形的b[i][j]为方阵的a[i+j-t][n+j-t]。(其中t=n-abs(i-n);) 下区: i>n,菱形的b[i][j]为方阵的a[i+j-n][j] 程序设计: // 方阵与菱阵旋转转换 #include #include #include #include void main() { int m,n,i,j,k,t,a[50][50],b[50][50]; printf("  请输入数字方阵的行数n:"); scanf("%d",&n); t=time(0)%1000; srand(t); //随机数发生器初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=rand()%10+1; for(m=1;m<=4;m++) // 转换4次 { if(m>1) printf("    菱阵旋转45度转换为方阵: \n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%3d",a[i][j]); // 打印n阶方阵 printf("\n"); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) // 由方阵a给菱阵b数组赋值 if(i+j>=n+2) b[i+j-1][n+1-i]=a[i][j]; else b[i+j-1][j]=a[i][j]; printf("    方阵旋转45度转换为菱阵: \n"); for(i=1;i<=2*n-1;i++) { t=n-abs(i-n); for(k=1;k<=36-2*t;k++) printf(" "); for(j=1;j<=t;j++) printf("%4d",b[i][j]); // 打印菱阵 printf("\n"); } for(i=1;i<=2*n-1;i++) { t=n-abs(i-n); for(j=1;j<=t;j++) // 由菱阵b给方阵a数组赋值 if(i>n) a[i+j-n][j]=b[i][j]; else a[i+j-t][n+j-t]=b[i][j]; } } }   请输入数字方阵的行数n:5 4 2 2 5 6 4 6 2 2 4 1 8 8 9 1 2 9 1 9 7 9 7 5 6 6    方阵旋转45度转换为菱阵:  4 4 2 1 6 2 2 8 2 5 9 9 8 2 6 7 1 9 4 5 9 1 6 7 6    菱阵旋转45度转换为方阵:  9 2 1 4 4 7 9 8 6 2 5 1 8 2 2 6 9 9 2 5 6 7 1 4 6    方阵旋转45度转换为菱阵:  9 7 2 5 9 1 6 1 8 4 6 9 8 6 4 7 9 2 2 1 2 2 4 5 6    菱阵旋转45度转换为方阵:  6 6 5 7 9 7 9 1 9 2 1 9 8 8 1 4 2 2 6 4 6 5 2 2 4    方阵旋转45度转换为菱阵:  6 7 6 1 9 5 4 9 1 7 6 2 8 9 9 5 2 8 2 2 6 1 2 4 4    菱阵旋转45度转换为方阵:  6 4 1 7 6 5 2 9 9 6 2 2 8 1 5 2 6 8 9 7 4 4 1 2 9    方阵旋转45度转换为菱阵:  6 5 4 2 2 1 2 2 9 7 4 6 8 9 6 4 8 1 6 1 9 5 2 7 9

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档