1983 等式问题

系统管理员 2022-06-18 09:00 171阅读 0赞

题目描述 Description

有一个未完成的等式：1 2 3 4 5 6 7 8 9=N 空格（1前面没有空格）内可以填入+,-,也可以不填。 编程找出输入某个整数 N 后使等式成立的所有方案的总数。保证有解。

输入描述 Input Description

输入一个数N。

输出描述 Output Description

输出一个数。所有的方案数。

样例输入 Sample Input

108

样例输出 Sample Output

15

数据范围及提示 Data Size & Hint

递归遍历+-和空格的情况，空格就是将两端的数进行连接， -2和3用空格连接起来是-23，而不是-2\*10+3，所以要判断前一个是否为负数的情况

#include<iostream>
    using namespace std;
    int n,cnt=0;
    int a[8]={2,3,4,5,6,7,8,9};
    int b[8];
    int check()
    {
    	int t[9]={0},k=0,c=0,i,s=0;
    	t[0]=1;
    	for (i=0;i<8;i++)
    	{
    		if(b[i]==0)
    		{
    			t[++c] = a[k++];
    		}
    		else if (b[i]==1)
    		{
    			t[++c] = -1*a[k++];  
    		}
    		else
    		{
    			t[c] = t[c] < 0 ?  t[c]*10 - a[k] : t[c]*10 + a[k]; //判断是否为负数
    			k++;
    		}
    	}
    	
    	for (i=0; i<=c; i++)
    	{
    		s+=t[i];
    	}
    	if (s==n)
    	 return 1;
    	return 0;
    }
    void dfs(int x)
    {
    	int i;
    	if (x == 8)
    	{
    		if (check())
    		{
    			cnt++;
    		}
    		 return ;
    	}
    	for (i=0; i<3; i++) //0+ 1- 2空格 
    	{
    		b[x] = i;
    		dfs(x+1);
    	}
    }
    int main()
    {
    	cin>>n;
    	dfs(0);
    	cout<<cnt;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关求等式成立

![alt][] 624 \ 13 \ 9 \ 14 \ 132 \ 54 符号Punctuation替代上面的 \ 设法等式成立！ from itertools

小咪咪/ 2024年04月01日 15:24/ 0 赞/ 83 阅读

相关神奇的等式

大贤者福尔在研究数学问题时，发现有一些自然数能够构成一个形如下式的等式，颇为神奇。![x0x1x2x3x4 / x5x6x7x8x9 = N][x0x1x2x3x4 _ x5x

电玩女神/ 2022年10月12日 12:20/ 0 赞/ 213 阅读

相关啊哈！算法—火柴棍等式

现手中有m(m<=24)个火柴棍，希望拼出A+B=C等式。等式中的A、B、C均为火柴棍拼出来的整数（若该数非0，则最高位不能为0）。注意： 1、加号与等号各自需要2根火

小灰灰/ 2022年08月21日 12:47/ 0 赞/ 208 阅读

相关立方和等式

考虑方程式：a^3 + b^3 = c^3 +d^3 其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整数。这个方程有很多解。比如： a = 1，b=12，

蔚落/ 2022年08月02日 07:19/ 0 赞/ 164 阅读

相关等式变换

第三题：等式变换输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。 1 2 3 4 5 6 7 8 9 = X 比如

左手的ㄟ右手/ 2022年07月21日 00:29/ 0 赞/ 178 阅读

相关补全等式(DFS,全排列)

下图中，每个方块代表 1…13 中的某一个数字，但不重复。 ![这里写图片描述][SouthEast] 例如： 1×2+9×7=13×5 10×8+12×3=1

迈不过友情╰/ 2022年06月18日 09:14/ 0 赞/ 196 阅读

相关 1983 等式问题

题目描述 Description 有一个未完成的等式：1 2 3 4 5 6 7 8 9=N 空格（1前面没有空格）内可以填入+,-,也可以不填。编程找出输入某个整数 N

系统管理员/ 2022年06月18日 09:00/ 0 赞/ 172 阅读

相关算法六：等式

免费版：[算法六：等式][Link 1] 描述有n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。输入第

r囧r小猫/ 2022年05月24日 06:59/ 0 赞/ 167 阅读

相关 NCSTOJ-1403 : 等式

[1403 : 等式][1403 _] Description n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。

拼搏现实的明天。/ 2022年03月02日 07:22/ 0 赞/ 194 阅读

相关入门OJ 6247【算式等式】

描述　　给你N个数字，每个数字均不相同，你可以取其中任意个数字相加，如果所得到的结果在给出的数列中也能找到，则输出这个等式输入输出格式输入

分手后的思念是犯贱/ 2021年11月10日 08:24/ 0 赞/ 225 阅读