不使用迭代反转数组

Question

不使用迭代反转数组

calgorithm

39

今天有人问了我一个问题，我认为这是不可能的，但我可能是错的或者想太多了。如何在C语言中不使用迭代来反转数组？

我的想法是这是不可能的，因为数组可以是任何大小，没有使用任何形式的迭代就不能用C程序来实现。

- Michael J. Gray

一个例子可能是个好主意：{ 0, 1, 2, 3, 4 } 在内存中变成了 { 4, 3, 2, 1, 0 }。 - Michael J. Gray

1

+1。这可能是不可能的。但我们需要一些证据或一群人来确认它是否可能。 :) - madhairsilence

6

这主要涉及到定义，比如“迭代”究竟包括/不包括哪些内容。 - Jerry Coffin

如果你真的想要创意，难道不可能改变操作系统内存管理器，允许一个内存块被反转，以便逻辑开头现在指向旧的物理结尾，然后对指针算术进行减法而不是加法吗？没有好的理由去实现这个功能，而且会增加很多开销，但如果你在Linux中使用C语言实现它，那就可以了。 :) - Justin

@aps2012 很久没见到这个问题了，但如果你是在引用我的回答，请注意我说过：“如果将递归仅仅视为迭代的一种替代方式，那么Kalai的回答是正确的。” 我不认为这是“绝对确定”，也不是“不理解递归”。 :-) 不过没关系——只是想澄清一下。顺便说一句，我确实喜欢你的回答，并且很早就点赞了。 - Ray Toal

显示剩余5条评论

8个回答

23

正如评论中所说，这取决于迭代的定义。

情况1：作为编程风格的迭代，与递归不同

如果将递归仅仅视为迭代的一种“替代方法”，那么Kalai提出的递归解法就是正确答案。

情况2：迭代作为下限线性时间

如果将迭代理解为“检查每个元素”，那么问题就变成了数组翻转是否需要线性时间或者可以在次线性时间内完成。

为了证明数组翻转没有次线性算法，考虑一个包含n个元素的数组。假设存在一种算法A可以在不需要读取每个元素的情况下进行翻转。那么对于一些0到n-1范围内的i，存在一个元素a[i]，该算法从未读取过它，但仍能够正确地翻转数组。（编辑：我们必须排除奇数长度数组的中间元素--请参见下面的注释--但这不影响算法是否在渐近情况下是线性还是次线性的）

由于算法从未读取元素a[i]，所以我们可以改变其值。假设我们这样做了。那么该算法从未读取过这个值，却会产生与之前相同的翻转答案。但这个答案对于新值的a[i]来说是不正确的。因此，不存在一种能够在不至少读取每个输入数组元素（除一个）的情况下进行正确翻转的算法。因此，数组翻转具有O(n)的下限，因此需要迭代（根据此情况下的工作定义）。

（请注意，这个证明只适用于数组翻转，而不能推广到真正具有次线性实现的算法，例如二分查找和元素查找。）

情况3：迭代作为循环结构

如果迭代被视为“循环直到满足条件”，那么它将转换为机器码，需要进行一些严格的编译器优化（利用分支预测等）。在这种情况下，询问是否有一种“不需要迭代”的方法可能会考虑展开循环（变成一条直线的代码）。在这种情况下，您可以原则上编写直线式（无循环）C代码。但是这种技术并不通用；它仅在您事先知道数组大小的情况下才起作用。(抱歉将这个更多或更少的轻率案例添加到答案中，但我这样做是为了完整性和因为我听过“迭代”这个术语，并且展开循环是一个重要的编译器优化。)

- Ray Toal

@WillNess：在长度为奇数的数组中间的元素是唯一可以安全跳过读取的元素。也就是说，你只能跳过读取O(1)个O(n)元素。如果Ray的证明处理了这个特例（并且如果它说“但是我们总是可以选择一个值给a[i]，以便于对于a[i]新值来说这个答案将不正确”会更好），那么他的推理和O(n)下界基本上是正确的。 - j_random_hacker

