欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言程序设计100例之(15):除法算式

程序员文章站 2022-06-07 11:27:02
例15 除法算式 问题描述 输入正整数n(2≤n≤68),按从小到大输出所有形如abcde/fghi=n的表达式。其中a~i为1~9的一个排列。 输入格式 每行为一个正整数n (n <= 1500),输入n=0结束。 输出格式 输出满足条件的所有形如abcde/fghi=n的表达式,每个表达式占一行 ......

例15   除法算式

问题描述

输入正整数n(2≤n≤68),按从小到大输出所有形如abcde/fghi=n的表达式。其中a~i为1~9的一个排列。

输入格式

每行为一个正整数n (n <= 1500),输入n=0结束。

输出格式

输出满足条件的所有形如abcde/fghi=n的表达式,每个表达式占一行,具体格式参见输出样例。

输入样例

4

20

62

0

输出样例

15768/3942=4

17568/4392=4

23184/5796=4

31824/7956=4

no solution!

79546/1283=62

94736/1528=62

(1)编程思路。

本例需要先确定好穷举的思路。虽然题目说a~i为1~9的一个排列,但穷举1~9的所有排列显然没有必要。

可以穷举除数fghi,这是一个4位数,最小可为1234,最大可为9876,然后按fghi*n计算出abcde,最后判断这9个数字是否不相同。

为判断9个数字是否相同,可以定义一个数组flag[10],其中flag[i]的值表示数字i在算式中出现的次数,显然flag[1]~flag[9]的值全为1才满足要求。

另外,在穷举时进行适当优化。若计算出abcde小于12345,显然除数fghi太小,直接增大除数进行下次穷举;若计算出abcde大于98765,显然除数fghi太大,不再可能找到解,直接退出穷举循环。

(2)源程序。

#include <stdio.h>

int main()

{

    int n,x,y,i,flag[10],t;

    while (scanf("%d",&n) && n!=0)

    {

        t=0;

        for (y=1234;y<=9876;y++)

        {

            x=y*n;

            if (x<12345) continue;

            if (x>98765) break;

            for (i=0;i<10;i++)

               flag[i]=0;

            flag[x/10000]++; flag[x%10000/1000]++;

            flag[x%1000/100]++; flag[x%100/10]++;

            flag[x%10]++;

            flag[y/1000]++; flag[y%1000/100]++;

            flag[y%100/10]++; flag[y%10]++;

            for (i=1;i<10;i++)

                if (flag[i]!=1) break;

            if (i==10)

            {

                printf("%d/%d=%d\n",x,y,n);

                t++;

            }

        }

        if (t==0) printf("no solution!\n");

    }

    return 0;

}

习题15

15-1  完美立方

问题描述

a3 +b3 + c3 = d3为完美立方等式。例如13 + 63 + 83 =93。编写一个程序,输出100以内的所有四元组(a, b, c, d),使得a3 +b3 + c3 = d3,其中1≤a< b< c< d≤100。

输入格式

无输入

输出格式

100以内所有满足a3 +b3 + c3 = d3的四元组(a, b, c, d),每行输出5组。

输入样例

无输入

输出样例

(  3,  4,  5,  6)  ( 1, 6,  8,  9)  ( 6,  8, 10, 12)  (  2, 12, 16, 18)  (  9, 12, 15, 18)

(  3,  10, 18, 19)  ( 7, 14, 17, 20)  ( 12, 16, 20, 24)  (  4, 17, 22, 25)  (  3, 18, 24, 27)

……

(1)编程思路。

因为要求100以内所有满足a3 +b3 + c3 = d3的四元组(a, b, c, d),因此先定义一个数组int cube[101];,且cube[i]的值赋i3,以便于后面直接引用。

从d出发进行穷举,则穷举范围为

6≤d≤100

1≤a≤d-3

a+1≤b≤d-2

b+1≤c≤d-1

(2)源程序。

#include <stdio.h>

int main()

{

    int  i, a, b, c, d,cnt=0;

    int cube[101];

    for (i=1 ; i<=100; i++)

       cube[i]=i*i*i;

    for (d=6 ; d<=100; d++)

       for (a=1; a<d-2; a++ )

       {

          if (cube[d] <cube[a]+cube[a+1]+cube[a+2]) break;  // 没必要继续搜索b 和c

          for (b=a+1 ; b<d-1; b++)

          {

              if (cube[d] <cube[a]+cube[b]+cube[b+1])  break; //  没必要继续搜索c

              for (c=b+1; c<d;  c++)

                 if (cube[d]==cube[a]+cube[b]+cube[c])

                  {

                                cnt++;

                                printf("(%3d,%3d,%3d,%3d)  ",a,b,c,d);

                                if (cnt%5==0) printf("\n");

                  }

         }

    }

    return 0;

}

