найти максимальный массив, из которого можно удалить некоторые элементы, чтобы получились другой данный массив
Дан массив А длины N, и K массивов M1,...,Mk длин m1,...,mk. Требуется найти наибольший по длине массив среди M1,...,Mk , который может быть получен из массива A при помощи удаления каких-либо элементов массива A. Все данные читаются из файлов. Все массивы M1,...,Mk записаны по порядку в одном файле: первые два числа в файле - кол-во элементов SizeM, и кол-во массивов K. Далее, идут массивы: первое число - длина массива Mi, далее сам массив Mi. Написал такой код на си, но когда запускаю он не решает задачу, а возвращает рандомное число. Хотелось бы узнать, на что стоит обратить внимание, чтобы пофиксить это недорозумение.
#include <stdio.h>
#include <stdlib.h>
int Process(int* dataA, int* dataM, int n, int index);
int ReadArray(FILE* file, int* data, int size);
int ReadArray(FILE* file, int* data, int size){
for(int i = 0; i < size; i++){
if(fscanf(file, "%d", data + i) != 1){
return -1;
}
}
return 0;
}
int Process(int* dataA, int* dataM, int n, int index){
int tmp1 = dataM[index];
int tmp2 = index;
int ind = 0;
for(int i = 0; i < n; i++){
for(int j = (tmp2+1); j < (tmp2+tmp1+1); j++){
if(dataA[i] == dataM[j]){
ind++;
tmp2 = j-1;
break;
}
}
}
if(ind == n){
return tmp1;
}
else{
return -1;
}
}
int main(void){
FILE* finA;
FILE* finM;
int* dataA;
int* dataM;
int n;
int k;
int sizeM;
int index = 0;
int indexmax1 = -1;
int indexmax2 = 0;
if((finA = fopen("inputA.txt", "rt")) == NULL){
printf("Can't open input file!\n");
return -1;
}
if(fscanf(finA, "%d", &n) != 1){
printf("Can't read size!\n");
fclose(finA);
return -1;
}
if(n < 1){
printf("Incorrect size!\n)");
fclose(finA);
return -1;
}
if((dataA = (int*) malloc(n * sizeof(int))) == NULL){
printf("Can't allocate memory!\n");
fclose(finA);
return -1;
}
if(ReadArray(finA, dataA, n) < 0){
printf("Can't read array!\n");
free(dataA);
fclose(finA);
return -1;
}
if((finM = fopen("inputM.txt", "rt")) == NULL){
printf("Can't open input file!\n");
return -1;
}
if(fscanf(finM, "%d", &sizeM) != 1){
printf("Can't read size!\n");
fclose(finM);
return -1;
}
if(fscanf(finM, "%d", &k) != 1){
printf("Can't read count of files!\n");
fclose(finM);
return -1;
}
if(n < 1){
printf("Incorrect size!\n)");
fclose(finM);
return -1;
}
if((dataA = (int*) malloc(sizeM * sizeof(int))) == NULL){
printf("Can't allocate memory!\n");
fclose(finM);
return -1;
}
if(ReadArray(finM, dataM, sizeM) < 0){
printf("Can't read array!\n");
free(dataM);
fclose(finM);
return -1;
}
for(int i = 0; i < k; i++){
if(indexmax1 < Process(dataA, dataM, n, index)){
indexmax1 = Process(dataA, dataM, n, index);
indexmax2 = index;
}
index += Process(dataA, dataM, n, index)+1;
}
if(indexmax1 != -1){
for(int i = indexmax2; i < (indexmax2+indexmax1+1); i++){
printf("%d\n", dataM[i]);
}
free(dataA);
free(dataM);
return 0;
}
else{
printf("There are no need sequences!");
free(dataA);
free(dataM);
return -1;
}
}
Ответы (1 шт):
Вы два раза выделяете память на один указатель.
// первый раз
if((dataA = (int*) malloc(n * sizeof(int))) == NULL)
{}
// второй раз
if((dataA = (int*) malloc(sizeM * sizeof(int))) == NULL)
{}
А массив dataM остается невыделенным. И вы пытаетесь туда записывать значения.
Ещё один момент - вы уверены, что оптимизатор отработает как надо и в этом куске функция Process() вызовется 1 раз, а не 3?
for(int i = 0; i < k; i++)
{
if(indexmax1 < Process(dataA, dataM, n, index))
{
indexmax1 = Process(dataA, dataM, n, index);
indexmax2 = index;
}
index += Process(dataA, dataM, n, index)+1;
}
// Может проще
for(int i = 0; i < k; i++)
{
int tmp = Process(dataA, dataM, n, index);
if(indexmax1 < tmp)
{}
Ну и последнее (возможно самое главное) функция int Process() делает не то, что требуется в условии задачи. Вам нужно, чтобы массив Mi являлся подмножеством массива A. А на самом деле функция считает количество совпадений элементов между массивами в штуках.
Пример A[] = {1,2,3} и M[] = { 1, 1, 1};. Результатом вашей функции будет число 3, которое совпадет с размером массива A, что вы почему-то считаете правильным ответом.
По условию задачи, массив М будет меньше или равен массиву А и совпадений между элементами будет меньше (или равно).
Ещё нельзя забывать, что элементы могут повторяться, как в массиве А, так и в М.