等式变换

左手的ㄟ右手 2022-07-21 00:29 178阅读 0赞

第三题：等式变换

输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。

1 2 3 4 5 6 7 8 9 = X

比如：

12-34+5-67+89 = 5

1+23+4-5+6-7-8-9 = 5

请编写程序，统计满足输入整数的所有整数个数。

输入：       正整数，等式右边的数字

输出：       使该等式成立的个数

样例输入：5

样例输出：21

#include<iostream>
    #include<vector>
    #include<string>
    #include<map>
    #include<algorithm>
    using namespace std;
    int vec2num(int st,int en)
    {
    	int n(0);
    	for (int i = st; i < en; i++)
    		n = 10 * n + i + 1;
    	return n;
    }
    void solve(int x,vector<int>op, vector<vector<int>>&re)
    {
    	if (op.empty())
    	{
    		for (int i = 1; i < 9; i++)
    		{
    			vector<int>oper,oper1;
    			oper.push_back(i);
    			int n = vec2num(i, 9);
    			solve(x -n , oper, re);
    			oper1.push_back(-i);
    			solve(x + n, oper1, re);
    		}
    	}
    	else
    	{
    		if (x == vec2num(0, abs(op.back())))
    			re.push_back(op);
    		else
    		{
    			for (int i = 1; i<abs(op.back());i++)
    			{
    				vector<int>oper(op), oper1(op);
    				oper.push_back(i);
    				int n = vec2num(i, abs(op.back()));
    				solve(x - n, oper, re);
    				oper1.push_back(-i);
    				solve(x + n, oper1, re);
    			}
    		}
    	}
    }
    
    int main()
    {
    	int x(0);
    	while (cin >> x)
    	{
    		vector<vector<int>>re;
    		vector<int>op;
    		solve(x, op, re);
    		cout << re.size() << endl;
    	}
    	return 0;
    }

思路：递归方法解决。开始等式右边是x，每次从等式末尾截取几位数字组成一个操作数n，其前面的操作符取正负，然后将这个操作数n移到等式右边，这样就要在剩下的数添加操作符使其值等于x+/-n；然后又回到之前的解法，递归

发表评论取消回复

表情：

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

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

相关阅读

相关求等式成立

![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 阅读

相关华为校招一道上机题：等式变换

参考来源：[http://blog.csdn.net/Hackbuteer1/article/details/39253767][http_blog.csdn.net_Hack

傷城~/ 2022年09月29日 12:55/ 0 赞/ 170 阅读

相关立方和等式

考虑方程式：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 赞/ 179 阅读

相关 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 赞/ 168 阅读

相关 NCSTOJ-1403 : 等式

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

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

相关图像变换——等距变换，相似变换，仿射变换，投影变换

[https://blog.csdn.net/hailiannanhai/article/details/80742517][https_blog.csdn.net_haili

﹏ヽ暗。殇╰゛Y/ 2022年01月27日 02:45/ 0 赞/ 412 阅读

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

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

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