首页 > 试题广场 > 如何添加运算符
[编程题]如何添加运算符
  • 热度指数:891 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给出一个数字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

#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 回复(3)
//动态方程(有点难理解):当前种类=符号位加号+符号为减号+没有符号的种类
//dp(before,des,n,ex)= dp(before - 1, before, res + des,1) + dp(before - 1, before, res - des,1) + dp(before - 1, before*pow(10, ex)+des, res,ex+1);
// before: 需要判定的符号前面的数字的个数,初始为8
// des: 需要判定的符号后面的数字,初始为9
// n:方程右边的结果
// ex:阶乘数,因为符号有三种可能,加号,减号,或者没有,如果没有,那么ex就用于计算当前值
#include<iostream>
#include<cmath>
using namespace std;
int dp(int before, int des, int res, int ex) {
	if (before == 0) {
		if (des == res) {
			return 1;
		}
		else {
			return 0;
		}
	}
	else {
		return dp(before - 1, before, res + des, 1) + dp(before - 1, before, res - des, 1) + dp(before - 1, before*pow(10, ex) + des, res, ex + 1);
	}
}
int main() {
	int m,n; 
    cin >>m>>n;
    
	cout << dp(m-1, m, n, 1);

}

发表于 2019-08-20 15:09:29 回复(0)

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)
""""
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)
暴力dfs  很粗暴 一点都不优雅
#include<bits/stdc++.h>
using namespace std;

char cal[3] = {' ', '+', '-'};

vector<string> res;

int extract_str(string s) {
    int res = 0;
    string tmp;
    for(int i = s.length() - 1; i >= 0 ; i--) {
        if(s[i] == '+')
        {res += atoi(tmp.c_str());tmp.clear();}
        else if(s[i] == '-')
        {res -= atoi(tmp.c_str());tmp.clear();}
        else if(s[i] == ' ') continue;
		else tmp = string(1, s[i]) + tmp;
    }
    return res + atoi(tmp.c_str());
}

void dfs(int pos, int N, string cur) {
    if(pos == N - 1) {
        string tmp = "1";
        for(int i = 1; i < N ; i++) {
            tmp.push_back(cur[i-1]);
            tmp.push_back(i + '1');
        }
        res.push_back(tmp);
        return;
    }
    for(int i = 0; i < 3; i++){
        cur.push_back(cal[i]);
        dfs(pos+1, N, cur);
        cur.pop_back();
    }
}


int main() {
    int N, M; scanf("%d%d", &N, &M);
    string empty = "";
    dfs(0, N, empty);
    int cnt = 0;
    for(int i = 0; i < res.size(); i++)
        if(extract_str(res[i]) == M) cnt++;
    cout<<cnt<<endl;
}
/*
7 0
*/


发表于 2019-12-03 12:45:26 回复(0)
def methods(s, n, m, step):
    s += str(step)
    if step == n :
        if eval(s) == m:
            return 1
        else:
            return 0
    return methods(s+"+", n, m, step+1) + methods(s+"-", n, m, step+1) + methods(s, n, m, step+1)

n, m = map(int, input().split())
print(methods("", n, m, 1))

发表于 2019-08-22 22:17:47 回复(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)

问题信息

上传者:小小
难度:
8条回答 1577浏览

热门推荐

通过挑战的用户

查看代码