首页 > 试题广场 >

如何添加运算符

[编程题]如何添加运算符
  • 热度指数:2234 时间限制: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
package main

import (
    "fmt"
    "strconv"
)

func main() {
    var n,m int
    fmt.Scan(&n,&m)
    ans:=0
    var dfs func(string,int)
    dfs=func(s string,idx int){
        if idx==n+1{
            if cal(s)==m{
                ans++
            }
            return
        }
        dfs(s+"+"+strconv.Itoa(idx),idx+1)
        dfs(s+"-"+strconv.Itoa(idx),idx+1)
        dfs(s+strconv.Itoa(idx),idx+1)
    }
    dfs("1",2)
    fmt.Print(ans)
}

func cal(s string)int{
    arr1,arr2:=[]int{},[]byte{}
    pre:=""
    for _,ch:=range []byte(s){
        if ch=='+'||ch=='-'{
            x,_:=strconv.Atoi(pre)
            arr1=append(arr1,x)
            arr2=append(arr2,ch)
            pre=""
        }else{
            pre+=string(ch)
        }
    }
    x,_:=strconv.Atoi(pre)
    arr1=append(arr1,x)
    ans:=arr1[0]
    for i:=1;i<len(arr1);i++{
        if arr2[i-1]=='+'{
            ans+=arr1[i]
        }else{
            ans-=arr1[i]
        }
    }
    return ans
}

发表于 2023-03-23 10:34:14 回复(0)