首页 > 试题广场 > 如何添加运算符
[编程题]如何添加运算符
给出一个数字N,对于数字序列 1,2,3 ... N。现在在其中插入“+”, "-", " ",使得表达式的和为M。" "的含义是把相邻的两个数字组成一个数。例如:1 + 2 3 - 4,含义是:1 + 23 - 4 = 20。
给出N和M,求出所有合法的序列的个数。

输入描述:
两个整数N,M ( 1 <= N <= 7, -100 <= M <= 100)


输出描述:
合法序列的个数
示例1

输入

7 0

输出

6

说明

样例中的六种合法序列
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

dfs解法

#include <iostream>
using namespace std;
int n, m;
int dfs(int sum, int current,int step) {
    //当前和,当前位,当前数字(步数)
    if (step == n + 1) {
        if (sum == m&&current == step) {
            return 1;
        }
        else return 0;
    }
        //当当前位为一的时候,不允许减操作,如1 2 3 得到-15,通过-12-3是不允许的。同理1也不能得到-1
    int temp = current;
    while (temp > 9 ) {
        temp = temp / 10;
    }
    if(temp ==1) return dfs(sum + current, step + 1, step + 1) + dfs(sum, current * 10 + step + 1, step + 1);
    else return  dfs(sum + current, step + 1,step+1) + dfs(sum - current, step + 1,step+1) + dfs(sum, current *10+ step +1,step+1);
}
int main() {
    cin >> n >> m;
    cout << dfs(0, 1,1);
    system("pause");
    return 0;
}
编辑于 2019-07-27 15:46:51 回复(0)

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt=0;

void DFS(int sum, int p){
    if(sum==m && p==n+1)
        cnt++;
    int t = 0;
    for(int i=p;i<=n;i++,t*=10){
        t += i;
        DFS(sum+t, i+1);
        if(p!=1)
            DFS(sum-t,i+1);
    }
}

int main(){
    cin>>n>>m;
    DFS(0,1);
    cout<<cnt<<endl;
    return 0;
}
发表于 2019-07-20 23:53:11 回复(1)
""""
DFS,用了eval直接字符串转表达式
"""
def dfs(s, n, m, step):
    s += str(step)
    if step == n:
        if eval(s) == m:
            return 1
        return 0
    return dfs(s + '+', n, m, step + 1) + dfs(s + '-', n, m, step + 1) + dfs(s, n, m, step + 1)


if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    ans = dfs("", n, m, 1)
    print(ans)

编辑于 2019-07-14 22:46:55 回复(0)
#include<stdio.h>
#include<string>
#include<iostream>
#include<set>
#include<vector>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
int res_count = 0;
int m;
int n;
 
void check_eq(int cur_eq, int step)
{
    if (step > n)
        return;
    if (step == n)
    {
        if (cur_eq == m)
        {
            res_count++;
            return;
        }
         
    }
	if(step <= n-2){
		check_eq(cur_eq + ((step + 1) * 10 + (step + 2)), step + 2);
		check_eq(cur_eq - ((step + 1) * 10 + (step + 2)), step + 2);
	}
    check_eq(cur_eq + (step + 1), step + 1);
    check_eq(cur_eq - (step + 1), step + 1);
    //check_eq(cur_eq * 10 + (step + 1), step + 1);
}
 
 
int main()
{
     
    cin >> n >> m;
    check_eq(1, 1);
	char s[500];
	if( n >1 )
		check_eq(12, 2);
    printf("%d", res_count);
    return 0;
}

发表于 2019-08-14 00:20:57 回复(0)
//李智海快来看呀,我做出来了

#include <stdio.h>
#include <math.h>

int ou_result = 0;

void dfs(int step,int now_result,int N,int M,int pre){
    if (now_result == M && step == N+1){
        ou_result++;
        return;
    }    
    if(step == N+1)
          return;
    int i = step;
    int temp = 0;

    temp = pre * 10;
    
    if(pre >= 0)
        dfs(i+1,now_result +i + temp - pre,N,M,temp + i);
    else
        dfs(i+1,now_result -i + temp - pre,N,M,temp - i);
    dfs(i+1,now_result + i,N,M,i);
    dfs(i+1,now_result - i,N,M,-i);
}
int main(){
    int num,result;
    scanf("%d %d",&num,&result);
    
    dfs(2,1,num,result,1);   
    printf("%d",ou_result);
    
    return 0;
}
发表于 2019-08-13 11:54:58 回复(0)

问题信息

上传者:小小
难度:
5条回答 477浏览

热门推荐

通过挑战的用户

查看代码