ребята.У меня есть проект, где мне дают несколько стульев, несколько зонтиков и расположение стульев.Я думаю, нужно найти оптимальную ширину всех зонтов (все равны друг другу), чтобы покрыть каждый стул.Я создал этот фрагмент кода, который работает для примеров случаев в файле подборки (он грязный, но работает):
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void search();
int* constructParasols();
int check();
void draw();
int main(void)
{
int n, k, totalSize;
scanf("%d", &n);
printf("\n");
scanf("%d", &k);
printf("\n");
int* chairs = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < n; i++)
{
scanf("%d", &chairs[i]);
}
printf("\n");
totalSize = chairs[n - 1];
search(n, k, chairs, totalSize, 0, totalSize/k);
free(chairs);
chairs = NULL;
system("pause");
}
void search(int n, int k, int* chairs, int totalSize, int low, int hi)
{
int mid = (low + hi)/2;
int tempPos = 0;
if (low >= hi - 1)
{
if (check(n, k, low, chairs, constructParasols(k,totalSize,low), k - 2, totalSize - (low * 2), totalSize) == 1)
{
printf("width %d is optimal\n", low);
}
else if (check(n, k, hi, chairs, constructParasols(k, totalSize, hi), k - 2, totalSize - (low * 2), totalSize) == 1)
{
printf("width%d is optimal\n", hi);
}
else
{
printf("no solution found\n");
}
}
else if (check(n, k, mid, chairs, constructParasols(k, totalSize, mid), k - 2, totalSize - (mid * 2), totalSize) == 1)
{
search(n, k, chairs, totalSize, low, mid-1);
}
else
{
search(n, k, chairs, totalSize, mid+1, hi);
}
}
int* constructParasols(int k, int totalSize, int width)
{
int* parasols = (int*)calloc(k + 1, sizeof(int));
int tempPos = 0;
for (int i = 0; i < k - 1; i++)
{
parasols[i] = tempPos;
tempPos += width;
}
parasols[k - 1] = totalSize - width;
return parasols;
}
int check(int n, int k, int width, int* chairs, int* parasols, int pNum, int maxPos, int totalSize)
{
int* cover = (int*)calloc(totalSize + 1, sizeof(int));
int failed = 0;
for (int i = 0; i < totalSize; i++)
{
cover[i] = 0;
}
if (k<=2)
{
draw(n, k, width, chairs, parasols, totalSize);
for (int i = 0; i < width; i++)
{
cover[i] = 1;
if(k==2) cover[parasols[1] + i] = 1;
}
for (int i = 0; i < n; i++)
{
if (cover[chairs[i] - 1] == 0)
{
failed = 1;
}
}
if (failed == 0)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 1;
}
else
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 0;
}
}
draw(n, k, width, chairs, parasols, totalSize);
for (int i = 0; i < k; i++)
{
for (int j = 0; j < width; j++)
{
cover[parasols[i] + j] = 1;
}
}
for (int i = 0; i < n; i++)
{
if (cover[chairs[i]-1] == 0)
{
failed = 1;
}
}
if (failed == 0)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 1;
}
if (pNum <= 1 && parasols[pNum] == maxPos)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 0;
}
else if (parasols[pNum] == maxPos)
{
free(cover);
cover = NULL;
return check(n, k, width, chairs, parasols, pNum - 1, maxPos - width, totalSize);
}
else
{
free(cover);
cover = NULL;
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
}
void draw(int n, int k, int width, int* chairs, int* parasols, int totalSize)
{
int* dCover = (int*)calloc(totalSize, sizeof(int));
int* chairPos = (int*)calloc(totalSize, sizeof(int));
for (int i = 0; i < totalSize; i++)
{
dCover[i] = 0;
chairPos[i] = 0;
}
for (int i = 0; i < k; i++)
{
for (int j = 0; j < width; j++)
{
if (dCover[parasols[i] + j] >= 1) dCover[parasols[i] + j] = 2;
else dCover[parasols[i] + j] = 1;
}
}
for (int i = 0; i < n; i++)
{
chairPos[chairs[i]-1] = 1;
}
for (int i = 0; i <= totalSize; i++)
{
if (dCover[i] == 2)
{
printf("=");
}
else if (dCover[i] == 1)
{
printf("-");
}
else
{
printf(" ");
}
}
printf("\n");
for (int i = 0; i <= totalSize; i++)
{
if (chairPos[i] == 1)
{
printf("|");
}
else
{
printf(" ");
}
}
printf("\n");
free(dCover);
dCover = NULL;
free(chairPos);
chairPos = NULL;
return;
}
(некоторые комментарии и отладочные отпечатки удалены для ясности и уменьшенного размера)
Однако это были только два образца из десяти, которые он попытается сделать.Я хочу, чтобы все они были правильными, потому что я перфекционист в программировании, и я заметил слепую точку в том, как я проверяю, работает ли обложка.Прямо сейчас, он возьмет второй зонтик справа и перетянет его на пробел через пробел и проверяет каждый раз.Как только он касается зонта справа от него, он запускается со следующего зонта слева и будет делать это до тех пор, пока не останется только крайний левый угол, и решит, что эта конфигурация не удастся.
Это означает, чточто если я дам пример ввода, например, 8 4 1 3 6 9 12 15 17 20, он не сможет проверить ситуацию, в которой зонтики имеют ширину 4 и равномерно распределены.Я решил исправить это, изменив это:
else
{
free(cover);
cover = NULL;
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
(где он пытается отодвинуть зонтик влево и попытаться снова) на следующее:
else
{
printf("freeing cover\n");
free(cover);
cover = NULL;
printf("iteration failed\n");
//parasols[pNum]++;
//return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
if (parasols[pNum] != parasols[pNum - 1] + width && check(n, k, width, chairs, parasols, pNum - 1, parasols[pNum]-width, totalSize) == 1)
{
return 1;
}
else
{
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
}
Кажетсяпридавать смысл.Только когда я запускаю его сейчас, я получаю нарушение прав на чтение.Прямо здесь:
else dCover[parasols[i] + j] = 1;
dCover.Под командой draw.
Он захватит зонтик и сдвинет его вправо, проверит его, затем захватит зонтик слева от него и сдвинет его вправо.Как я и ожидал.Только после выдает исключение.
Если я возвращаю код, все работает отлично.Я понятия не имею, как это связано с этим - это два совершенно разных указателя.Я использую Visual Studio 2017 для создания этого, если это имеет значение.Кто-нибудь может мне помочь?