15-2  分数拆分

问题描述

输入正整数k,找到所有的正整数x≥y,使得1/k=1/x+1/y。

输入格式

输入包含多组测试数据,每组为一行,一个正整数k。

输出格式

对每组数据先输出解的个数,然后输出全部的解,没个解占一行。具体格式参见输出样例。

输入样例

2

12

输出样例

2

1/2=1/6+1/3

1/2=1/4+1/4

8

1/12=1/156+1/13

1/12=1/84+1/14

1/12=1/60+1/15

1/12=1/48+1/16

1/12=1/36+1/18

1/12=1/30+1/20

1/12=1/28+1/21

1/12=1/24+1/24

(1)编程思路。

乍一看穷举的范围好像无法确定,但由于x≥y, 有1/x≤1/y,

因此由1/k=1/x+1/y 可知  1/y =1/k-1/x≥1/k-1/y, 故 2/y≥1/k  即y≤2k。当然y≥k+1。这样只要在k+1~2k范围之内穷举y,然后根据y尝试计算出x即可。

(2)源程序1。

#include <stdio.h>

int main()

{

    int k;

    while (scanf("%d",&k)!=eof)

    {

        int x,y,cnt=0;

        for (y=k+1;y<=2*k;y++)

        {

            if(k*y%(y-k)==0)

            {

                cnt++;

            }

        }

        printf("%d\n",cnt);

        for (y=k+1;y<=2*k;y++)

        {

            if(k*y%(y-k)==0)

            {

                x=k*y/(y-k);

                printf("1/%d=1/%d+1/%d\n",k,x,y);

            }

        }

    }

    return 0;

}

       (3)源程序2。

        在源程序1中,穷举的循环进行了两次,一次用循环求出解的个数,另一次用循环输出各个解的情况。显然,可以在用循环求解的个数时用数组将求得的解的情况保存下来,这样就不用再次循环求解,直接输出用数组保存的解的情况即可。

#include <stdio.h>

int main()

{

    int k;

    while (scanf("%d",&k)!=eof)

    {

        int cnt=0;

        int t;

        int x[2*k],y[2*k];

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

        {

            if(k*t%(t-k)==0)

            {

                x[cnt]=k*t/(t-k);

                y[cnt]=t;

                cnt++;

            }

        }

        printf("%d\n",cnt);

        for (t=0;t<cnt;t++)

        {

            printf("1/%d=1/%d+1/%d\n",k,x[t],y[t]);

        }

    }

    return 0;

}

        注意:在上面的源程序2中,x和y数组是定义的可变长数组,现在的c标准支持这样的用法。

15-3  一数三平方

问题描述

有一类六位数,不仅它本身是平方数,而且它的前三位与后三位也都是平方数,这类数称为“一数三平方数”。

输入格式

无输入

输出格式

输出所有的一数三平方数。每行输出一个一数三平方数,具体格式参见输出样例。

输入样例

无输入

输出样例

144400 : 12*12=144,20*20=400,380*380=144400

225625 : 15*15=225,25*25=625,475*475=225625

……

  (1)编程思路。

如果程序对所有的六位数(100000~999999)进行穷举,判断这个六位数是否是一数三平方,显然比较麻烦。

由于一个“一数三平方”数,其前三位与后三位一定都是平方数,因此,可以先求出999以内的所有的平方数,最多只有32个(即0的平方~31的平方,32的平方1024超过了3位)。定义一个数组int a[32]来保存这32个平方数。

程序中对这32个平方数两两组成的六位数进行穷举判断,显然高三位必须为数组中a[10](即不小于10的平方100的数首位才不为0)之后的平方数。算法描述为:

         for(i=10;i<=31;i++)

                   for(j=0;j<=31;j++)

                   {

                            c=1000*a[i] +a[j];              // a[i]作为高三位、a[j]作为低三位构成六位数

                            if( c是平方数)

                                 输出相应信息并计数

                   }

       (2)源程序。

#include <stdio.h>

#include <math.h>

int main()

{

         int a[32],i,j;

         long b,c,t;

         for(i=0;i<=31;i++)              // 统计出从0到999之内的所有平方数

                   a[i]=i*i;

         for(i=10;i<=31;i++)

         {

                   b=1000*a[i];                                /*高三位数*/

                   for(j=0;j<=31;j++)

                   {

                            c=b+a[j];                              /*六位数*/

                            t=sqrt(c);                             /*六位数开方*/

                            if(c==t*t)                             /*判断六位数是否为平方数*/

                            {

                                     printf("%d : %d*%d=%d,%d*%d=%d,%d*%d=%d\n",c,i,i,a[i],j,j,a[j],t,t,c);

                            }

                   }

         }

    return 0;

}