寻找表达式
题目描述
给定一个只由0,1,2,3,4,5,6,7,8,9组成的字符串，要求你在字符之间添加"+"或者"-",例如给定的字符串是"12345"，你可以找到一个表达式"123+4-5"，现在给一个整数N，请找出所有的表达式使得表达式的值为N。两个相邻的字符之间最多只能使用一个符号。
输入格式
输入包含多组测试数据，每组测试数据占一行，是一个字符串和一个整数N。
其中字符串的长度最大为12，N的最大值为999999999999
输出格式
对于每组测试数据，输出能够满足条件的表达式的个数。
输入输出样例
输入样例1：
123456789 3
21 1
输出样例1：
18
1
【耗时限制】1000ms 【内存限制】128MB
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
#include <sstream>
#include <cstring>
#include <algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
const int N=15;
const char op[3]={' ','+','-'};
int n,a[N];
char c[N];
bool check(){
int sum=0;
int num=a[1];
char pre='+';
for(int i=1;i<=n-1;i++){
if(c[i]==' '){
num=num*10+a[i+1];
}else if(c[i]=='+'||c[i]=='-'){
if(pre=='+')sum+=num;
else sum-=num;
num=a[i+1];
pre=c[i];
}
}
if(pre=='+')sum+=num;
else sum-=num;
return sum==0;
}
void print(){
for(int i=1;i<=n-1;i++)printf("%d%c",a[i],c[i]);
printf("%d\n",a[n]);
}
void dfs(int cur){
if(cur==n){
if(check())print();
return ;
}
for(int i=0;i<3;i++){
c[cur]=op[i];
dfs(cur+1);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)a[i]=i;
dfs(1);
return 0;
}
你可以这样子做
```c++
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
#include <sstream>
#include <cstring>
#include <algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
const int N=20;
const char op[3]={' ','+','-'};
int n,a[N+10],d,cnt;
char c[N+10];
bool check(){
int sum=0;
int num=a[1];
char pre='+';
for(int i=1;i<=n-1;i++){
if(c[i]==' ')num=num*10+a[i+1];
else{
if(pre=='+')sum+=num;
if(pre=='-')sum-=num;
num=a[i+1];
pre=c[i];
}
}
if(pre=='+')sum+=num;
if(pre=='-')sum-=num;
return sum==d;
}
void dfs(int cur){
if(cur==n){
if(check())cnt++;
return ;
}
for(int i=0;i<3;i++){
c[cur]=op[i];
dfs(cur+1);
}
}
int main(){
string s;
while(cin>>s>>d){
cnt=0;
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
n=s.size();
for(int i=1;i<=n;i++) a[i]=(s[i-1]-'0');
dfs(1);
printf("%d\n",cnt);
}
return 0;
}
```
不知道你这个问题是否已经解决, 如果还没有解决的话:// 传入数据，在main里面调用该方法
public static int demo13(int n) {
int max, min;
if (n < 1000) {
return -1;
}
if (n == 6174) {
return 1;
} else {
int[] numbers = new int[4];
numbers[0] = n % 10;
numbers[1] = n / 10 % 10;
numbers[2] = n / 100 % 10;
numbers[3] = n / 1000;
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - i - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
min = numbers[0] * 1000 + numbers[1] * 100 + numbers[2] * 10 + numbers[3] * 1;
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - i - 1; j++) {
if (numbers[j] < numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
max = numbers[0] * 1000 + numbers[1] * 100 + numbers[2] * 10 + numbers[3] * 1;
return 1 + demo13(max - min);
}
}
优化后问题：
问题标题：给定数字字符串，寻找组合后的所有表达式
问题描述：
给定一个只由0到9组成的字符串，要求您在字符之间添加"+"或"-"，例如给定的字符串是"12345"，您可以找到一个表达式"123+4-5"，现在给一个整数N，请找出所有的表达式，使得表达式的值为N。两个相邻的字符之间最多只能使用一个符号。
输入格式：
输入包含多组测试数据，每组测试数据占一行。其中字符串的长度最大为12，N的最大值为999999999999。
输出格式：
对于每组测试数据，输出能够满足条件的表达式的个数。
样例输入：
123456789 3 21 1
样例输出：
18 1
提示：
注意输入输和出格式。
用递归的方法生成每个可能的表达式，并计算表达式的值。
注意保证表达式合法性，即相邻字符之间最多只能使用一个符号。
时间限制为1000ms，内存限制为128MB。
参考代码：
def find_expression(expressions, start, curr, target, s):
if start == len(s):
# 生成一个表达式
expressions.append(curr)
# 计算表达式的值
if eval(curr) == target:
return 1
else:
return 0
count = 0
# 对于每一种符号进行递归
if curr:
count += find_expression(expressions, start+1, curr+"+"+s[start], target, s)
count += find_expression(expressions, start+1, curr+"-"+s[start], target, s)
else:
count += find_expression(expressions, start+1, s[start], target, s)
return count
# 主函数
if __name__ == '__main__':
while True:
try:
s, target = input().split()
expressions = []
count = find_expression(expressions, 1, s[0], int(target), s)
print(count)
except:
break
你的程序样例满足不了，输出方式也有问题