在F#中将列表分成两个相等的列表 [英] Split list into two equal lists in F#

问题描述

我真的是F#的新手，在F#问题上我需要一些帮助.

I'm really new to F#, and I need a bit of help with an F# problem.

我需要实现一个cut函数，该函数将列表分成两半，以便输出为...

I need to implement a cut function that splits a list in half so that the output would be...

cut [1; 2; 3; 4; 5; 6] ;;

cut [1;2;3;4;5;6];;

val it:int list * int list =([1; 2; 3]，[4; 5; 6])

val it : int list * int list = ([1; 2; 3], [4; 5; 6])

我可以假设列表的长度是偶数.

I can assume that the length of the list is even.

我还希望定义一个辅助函数gencut(n，xs)，它将xs分为两部分，其中n给出第一部分的大小:

I'm also expected to define an auxiliary function gencut(n, xs) that cuts xs into two pieces, where n gives the size of the first piece:

gencut(2，[1; 3; 4; 2; 7; 0; 9]);;

gencut(2, [1;3;4;2;7;0;9]);;

val it:int list * int list =([1; 3]，[4; 2; 7; 0; 9])

val it : int list * int list = ([1; 3], [4; 2; 7; 0; 9])

我通常不会在这里寻求运动帮助，但我真的不知从何开始.任何帮助，即使只是在正确方向上的推动，都会有所帮助.

I wouldn't normally ask for exercise help here, but I'm really at a loss as to where to even start. Any help, even if it's just a nudge in the right direction, would help.

谢谢！

推荐答案

由于列表的长度是均匀的，并且您要将其整洁地切成两半，因此我建议使用以下方法(首先使用伪代码):

Since your list has an even length, and you're cutting it cleanly in half, I recommend the following (psuedocode first):

• 从两个指针开始:slow和fast.
• slow一次遍历列表中的一个元素，fast一次遍历两个元素.
• slow将每个元素添加到累加器变量，而fast向前移动.
• fast指针到达列表的末尾时，slow指针将只有元素数量的一半，因此它位于数组的中间.
• 返回元素slow跳过+剩余元素.这应该是两个列表，整齐地切成两半.

• Start with two pointers: slow and fast.
• slow steps through the list one element at a time, fast steps two elements at a time.
• slow adds each element to an accumulator variable, while fast moves foward.
• When the fast pointer reaches the end of the list, the slow pointer will have only stepped half the number of elements, so its in the middle of the array.
• Return the elements slow stepped over + the elements remaining. This should be two lists cut neatly in half.

上面的过程需要遍历整个列表，并在O(n)时间内运行.

The process above requires one traversal over the list and runs in O(n) time.

由于这是家庭作业，因此我不会给出完整的答案，只是为了让您起步，这是将清单切成两半的步骤:

Since this is homework, I won't give a complete answer, but just to get you partway started, here's what it takes to cut the list cleanly in half:

let cut l =
    let rec cut = function
        | xs, ([] | [_]) -> xs
        | [], _ -> []
        | x::xs, y::y'::ys -> cut (xs, ys)
    cut (l, l)

请注意x::xs步骤1元素，y::y'::ys步骤2.

Note x::xs steps 1 element, y::y'::ys steps two.

此函数返回列表的后半部分.修改它非常容易，因此它也返回列表的前半部分.

This function returns the second half of the list. It is very easy to modify it so it returns the first half of the list as well.

这篇关于在F#中将列表分成两个相等的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！