C 练习实例3

既然是计算机解题，那么就用最笨的方法，尽量少动脑筋。

分析：假设这个数是 x，那么有 x+100=a*a，x+268=b*b。找到满足 b*b-a*a=168 的数，就能找到 x。

#include<stdio.h>

int main(){
    int a,b;
    for(b=13;b*b-(b-1)*(b-1)<=168;b++){//如果你不知道第一个大于168的平方数，可以设置b=1;
        for(a=0;a<b;a++){
            if(b*b-a*a==168) 
                printf("%d  ",a*a-100);
        }
    }
}

我的思路是这样：关键是两个平方数之差是168，于是搜索所有符合条件的平方数。i 为比较小的那个，j 为比较大的那个。符合 j*j-i*i=168 时，x 就等于 i*i-100。

搜索 i 时，如果 (i+1) 的平方减去i的平方都比 168 大，那就不用搜索，不可能符合条件了。搜索 j 时，从 i+1 开始搜索，如果 j 平方 -i 平方 比 168 大，那也没必要搜索了。

#include<stdio.h>
#include<math.h>

int main(void){
    for (int i = 0; (i+1)*(i+1)-i*i <= 168 ; ++i)
    {
        for (int j = i+1; j*j-i*i<=168 ; ++j)
        {
            if(j*j-i*i==168) {
                printf("j = %d,i = %d,j*j-i*i=%d\n", j,i,j*j-i*i);
                printf("x = %d\n", i*i-100);
            }
            
        }
    }
}

参考方法：

/*一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？*/
/*依据x+100=b^2 x+268=a^2得(a-b)(a+b)=168分解因式检验即可*/
#include<stdio.h>
int main(void)
{
    int i = 1;
    int a, b, n;
    for (i = 1; i*i <= 168; i++)
    {
        if (!(168 % i))
        {
            a = (i + 168 / i) / 2;
            b = (168 / i - i) / 2;
                        n = a*a - 268;
            if ((a*a - 268) == (b*b - 100))
                printf("The correct answer is %d.\n", n);
        }
    }
    return 0;
}

参考方法:

#include <stdio.h>
#include <math.h>

int main()
{
    int a,x;    // x 为该整数，x+100 可被 a 开平方；
    double b;   // x+268 可被 b 开平方；
    for(a=0;b*b-(b-1)*(b-1)<168;a++)  // a*a 最小值为 0，故 a 取值从 0 开始，需满足 b*b-(b-1)*(b-1)<168，否则不存 在a*a +168=b*b
    {
        b=sqrt(a*a+168);
        if    ( b==(int)b ) {
            x=a*a-100;  
            printf("x=%d a=%d b=%f\n",x,a,b);  
        }
    }
}

参考方法：

#include <stdio.h>

/*
    x + 100 = m^2;
    x + 268 = n^2;
    x∈Z,m,n∈Z+;
    (m+n)(m-n)=168=2*2*2*3*7
    =2*84=4*42=6*28=12*14
    数论问题：奇偶分析、因式分解
    计算机优化整数搜索空间：枚举法
    i*j=168,m=(i+j)/2,n=(j-i)/2,i<j
    for i∈[2,84]
    for i∈[2,12],13^2=169>168
*/
// bit field
struct
{
    unsigned int i: 4;
    unsigned int j: 7;
    unsigned int n: 6;
    int x: 12;
}num;

int main()
{
    for(num.i=2; num.i<=12; num.i++)
    {
        if(168%num.i==0)
        {
            num.j = 168/num.i;
            if(num.i%2==0 && num.j%2==0)
            {
                num.n = (num.i+num.j)/2;
                num.x = num.n*num.n-268;
                printf("i=%d,x=%d\n",num.i,num.x);
                printf("%lu",sizeof(num));
            }
        }
    }
    return 0;
}

参考方法：

#include <stdio.h>