@WillNess：即使数组元素是复杂结构体，O(n)-1 = O(n)指针仍需要交换 => O(n)工作量。构建一个反转适配器通常是个好主意，因为它将允许O(1)查找，但这超出了问题定义的范围 - 同样，您可以使用一个使用偏移量的适配器创建一个旋转视图，但这与旋转其元素不同 :) - j_random_hacker

@j_random_hacker 谢谢您的回复。 :) 我不否认通过交换来进行反转是O(n)的，我没有在这里提供适配器概念的答案的原因是我也认为这个问题是关于物理反转数组的。但是，我无法理解在某个i处更改值与反转有什么关系。反转是无视值的，它是按位置进行的 - 这就是我的观点 - 因此在任何i处更改值不能证明任何关于反转的事情。 - Will Ness

@WillNess：让我尝试更详细地阐述一下证明思路：基本上我们需要以某种方式操纵数组A，以便如果我们将结果A返回给已经复制原始A的人（我们称之为B），他们可以检查它“似乎”被反转了 - 即对于所有0 <= i < n都满足条件A[i] == B[n-i-1]。现在假设有一个次线性算法，通过不查看某个位置j（中间位置除外！）来实现亚线性。如果该算法正确地似乎颠倒了某个特定的数组A，那么必须是这样的情况... - j_random_hacker

在一开始，A[j] == A[n-j-1] 是正确的，因为如果这两个元素不同，那么当此人测试特定条件时，它将失败，并且算法将被观察到在此特定数组上失败。假设我们的数据类型仅包含多个不同的值，现在可以构造一些新数组C，该数组与A相同，除了在位置C[j]处，它包含某个元素而不是A[n-j-1]（任何一个都可以）。子线性算法现在必须在此数组C上失败。 - j_random_hacker

显示剩余6条评论

15

使用递归函数。

void reverse(int a[],int start,int end)
{
     int temp;
     temp = a[start];
     a[start] = a[end];
     a[end] = temp;


    if(start==end ||start==end-1)
       return;
    reverse(a, start+1, end-1);
}

只需调用上述方法：reverse(array,0,lengthofarray-1)

- Kalai Selvan Ravi

3

递归是伪装成循环的。最终，CPU 无论如何都要迭代地访问内存。只是带有无用的额外开销。 - Ondra Žižka

1

@aps2012，这是一个递归算法：本质上与 rev(a) = (a[n]) + rev(a[2..n-1]) + (a[1]) 相同（具有适当的停止条件）。 - huon

3

@aps2012，就争论定义而言是没有意义的（这也是这个问题），但是常见用法表明这个答案是递归：除了你的答案外，所有我看过的递归定义（包括递归算法）并不仅限于分治。请参考以下链接：所有定义递归，以及递归算法。 - huon

2

此外，你那种被动攻击的说法“分享你的智慧，就像我一样详细地做”，是不必要的，请以后避免这样做；像“如果你能更详细地解释一下，我会很感激”的说法会更好。 - huon

2

@aps2012，我已经备份了我的视图：这个答案符合“递归算法”的传统定义。你没有阅读我提供的四个链接吗？（无论如何，我不喜欢从权威性争辩，但是：我在这里的时间比你长（并且拥有更高的“声望”和更高的平均回答声望），所以我可能更好地理解SO的动态。:)） - huon

显示剩余7条评论

1

实现一个递归函数来反转已排序的数组。例如，给定数组[1, 2, 3, 4, 5]，您的程序应返回[5, 4, 3, 2, 1]。

- Ntsika

2

没有必要回答已经有答案的问题。这样做不会为此处增加任何价值，除非你的答案与已经给出的答案不同，否则你也不会得到任何赞同。尝试回答那些还没有被接受的问题吧。 - Aseem Bansal

1

void reverse(int a[], int start,  int end )
{
     std::cout<<a[end] <<std::endl;
    if(end == start)
       return;         
    reverse(a, start, end-1);
}

这样做更好，因为我们甚至不需要循环来打印数组的值。

