V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
hakono
V2EX  ›  问与答

请教一道某公司的(简单?)算法题?

  •  
  •   hakono · 2019-04-27 00:06:44 +08:00 · 2525 次点击
    这是一个创建于 1798 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有道题目一时半会解不出来,简单我感觉应该是挺简单的,但是想不出来怎么解,考试结束后也没想到很好的方案。请教下

    给定一个整数范围,范围内数字依次递增,步长为 1 如: 1 ~ 10

    然后再给定几个数字,将这些数的倍数从给定的整数范围内剔除,问整数范围内还剩下几个数字

    说起来抽象,举个例子就是:

    出题者给定个整数范围比如1~10, 有十个数字

    然后出题者给出几个要剔除的数字如:2 4 5,因为 2 的倍数是 2 4 6 8 , 4 的倍数是 4 8,5 是 5 10 从1~10中剔除这几个数,剩下1 3 7 9 剩余数量为 4

    这个问题比较困难的地方在于,实际做题时,给出的数字范围是极大的比如 1~999999999999999999

    500000000~100000000000000000000

    这种

    不可能简单搞个长度为 n 的数组,一个个从里面剔除掉,然后算剩余多少元素

    26 条回复    2019-04-27 16:27:21 +08:00
    KKKKKK
        1
    KKKKKK  
       2019-04-27 00:11:18 +08:00 via iPhone
    最简单的,直接想到的 O(nm) 算法
    dfjslkjdf
        2
    dfjslkjdf  
       2019-04-27 00:18:04 +08:00   ❤️ 1
    比如,1-100,
    剔除 2,5,7 倍数;
    可以每 2*5*7 为一个数组。
    LxExExl
        3
    LxExExl  
       2019-04-27 00:26:09 +08:00 via iPhone
    剔除一个数 (b-a)/x 即可 注意处理边界
    剔除多个数先把倍数去掉然后就和去掉一个数一样了吧
    Vegetable
        4
    Vegetable  
       2019-04-27 00:30:09 +08:00
    2# 的思路我觉得不错.取 n 个数的最小公倍数 a.求出 0~a 之间有多少个,后边就不需要遍历了,简单处理一下就行了
    shs10978
        5
    shs10978  
       2019-04-27 00:32:44 +08:00 via Android
    划掉数字互质的话 dp 应该能做吧,O(sqrt(n)*m)。不互质会复杂一些。
    JCZ2MkKb5S8ZX9pq
        6
    JCZ2MkKb5S8ZX9pq  
       2019-04-27 00:33:17 +08:00
    假设范围 r1-r2,要剔除的基数[n1,n2,n3,...]

    第一步找出某一个基数在范围里有几个吧,比如 c1。
    如果是 python 语法 c1 = r2//n1-r1//n1

    第二步穷举一下公约数,计算出现次数再扣掉。
    不过如果基数的个数也很多的话,复杂度还是很高啊。
    hakono
        7
    hakono  
    OP
       2019-04-27 00:35:02 +08:00
    @LxExExl 其实我最开始就是这样做的。

    但后来发现,给定数字还得考虑公倍数。比如要去除 31 46 的倍数的话,还得考虑 31 46 的公倍数 1426 多减去的情况。然后如果给定的数字数量比较多给了 10 几个的话,每个数字互相之间的公倍数都得考虑
    shs10978
        8
    shs10978  
       2019-04-27 00:35:15 +08:00 via Android
    嗯有点想复杂了,如果划掉的 m 个数字最小公倍数远远小于 n 的话,2 楼方法更好一些
    hakono
        9
    hakono  
    OP
       2019-04-27 00:47:34 +08:00
    @JCZ2MkKb5S8ZX9pq 是的,我一开始就是这么想着去解的,但是给定的数字数量不少,10 到 30 个之间,还得穷举每种组合的公倍数。然后穷举出来的公倍数还得推算下公倍数,多次重复的情况也得剔除。
    最后写出来结果是有挺多题答案是错的。所以才觉得这个方法可能有点问题或者哪里没有考虑清楚
    maggch
        10
    maggch  
       2019-04-27 00:47:51 +08:00
    容斥
    starrycat
        11
    starrycat  
       2019-04-27 00:51:43 +08:00 via Android
    想到了素数筛选法,有点类似😂
    Vegetable
        12
    Vegetable  
       2019-04-27 00:54:10 +08:00
    from functools import reduce


    def rm(x, r):
    _min = reduce(lambda x, y: x*y, x)
    circulate, rest = divmod(r, _min)
    r = common = 0
    for i in range(1, _min):
    for j in x:
    if i % j == 0:
    break
    else:
    common += 1
    if i <= rest:
    r += 1
    return common*circulate+r


    if __name__ == "__main__":
    x = [2, 5, 7]
    r = 10000
    a = rm(x, r)
    c = 0
    for i in range(1, r):
    for j in x:
    if i % j == 0:
    break
    else:
    c += 1
    print(a)
    assert c == a

    没格式的话忍一忍...我测试没什么问题.
    Vegetable
        13
    Vegetable  
       2019-04-27 00:56:10 +08:00   ❤️ 1
    Vegetable
        14
    Vegetable  
       2019-04-27 01:01:54 +08:00
    ..最小公倍数求错了
    @Vegetable
    hakono
        15
    hakono  
    OP
       2019-04-27 01:05:07 +08:00
    @Vegetable 感谢代码!不过在给定范围很大的情况下,代码执行时间会极长。因为 for range(1,r),所以在比如
    r = 1000000000000000000
    x = ['29516', '34882', '63315', '28983', '7176', '96533', '33422', '84834', '43803', '61310']
    的时候,执行时间很久
    hakono
        16
    hakono  
    OP
       2019-04-27 01:14:15 +08:00
    @dfjslkjdf
    @Vegetable
    啊,这个 n 个数求公倍数思考了半天终于幡然醒悟!懂了 orz
    果然人笨
    shs10978
        17
    shs10978  
       2019-04-27 01:33:57 +08:00
    @hakono 15 楼这个例子答案是 999656713995364547 ?
    liyunlong41
        18
    liyunlong41  
       2019-04-27 01:34:51 +08:00 via iPhone   ❤️ 1
    这题感觉是典型的容斥啊。
    假设给定四个数 和总数 n。
    容斥原理计算四个数的倍数在 n 范围内的数量 m=sum(n/单个数)-sum(n/任意两数公倍数+sum(n/任意三数公倍数)-sum(n/四个数的公倍数)
    最终结果就是 n-m
    clatisus
        19
    clatisus  
       2019-04-27 01:36:54 +08:00 via iPhone
    如果剔除的数字个数很少的话,可以枚举它们的子集,然后用容斥原理。

    假设剔除 m 个数字,复杂度就 O(2^m)。
    clatisus
        20
    clatisus  
       2019-04-27 01:38:24 +08:00 via iPhone
    @clatisus 补充:这样 n 不管多大都可以,如果是区间 [l, r] 的话,就 r 的答案减去 l - 1 的答案。
    hakono
        21
    hakono  
    OP
       2019-04-27 01:43:38 +08:00
    @shs10978 测试里的参考答案是 999656834379155073
    shs10978
        22
    shs10978  
       2019-04-27 01:44:53 +08:00 via Android
    @hakono 那就对了。。我素数 list 范围取小了所以答案偏了一点。。dbq
    liyunlong41
        23
    liyunlong41  
       2019-04-27 02:55:41 +08:00
    花时间用 golang 写了下程序,1e18 的样例已经能正确跑出结果,999656834379155073,用的是容斥原理,枚举数组所有子集,看子集个数,奇数个就减,偶数个就加。秒出结果,被乘法溢出搞了好久…… 代码凑活着看。
    `
    func gcd(x, y int64) int64 { //辗转相除法
    tmp := x % y
    if tmp > 0 {
    return gcd(y, tmp)
    }
    return y
    }
    func lcm(x, y int64) int64 {
    return x / gcd(x, y) * y //计算 lcm 的小技巧,先除 gcd,再乘另一个数,有效防止溢出
    }
    func main() {
    var (
    n = int64(1000000000000000000)
    i = uint(1)
    j = uint(0)
    nums = []int{29516, 34882, 63315, 28983, 7176, 96533, 33422, 84834, 43803, 61310}
    len = uint(len(nums))
    )
    sum := int64(0)
    for i = 0; i < (1 << len); i++ {
    count := 0
    curLcm := int64(1)
    ok := true
    for j = 0; j < len; j++ {
    if (i & (1 << j)) > 0 {
    count++
    tmp := curLcm
    curLcm = lcm(int64(nums[j]), curLcm)
    //这里判断乘法溢出!!被卡了好久
    if curLcm > n || curLcm < tmp || curLcm % tmp != 0 || curLcm % int64(nums[j]) != 0 {
    ok = false
    break
    }
    }
    }
    if !ok {
    continue
    }
    if count%2 == 1 {
    sum -= n / curLcm
    } else {
    sum += n / curLcm
    }
    }
    fmt.Println(sum)
    }

    `
    liyunlong41
        24
    liyunlong41  
       2019-04-27 02:58:40 +08:00
    @liyunlong41 代码格式乱了,不太会搞,贴在网页上吧: https://github.com/hackssssss/test_git/blob/master/rc.go
    geelaw
        25
    geelaw  
       2019-04-27 04:43:38 +08:00
    要删除的数字数目不多的时候可以用容斥原理,枚举子集进行公倍数的删除和加回即可。
    这样需要的时间是 O(poly(log n) * 2^m poly(m)),其中 n 是范围,m 是要删除的数的个数。

    并不知道是否有多项式时间算法(
    mooncakejs
        26
    mooncakejs  
       2019-04-27 16:27:21 +08:00
    约瑟夫环问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   958 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 21:40 · PVG 05:40 · LAX 14:40 · JFK 17:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.