Программа C - Рекурсия
У меня есть программа, в которой на поле есть числа и игроки постепенно убирают либо два элемента, либо один справа или слева, игроки ходят по очереди. Я хочу подсчитать все комбинации (суммы игроков). Почему я иногда получаю здесь бессмысленные результаты?
#include <stdio.h>
int rekurze(int *mince, int start, int last, int playerA, int playerB, int player)
{
if (start < last)
{
if (player)
{
if (last-start == 1)
{
rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
}
rekurze(mince, start+2, last, playerA+mince[start]+mince[start+1], playerB, 0);
rekurze(mince, start+1, last, playerA+mince[start], playerB, 0);
rekurze(mince, start+1, last-1, playerA+mince[start]+mince[last], playerB, 0);
rekurze(mince, start, last-1, playerA+mince[last], playerB, 0);
rekurze(mince, start, last-2, playerA+mince[last]+mince[last-1], playerB, 0);
}
else
{
if (last-start == 1)
{
rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
}
rekurze(mince, start+2, last, playerA, playerB+mince[start]+mince[start+1], 1);
rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
rekurze(mince, start+1, last-1, playerA, playerB+mince[start]+mince[last], 1);
rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
rekurze(mince, start, last-2, playerA, playerB+mince[last]+mince[last-1], 1);
}
}
else if (start==last)
{
if (player)
playerA += mince[start];
else
playerB += mince[start];
}
printf("Skore A: %d, ", playerA);
printf("Skore B: %d\n", playerB);
}
int main (void)
{
int mince[] = {3,5,3};
int konec = (sizeof(mince)/sizeof(int))-1;
int start = 0;
rekurze (mince, start, konec, 0, 0, 1);
}
Ответы 1
вы получаете бессмысленные результаты, потому что ваши операторы printf не находятся в блоке else if.
Следовательно, когда if (start < last) и else if (start==last) ложны, вы все равно печатаете значения в ситуациях, которые недействительны в вашем случае.
И если вы хотите подсчитать возможные уникальные комбинации, вы можете взглянуть на отредактированный код ниже.
#include <stdio.h>
int table[100][100] = {0};
int rekurze(int *mince, int start, int last, int playerA, int playerB, int player)
{
int ans=0;
if (start < last)
{
if (player)
{
if (last-start == 1)
{
ans+=rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
ans+=rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
}
ans+=rekurze(mince, start+2, last, playerA+mince[start]+mince[start+1], playerB, 0);
ans+=rekurze(mince, start+1, last, playerA+mince[start], playerB, 0);
ans+=rekurze(mince, start+1, last-1, playerA+mince[start]+mince[last], playerB, 0);
ans+=rekurze(mince, start, last-1, playerA+mince[last], playerB, 0);
ans+=rekurze(mince, start, last-2, playerA+mince[last]+mince[last-1], playerB, 0);
}
else
{
if (last-start == 1)
{
ans+=rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
ans+=rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
}
ans+=rekurze(mince, start+2, last, playerA, playerB+mince[start]+mince[start+1], 1);
ans+=rekurze(mince, start+1, last, playerA, playerB+mince[start], 1);
ans+=rekurze(mince, start+1, last-1, playerA, playerB+mince[start]+mince[last], 1);
ans+=rekurze(mince, start, last-1, playerA, playerB+mince[last], 1);
ans+=rekurze(mince, start, last-2, playerA, playerB+mince[last]+mince[last-1], 1);
}
return ans;
}
else if (start==last)
{
if (player)
playerA += mince[start];
else
playerB += mince[start];
printf("Skore A: %d, ", playerA);
printf("Skore B: %d\n\n", playerB);
if (table[playerA][playerB] == 0)
{
table[playerA][playerB] = 1;
return 1;
}
return 0;
}
return 0;
}
int main (void)
{
int mince[] = {3,5,3};
int konec = (sizeof(mince)/sizeof(int))-1;
int start = 0;
printf("\nUnique results: %d\n",rekurze (mince, start, konec, 0, 0, 1));
}
Спасибо, я сохраняю количество уникальных значений в переменной ans, а затем сохраняю конкретные значения в поле? Я правильно понимаю?
Если можно еще один вопрос? Можно ли предотвратить повторный подсчет повторяющихся значений?
@ Aaron7 Итак, здесь я сохраняю количество возможных значений в переменной ans. И чтобы избежать дубликатов, я использовал массив table[][]. Массив таблицы сначала равен 0, и для каждого значения я устанавливаю его равным 1. (Вы также можете использовать хэш-структуру данных для этого задания. Прочтите об этом :)) Позже я избегаю дубликатов, проверяя, равно ли это значение 1.
Могу я еще спросить, как мне узнать, в каком вызове рекурсии было получено наибольшее значение игрока А? Для чего первый вызов рекурсии. Какой первый ход должен сделать игрок, чтобы набрать максимальное количество очков?
Вы можете использовать глобальную переменную для отслеживания наивысшего результата, полученного на данный момент, и добавить условие if, когда будет достигнут конец рекурсии. и чтобы отслеживать первый ход, добавьте еще несколько параметров в функцию, чтобы отслеживать первый ход.
Глядя на ответ, рекомендую выработать привычку использовать последовательные отступы. На самом деле вы сделали довольно строгий отступ, даже проблемные строки находятся на отступе, соответствующем ответу. Но вы не отреагировали на очевидный конфликт между этой глубиной отступа и неправильным отношением к ближайшему
}. С укоренившейся привычкой, которая бы вам очень заметно выделялась.