Início / coding / Perguntas / 77164838
Accepted
Sai
Asked: 2023-09-24 04:46:28 +0800 CST

Encontre o menor número inteiro positivo, que não divide nenhuma diferença mútua de inteiros em uma matriz

  • 772

Dado um array A consistindo em N inteiros positivos.

Encontre o menor número inteiro positivo, d, st, não existe nenhum par de inteiros (i,j)(1<=i<j<= N) onde abs(A_i - A_j) é divisível por d.

Dados N elementos, e assumindo todos únicos, o número de diferenças pode ser:

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)º;
.
.
.
2º - 1º;
ou seja, um total de N(N-1)/2 diferenças.

Deixe o array de inteiros ser chamado: arr. Então, tenha:

int arr[N];

Não tenho ideia de como resolver esse problema de uma maneira melhor do que a força bruta, na qual definitivamente existe O (N ^ 2) complexidade de tempo.

Mas parece que uma maneira mais fácil é calcular o mdc de dois números, digamos, tomando o menor número inteiro

d = arr[0]

Então, é possível calcular recursivamente o

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

Mas não consigo descobrir se está correto.

  `
       #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);
       }
  `

O resultado obtido sugere que a implementação da lógica no programa pode estar errada, como obter entradas de: 12, 23, 34, 45, 56, 67; resposta de 1. O valor único das diferenças abs(arr[i]-arr[j]) são:

  `
       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,
  `

Portanto, o mdc deveria ser 11; embora não esteja claro se o GCD é necessário ou não.

Além disso, a resposta deve ser: 10.

algorithm

1 respostas

  1. Best Answer

    Sua abordagem é interessante, mas vejo um problema na sua lógica. Deixe-me esclarecer o problema e, em seguida, orientá-lo na solução.

    A declaração do problema pede o menor número inteiro positivo (d) tal que ( |A[i] - A[j]| ) não seja divisível por (d) para qualquer par (i, j). Em vez de calcular diretamente o mdc de toda a matriz, você deve calcular as diferenças entre todos os elementos da matriz e, em seguida, determinar o mdc dessas diferenças. Isso ocorre porque, por definição, se (d) divide todas as diferenças na matriz, então ( |A[i] - A[j]| ) será divisível por (d).

    Então, o algoritmo correto seria:

    1. Calcule todas as diferenças entre os elementos da matriz.
    2. Calcule o mdc dessas diferenças.
    3. Retorne o mdc como resposta.

    Veja como você pode corrigir seu código:

    #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]
}

    Para a entrada fornecida: 12, 23, 34, 45, 56, 67, o mdc das diferenças seria de fato 11.

    No entanto, esta abordagem ainda tem uma complexidade (O(N^2)) devido ao cálculo de todas as diferenças entre pares. Dependendo das restrições do problema, isso pode ou não ser suficientemente eficiente.

    • -2

relate perguntas