V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
feuto
V2EX  ›  算法

一道算法题

  •  
  •   feuto · 2021-08-12 06:55:07 +08:00 · 1359 次点击
    这是一个创建于 1203 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Q1: 设计一种算法,依次输出自然数序列 N 的元素, 0,1,2,3,4,... (这题很简单) 像这一个死循环就完事了 i = 0; do {print(i++)} while(i>=0)

    Q2: 尝试设计一种算法,输出所有“由(互不相等的)自然数”构成的无穷序列

    5 条回复    2021-12-03 03:01:29 +08:00
    nvkou
        1
    nvkou  
       2021-08-12 07:32:26 +08:00 via Android
    Q1 简单? 没考虑数值上限吗?
    Q2 没看懂,是需要排列组合的穷举吗?
    Raven316
        2
    Raven316  
       2021-08-12 07:34:38 +08:00
    你是不是对算法有什么误解
    jmc891205
        3
    jmc891205  
       2021-08-12 08:59:37 +08:00
    An algorithm is a *finite* sequence of well-defined, computer-implementable instructions.
    raaaaaar
        4
    raaaaaar  
       2021-08-12 09:43:56 +08:00 via Android
    确定,有限,定义上来说的确是算法吧。
    wffnone
        5
    wffnone  
       2021-12-03 03:01:29 +08:00
    不懂数学纯胡扯。以下的话都是毫无价值的废话。

    Q2 。

    如果是顺序输出,就是一个序列一个序列输出。那么,程序无法完成第一个序列,永远只在输出第一个序列。

    所以显然我们不能用顺序输出,那怎么输出呢?我们可以考虑把这无穷个序列排序出来,组成一个二维的无穷数阵,每一行是一个要求的无穷序列,每一列就是按照这个排序的所有无穷序列的第 N 项构成的序列。我们可以沿着 i+j<=k ,递增 k 来输出。这样看起来是规避了输出的问题。

    先尝试去解决有限元素的序列,作为启发。

    显然,对有限元素,就是一个全排列。找一个简单的遍历方法:依次两两对换。这个办法对无穷序列的问题是,对换第一个元素的过程又是无限的,所以我们的第二个维度又被占用了。

    没关系,我们可以把这个序列的输出,表示成任意维度的数阵。其中一个维度是序列,其他的维度作为遍历序列的顺序。然后输出,( m 维时)按照 d1+d2+...+dm <= k ,递增 k ,就可以了。

    到这里我已经没有特别的兴致去往下进行了。我猜想 m<10 的时候就应该有一个解。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3513 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 04:51 · PVG 12:51 · LAX 20:51 · JFK 23:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.