ZOJ1204——Additive equations(DFS)

Additive equations

Description
We all understand that an integer set is a collection of distinct integers. Now the question is: given an integer set, can you find all its addtive equations? To explain what an additive equation is, let's look at the following examples:
1+2=3 is an additive equation of the set {1,2,3}, since all the numbers that are summed up in the left-hand-side of the equation, namely 1 and 2, belong to the same set as their sum 3 does. We consider 1+2=3 and 2+1=3 the same equation, and will always output the numbers on the left-hand-side of the equation in ascending order. Therefore in this example, it is claimed that the set {1,2,3} has an unique additive equation 1+2=3.
It is not guaranteed that any integer set has its only additive equation. For example, the set {1,2,5} has no addtive equation and the set {1,2,3,5,6} has more than one additive equations such as 1+2=3, 1+2+3=6, etc. When the number of integers in a set gets large, it will eventually become impossible to find all the additive equations from the top of our minds -- unless you are John von Neumann maybe. So we need you to program the computer to solve this problem.
Input
The input data consists of several test cases.
The first line of the input will contain an integer N, which is the number of test cases.
Each test case will first contain an integer M (1<=M<=30), which is the number of integers in the set, and then is followed by M distinct positive integers in the same line.
Output
For each test case, you are supposed to output all the additive equations of the set. These equations will be sorted according to their lengths first( i.e, the number of integer being summed), and then the equations with the same length will be sorted according to the numbers from left to right, just like the sample output shows. When there is no such equation, simply output "Can't find any equations." in a line. Print a blank line after each test case.
Sample Input
3
3 1 2 3
3 1 2 5
6 1 2 3 5 4 6
Output for the Sample Input
1+2=3
Can't find any equations.
1+2=3
1+3=4
1+4=5
1+5=6
2+3=5
2+4=6
1+2+3=6

题目大意：

　　　　给定一个数列找出其中的加法等式x1+x2+x3+..xn=y(其中x1，x2，x3，xn，y属于数列) (n>=2)

解题思路：

　　　　可以将数列看做一个无向完全图（即每个顶点都指向其他所有顶点）。用DFS搜索，将符合题目要求的存起来，再排序输出即可。具体细节请看代码（语死早，没办法^^）

　　　　细节：

　　　　　　1）符合要求的等式比能保证x1<x2<x3<<xn<y

　　　　　　2）搜索前排好序，由小到大。根据1）可知只搜素比当前元素靠后的元素是否等于当前递归的总和即可。

Code:

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #define MAXN 30000

 using namespace std;

 int a[],flag[];

 int N;

 struct s //用于存等式用的结构体，记录等式中的各个元素和元素个数（最后一个元素必为等号右边元素）

 {

     int a[];

     int lenth;

 } str[MAXN];

 int k=;

 void output() //输出函数，k表示搜索后的符合要求的等式的数量。

 {

     if (k==) printf("Can't find any equations.\n\n");

     else

     {

         for (int i=; i<=k; i++)

         {

             int j;

             printf("%d",str[i].a[]);

             for (j=; j<str[i].lenth; j++)

                 printf("+%d",str[i].a[j]);

             printf("=%d\n",str[i].a[j]);

         }

         printf("\n");

     }

 }

 void input()//DFS到符合要求的等式，将等式的各个元素存入数组

 {

     k++;

     str[k].lenth=;

     int t=;

     for (int i=; i<=N; i++)

         if (flag[i]!=) str[k].a[t++]=a[i],str[k].lenth++;

 }

 void DFS(int i,int sum) //flag[i]==1表示当前DFS中 i被使用了。

 {                       //当递归到符合条件的时候可根据当前的flag数组情况来获取等式的相关元素

     sum+=a[i];

     if (sum>a[N]) return ;

     for (int j=i+; j<=N; j++)

         if (sum==a[j])

         {

             flag[j]=;

             input();

             flag[j]=;

         }

     for (int j=i+; j<=N; j++)

     {

         flag[j]=;

         DFS(j,sum);

         flag[j]=;

     }

 }

 bool cmp(struct s a,struct s b)//根据题目要求排序，保证短的在前，相同长度情况下数字小的在前

 {

     if (a.lenth!=b.lenth) return a.lenth<b.lenth;

     for (int i=; i<=a.lenth; i++)

         if (a.a[i]!=b.a[i]) return a.a[i]<b.a[i];

 }

 int main()

 {

     int T;

     cin>>T;

     while (T--)

     {

         memset(flag,,sizeof(flag));

         memset(a,,sizeof(a));

         k=;

         cin>>N;

         for (int i=; i<=N; i++)

             cin>>a[i];

         sort(a+,a++N);

         for (int i=; i<=N; i++)

         {

             flag[i]=;

             DFS(i,);

             flag[i]=;

         }

         sort(str+,str+k+,cmp);

         output();

     }

     return ;

 }

巴特西

ZOJ1204——Additive equations(DFS)

最新文章

热门文章