主页 / coding / 问题 / 77164838
Accepted
Sai
Asked: 2023-09-24 04:46:28 +0800 CST

找到能够整除数组中整数之间互不差的最小正整数

  • 772

给定一个由 N 个正整数组成的数组 A。

找到最小的正整数 d, st，不存在整数对 (i,j)(1<=i<j<= N)，其中 abs(A_i - A_j) 可被 d 整除。

给定 N 个元素，并假设所有元素都是唯一的，差异的数量可以是：

第 N - 第 1 个、第 N - 第 2 个、...、第 N - 第 (N-1) 个；
第(N-1)个 - 第1个，第(N-1)个 - 第2个，...，第(N-1)个 - 第(N-2)个；
第(N-2)个-第1个、第(N-2)个-第2个、第(N-2)个-第3个、...、第(N-2)个-第(N-3)个；
。
。
。
第二名 - 第一名；
即总共有 N(N-1)/2 个差异。

让整数数组称为：arr。那么，有：

int arr[N];

我不知道如何以比暴力更好的方式解决这个问题，其中绝对存在 O(N^2) 时间复杂度。

但是，似乎更简单的方法是计算两个数字的 gcd，比如说取最小的整数

d = arr[0]

那么是否可以递归计算

gcd(d, arr[i]), i=1,2,3,..., N-1。

但是，我什至不知道它是否正确。

  `
       #include <limits.h>
       #include <stdio.h>
       #include <stdlib.h>
       #include <string.h>

       int checked_atoi (const char *from) {
         char *endptr= NULL;
         long lval= strtol(from, &endptr, 10);
         if (*endptr) {
           fprintf(stderr, "invalid number '%s'\n", from);
           exit(12);
         } 
         else if (lval<INT_MIN || lval>INT_MAX) {
           fprintf(stderr, "value '%ld' out of range\n", lval);
           exit(13);
         }
         return (int)lval;
       }

       int gcd(int a, int b, int c){
         if (b==0)
           return a;
        printf("\n step: %d<> gcd : a: %d, b: %d", c++, a, b);
        return gcd(b, a%b, c);
       }
       int find_smallest_d(int *arr, int N){
         int smallest_d = arr[0];
            printf("\n find_smallest_d");
            for (int i=1; i<N; i++){
               smallest_d = gcd(smallest_d, arr[i], 1);
            }
         return smallest_d;
       }
       int main(int argc, char *argv[]){
          int N=argc-1;
          printf("The size of array: %d", N);
         
          int arr[N];
          for (int i=0; i<N; ++i) {
            arr[i]= checked_atoi(argv[i+1]);
          }
          printf("The %d values:", N);
          for (int i=0; i<N; ++i) {
            printf(" %d", arr[i]);
          }
          printf("\n");
          int smallest_d = find_smallest_d(arr, N);
          printf("\n smallest value of d is: %d", smallest_d);
       }
  `

得到的结果表明程序中逻辑的实现可能是错误的，如获取输入：12,23,34,45,56,67；1. 差异abs(arr[i]-arr[j])的唯一值是：

  `
       1. abs(12-23) = 11,
       2. abs(12-34) = 22,
       3. abs(12-45) = 33,
       4. abs(12-56) = 44,
       5. abs(12-67) = 55,
  `

因此，gcd应该是11；虽然不清楚是否需要 gcd。

另外，答案应该是：10。

algorithm

1 个回答

  1. Best Answer

    你的方法很有趣，但我发现你的逻辑有问题。让我澄清问题，然后引导您完成解决方案。

    问题陈述要求最小的正整数 (d)，使得 ( |A[i] - A[j]| ) 对于任何 (i, j) 对都不能被 (d) 整除。您应该计算数组中所有元素之间的差异，然后确定这些差异的 gcd，而不是直接计算整个数组的 gcd。这是因为，根据定义，如果 (d) 除以数组中的所有差值，则 ( |A[i] - A[j]| ) 将能被 (d) 整除。

    所以，正确的算法是：

    1. 计算数组元素之间的所有差异。
    2. 计算这些差异的 gcd。
    3. 返回 gcd 作为答案。

    以下是更正代码的方法：

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

int checked_atoi (const char *from) {
    // [Your existing checked_atoi implementation]
}

int gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

int find_smallest_d(int *arr, int N){
    int smallest_d = abs(arr[1] - arr[0]);
    for (int i = 0; i < N; i++){
        for (int j = i + 1; j < N; j++){
            int diff = abs(arr[i] - arr[j]);
            smallest_d = gcd(smallest_d, diff);
        }
    }
    return smallest_d;
}

int main(int argc, char *argv[]){
    // [Your existing main implementation]
}

    对于给定的输入：12、23、34、45、56、67，差异的 gcd 确实是 11。

    然而，由于计算所有成对差异，这种方法仍然具有 (O(N^2)) 复杂度。根据问题的限制，这可能足够有效，也可能不够有效。

    • -2

相关问题