首页 > 试题广场 >

如何添加运算符

[编程题]如何添加运算符

热度指数：2262 时间限制：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

输出

说明

样例中的六种合法序列
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

算法知识视频讲解

Java

LHC0512

import java.util.Scanner;

public class Main {
    
    private static int num;
    private static int target;
    private static int count=0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        num = scanner.nextInt();
        target = scanner.nextInt();
        dfs(0, 1);
        System.out.println(count);
    }

    private static void dfs(int sum,int p){
        if (sum==target&&p==num+1)
            count++;
        int t=0;
        for (int i = p; i <=num; i++,t*=10) {
            t+=i;
            dfs(sum+t,i+1);
            if (p!=1){
                dfs(sum-t,i+1);
            }
        }
    }
}

编辑于 2020-02-29 12:05:53 回复(0)