鱼C论坛

 找回密码
 立即注册
查看: 1564|回复: 1

[已解决]每日一题的第55题,答案不同

[复制链接]
发表于 2021-5-12 22:49:07 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
有一个数列u,使得u符合以下规则:
1、u的第一个数字是1.
2、对于u中的每一个x,都有y=2*x+1 和z=3*x+1,且y和z都在u中。
3、u中没有其他数字。
复制代码

例如:
u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
复制代码


1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13
....

要求:给出函数dbl_linear(n),  返回按顺序排列的u[n]。
例如: dlb_linear(10) 返回  22.
注意:请考虑效率问题(1<n<100000)

参考答案的代码:
from collections import deque


def dbl_linear1(n):
    h = 1
    cnt = 0
    q2, q3 = deque([]), deque([])
    while True:
        if (cnt >= n):
            return h
        q2.append(2 * h + 1)
        q3.append(3 * h + 1)
        h = min(q2[0], q3[0])
        if h == q2[0]: h = q2.popleft()
        if h == q3[0]: h = q3.popleft()
        cnt += 1
输出是2911582。花费1s不到....

我的代码:
from timeit import timeit


def dlb_linear(n):
    u = [1]
    length = len(u)
    num = 0
    while length <= n:
        x = 2 * u[num] + 1
        y = 3 * u[num] + 1
        u.append(x)
        u.append(y)
        u.sort(reverse = False)
        length = len(u)
        num += 1
    print(u[n])
    print(u)
    return u


t = timeit("dlb_linear(100000)", 'from __main__ import dlb_linear', number = 1)
print(t)
输出是2942626,花费9.22s

如果题目中的u列表是按从小到大排序的,那么x和y的生成也应该是从小到大,求指点哪里出了问题...为什么输出不一样?
最佳答案
2021-5-13 09:20:53
本帖最后由 qq1151985918 于 2021-5-13 09:34 编辑

你的问题在于这一句  

1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13

理解不到位

实际上 y(4) < z(3) 这种情况你就没有作出处理,所以才会错误
而且你的 数组 u 在不断进行排序过程,索引值 num 是变化的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-5-13 09:20:53 | 显示全部楼层    本楼为最佳答案   
本帖最后由 qq1151985918 于 2021-5-13 09:34 编辑

你的问题在于这一句  

1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13

理解不到位

实际上 y(4) < z(3) 这种情况你就没有作出处理,所以才会错误
而且你的 数组 u 在不断进行排序过程,索引值 num 是变化的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-15 21:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表