/*
    一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？
    x + 100 = m^2;
    x + 268 = n^2;
    x∈Z,m,n∈Z+;
    (m+n)(m-n)=168=2*2*2*3*7 <因式分解>
    =2*84=4*42=6*28=12*14
    数论问题：奇偶分析
    计算机优化整数搜索空间：枚举法
    i*j=168,m=(i+j)/2,n=(i-j)/2,i>j
    for i∈[2,84]
    for i∈[2,12],13^2=169>168
*/

int main()
{
    int i=0,j=0,n=0,x=0;
    for(i=2; i<=12; i++)
    {
        if(168%i == 0)
        {
            j = 168/i;
            if(i%2==0 && j%2==0 && i<j)
            {
                n = (i+j)/2;
                x = n*n-268;
                printf("i=%d,x=%d\n",i,x);
            }
        }
    }
    return 0;
}

参考方法：

#include <stdio.h>

int main() {
    int m, n;
    int j;
    for ( int i = 1;  i < 168;  i++)
    {
        j = 168 / i;
        if (j > i || 168 % i != 0)
        {
            continue;
        }

        if ((i + j) % 2 != 0 || (i - j) % 2 != 0)
        {
            continue;
        }

        m = (i + j) / 2;
        n = (i - j) / 2;
        printf("m和n分别是：%d,%d,", m, n);
        printf("这个数是：%d\n", n * n - 100);
    }
}

/*
  思路：
    1.根据已知条件判断该整数 x 的上下限
        由已知条件得
            sqrt(x + 100) = y    由 y>=0 可知 x 的下限即为 -100
            sqrt(x + 268) = z
        由上面两式可得
            z^2 - y^2 = 168
        按照两个相邻整数的平方差间隔越来越大的特性，找出极限情况下的数值 y 与 z
        将 z^2 - 268 或 y^2 - 100 作为 x 的上限
    2.然后在范围内暴力搜索，找出所有符合描述的值
        根据 x 的值计算 y, z
        判断 y, z 均为整数，即输出 x
*/

# include <stdio.h>
# include <math.h>

int main()
{
    int x, c1, c2, L, H;
    c1 = 100;
    c2 = 168;

    L = -c1;

    int i = 0;    
    for (i = 1; i*i - (i - 1)*(i - 1) <= c2; ++i)
        ;

    H = i*i - (c1 + c2);

    int j;
    double y, z;
    for (j = L; j <= H; ++j)
    {
        y = sqrt(j + c1);
        z = sqrt(j + c1 + c2);
        if (y == (int)y && z == (int)z)
            printf("x的值为 %d\n", j);
    }

    return 0;
}

输出结果为：

x的值为 -99
x的值为 21
x的值为 261
x的值为 1581

思路：

由 m^2 - n^2 = (m + n)(m - n) = 168, 得到 |m|>|n|

上式中 |n| 最大时则有：（n+1）^2-n^2≥168 → n≥83.5 , 故选择n的取值范围为1~84，

此时，x=n^2-100, m=(x+268)^0.5, 只需求得每个n所对应的x与m，再从中选择整型的x与m进行输出即可

程序：

#include <stdio.h>
#include <math.h> 

int main()
{
    int n,x,a,m;
    double b;

    for (n = 1; n <= 168 / 2 ; n++)
    {
        x=n*n-100;
        a=x+268;
        b=sqrt(a);
        if((int)b==b)
        {
            m=(int)b;
            printf ("%d + 100 = %d * %d\n", x, n, n);
            printf ("%d + 268 = %d * %d\n", x, m, m);
        }
    }
    return 0;
}

优化,有两点多余，i 可以从 2 开始加 2，i-j 必定是偶的:

#include <stdio.h>

int main (void)
{
    int  i, j, m, n, x;
    for (i = 2; i <= 168 / 2; i=i+2)
    {
        if (168 % i == 0)
        {
            j = 168 / i;
            if ( i > j && (i + j) % 2 == 0)
            {
                m = (i + j) / 2;
                n = (i - j) / 2;
                x = n * n - 100;
                printf ("%d + 100 = %d * %d\n", x, n, n);
                printf ("%d + 268 = %d * %d\n", x, m, m);
            }
        }
    }
    return 0;
}