C – 数组中最小间隙的递归函数

发布时间：2020-12-16 10:05:20 所属栏目：百科来源：网络整理

导读：我正在尝试优化一个函数,给定一个N int数组,返回一个元素和前一个元素之间的最小差异.显然,该函数仅适用于维度 = 2的数组. 例如,给定数组{2,5,1},函数返回-4. 我试着写我的代码,但我认为它真的错综复杂. #include stdio.h#define N 4/*Function for the diff

我正在尝试优化一个函数,给定一个N int数组,返回一个元素和前一个元素之间的最小差异.显然,该函数仅适用于维度> = 2的数组.
例如,给定数组{2,5,1},函数返回-4.
我试着写我的代码,但我认为它真的错综复杂.

#include <stdio.h>
#define N 4
/*Function for the difference,works because in the main I already gives one difference*/
int minimodiff(int *a,int n,int diff) {
  if (n==1) {
    return diff;
  }
  if (diff>(*(a+1) - *a))
     return minimodiff(a+1,n-1,*(a+1)-*a);
  else return minimodiff(a+1,diff);
}

int main() {
  int a[N]= {1,8,4,3};
  printf("%d",minimodiff(a+1,N-1,*(a+1)-*a));
}

我想知道是否有办法避免传递main中的第一个差异,但是在递归函数中执行所有操作.
我可以使用头文件stdio.h / stdlib.h / string.h / math.h.非常感谢您的帮助,我希望这可以让我更好地理解递归函数.

解决方法

minimodiff(a 1,*(a 1) – * a)是一种使用递归的弱方法,因为它使用N的递归深度,这很容易压倒系统资源的深度限制.在这种情况下,简单的循环就足够了.

一个好的递归方法会在每次调用时将问题减半,找到左半部分和右半部分的最小值.它可能运行得不快,但最大递归深度为log2(N).

// n is the number of array elements 
int minimodiff2(const int *a,size_t n) {
  if (n == 2) {
    return a[1] - a[0]; 
  } else if (n <= 1) {
    return INT_MAX;
  }
  int left = minimodiff2(a,n/2 + 1);  // +1 to include a[n/2] in both halves
  int right = minimodiff2(a + n/2,n - n/2);
  return (left < right) ? left : right;
}

int main() {
  int a[]= {1,minimodiff2(a,sizeof a/ sizeof a[0]));
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!