解题思路

数字1~9分别出现且只出现一次

这句话其实就是告诉我们需要用1~9的全排列，‘+’和‘/’无非就是以不同的位置插入到全排列中，然后验证分成的3个数是否满足题意。

代码实现

使用库函数版

#include<iostream> #include<algorithm> using namespace std; int main() { int n; cin >> n; int cnt = 0; string str("123456789");// = "123456789"; do { for(int i = 1; i <= 7; ++i) //加号前长度 { string str_piece_one = str.substr(0, i); int first_num = atoi(str_piece_one.c_str()); if(first_num >= n) break; for(int j = 1; j <= (9 - i - 1); ++j) //除号前长度 { string str_piece_two = str.substr(i, j); int secone_num = atoi(str_piece_two.c_str()); string str_piece_three = str.substr(i + j, 9 - i - j); int third_num = atoi(str_piece_three.c_str()); if(secone_num % third_num == 0 && (first_num + secone_num / third_num == n)) ++cnt; } } } while(next_permutation(str.begin(), str.end())); cout << cnt << endl; return 0; }

底层实现版

#include<iostream> #include<cstring> using namespace std; char str[100], strTmp[100]; char *pstr; int n; int vis[100], box[100]; int size = 0, cnt = 0, ans = 0; const char * substring(int begin, int length) { strcpy(strTmp, str); pstr = &strTmp[begin]; strTmp[begin + length] = '\0'; return pstr; } void judge(char str[]) { for(int i = 1; i <= 7; ++i) { const char *str_piece_one = substring(0, i); int first_num = atoi(str_piece_one); for(int j = 1; j <= (9 - i - 1); ++j) { const char *str_piece_two = substring(i, j); int secone_num = atoi(str_piece_two); const char *str_piece_three = substring(i + j, 9 - i - j); int third_num = atoi(str_piece_three); if(secone_num % third_num == 0 && (first_num + secone_num / third_num == n)) ++ans; } } } void dfs(int index) { if(index == 10) { for(int i = 1; i<= cnt; ++i) { str[i - 1] = box[i] + '0'; } judge(str); return ; } for(int i = 1; i <= 9; ++i) { if(!vis[i]) { vis[i] = 1; box[++cnt] = i; dfs(index + 1); vis[i] = 0; --cnt; } } } int main() { cin >> n; dfs(1); cout << ans << endl; }