解题心得:
1、在明确使用DFS之后一定要找到递归函数的出口、方向,以及递归的点(在某个情况下开始递归)(void 也可以return,但是没有返回值)。递归时也要有递归的方向,最后都能够达到递归的出口。
2、在DFS递归的出口处可以用一个数组来进行记录最终的结果,双向递归可以用一个二位数组来记录结果。
3、在循环中,尽量不要多次使用一个变量(不然找错找得你哭瞎双眼。伤心。。。。。。)。
4、先找思路再写程序,写程序时小心变量是否用对,数组是否越界,变量是否初始化,特别实在循环中时。当循环出现多层的时候,检查关键的步骤是否放对循环。
5、找错找得哭瞎双眼的时候一定要反思总结啊。
Description
最近小Y迷上了数学,总是在思考各种数学问题。有一天,他不小心把墨水洒在草稿纸上。他现在能看到的是“2?3?1?4”(?表示看不清的地方)。小Y的记忆力不错,他知道:
1、每个?只会是“+”、“-”,“=”三个符号之一。
2、总共有且仅有一个“=”。
3、原式一定是一个等式。如“2+3-1=4”
现在他突然想知道,有多少种可能性,满足上面3个要求。
Input
多组输入。
每组第一行有一个数字n。表示小Y从左到右,一共可以看到n个数字。(2<=n<=15)
每组第二行有n个数字。分别表示这n个数字是什么。保证每个数字都是非负整数,且小于10^7。
Output
对于每组,输出一行,这一行只有一个数字,表示有多少种可能性满足题意。
Sample Input
Raw
4
2 3 1 4
4
1 1 1 1
Sample Output
Raw
2
6
Hint
数字间一定有且仅有一个符号,第一个数字前没有符号。
#include<stdio.h>
int a[16],i,j,jie[2][30000],k,l,n,d[2],b,z;//命名混乱
void DFS(int n,int sum)
{
if(n == k)//递归的出口
{
jie[l][d[l]++] = sum; //二维数组记录最终的结果
return ; //void也可以return 但没有值
}
DFS(n+1,sum + a[n+b]); //‘+’
DFS(n+1,sum - a[n+b]); //‘-’
}
int main()
{
int num;
while(scanf("%d",&n)!=EOF)
{
num = 0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
b = 0;
k = i;
l = 0;
d[0] = 0;
DFS(1,a[0]);
b = i;
k = n - i;
l = 1;
d[1] = 0;
DFS(1,a[i]);
for(z=0;z<d[0];z++) //不要使用i,找瞎了双眼
{
for(j=0;j<d[1];j++)
{
if(jie[0][z] == jie[1][j])
num++; //记录个数
}
}
}
printf("%d\n",num);
}
}