C语言程序设计100例之（8）：尼科彻斯定理
aTeacher 人气:1例8 尼科彻斯定理
题目描述
尼科彻斯定理可以叙述为：任何一个整数的立方都可以表示成一串连续的奇数的和。需要注意的是，这些奇数一定是连续的，如：1，3，5，7，9，…。
例如，对于整数5，5*5*5=125=21+23+25+27+29。
对于整数6，216=31+33+35+37+39+41，
也可以表示为216=7+9+11+13+15+17+19+21+23+25+27+29。
请你编写程序对这个定理进行验证。
输入格式
一个整数n（2≤n≤1000）。
输出格式
将n的立方表示为一串连续的奇数的和，具体格式见输出样例。若有多种表示方式，任意输出一种即可。
输入样例
29
输出样例
29*29*29=24389=813+815+817+819+821+823+825+827+829+831+833+835+837+839+841+843+845+847+849+851+853+855+857+859+861+863+865+867+869
（1）编程思路1。
先计算输入数n的立方num，然后从1（用变量i记录）开始累计和sum，累计每次j加2保证下个数也为奇数，如果累加和sum大于立方数num时，跳出本次循环，进行下一次的尝试（i=3或5、7、…开始累积和）。当找到后，记录开始位置（即i），结束位置（即j），输出。
程序写成一个嵌套的二重循环。外循环i控制累计和的起点，内循环累计i、i+2、i+4、…的和。
（2）源程序1。
#include<stdio.h>
int main()
{
int n,num,sum,i,j,k,flag;
while(1)
{
scanf("%d",&n);
if(n==0) break;
num = n * n * n;
flag=0;
for(i=1; i<num && flag==0; i=i+2)
{
sum=0;
for(j=i; j<num; j=j+2)
{
sum += j;
if(sum == num)
{
printf("%d*%d*%d=%d=%d",n,n,n,num,i);
for (k=i+2; k<=j;k+=2)
printf("+%d",k);
printf("\n");
flag=1;
break;
}
else if (sum > num)
break;
}
}
}
return 0;
}
（3）编程思路2。
源程序1的思路是通过试探的方法来验证尼科彻斯定理，采用二重循环实现。
实际上，n的立方一定可以表示为一个等差数列的各项和，该等差数列的首项为n*n-n+1，公差为2，项数为n。
按等差数列的求和公式知该数列的和为：
[(n*n-n+1)+( n*n-n+1)+ 2 (n-1)]*n/2 =n*n*n
因此，直接用循环输出这个等差数列的各项即可。
（4）源程序2。
#include<stdio.h>
int main()
{
int n,a,i;
while(1)
{
scanf("%d",&n);
if(n==0) break;
// 输出等差数列，首项为n*n-n+1，公差为2，项数为n
a=n*n-n+1;
printf("%d*%d*%d=%d=%d",n,n,n,n*n*n,a);
for (i=1; i<n;i++)
printf("+%d",a+i*2);
printf("\n");
}
return 0;
}
习题8
8-1 谷角猜想
题目描述
日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2 ；若 n 为奇数，则将其乘以 3 ，然后再加 1 。如此经过有限次运算后，总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。
请你编写程序对这个猜想进行验证。
输入格式
一个自然数n。
输出格式
把 n 经过有限次运算后，最终变成自然数 1 的全过程输出。具体格式见输出样例。
输入样例
34
输出样例
34/2=17
17*3+1=52
52/2=26
26/2=13
13*3+1=40
40/2=20
20/2=10
10/2=5
5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
（1）编程思路。
定义迭代变量为n，按照谷角猜想的内容，可以得到两种情况下的迭代关系式：当 n 为偶数时，n=n/2 ；当 n 为奇数时， n=n*3+1 。
这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次，才能使迭代变量 n 最终变成自然数 1 ，这是我们无法计算出来的。因此，还需进一步确定用来结束迭代过程的条件。由于对任意给定的一个自然数 n ，只要经过有限次运算后，能够得到自然数 1 ，从而完成验证工作。因此，用来结束迭代过程的条件可以定义为： n==1 。
（2）源程序。
#include<stdio.h>
int main()
{
unsigned int data;
scanf("%d",&data);
while(data!=1)
{
if((data%2==0))
{
printf("%d/2=%d\n",data,data/2);
data/=2;
}
else
{
printf("%d*3+1=%d\n",data,data*3+1);
data=data*3+1;
}
}
return 0;
}
8-2 四方定理
题目描述
数论中著名的“四方定理”是：所有自然数至多只要用四个不小于0的整数的平方和就可以表示。
编写一个程序验证此定理。
输入格式
一个自然数n。
输出格式
把自然数 n 表示为四个数的平方和。具体格式见输出样例。
输入样例
147
输出样例
7*7+7*7+7*7+0*0=147
8*8+7*7+5*5+3*3=147
9*9+5*5+5*5+4*4=147
9*9+7*7+4*4+1*1=147
9*9+8*8+1*1+1*1=147
11*11+4*4+3*3+1*1=147
11*11+5*5+1*1+0*0=147
12*12+1*1+1*1+1*1=147
（1）编程思路。
对于待验证的自然数n，用四个变量i、j、k、l采用试探的方法，穷举进行计算，满足要求（i *i + j * j + k * k + l * l == n）时输出计算结果。
在穷举时，不妨设i≥j≥k≥l。因此，穷举的范围可确定为：
1 ≤ i ≤ n/2
0 ≤ j ≤ i
0 ≤ k ≤ j
0 ≤ l ≤ k
（2）源程序。
#include<stdio.h>
int main()
{
int n,i,j,k,l;
scanf("%d",&n);
for (i = 1; i <= n/2; i++) // 对i，j，k，l进行穷举
for (j = 0; j <= i; j++)
for (k = 0; k <= j; k++)
for (l = 0; l <= k; l++)
if (i *i + j * j + k * k + l * l == n)
{
printf("%d*%d+%d*%d+%d*%d+%d*%d=%d\n",i,i,j,j,k,k,l,l,n);
}
return 0;
}
8-3 卡布列克运算
问题描述
所谓卡布列克运算，是指任意一个四位数，只要它们各个位上的数字不全相同，就有这样的规律：
（1）把组成这个四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；
（2）把组成这个四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数（如果四个数字中含有0，则此数不足四位）；
（3）求出以上两数之差，得到一个新的四位数。
重复以上过程，总能得到最后的结果是 6174。
例如，n= 3280，验证结果为：8320-238=8082 8820-288=8532 8532-2358=6174
编写一个程序对卡布列克运算进行验证。
输入数据
一个各位上的数字不全相同的四位数n。
输出要求
把 n 经过有限次卡布列克运算后，最终变成6174的全过程输出。具体格式见输出样例。
输入样例
2019
输出样例
9210-129=9081
9810-189=9621
9621-1269=8352
8532-2358=6174
YES
（1）编程思路。
为实现验证程序，编写4个函数。
void parse_sort(int each[],int num) 将num分解为各位数字并排序后存入数组each[]中。
int minD(int each[]) 求数组each中的4个数字可组成的最大数。
int maxD(int each[]) 求数组each中的4个数字可组成的最小数。
int pow10_int(int n) 求10的N次方。
（2）源程序。
#include <stdio.h>
#define N 4
int pow10_int(int n); // 求10的N次方
void parse_sort(int each[],int num); // 把num分解各个位上的数后存入数组each[]中
int minD(int each[]); // 求数组each可组成的最大数
int maxD(int each[]); // 求数组each可组成的最小数
int main()
{
int number,max,min;
int each[N];
scanf("%d",&number);
while(number!=6174)
{
parse_sort(each,number);
max=maxD(each);
min=minD(each);
number=max-min;
printf("%d-%d=%d\n",max,min,number);
}
printf(" YES\n");
return 0;
}
int pow10_int(int n) // 求10的N次方的函数
{
int sum=1;
for(int i=0;i<n;i++)
sum=sum*10;
return sum;
}
void parse_sort(int each[],int num) // 把num分解各个位上的数后存入数组each[]中
{
int m,i,j,t;
for (i=0;i<N;i++)
each[i]=0;
i=0;
while(num!=0)
{
m=num%10; num=num/10;
each[i++]=m;
}
for(i=0;i<N-1;i++)
for (j=0;j<N-1-i;j++)
if (each[j]>each[j+1])
{
t=each[j];
each[j]=each[j+1];
each[j+1]=t;
}
}
int minD(int each[]) // 求数组each可组成的最大数
{
int sum=0,i;
for(i=0;i<N;i++)
sum+=each[i]*pow10_int( (N-1-i) );
return sum;
}
int maxD(int each[]) // 求数组each可组成的最小数
{
int sum=0,i;
for(i=0;i<N;i++)
sum=sum+each[i]*pow10_int(i);
return sum;
}
加载全部内容