счетчик, чтобы проверить, не является ли массив X подпоследовательностью A (C) - PullRequest
Новая
       17

счетчик, чтобы проверить, не является ли массив X подпоследовательностью A (C)

0 голосов
/ 06 октября 2018

Я пытался следовать этой программе вручную, но все еще не могу заставить ее работать.

У меня есть массив A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1] и массив X = [1,2,3].
Мне нужно найтимаксимальное число i для X^i, которое является подпоследовательностью A, и сделать это с помощью двоичного поиска.

Поскольку размер A равен 20, а размер X равен 3,максимально возможный i = 20/3 = 6.Так что мой поиск начнется с i = 3, что означает, что X^3 = [1,1,1,2,2,2,3,3,3].
Это не подпоследовательность A, поэтому двоичный поиск повторяется для i = 1, X^1 = [1,2,3].
Это подпоследовательность A, что означаетон должен пройти, и бинарный поиск должен повторить попытку для i = 2.

Однако, мое условие, чтобы увидеть, проходит ли итерация или нет, не работает должным образом.

Здесьэто код: 

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

void create_initial_arrays(int size_a, int *A, int size_x, int *X);
void binary_search(int size_a, int * A, int size_x, int *X, int max_i, int min_i);

int main(){


    int size_a, size_x;
    scanf("%d", &size_a);
    scanf("%d", &size_x);

    int max_i = size_a / size_x;
    int min_i = 0;

    printf("Max: %d\n", max_i);

    int *A = (int*) malloc(size_a *sizeof(int));
    int *X = (int*) malloc(size_x *sizeof(int));

    create_initial_arrays(size_a, A, size_x, X);

    printf("Old X: ");
    for(int i = 0; i < size_x; i++){
        printf("%d ", X[i]);
    }
    printf("\n");

    binary_search(size_a, A, size_x, X, max_i, min_i);
    free(X);
    free(A);

}

void create_initial_arrays(int size_a, int *A, int size_x, int *X){
    int i, throwaway;

    for(i = 0; i < size_a; i++){
        scanf("%d", &A[i]);
    }

    scanf("%d", &throwaway);

    for(i = 0; i < size_x; i++){
        scanf("%d", &X[i]);
    }

    scanf("%d", &throwaway);
}



void binary_search(int size_a, int * A, int size_x, int *X, int max_i, int min_i){

    int j, k, max_repeat = 0;

    while(min_i <= max_i){

        int i = 0, count = 0, repeats = (max_i + min_i)/2;

        printf("\n");
        int * temp = (int*) malloc(size_x * sizeof(int) * repeats);

        for(k = 0; k < size_x; ++k){
            for(j = 0; j < repeats; ++j){
                temp[k * repeats + j] = X[k];
            }
        }

        printf("New X: ");
            for(i = 0; i < size_x * repeats; i++){
                printf("%d ", temp[i]);
            }

        printf("A: ");
        for (i = 0; i < size_a; i++){
            printf("%d ", A[i]);
        }

        for(j = 0; j < size_a; j++){
            if(A[j] == temp[i]){
                count++;
                i++;
            }
        }



        printf("Count: %d", count);


        if (count >= size_x * repeats){
            printf("Low: %d Mid %d High % d Passes\n", min_i, repeats, max_i);
            min_i = repeats + 1;
            max_repeat++;
        }
        else{
            printf("Low: %d Mid %d High % d Fails\n", min_i, repeats, max_i);
            max_i = repeats - 1;
        }

        free(temp);
    }   
        printf("Max repeat: %d", max_repeat);
}

И этот раздел, на мой взгляд, должен быть проблематичным: 

for(j = 0; j < size_a; j++){
            if(A[j] == temp[i]){
                count++;
                i++;
            }
        }

Я вывел оба массива, чтобы убедиться, что они заполнены правильно (они) и счетчик после каждой итерации.Вот мой вывод кода: 

Old X: 1 2 3 

New X: 1 1 1 2 2 2 3 3 3 A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 3 High  6 Fails

New X: 1 2 3 A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 1 High  2 Fails

New X: A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 0 High  0 Passes
Max repeat: 1

Обратите внимание, что количество остается 0 во всемНа первой итерации для X^3 = [1,1,1,2,2,2,3,3,3] условие выполняется 5 раз ([1,1,1,2,2] является подпоследовательностью A, поэтому число должно быть 5, но 5 is not >= size_x * repeats(3 * 3), поэтому оно завершается с ошибкой, как и ожидалось. Двоичный поиск уменьшается до Low 0 Mid 1Высокое 2, поэтому i = repeats = 1.

X^1 = [1,2,3] является подпоследовательностью A, и на этой итерации должно быть 5 ([1,2,3] плюс два дополнительных числа 3), что составляет >= size_x * repeats (3*1),поэтому он должен пройти и повторить поиск i = 2. Однако счет остается равным нулю и дает сбой.

Почему счет не обновляется? Я знаю, что мне нужно держать его в цикле, потому что мне нужно сбросить его на0 для каждой итерации, но я не совсем понимаю, почему A[j] == temp[i] никогда не проходит.

...