首页 > 考试 > 其他 >

hdu2266How Many Equations Can You Find(简单深搜)c语言

2017-08-16

hdu2266How Many Equations Can You Find(简单深搜)c语言,题目大意:输入一段数字,在这段数字中任意添加加号,减号,使其能够等于结果。

hdu2266How Many Equations Can You Find(简单深搜)c语言,题目大意:输入一段数字,在这段数字中任意添加加号,减号,使其能够等于结果

思路:直觉上直接想到枚举尝试(类似于算24分,只不过牌变多了,运算规则变简单了),但是用过的牌(数字)不能重复使用,于是就可以用深搜解题。

搜的范围大概是:得到一个数字,1.该数字加到sum中 2.该数字和sum作差 3.该数字啥都不做进入下一个搜索(不做的话要把他成为数字的尾部)

附代码:

#include
#include
#include
#include
using namespace std;

char a[20];
int result,cnt;

void dfs(int k,int sum)
{
	if(k==strlen(a))
	{
		if(sum==result)
			cnt++;
		return ;
	}
	int i,j,s;
	for(i=k;i0) //这个判断是必要的,因为当k为第一个数字时,不能做啥操作,即加号没影响,但减号有影响
		dfs(i+1,sum-s);
	}
	return ;
}

int main()
{
	while(~scanf("%s %d",a,&result))
	{
		cnt=0;
		dfs(0,0);
		printf("%d\n",cnt);
	}
	return 0;
}


相关文章
最新文章
热点推荐