时间限制: 1 Sec 内存限制: 128 MB
提交: 349 解决: 126
[提交][状态]
题目描述
看下面的算式：
□□ x □□ = □□ x □□□
它表示：两个两位数相乘等于一个两位数乘以一个三位数。
如果没有限定条件，这样的例子很多。
但目前的限定是：这9个方块，表示1~9的9个数字，不包含0。
该算式中1至9的每个数字出现且只出现一次！
比如：
46 x 79 = 23 x 158
54 x 69 = 27 x 138
54 x 93 = 27 x 186
.....
请编程，输出所有可能的情况！
注意：左边的两个乘数交换算同一方案，不要重复输出！
（乘号用英文字母x代替，符号与数字之间有一个空格）
输入
输出
提示
1.
#include<stdio.h>
#include<string.h>
bool used[10]={false};
int a[10];
int getv(int s,int len)
{
int ret=0,i;
for(i=s;i<s+len;i++)ret=ret*10+a[i];
return ret;
}
void DFS(int deep,int n)
{
int i,x,b,c,d;
if(deep==n)
{
x=getv(0,2);
b=getv(2,2);
c=getv(4,2);
d=getv(6,3);
if(x>b)return ;
if(x*b==c*d)
{
printf("%d x %d = %d x %d\n",x,b,c,d);
}
return ;
}
for(i=1;i<10;i++)
{
if(used[i])continue;
used[i]=true;
a[deep]=i;
DFS(deep+1,n);
used[i]=false;
}
}
int main()
{
DFS(0,9);
return 0;
}
2.暴力
#include<stdio.h>
int main()
{
int i1,i2,i3,i4,i5,i6,i7,i8,i9,k,p,j=0;
int a1[30]={0},a2[30]={0},a3[30]={0},a4[30]={0},a5[30]={0},a6[30]={0},a7[30]={0},a8[30]={0},a9[30]={0};
bool mark=false;
for(i1=1;i1<10;i1++)
for(i2=1;i2<10;i2++)
{
if(i2==i1)continue;
for(i3=1;i3<10;i3++)
{
if(i3==i1||i3==i2)continue;
for(i4=1;i4<10;i4++)
{
if(i4==i1||i4==i2||i4==i3)continue;
for(i5=1;i5<10;i5++)
{
if(i5==i1||i5==i2||i5==i3||i5==i4)continue;
for(i6=1;i6<10;i6++)
{
if(i6==i1||i6==i2||i6==i3||i6==i4||i6==i5)continue;
for(i7=1;i7<10;i7++)
{
if(i7==i1||i7==i2||i7==i3||i7==i4||i7==i5||i7==i6)continue;
for(i8=1;i8<10;i8++)
{
if(i8==i1||i8==i2||i8==i3||i8==i4||i8==i5||i8==i6||i8==i7)continue;
for(i9=1;i9<10;i9++)
{
if(i9==i1||i9==i2||i9==i3||i9==i4||i9==i5||i9==i6||i9==i7||i9==i8)continue;
int flag1=(i1*10+i2)*(i3*10+i4);
int flag2=(i5*10+i6)*(i7*100+i8*10+i9);
if(flag1==flag2)
{
a1[j]=i1;a2[j]=i2;a3[j]=i3;a4[j]=i4;a5[j]=i5;a6[j]=i6;
j++;
for(p=0;p<=j;p++)
{ if(a1[p]==i3&&a2[p]==i4&&a3[p]==i1&&a4[p]==i2&&a5[p]==i5&&a6[p]==i6)
{
mark=true;
// printf("in\n");
break;
} }
if(mark==false&&j>0)
{
printf("%d%d*%d%d=%d%d*%d%d%d\n",i1,i2,i3,i4,i5,i6,i7,i8,i9);
}
mark=false;
}
}
}
}
}
}
}
}
}
/*
for(p=0;p<=j;p++)
printf("%d %d\n",a1[p],j);
*/
return 0;
}
