c - 如何递归地将整数数组的所有项移动到第一个单元格？

Question

我在递归方面遇到了困难。我需要编写一个递归调用的函数来比较两个整数数组。该函数接收两个数组及其对应的长度。

数组包含数字。我的目标最终是将每个数组的所有项目移动到数组的第一个单元格，并让退出条件比较数组的前两个单元格。因为这是一个整数数组，所以我无法理解如何将数字从下一个单元格“连接”到前一个单元格，以及通常如何完成整个操作。我非常感谢您的回答或提示。

解释:

该函数将采用两个数组及其长度作为参数，例如 [123, 456, 7891] 和 [12345, 6, 78, 91]。我的函数需要返回这两个是否相等。

我的想法是，我以某种方式递归地将两个数组中的所有项相应地移动到第一个单元格，然后比较最终返回条件下的单元格，谢谢!

这显然可以用另一种方式来完成，对我来说，只要它有效，哪种方式都无所谓:D

[编辑]:

以下是一些可能的比较:

compare( [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]) => SAME
compare( [12, 34, 5], [1, 2, 3, 4, 5]) => SAME  
compare( [12, 34, 5], [123, 45]) => SAME
compare( [1, 2], [5, 6]) => DIFFER

Answer 1

表示相等的递归求解

在这种情况下，我们不会检查数组是否相等(见下文)，而是检查表示为字符串然后连接起来的数字是否相等。例如:

[1,2,3,4,5] === [12,34,5] === [123,45]

我们的想法是 reduce/fold在每个数组上，将表示的字符串作为我们的最终值，将空字符串作为我们的初始值，获取每个整数，将其转换为字符串，并将其连接到结果的末尾。然后我们发现自己有两个字符串，我们比较它们是否相等。

请注意，我的解决方案存在几个问题。

1. 首先，我没有对字符串操作做任何边界检查，所以下面的代码将愉快地填满你的内存。

2. 我们也不跟踪结果的结尾，这意味着每次连接都需要遍历结果字符串，这不是一种有效的方法。

3. 给定的 itoa 实现的一个限制是它不能正确处理最大的负整数。

但总体思路保持不变。用一种很好的编程语言，你可以写:

(eq?     
  (reduce concat "" (map tostr [1,2,3,4,5] ))
  (reduce concat "" (map tostr [1,2,3,4,5] )))

或等效的；但这是 C，所以我们必须用困难的方式来做:

#include <assert.h>
#include <string.h>

#define SAME 0
#define DIFFER 1

void reverse(char s[]);
void itoa(int n, char s[]);

void reduce_to_string(char *result, int values[], int values_len){
  char tmpstr[256] = "";

  if( values_len == 0 ){ return; }

  // convert the first number to a string, writing the representation to tmpstr
  itoa(values[0], tmpstr);

  // concatenate the first number with the accumulated string
  result = strcat(result, tmpstr);

  // recur with a smaller array.
  return reduce_to_string(result, &values[1], (values_len-1));
}

int compare_representation(int a[], int a_len, int b[], int b_len){
  char a_as_string[512] = "";
  char b_as_string[512] = "";

  reduce_to_string(a_as_string, a, a_len);
  reduce_to_string(b_as_string, b, b_len);

  if( 0 == strcmp(a_as_string, b_as_string) ){ return SAME;}

  return DIFFER;
}


int main(void){

  int b[] = {6,7,8,9};
  int b_len = 4;

  int c[] = {1,2,3,4,5};
  int c_len = 5;

  int d[] = {67, 89};
  int d_len = 2;

  assert(SAME == compare_representation(b,b_len,d,d_len));
  assert(DIFFER == compare_representation(b,b_len,c,c_len));

  return 0;
}



/*
 * The following are from K&R C, second edition.
 */

/* reverse:  reverse string s in place. page 62 */
void reverse(char s[])
{
    int i, j;
    char c;

    for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

/* itoa:  convert n to characters in s. page 64*/
void itoa(int n, char s[])
{
    int i, sign;

    if ((sign = n) < 0)  /* record sign */
        n = -n;          /* make n positive */
    i = 0;
    do {       /* generate digits in reverse order */
        s[i++] = n % 10 + '0';   /* get next digit */
    } while ((n /= 10) > 0);     /* delete it */
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

语法解释:

如果您是 C 语言的新手，使用 &a[1] 作为数组 'a' 的尾部可能不太清楚。

(当我说尾部时，我指的是除第一个元素之外的所有其他元素。)

将其分解为英语 &a[1] 表示类似:“数组 'a' 中第二个值的地址”。为什么这行得通？因为在 C 语言中，数组只不过是指向用于存储变量的内存起始位置的指针，所以获取第二个变量的地址本质上就是一个少了一个元素的数组。为了确保我们考虑到数组更小，我们还减少了数组长度变量“a_len”，然后再将其传递给下一个函数调用。

递归求解和迭代求解(数组相等)

两个 compare_* 函数都在两个整数数组之间进行比较，检查数组是否相同。

#include <assert.h>

#define SAME 0
#define DIFFER 1

int compare_recursive(int a[], int a_len, int b[], int b_len){
  if( a_len != b_len ){ return DIFFER; }
  if( a_len == 0 && b_len == 0 ){ return SAME; }
  if(a[0] == b[0]){
    return compare_recursive(&a[1], (a_len-1), &b[1], (b_len-1) );
  }else{
    return DIFFER;
  }
}

int compare_iterative(int a[], int a_len, int b[], int b_len){
  int i;
  if( a_len != b_len ){ return DIFFER; }
  for(i = 0; i < a_len; i++){
    if( a[i] != b[i] ){ return DIFFER; }
  }
  return SAME;
}

int main(void){
  int a[] = {1,2,3,4,5};
  int a_len = 5;

  int b[] = {6,7,8,9};
  int b_len = 4;

  int c[] = {1,2,3,4,5};
  int c_len = 5;

  assert(DIFFER == compare_recursive(a,a_len,b,b_len));
  assert(SAME == compare_recursive(a,a_len,c,c_len));

  assert(DIFFER == compare_iterative(a,a_len,b,b_len));
  assert(SAME == compare_iterative(a,a_len,c,c_len));

  return 0;
}