读书人

帮忙解决一个算法解决方法

发布时间: 2012-05-27 05:42:30 作者: rapoo

帮忙解决一个算法
把1到9这9个数分解为一个两位数和一个三位数和一个四位数(且这些数字不重复)使得这个两位数乘以这个三位数等于这个四位数!

[解决办法]
整理一下想法:
设这个算式为:
A B C
× D E
——————
* * *
* * *
——————
F G H I

1、两个因数中的个位都不能是5和1;
2、积是四位数,所以D乘ABC不能进位;
3、可以确定ACDE的取值范围不能是6、7、8、9,否则DE取最小16A取最小7那么16× 700=11200是五位数,所以ACDE的取值范围是:1、2、3、4,
3、AE不能同时是3和4,DE先从取最小的值12,AC取4和3,则出现算式:
4B3× 12
4、尝试可得 483×12=5796 符合条件。
12×483=5796
18×297=5346
27×198=5346
28×157=4396
39×186=7254
42×138=5796
48×159=7632
[解决办法]
1楼的解法虽然很好,但不适合程序来做
直接穷举就ok了:

C/C++ code
#include <stdio.h>int main() {    int i,j,k,a[9],*p=a;    int b[10]={1,2,3,5,7,11,13,17,19,23};    int multiOK =2*3*5*7*11*13*17*19*23;    int x =0;    for(i=12;i<=98;i++)     {        for(j=123;j<=987;j++)         {            int multi=1;            k=i*j;            if (k <1000 || k>10000)                continue;            *p=j/100;            *(p+1)=j/10%10;            *(p+2)=j%10;            *(p+3)=i/10;            *(p+4)=i%10;            *(p+5)=k/1000;            *(p+6)=k/100%10;            *(p+7)=k/10%10;            *(p+8)=k%10;            for (x=0;x<9;x++)                  multi *=b[a[x]];            if (multi == multiOK )            {            printf("%d×%d=%d\n",j,i,k);            }        }    }    getchar();    return 0;}
[解决办法]
C/C++ code
#include <stdio.h>#include<string.h>void Permutation(char list[], int k, int m){    if (k == m)    {        int a,b,c;        sscanf(list,"%2d%3d%4d",&a,&b,&c);        if(c==a*b)printf("%d X %d = %d\n",a,b,c);    }    else    {        char s[10];        for (int i=k; i <= m; i++)        {            int t;            t=list[k],list[k]=list[i],list[i]=t;            strcpy(s,list+k);            Permutation(list, k+1, m);            strcpy(list+k,s);        }    }}void main(){    char s[]="123456789";    Permutation(s, 0, 8);} 

读书人网 >C语言

热点推荐