C趣味程序百例(21)

65.乘式还原(2)
66.除式还原(1)
67.除式还原(2)



65.乘式还原(2)
    有乘法算式如下：
            ○○○
          ×  ○○
       ------------
          ○○○○
         ○○○○
       ------------
         ○○○○○   
18个○的位置上全部是素数(1、3、5或7)，请还原此算式。
*问题分析与算法设计
    问题中虽然有18数位，但只要确定乘数和被乘数后经过计算就可确定其它的数位。
    乘数和被乘数共有5个数位，要求每个数都是质数。完全可以采用穷举的方法对乘数和被乘数进行穷举，经过判定后找出答案。但是这种方法给人的感觉是“太笨了”，因为组成的数字只是质数(4个)，完全没有必要在那么大的范围内进行穷举，只需要试探每一位数字为质数时的情况即可。
    采用五重循环的方法实现对于5个数字的穷举，前面的许多例题中都已见过。循环实现简单易行，但嵌套的层次太多，需要穷举的变量的数量直接影响到循环嵌套的层数，这种简单的实现方法缺少技巧性。本例的程序中给出了另外一种同样功能的算法，该算法的实现思想请阅读程序。
    程序中并没有直接对质数进行穷举，而是将每个质数与1到4顺序一一对应，在穷举时为处理简单仅对1到4进行穷举处理，待要判定产生的乘积是否满足条件时再利用一个数组完成向对应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上是回朔法。
*程序与程序注释
#include<stdio.h>
#define NUM 5              /*需要穷举的变量数目*/
#define C_NUM 4            /*每个变量的值的变化范围*/
int a[NUM+1];              /*为需要穷举的变量开辟的数组*/
          /*a[1]:被乘数的百位，a[2]：十位,aa[3]:个位 a[4]:被乘数的十位  a[5]:个位*/
int b[]={0,2,3,5,7};          /*存放质数数字的数组，不使用第0号元素*/
int f(long sum);

