Используйте бинарный поиск, чтобы найти последовательность чередования в C

Question

У меня есть два массива, A и X, где A >= X. Я хочу найти максимальный коэффициент перемежения i для X^i, такой, что X^i является подпоследовательностью A. Например, если A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1], и X = [1,2,3], тогда i = 1, потому что X^1 = [1,2,3] и эта последовательность находится в A. Моя программа должна использовать бинарный поиск, чтобы найти этот максимальный коэффициент чередования i и проследить, является ли каждая итерация последовательностью A. Поэтому, используя бинарный поиск для приведенного выше примера, я бы начал = 3 (максимально возможное для A/X = 6), и X^3 = [1,1,1,2,2,2,3,3,3], и это не последовательность в A.

Вот мой код до сих пор:

#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); //practice reallocating size of array


    //for(int i = 0; i < size_x; i++){
      //  printf("%d ", A[i]);
    //}



}

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 i, j, k, count = 0, max_repeat = 0;

    while(min_i <= max_i){

    int repeats = (max_i + min_i)/2;

    printf("\n");

    int * temp = realloc(X, size_x * sizeof(int) * repeats);
    X = temp;

    for(k = 0; k < size_x; ++k){
        int idx = size_x - k -1;
        temp = &X[idx];
        for(j = 0; j < repeats; ++j){
            X[idx * repeats + j] = *temp;
        }
    }

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

    for(i = 0; i < size_x * repeats; i++){
        for(j = 0; j < size_a; j++){
            if(A[j] == X[i]){
                count++;
                i++;
            }
        }
    }

    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;
    }

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

Вот мой текущий вывод:

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

New X: 1 1 1 Low: 0 Mid 1 High  2 Fails

New X: Low: 0 Mid 0 High  0 Fails

Я ожидаю этого:

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

New X: 1 2 3 Low: 0 Mid 1 High  2 Passes

New X: Low: 2 Mid 2 High  2 Fails

Max i = 1.

Это означает, что мой код не создает правильный массив на второй итерации. X^1 должно равняться [1,2,3], а не [1,1,1]. Почему он не создает массив правильно на второй итерации, а на первой?

Answer 1

Почему он не создает массив правильно на второй итерации, а на первой?

В первом цикле вы берете X который {1, 2, 3} и изменить его в {1, 1, 1, 2, 2, 2, 3, 3, 3} повторяя первое число 3 раза, повторяя второе число 3 раза и повторяя третье число 3 раза.

Во втором цикле вы начинаете с X являющийся {1, 1, 1, 2, 2, 2, 3, 3, 3}, Теперь вы строите новый X повторяя первое число 1 раз, повторяя второе число 1 раз и повторяя третье число 1 раз.

Как первое, второе и третье числа все 1 вы в конечном итоге {1, 1, 1}

Другими словами: ваш первый цикл изменился X и, следовательно, вы второй цикл использовать другое значение для X чем первый цикл. Следовательно, второй цикл выдает неожиданное значение для X