Может кто-нибудь, пожалуйста, помогите мне с ошибкой в ​​алгоритме

Question

Problem ссылка: https://www.codechef.com/problems/PERMUT2

Проблема: Получение не неоднозначным для всех тестовых случаев. В выполнении программы абсолютно нет проблем, нет ошибок.

Можете ли вы указать на ошибку в моем код/​​алгоритм:

#include <stdio.h> 
#include <stdlib.h> 
int index_func(int number, int *array, int x); 
int main(){ 
    int n; 
    scanf("%d", &n); 
    int *nums = (int*)malloc(n*sizeof(int)); 
    int i; 
    for(i=0; i<n; i++){ 
     scanf("%d", &nums[i]); 
    } 
    int j; 
    int counter = 0; 
    for(j=0; j<n; j++){ 

     if(nums[j] != index_func(j+1, nums, n)){ 
      counter = 1; 
      break; 

     } 
    } 
    if(counter == 0){ 
     printf("ambiguous\n"); 
    }else{ 
     printf("non ambiguous\n"); 
    } 
    return 0; 
} 
int index_func(int number, int *array, int x){ 
    int z, index; 
    for(z=0; z<x; z++){ 
     if(number == array[z]){ 
      index = z; 
      return z; 
     } 
    } 

} 

Answer 1

попробовать это решение:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
int index_func(int number, int *array, int x); 
int main(){ 
    int n; 
    scanf("%d", &n); 
    int *nums = (int*)malloc(n*sizeof(int)); 
    int i; 
    for(i=0; i<n; i++) { 
     scanf("%d", &nums[i]); 
    } 
    int j; 
    int counter = 0; 
    for(j=0; j<n-1; j++){ 
     if((abs(nums[j+1] - nums[j]) != abs(n-1)) && (abs((nums[j+1] - nums[j]) != 1))) 
     { 
      counter = 0; 
     } 
     else 
     { 
      counter = 1; 
     } 
    } 
    if(counter == 0){ 
     printf("ambiguous\n"); 
    }else{ 
     printf("non ambiguous\n"); 
    } 
    free(nums); 
    return 0; 
} 

Answer 2

Числа в массиве начинаются с одной, а индексы в массивах C начните с 0. Быстрое исправление вашей программы было бы добавить ее к возвращенному индексу при сравнении с текущим номером:

if (nums[j] != index_func(j + 1, nums, n) + 1) ... 

Альтернативным решением является настройка данных массива путем вычитания одного из них после сканирования, так что массив содержит нулевые числа.

Проблема может возникнуть с большими массивами, потому что каждый вызов index_func сканирует весь массив с самого начала и будет пересекать половину его в среднем. Решение будет правильным, но очень медленным.

Но вам не нужно определять индекс для сравнения. Достаточно проверить, является ли число в индексе текущего числа текущим индексом. Это приводит к этой функции:

int is_ambiguous(const int *array, int n) 
{ 
    int i; 

    for (i = 0; i < n; i++) { 
     if (array[array[i] - 1] != i + 1) return 0; 
    } 

    return 1; 
} 

Некоторые замечания по исходному коду:

• Вы должны вернуть неверный индекс, вероятно, − 1, из index_funct когда Nuber не в массиве. Я знаю, это не должно произойти здесь, но в следующий раз вы скопируете и вставьте код, а недостающее возвращаемое значение может вас укусить.
• Вам не нужна переменная index в index_funct. Разделение фрагментов кода на небольшие функции может облегчить управление программой. Сравните приведенную выше функцию is_ambiguous с вашим встроенным решением с переменной счетчиком и break.
• Когда вы выделяете, вы также должны указать free, которого у вас нет.