void main()
{
    int i,not_finish=1;
    i=2;                /*i:将要进行处理的元素的指针下标。设置初始值*/
    a[1]=1;             /*为第1号元素设置初始值*/
    while(not_finish)     /*not_finish:程序运行没结束标记*/
    {
        while(not_finish&&i<=NUM)
         /*处理包括第i个元素在内的后续元素，找出当前条件下的一种各个变量的一种可能的取值方法*/
            if(a[i]>=C_NUM)     /*当要处理的元素取超过规定的C_NUM时*/
                if(i==1&&a[1]==C_NUM)
                    not_finish=0;          /*若1号元素已经到C_NUM，则处理全部结束*/
                else a[i--]=0;           /*将要处理的元素置0，下标-1(回退一个元素)*/
            else a[i++]++;             /*当前元素值加1后下标指针加1*/
        if(not_finish)
        {
            long int sum1,sum2,sum3,sum4;          /*定义临时变量*/
            sum1=b[a[1>*100+b[a[2>*10+b[a[3>;   /*计算被乘数*/
                              /*利用数组的下标与质数的对应关系完成序号1到4向质数的转换*/
            sum2=sum1*b[a[5>;        /*计算乘数个位与被乘数的部分积*/
            sum3=sum1*b[a[4>;        /*计算乘数十位与被乘数的部分积*/
            if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3))
                                              /*判定两部分积是否满足题目条件*/
            if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4))
                              /*判定乘式的积是否满足题目条件*/
            {
                printf("  %d\n",sum1);          /*若满足题意，则打印结果*/              
                printf("* %d%d\n",b[a[4>,b[a[5>);
                printf("........................\n");
                printf(" %d\n",sum2);
                printf(" %d\n",sum3);
                printf("........................\n");
                printf(" %d\n",sum4);
            }
        i=NUM;                      /*为穷举下一个可能取值作预备*/
        }
    }
}
int f(long sum)           /*判定sum的每一位数字是否是质数，若不是返回0，若是返回1*/
{
    int i,k,flag;        /*flag=1:数字是质数的标记*/
    while(sum>0)            
    {
        i=sum%10;         /*取个位的数字*/
        for(flag=0,k=1;!flag&&k<=C_NUM;k++)
            if(b[k]==i)
            {
                flag=1;break;
            }
        if(!flag) return 0;
        else sum=sum/10;
    }
    return 1;
}

*运行结果
         7 7 5
       ×    3 3
     ----------
       2 3 2 5
     2 3 2 5
    -----------
     2 5 5 7 5


*思考题
    以下乘式中，A、B、C代表一确定的数字，○代表任意数字，请复原。
                      A B C                          2 8 6
                   ×    B A C                       ×   8 2 6
                -------------       答案：      ------------
                    ○○○○                       1 7 1 6
                    ○○A                          5 7 2
                ○○○B                        2 2 8 8
               -------------                 ----------------
                ○○○○○○                   2 3 6 2 3 6

-----------------------------------------------------------------------

66.除式还原(1)
    给定下列除式，其中包含5个7，其它打×的是任意数字，请加以还原。
  
                                   × 7 ×   --------------商
                            --------------
             除数------××|   ×××××-------------被除数
                               ×7 7
                            --------------
                                 × 7 ×
                                 × 7 ×
                               ----------
                                    × ×
                                    × ×
                                ----------
                                       ○
*题目分析与算法设计
    首先分析题目，由除式本身尽可能多地推出已知条件。由除式本身书已知：
    1、被除数的范围是10000到99999，除数的范围是10到99，且可以整除；
    2、商为100到999之间，且十位数字为7；
    3、商的第一位与除数的积为三位数，且后两位为77；
    4、被除数的第三位一定为4；
    5、 7乘以除数的积为一个三位数，且第二位为7；
    6、商的最后一位不能为0，且与除数的积为一个二位数。
由已知条件就可以采用穷举的方法找出结果。
*程序与程序注释
#include<stdio.h>
void main()
{
    long int i;
    int j,l;
    for(i=10000;i<=99999;i++)                     /*1. i:被除数*/
        if(i%1000-i%100==400)             /*4. 被除数的第三位一定为4*/
            for(j=10;j<=99;j++)           /*1. j: 余数*/
                if(i%j==0&&(l=i/j)%100>=70&&l%100<80&&l%10!=0&&l>100&&l<=999)
                    /*1. 可以整除&& 2.商l在100到999之间且十位数字为7&&6.商的个数不能为0*/
                    if((j*(l%10))<100&&j*(l%10)>10)    /*6. 商的个数与除数的积为二位数*/
                        if(j*7%100>=70&&j*7%100<80)   /*5. 7乘以除数的积的第二位为7*/
                            if(j*(l/100)%100==77&&j*(l/100)>100)
                                              /*商的第一位与除数的积的后两位为77*/
                                printf("%ld/%ld=%d\n",i,j,l);
}
*运行结果
     51463/53=971。 
可以看作为下列算式：

                        9 7 1
                   -------------
               5 3| 5 1 4 6 3
                    4 7 7
                  -------------
                      3 7 6
                      3 7 1
                     -----------
                        5 3
                        5 3
                     -----------
                          ○
*问题的进一步讨论
    在推出的已知条件中，几所有的条件都是十分明显的，换句话说，推出的已知条件就是对题目的平铺直叙。这种推已知条件的方法十分简单，并且行之有效。

*思考题
   下列除式中仅给定了一个8，其它打×的位置上是任意数字，请还原。
                              
                                   × 8 ×    ----------------商
                           ----------------
         除数-------×××|   ××××××---------------被除数
                              ××××
                            ---------------
                                  ×××
                                  ×××
                            ---------------
                                  ××××
                                  ××××
                            ---------------
                                        ○

-------------------------- ------------------------------

67.除式还原(2)
    下列除式中仅在商中给定了一个7，其它打×的位置全部是任意数字，请还原。
   
                                             ×7×××  -------------商
                                    ------------------ 
     除数 -------------------×××|  ××××××××  -------------被除数
                                      ××××          -------------1)
                                     ---------------  
                                          ×××        -------------2)
                                          ×××        -------------3)
                                     ---------------
                                          ××××      -------------4)
                                            ×××      -------------5)
                                     -----------------
                                              ××××  -------------6)
                                              ××××  -------------7)
                                     -----------------
                                                    0
*题目分析与算法设计
    这道题是不可能用单纯的穷举法求解的，一则计算时间太长，二则难于求出除式中各部分的值。
    对除式进行分析，改可能多地推出限制条件：
    由3)可以看出，商的第二位7乘除数得一个三位数，所以除数<=142。
    由除数乘商的第一位为一个四位数可知，商的第一位只能为8或9且除数>=112。同时商的第五位也为8或9数的前四位一定<=142*9+99且>=1000+10。
    由4)、5)、6)可以看出，4)的前两位一定为“10”；5)的第一位一定为“9”；6)的前两位一定在10到99之间；商的第四位一定为为0。
    由 5)的第一位一定是“9”和“112”<=除数<=142可知：商的第三位可能为7或8。
    由除式本身可知：商的第四位为0。
    由 1)可知：除数X商的第一位应当为一个四位数。
    由 5)可知：除数X商的第三位应当为一个三位数。
    编程时为了方便，将被除数分解：前四位用a[0]表示，第五位用a[1]，第六位用a[2]，第七八两位用a[3];除数用变量b表示；分解商：第一位用c[0]，第五位用c[2];其它的部分商分别表示为：2)的前两位为d[0]，4)的前三位为d[1]，6)的前二位为d[2]。将上述分析用数学的方法综合起来可以表示为：
        被除数：        1010<=a[0]<=1377  0<=a[1]<=9
                           0<=a[2]<=9     0<=a[3]<=99
        除数：           112<=b   <=142
        商：               8<=c[0]<=9     7<=c[1]<=8   8<=c[2]<=9
        2)的前两位：      10<=d[0]<=99
        4)的前三位：     100<=d[1]<b
        6)的前两位：      10<=d[2]<=99
        1)式部分积：        b*c[0]>1000
        5)式部分积：     100<b*c[1]<1000
