OCaml函数，用于检查列表是否是带有floor(n/2)个递归调用且没有列表分配的回文 [英] OCaml function to check if list is palindrome with floor(n/2) recursive calls and no list allocation

问题描述

我在uni上有这项任务，我已经研究了很长时间，但是我找不到如何编写此函数的方法.我需要它来检查列表是否为回文式，在最多floor(n/2)次时递归调用自身，并且不分配任何辅助列表(因此我不能使用任何列表构造函数).有任何想法吗?Tbh，我想要的是算法而不是完整的解决方案.

I have this task on uni, I have researched for a long time, but I cannot find out, how to write this function. I need it to check if a list is a palindrome, call itself recursively at most floor(n/2) times and not allocate any auxiliary list (so I can use no list constructors). Any ideas? Tbh, I would like an algorithm than a full solution.

推荐答案

我想出了这个方法，它可行:

I have come up with this and it works:

let palindrom l =
let rec aux l0 l1 =
    match (l0, l1) with
    | _,[] -> (true,[])
    | hd :: tl, [x] -> (hd = x, tl)
    | _, hd1 :: tl1 -> let (pal, ll) = aux l0 tl1 in
          match ll with
          | [] -> (pal, [])
          | hd::tl -> (pal && hd1 = hd, tl) in
match l with
[] -> true
| _ -> fst (aux l l)

这篇关于OCaml函数，用于检查列表是否是带有floor(n/2)个递归调用且没有列表分配的回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！