题目描述
看下面的算式：
□□ 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
…..
请编程，输出所有可能的情况！
注意：
左边的两个乘数交换算同一方案，不要重复输出！
不同方案的输出顺序不重要
输入
暂无
输出
暂无
样例输入
暂无
样例输出
暂无
参考代码
#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node
{
long w,s,num;
}
node;
node a[N];
long f[N],b[N],q[N],n;
int bigger(node x,node y)
{
if (x.w!=y.w) return (x.w>y.w); else return (x.s<y.s);
}
void sort(long left,long right)
{
long i,j;
node x,t;
i=left;
j=right;
x=a[(i+j)/2];
while (i<=j)
{
while (bigger(x,a[i])) i++;
while (bigger(a[j],x)) j--;
if (i<=j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
i++;
j--;
}
}
if (left<j) sort(left,j);
if (i<right) sort(i,right);
}
int main()
{
long i,j,k,max;
i=1;
while (scanf("%ld%ld",&a[i].w,&a[i].s)==2) a[i].num=i++;
n=i-1;
sort(1,n);
for (i=1;i<=n;i++)
{
f[i]=1;
b[i]=i;
}
for (i=1;i<=n;i++)
for (j=1;j<i;j++)
if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i])
{
f[i]=f[j]+1;
b[i]=j;
}
max=0;
for (i=1;i<=n;i++)
if (f[i]>max)
{
max=f[i];
k=i;
}
printf("%ldn",max);
q[1]=a[k].num; i=1;
while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
for (i=max;i>=1;i--)
printf("%ldn",q[i]);
return 0;
}
解析
暂无
