問題描述

編寫一個在1，2，…，9（順序不能變）數字之間插入+或-或什么都不插入，使得計算結果總是100的程序，并輸出所有的可能性。例如：1 + 2 + 34 – 5 + 67 – 8 + 9 = 100。

問題分析

這時我最近偶然看到的一道題目，發現實現起來還確實有些麻煩，所以把實現的過程記錄下來。
這種要羅列出所有結果的問題，我一般是采用回溯法解決的，說的通俗一點就是暴力解法，去遍歷所有的情況。
這個問題有一點比較難處理的地方就在于有這個“什么都不插入”這個選項，所以干脆單獨拎出來解決。也就是先把1-9這9個數組相互組合，形成一個數組，比如：

{1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,89} {1,2,3,4,5,6,78,9} {1,2,3,4,5,6,789} ...

在分組的過程當中，由于問題的特殊性（要求結果為100），我們會發現像

{123456,789}

這樣位數特別大的是不可能得到100這樣的結果的，一個最小的6位數和一個最大的3位數的差都有

100000?999=99001
所以本問題中不用考慮把1-9劃分成6位數及以上的情況。
將1-9劃分好之后，接下來要做的就是把”+”和”-“填到劃分的數字之間了，比如

劃分成{1,2,3,4,5,6,7,8,9}時有： 1+2+3+4+5+6+7+8+9 1+2+3+4+5+6+7+8-9 1+2+3+4+5+6+7-8+9 ... 劃分成{1,2,3,4,5,6,7,89}時有： 1+2+3+4+5+6+7+89 1+2+3+4+5+6+7-89 ... 其他情況就不列舉了，相信應該看明白了

基于這樣的思路，用C++對該想法進行了實現。

代碼展示

下面程序可以將結果100改成其他的整數，都是適用的。

#include <iostream> #include <math.h> #include <vector> #include <string>using namespace std;class Solution{ private:vector<string> res;vector<int> nums;vector<int> eles;private:void _compute(vector<int> vec, int index, int target, string &s){if (index == vec.size()){if (0 == target)res.push_back(s + "=100");return;}//分“+”和“-”兩種情況討論for (int i = 0; i < 2; i++){if (i == 0){string tempStr = s + "+" + to_string(vec[index]);_compute(vec, index + 1, target - vec[index], tempStr);}else if (i == 1){string tempStr = s + "-" + to_string(vec[index]);_compute(vec, index + 1, target + vec[index], tempStr);}}return;}//用來得到1-9的不同整數組合，比如{123, 456, 789}，本質是將“”這個空符號加入到數之間void _recursion(int index, int target){if (index == 9){string s = to_string(eles[0]);_compute(eles, 1, target - eles[0], s);return;}//為了問題的泛化采用i <= 9，如果針對結果為100的可以改成i <= 5for (int i = 1; i <= 9; i++){if (index + i > 9)break;int temp = 0;//求得分解出來的每個元素的值for (int j = 0; j < i; j++){temp += nums[index + j] * pow(10, i - j - 1);}eles.push_back(temp);_recursion(index + i, target);eles.pop_back();}return;}public:Solution(){nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };}vector<string> recursion(int index, int target){_recursion(index, target);return res;} };int main() {Solution s;vector<string> res = s.recursion(0, 100);cout << "共有" << res.size() << "種情況" << endl;for (string s : res){cout << s << endl;}return 0; }

總結

以上是生活随笔為你收集整理的利用回溯法解决1-9之间添加+或-或使得运算结果为100的问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。