*程序与程序注释
#include<stdio.h>
void main()
{
   int a[4],b,c[3],d[4],i=1;
   for(a[0]=1010;a[0]<=1377;a[0]++)
      for(b=112;b<=142;b++)
         for(c[0]=8;c[0]<=9;c[0]++)
            if(b*c[0]>1000&&(d[0]=a[0]-b*c[0])>=10&&d[0]<100)
               for(a[1]=0;a[1]<=9;a[1]++)
                  if((d[1]=d[0]*10+a[1]-b*7)>=100&&d[1]<b)
                     for(a[2]=0;a[2]<=9;a[2]++)
                        for(c[1]=7;c[1]<=8;c[1]++)
                           if(b*c[1]<1000&&(d[2]=d[1]*10+a[2]-b*c[1])>=10&&d[2]<100)
                              for(a[3]=0;a[3]<=99;a[3]++)
                                 for(c[2]=8;c[2]<=9;c[2]++)
                                    if(d[2]*100+a[3]-b*c[2]==0)
                                    {
                                       printf("No%2d:",i++);
                                       printf("%d%d%d%d%d/",a[0],a[1],a[2],a[3]/10,a[3]%10);
                                       printf("%d=",b);
                                       printf("%d%d%d%d%d\n",c[0],7,c[1],0,c[2]);
                                    }
}
*运行结果：
No 1:12128316/124=97809

*思考题
下列除式中“×”所在的位置全部是任意数字，请还原。
                             ×××××
                    -------------------
            ××× |   ××××××××
                       ××××
                     ------------------
                           ××××
                             ×××
                        ---------------
                               ×××
                               ×××
                            -----------
                               ××××
                               ××××
                            -----------
                                     0