如何检查列表是否具有连续幂

Question

我是 ruby 新手，正在解决一个问题，但我不知道如何解决它。 我想编写一个函数，如果每个连续元素是前一个元素的幂，则返回 true，否则返回 false

例如：如果我有一个列表 [2;4;8;16] 该函数应该返回 true 函数应该返回 false ，[3; 7； 9;]

let consec_ele element = match element with
[] -> true
h::t -> 
if h > t then false
else
  if t/h = 0 && t mod h = 0 then true
;;

我只是不知道如何让它工作并且如此递归。

Answer 1

好吧，你首先需要将你的问题形式化：

• 如果我的列表为空，那么

  true

• 如果我的列表不是，那么它以数字开头

  n

  • 如果

    n = 1

    ，那么我需要重新开始，因为

    a^0 = 1 for all a

  • if

    n > 0

    然后我在列表的其余部分上调用一个新函数

    check

    ，

    tl

    ，其作用如下：
    • 如果

      tl

      为空，则为 true
    • else

      tl

      以

      n'

      开头，然后如果

      n' = n * n

      那么我在其余部分递归地调用

      check

      ，我需要保留这样一个事实：我现在正在检查

      n * n * n

      ...
  • 如果

    n <= 0

    那么

    false

在 OCaml 中，这将是

let consec_ele l = 
  let rec cer b = function
    | [] -> true
    | n :: tl ->
      if n <= 0 then false
      (* We can start again for the first 1 we see, but if our
       * list is [1; 1; 1; ...; 1] then we need to stop
       * That's why we have this boolean b which is true and once
       * we see 1 as the head of our list we swap it to false
       *)
      else if n = 1 then b && cer false tl
      else
        let rec check p = function
          | [] -> true
          | n' :: tl -> n' =  pow n p && check (p + 1) tl
        in check 1 tl
  in cer true l;;

（对于

pow

函数，我让你写它；-）当然，这可能很糟糕，因为你可能会溢出，也许你更愿意看看是否

n' ^ (1/p) = n

（

n'

的 pth 根） （为什么我们在 stackoverflow 上没有 LaTeX 数学模式？:-())

Answer 2

能够对列表中的前两个元素进行模式匹配使这变得微不足道。显然，空列表是

true

，只有一个元素的列表也是

true

。否则，如果我们考虑前两个元素，如果第二个元素是第一个元素的幂，则函数为

true

，我们可以丢弃第一个元素并递归地考虑列表的其余部分。否则，结果显然是

false

。

let rec consec_ele =
  function
  | [] | [_] -> true
  | a::(b::_ as tl) when is_power_of a b -> consec_ele tl
  | _ -> false

请注意，您的

[2;4;8;16]

测试用例实际上应该返回

false

，因为

8

是 multiple，但不是 4 的

power

。