代码之家 › 专栏 › 技术社区 › brokenglass12

OCaml薛定谔数递归

ocaml recursion

brokenglass12 · 技术社区 · 3 年前

我正试图解决一个问题,在ocaml中使用shcroder序列。但我真的不能通过这个。如果有人能帮我。谢谢

前3个值是正确的:S0=1 S1=2 S2=6 S3=22

从这里返回错误的答案

let rec s n =
  match n with 
  |0 -> 1 
  |1 -> 2
  |_ -> ((3 * (s (n-1))) + (sum_s (n-2)))
and 
  sum_s n2 =
  let sum = ref (0) and k = ref(0) in
  if n2 = 0 then 0
  else (while n2 >= !k do 
          sum := !sum + ((s !k) * (s (n2-(!k)))); 
          k := !k+1 done; 
        !sum)

enter image description here

我对解决办法很好奇。顺便说一句,我是OCaml的新手

1 回复 | 直到 3 年前

ForceBru 3 年前

不知道为什么 k 在代码中从0开始,在公式中从1开始。还有为什么代码会说 s (n2-(!k)) 当公式成立时 s (n-(!k)-1) ?

你的代码就是你在计算 s(n2-(!k)) 对于 n2 = n - 2 ,但公式上说应该计算 s(n-(!k)-1) 对于 n 本身,而不是 n-2 .你的代码最终会计算 s (n-(!k)-2) ,减去2而不是1。但你也要从 k=0 (可能是为了补偿减去2的损失?),但这导致了计算 s 0 而不是 s 1 对于产品中的第一个术语, s 1 而不是 s 2 等

看起来这可以在没有循环或循环的情况下实现 ref :

let rec s n =
  (* Same as your code *)
  match n with
   | 0 -> 1
   | 1 -> 2
   | _ -> 3 * (s (n-1)) + (sum_s n) (* `n` here! *)
and
  sum_s n =
   let rec sum_s_impl (n, k) =
     (* Implement the formula *)
     if (n-2 < 1) || (k > n-2) then 0
     else (s k) * (s (n-k-1)) + (sum_s_impl (n, k+1))
   in sum_s_impl (n, 1);;

for n = 0 to 10 do
  print_int (s n);
  print_newline ()
done;;

输出:

$ ocaml code.ml
1
2
6
22
90
394
1806
8558
41586
206098
1037718

这似乎与OEIS在 https://oeis.org/A006318 .

推荐文章

jkfe · 为什么println会在这段递归代码中执行?

3 年前

Brian Patterson · Javascript自定义数组。原型方法日志“未定义”

3 年前

Jimmy · 这种算法怎么能按顺序遍历树“爬上”树呢?

3 年前

iRon · 匿名递归函数

3 年前

ProgrammingNoob321312 · 为什么这个Java代码会输出“3210123”?

3 年前

AvirukBasak · gcc中无return语句的尾部递归

3 年前

Dharmik Patel · 使用python递归完全可以整除

3 年前

W.tan · 一维最短距离递归算法

3 年前

ncarrawa · 将1添加到i(递归)时出现类型错误

3 年前

Eren · Python递归何时返回[duplicate]

3 年前