首页 > 7.25 拼多多笔试第三题 无限数字集合求指教
头像
runshui
编辑于 2021-07-25 21:46
+ 关注

7.25 拼多多笔试第三题 无限数字集合求指教

题意:
1、初始集合有一个元素A
2、集合中每个元素X,X+B也属于集合
3、集合中每个元素X,X*C也属于集合
问Q是不是集合的元素?
如下代码,想用dfs解决,结果一直说超出内存限制,猜测是递归结束条件可能没写对,导致一直递归调用,但想不出来到底哪不对,网牛友指教。😣
func main() {
    n := 0 
    fmt.Scan(&n)
    for i:=0; i<n; i++ {
        A, B, C, Q := 0, 0, 0, 0
        fmt.Scan(&A, &B, &C, &Q)
        if dfs(A, B, C, Q) {
            fmt.Println(1)
        } else {
            fmt.Println(0)
        }
    }
}


func dfs(A, B, C, Q int) bool {
    if Q == A {
        return true
    }
    if Q < A {
        return false
    }
    return dfs(A, B, C, Q-B) || dfs(A, B, C, Q/C)
}


全部评论

(10) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