I've tried following this program by hand, but I still can't get it to work. I have an Array A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1] and array X = [1,2,3]. I need to find the max number i for X^i that is a subsquence of A, and do this by binary search. Since size of A is 20, and size of X is 3, the max possible i = 20/3 = 6. So my search will start at i= 3, which means that X^3 = [1,1,1,2,2,2,3,3,3]. This is not a subsequence of A, so binary search repeats for i = 1, X^1 = [1,2,3]. This is a subsequence of A, meaning it should pass and binary search should try again for i = 2. However, my condition to see if the iteration passes or not is not working properly.
Here is the code:
#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);
}
And this is the section that I think must be problematic:
for(j = 0; j < size_a; j++){
if(A[j] == temp[i]){
count++;
i++;
}
}
I've output both Arrays to make sure they are populated correctly (they are) and the counter after each iteration. Here is my code output:
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
Notice that count remains 0 throughout. On the first iteration for X^3 = [1,1,1,2,2,2,3,3,3], the condition is true 5 times ([1,1,1,2,2] is a subsequence of A, so count should be 5, but 5 is not >= size_x * repeats(3 * 3), so it fails as expected. Binary search reduces to Low 0 Mid 1 High 2, so i = repeats = 1.
X^1 = [1,2,3] is a subsequence of A, and count should be 5 on this iteration ([1,2,3] plus two extra counts of 3) which is >= size_x * repeats (3*1), so it should pass, and redo the search for i = 2. However, count remains zero and fails.
Why is count not updating? I know I need to keep it in the loop because I need it reset to 0 for each iteration, but I don't really understand why A[j] == temp[i] is not ever passing.
Aucun commentaire:
Enregistrer un commentaire