本文主要是介绍五个整数任意组合(加减)得到1~122之间的数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
/问题描述
/*
给定五个整数1,3,9,27,81,这个五个整数可以任意组合进行加减(可以是五个数中的部分相加),这五个数组合进行加减可以得到1~122之间的数, 任意输入1~122之间的一个整数,得到其相应的组合,并且按照由大到小的顺序输出其表达式
示例输入输出
输入:5
输出:9-3-1
*/
之前写过一个华为上机题,五个数字相加任意组合成1~122之间的数,这几天看到了,感觉当时写的方法太挫了,居然是利用多层循环,那如果有更多数,或者数字个数不确定,那不就没辙了。
利用循环实现:
对于这个数字任意组合,很容易想到的就是排列组合(输出n个数字的所有排列)。类似,就可以用回溯的方法来实现。这里回溯其实也就是直接搜索,执行过程与利用多层循环实质相同,但对于解决问题比多层循环的挫办法要实用得多。
代码与求n个数字的排列类似,也是到达最里面一层判断是否满足条件,否则返回上一层,并更改这一层的状态,继续往下一层走。
- #include <iostream>
- using namespace std;
- int weights[5] = {81,27,9,3,1};
- void combine(int n, int sign[], int value)
- {
- if (n == 5)
- {
- int sum = 0;
- for (int i = 0; i < 5; i++)
- {
- int tmp = weights[i]*sign[i];
- sum += tmp;
- }
- if (sum == value)
- {
- //输出
- bool flag = false;
- for (int j = 0; j < 5; j++)
- {
- if (sign[j] != 0)
- {
- if (sign[j] == 1)
- {
- if (flag)
- {
- cout << "+";
- }
- cout << weights[j];
- }
- else if (sign[j] == -1)
- {
- cout << "-" << weights[j];
- }
- flag = true;
- }
- }
- cout << endl;
- }
- }
- else
- {
- sign[n] = 0; combine(n+1, sign, value);
- sign[n] = 1; combine(n+1, sign, value);
- sign[n] = -1; combine(n+1, sign, value);
- }
- }
- int main()
- {
- int Value;
- int sign[5];
- while(cin>>Value)
- {
- combine(0, sign, Value);
- }
- return 0;
- }
当输入的数不再是5个二是任意个数时该怎么解决(留个小问题)??
这篇关于五个整数任意组合(加减)得到1~122之间的数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!