在F#中将列表分成两个相等的列表

本文介绍了在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.