- user2997518

https://onecompiler.com/cpp/3yrtpftcj 【运行测试用例的链接】 - user2997518

同意作为仍然较旧的递归解决方案，我们需要通过迭代打印值，而我的面试并不赞同这种方法。谢谢 https://stackoverflow.com/users/2997518/user2997518 - user2907032

0

一个解决方案可能是：

#include <stdio.h>
#include <stdlib.h>

void swap(int v[], int v_start, int v_middle, int v_end) {
    int *aux = calloc(v_middle - v_start, sizeof(int));
    
    int k = 0;
    for(int i = v_start; i <= v_middle; i++) {
        aux[k] = v[i];
        k = k + 1;
    }

    k = v_start;
    for(int i = v_middle + 1; i <= v_end; i++) {
        v[k] = v[i];
        k = k + 1;
    }

    for(int i = 0; i <= v_middle - v_start; i++) {
        v[k] = aux[i];
        k = k + 1;
    }
}

void divide(int v[], int v_start, int v_end) {
    if(v_start < v_end) {
        int v_middle = (v_start + v_start)/2;
        divide(v, v_start, v_middle);
        divide(v, v_middle + 1, v_end);
        swap(v, v_start, v_middle, v_end);
    }
}

int main() {
    int v[10] = {4, 20, 12, 100, 50, 9}, n = 6;
    
    printf("Array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    printf("\n\n");

    divide(v, 0, n - 1);

    printf("Reversed: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }

    return 0;
}

- Alexandru Darie

0

这是一个使用JavaScript函数中的递归的巧妙解决方案。它不需要除数组本身以外的任何参数。

/* Use recursion to reverse an array */
function reverse(a){
    if(a.length==undefined || a.length<2){
        return a;
    }
    b=[];
    b.push(reverse(copyChop(a)));
    b.push(a[0]);
    return b;
    /* Return a copy of an array minus the first element */
    function copyChop(a){ 
        b=a.slice(1); 
        return b;
    }
}

按以下方式调用：

reverse([1,2,3,4]);

请注意，如果您不使用嵌套函数copyChop来进行数组切片，最终结果的第一个元素将是一个数组。不太确定为什么会这样。

- Phil C

这个问题被标记为C语言，为什么要提供Javascript的解决方案？ - Aseem Bansal

0

   #include<stdio.h>


   void rev(int *a,int i,int n)
  {

if(i<n/2)
{
    int temp = a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=temp;
    rev(a,++i,n);
 }
}
int main()
    {
    int array[] = {3,2,4,5,6,7,8};
   int len = (sizeof(array)/sizeof(int));
   rev(array,0,len);    
   for(int i=0;i<len;i++)
   {
    printf("\n array[%d]->%d",i,array[i]);
  }
}

- Monis Majeed

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aps2012 · Accepted Answer

你的问题的答案是，是的，可以不使用迭代来反转一个数组。然而，问题本身的措辞可能存在歧义，但问题的精神很明显：可以使用递归算法；在这种意义下，“递归”的含义毫无歧义。

如果在与一家顶尖公司的面试中，被问到这个问题，那么以下伪代码足以证明你真正理解了递归的含义：

function reverse(array)

    if (length(array) < 2) then
        return array

    left_half = reverse(array[0 .. (n/2)-1])
    right_half = reverse(array[(n/2) .. (n-1)])

    return right_half + left_half

end

例如，如果我们有一个包含拉丁字母表前16个字母（[A]..[P]）的16个元素的数组，则上述反转算法可以可视化为以下方式：

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Recurse
2.        ABCDEFGH                IJKLMNOP           Recurse
3.    ABCD        EFGH        IJKL        MNOP       Recurse
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Recurse

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Reverse
7.    DCBA        HGFE        LKJI        PONM       Reverse
8.        HGFEDCBA                PONMLKJI           Reverse
9.                PONMLKJIHGFEDCBA                   Reverse

                  Reversed Output

任何使用递归算法解决的问题都遵循“分而治之”的范例，即：

1. 将问题分成[两个或多个]子问题，其中每个子问题比原问题小，但可以用类似于原问题的方式解决（“分”）。 2. 将问题分成[两个或多个]子问题，其中每个子问题是独立的，可以通过递归或直接解决（如果足够小）来解决（“治”）。 3. 将问题分成[两个或多个]子问题，这些子问题的结果被组合在一起以给出原始问题的解决方案（“合”）。

上述伪代码严格符合上述标准，因此它可以被认为是一种递归算法，并且我们可以毫无疑问地声明，在不使用迭代的情况下可以翻转数组。

附加背景信息：

迭代、递归实现和递归算法的区别

常见的误解是认为递归实现意味着算法是递归的。它们并不等价。以下是一个明确的解释，包括上述解决方案的详细说明。

迭代和递归是什么？

回到1990年，计算机科学领域现代算法分析中最受尊敬的三位学者Thomas H. Cormen、Charles E. Leiserson和Ronald L. Rivest发表了他们备受赞誉的著作Introduction to Algorithms。在这本书中，他们汇集了200多本自己的著作，并明确说明了什么构成了“迭代”和“递归”。这本书已经被世界上大多数顶尖大学用作教授算法的第一本教材超过20年。

在他们对两种经典排序算法——插入排序和归并排序进行分析和比较时，他们解释了迭代和递归算法的基本属性（有时被称为增量算法，以消除当经典数学概念迭代在相同上下文中使用时的歧义）。

首先，插入排序被归类为迭代算法，其行为总结如下：

“在已经排序好的子数组A[1..j-1]的基础上，我们将单个项A[j]插入到它应该在的位置，从而得到排序好的数组A[1..j]。”

这个描述将迭代算法归类为依赖于先前执行（“迭代”）算法的结果或状态，并且这些结果或状态信息然后用于解决当前迭代的问题的算法。

归并排序，另一方面，被归类为递归算法。递归算法遵循一种称为“分而治之”的处理范例，这是一组区别递归算法和非递归算法操作的三个基本标准。在给定问题的处理过程中，如果一个算法可以被认为是递归的，则需要满足以下条件：

1. 将问题划分为[两个或多个]子问题，其中每个子问题都比原问题小，但可以通过类似于原问题的方式来解决（分治）。 2. 将问题划分为[两个或多个]子问题，其中每个子问题可以通过递归或简单地解决（如果足够小）来解决（征服）。 3. 将问题划分为[两个或多个]子问题，其中这些子问题的结果结合起来得到原问题的解决方案（组合）。

参考资料：算法导论-Cormen，Leisersen，Rivest，1990年麻省理工学院出版社

迭代算法和递归算法都会继续执行，直到达到一个“终止条件”。插入排序中的终止条件是第j个项目已正确放置在数组A [1 .. j ]中。分治算法中的终止条件是范例的标准2“底部”，即子问题的大小达到足够小的规模，可以在不进一步分割的情况下解决。
需要注意的是，分治范式要求子问题必须以类似于原始问题的方式可解，以允许递归。由于原问题是一个独立问题，没有任何外部依赖关系，因此子问题也必须像独立问题一样可解，没有任何外部依赖关系，特别是其他子问题上的依赖关系。这意味着，在分治算法中，子问题应该是自然独立的。
相反，同样重要的是注意到迭代算法的输入是基于先前迭代的结果，并且必须按顺序考虑和处理。这会在迭代之间创建依赖关系，防止算法将问题分解为可以递归解决的子问题。例如，在插入排序中，您不能将项A [1 .. j ]分成两个子集，以便在放置所有项A [1 .. j -1]之前就决定了A [j]在数组中的排序位置，因为A [j]的真正正确位置可能在放置任何A [1 .. j -1]时移动。
递归算法与递归实现
对术语“递归”的普遍误解源于一个常见而错误的假设：递归任务的递归实现自动意味着使用递归算法解决了问题。递归算法并不等同于递归实现，从来没有。
一种递归实现涉及到一个函数或一组函数，它们最终会调用自身，以完全相同的方式解决任务的子部分，就像整个任务正在被解决一样。事实上，递归算法（即满足分治范式的算法）往往很适合递归实现。然而，所有算法，包括递归算法，最终都会重复执行某些任务以获得结果，因此可以使用迭代结构（如for(...)和while(...)）来实现递归算法。
本帖的其他贡献者已经完美地证明了迭代算法可以使用递归函数来实现。事实上，对于任何需要迭代直到满足某个终止条件的任务，都可以进行递归实现。如果在底层算法中没有分割或合并步骤，则递归实现等效于具有标准终止条件的迭代实现。
以插入排序为例，我们已经知道（并已经证明）插入排序是一种迭代算法。然而，这并不妨碍插入排序的递归实现。事实上，可以非常容易地创建一个递归实现，如下所示：
function insertionSort(array) if (length(array) == 1) return array end itemToSort = array[length(array)] array = insertionSort(array[1 .. (length(array)-1)]) find position of itemToSort in array insert itemToSort into array return array end

可以看出，这个实现是递归的。然而，插入排序算法是迭代的，我们知道这一点。那么，即使使用上述递归实现，我们如何知道我们的插入排序算法没有变成递归？让我们将“分治”范式的三个标准应用于我们的算法并检查一下。
问题被分成[两个或更多]子问题，每个子问题都比原问题小，但可以用类似的方法解决。
是的：除了长度为一的数组外，将项A [j]插入其在数组中的正确位置的方法与将所有先前的项A [1 .. j-1]插入数组中使用的方法相同。
问题被分成[两个或更多]子问题，每个子问题都是独立的，如果足够小，则可以递归地或以简单的方式解决。
不是的：项A [j]的正确放置完全取决于包含A [1 .. j-1]项的数组以及这些项的排序。因此，在处理完数组的其余部分之前，不会将项A [j]（称为itemToSort）放入数组中。
问题被分成[两个或更多]子问题，这些子问题的结果合并以给出原始问题的解决方案。
不是的：作为迭代算法，任何给定迭代中只能正确放置一个项A [j]。空间A [1 .. j]没有被分成子问题，其中A [1]，A [2] ... A [j]都是独立放置的，然后将所有这些已正确放置的元素组合在一起以给出排序后的数组。
显然，我们的递归实现没有使插入排序算法具有递归性质。实际上，在这种情况下，实现中的递归充当了流控制，使迭代继续进行，直到满足终止条件。因此，使用递归实现并没有将我们的算法转变为递归算法。
无使用迭代算法反转数组
既然我们理解了什么是迭代算法，什么是递归算法，那么如何“不使用迭代”来反转一个数组呢？
有两种方法可以反转一个数组。这两种方法都需要您事先知道数组的长度。迭代算法因其效率而受到青睐，其伪代码如下：
function reverse(array) for each index i = 0 to (length(array) / 2 - 1) swap array[i] with array[length(array) - i] next end

这是一个纯迭代算法。让我们通过将其与分治范例进行比较来分析为什么我们可以得出这个结论，该范例确定了算法的“递归性”。
问题被分解成[两个或更多]子问题，每个子问题都比原问题小，但可以用类似的方法解决。
是的：数组的反转被分解为其最细微的粒度，即元素，并且对于每个元素的处理与所有其他处理过的元素相同。
问题被分解成[两个或更多]子问题，每个子问题都是独立的，如果足够小，则可以递归地或以简单的方式解决。
是的：在不需要反转元素(i+1)的情况下，可以反转数组中的元素i。此外，反转数组中的元素i不需要其他元素反转的结果才能完成。
问题被分解成[两个或更多]子问题，这些子问题的结果合并以给出原始问题的解决方案。
不是的：作为迭代算法，每个算法步骤只执行一个计算阶段。它不将问题分解为子问题，并且没有合并两个或多个子问题的结果来获得结果。
我们第一个算法的上述分析证实它不符合分治范例，因此不能被视为递归算法。然而，由于标准（1）和标准（2）都得到了满足，显然递归算法是可能的。
关键在于我们迭代解决方案中的子问题具有最小的粒度（即元素）。通过将问题分成越来越小的子问题（而不是从一开始就追求最细的粒度），然后合并子问题的结果，可以使算法变成递归的。
例如，如果我们有一个包含拉丁字母表前16个字母（A..P）的16个元素的数组，则递归算法的视觉效果如下：
Original Input 1. ABCDEFHGIJKLMNOP Divide 2. ABCDEFGH IJKLMNOP Divide 3. ABCD EFGH IJKL MNOP Divide 4. AB CD EF GH IJ KL MN OP Divide 5. A B C D E F G H I J K L M N O P Terminate 6. BA DC FE HG JI LK NM PO Conquer (Reverse) and Merge 7. DCBA HGFE LKJI PONM Conquer (Reverse) and Merge 8. HGFEDCBA PONMLKJI Conquer (Reverse) and Merge 9. PONMLKJIHGFEDCBA Conquer (Reverse) and Merge Reversed Output

从最高层开始，16个元素逐步分成完全相等的更小的子问题大小（从第1到第4级），直到我们达到最细粒度的子问题；按顺序排列的单元长度数组（步骤5，单个元素）。此时，我们的16个数组元素仍然呈现出有序状态。但是，它们同时也被反转了，因为单个元素数组本身也是一个反转的数组。然后将单个元素数组的结果合并以获得长度为2的8个反转数组（步骤6），再次合并以获得长度为4的4个反转数组（步骤7），直到我们的原始数组已经以相反的顺序重构（步骤6至9）。
用于递归算法反转数组的伪代码如下：
function reverse(array) /* check terminating condition. all single elements are also reversed * arrays of unit length. */ if (length(array) < 2) then return array /* divide problem in two equal sub-problems. we process the sub-problems * in reverse order so that when combined the array has been reversed. */ return reverse(array[(n/2) .. (n-1)]) + reverse(array[0 .. ((n/2)-1)]) end

正如您所看到的，该算法将问题分解为子问题，直到达到可以立即得出结果的最细粒度的子问题。然后在合并结果时将其反转以给出反转的结果数组。虽然我们认为这个算法是递归的，但让我们应用“分而治之”算法的三个标准来确认。
问题被划分为两个或更多的子问题，每个子问题都比原问题小，但可以用类似的方式解决。
是的：在第一级反转数组可以使用与第2、3、4或5级完全相同的算法。
问题被划分为两个或更多的子问题，每个子问题都是独立的，如果足够小，则可以通过递归或简单的方式解决。
是的：除了单位长度之外的每个子问题都通过将问题分成两个独立的子数组并递归地反转这些子数组来解决。单位长度的数组，即可能的最小数组，本身被反转，从而提供终止条件和保证第一个组合结果。
问题被划分为两个或更多的子问题，这些子问题的结果被组合以给出原始问题的解决方案。
是的：每个级别6、7、8和9的问题仅由上一级立即以上级别的结果组成；即它们的子问题。每个级别反转数组会导致整体反转的结果。
如下所示，我们的递归算法通过了分治范式的三个标准，因此可以被认为是一个真正的递归算法。因此，可以不使用迭代算法来反转数组。 有趣的是，我们最初用于数组反转的迭代算法可以使用递归函数实现。这样实现的伪代码如下：
function reverse(array) if length(array) < 2 return end swap array[0] and array[n-1] reverse(array[1..(n-1)]) end

这与其他帖子中提出的解决方案类似。这是一个递归的实现，因为定义的函数最终会调用自身，以重复执行相同的任务，覆盖数组中的所有元素。但是，这并不使算法成为递归算法，因为没有将问题划分为子问题，也没有合并子问题的结果以给出最终结果。在这种情况下，递归仅被用作流程控制构造，在算法上整体的结果可以证明执行相同的步骤序列，以完全相同的顺序，与最初提出的迭代算法一样。
这就是迭代算法、递归算法和递归实现之间的区别。