gpt4 book ai didi

arrays - 用分而治之的方法用 C 语言编写一个成本为 O(log(n)) 的算法

转载 作者:行者123 更新时间:2023-12-04 09:30:10 24 4
gpt4 key购买 nike

我必须在 C 中编写一个函数,它将数组和数组的维度作为输入。
我们假设该数组具有以下特征:

  • 数组中的每个元素都不同
  • 数组的第一个元素是奇数,其余元素是偶数
  • 数组中至少有一个奇数元素和一个偶数元素

  • 该函数必须使用分而治之的方法返回偶数元素的第一个索引,并且算法的成本应该是 O(log(n))。
    在正常情况下,我会使用这样的函数:
    int foo(int v[], int n){
    for(int i=0; i<n; i++){
    if(v[i]%2==0)
    return i;
    }
    }
    但我不知道如何用分而治之的方法解决这个问题。
    是否可以使用合并排序 o 快速排序算法的修改版本来解决问题?

    最佳答案

    想想这个:
    你的输入是 (1,3,5,7,......,2,4,6,8) 并且它的长度是 n。
    你的输出肯定不会是 0(你知道它是奇怪的),但它可能不会是最后一个。
    分而治之背后最重要的概念是征服较小的东西更简单。因此,将您的数组分为两部分,只看一侧,确保另一部分不会包含您的结果。
    假设我们的数组(从现在起称为“a”)的索引从 0 到 n-1 (a[n-1] = 8)。让我们检查中间,所以首先我们需要一个索引。

    int mid = (0 + n-1)/2
    什么是[中]?
  • 奇怪吗?然后我们要看看右边,从mid+1到n-1
  • 是吗?我们有两种可能:
  • mid-1 是一个有效的索引并且 a[mid-1] 是奇数吗?那么 a[mid] 是第一个偶数元素,mid 是结果
  • 否则从 0 到中间 1 查看左侧


  • 然后递归地做:)
    我不太习惯 C 所以我会写伪代码
    int exercise(int[] a, int n) {
    return exerciseRecursive(a, 0, n-1);
    }

    int exerciseRecursive(int[] a, int start, int end) {
    if (start>end) {
    return -1; //there is no even element
    }
    int mid = (start + end)/2;
    if (a[mid]%2==1) { //odd
    return exerciseRecursive(a,mid+1,end);
    }
    else {
    if (mid-1>=0 && a[mid-1]%2==1) { //the current element is even and the previous is odd
    return mid;
    }
    else {
    return exerciseRecursive(a,start,mid-1);
    }


    }
    }

    关于arrays - 用分而治之的方法用 C 语言编写一个成本为 O(log(n)) 的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62880734/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com