Простая рекурсивная функция для определения, являются ли два элемента транзитивно истинными
новичок здесь. Еще новее рекурсии. Я пишу функцию для моей программы на C ++, и, как вы уже заметите, я немного не в курсе, когда дело доходит до рекурсивных алгоритмов. Я был бы очень признателен, если бы кто-то мог исправить мою функцию, чтобы я мог заставить ее работать и, возможно, иметь лучшее представление о том, как потом обрабатывать рекурсию.
Моя функция принимает в качестве параметров двумерный квадратный массив логических значений, целое число i и целое число array_size. Функция возвращает логическое значение.
Массив — это матрица смежности, которую я использую для представления набора условий. Например, если значение в [0] [3] истинно, то 0 -> 3 (если 0, то 3). Если [3] [7] верно, то 3 -> 7 (если 3, то 7). По транзитивному свойству 0 -> 7 (если 0, то 7).
Целое число i является конкретным элементом в наборе условий. Функция вернет true, если этот элемент транзитивно связан с последним элементом в массиве. Последний элемент в массиве является целым числом (array_size — 1),
Целое число array_size — это размер каждого измерения квадратного массива. Если array_size равен 20, то массив равен 20×20.
Идея этой функции состоит в том, чтобы определить, существует ли какой-либо логический «путь» от первого целочисленного элемента до последнего целочисленного элемента по транзитивному свойству. Когда путь существует, функция возвращает true, в противном случае возвращает false. Рекурсивный вызов должен позволить ему обойти все возможные пути, возвращая истину, как только он наконец достигнет последнего элемента, и ложь, если все пути терпят неудачу.
Например, если i = 0 и array_size = 10, функция вернет, действительно ли 0 -> 9 допустимо в соответствии с условиями, предоставленными матрицей и переходным свойством.
Это мой код до сих пор:
bool checkTransitivity(bool **relations, int i, int array_size){
bool isTransitive = false;
if (i == array_size - 1)
{
isTransitive = true;
}
else
{
for (int j = i; j < array_size; j++){
if (relations[i][j])
{
isTransitive = checkTransitivity(relations, j, array_size);
}
}
}
return isTransitive;
В настоящее время функция возвращает true для всех входных данных.
Любая помощь на всех приветствуется. Заранее спасибо!
Решение
РЕДАКТИРОВАТЬ: Эта первая часть не нужна из-за вашего заявления if-else. Перейдите к концу редактирования.
Давайте начнем с того, что является базовым случаем в рекурсивной функции:
if (i == array_size - 1)
{
isTransitive = true;
}
Ну, у вас есть базовый случай, но ничего не возвращается. Вы просто устанавливаете флаг в true. Что вы хотите сделать, это:
if (i == array_size - 1) {
return true;
}
Теперь функция переместится вверх по рекурсивному стеку и вернет true. Конец редактирования.
Но нам все еще нужно исправить рекурсивный случай:
else {
for (int j = i; j < array_size; j++) {
if (relations[i][j]) {
isTransitive = isTransitive || checkTransitivity(relations, j, array_size);
}
}
}
return isTransitive;
|| означает двоичное ИЛИ. Таким образом, у вас есть логика правильно. Вы хотите проверить каждый возможный путь, чтобы увидеть, может ли он туда попасть, но установив isTransitive на результат каждой проверки, isTransitive будет установлен только на последний вызов. При выполнении isTransitive = isTransitive || recursive callisTransitive будет иметь значение true, пока один из вызовов приводит к истинному значению.
Последнее, что я хочу сказать, это предостережение: если relations[i][j] == true а также relations[j][i] == trueваш код все еще будет в бесконечном цикле. Вы должны найти способ устранить потенциальный возврат. Один из способов сделать это — создать другой массив, в котором будут храниться пути, которые вы уже проверили, чтобы вы не зацикливались.
Более подробную информацию можно найти здесь: Глубина Первый Поиск
Другие решения
я считать все, что вам нужно, это break условие прекращения продолжения цикла при обнаружении нетранзитивного элемента. Смотрите ниже (не проверял)
bool checkTransitivity(bool **relations, int i, int array_size){
bool isTransitive = false;
if (i == array_size - 1)
{
isTransitive = true;
}
else
{
for (int j = i; j < array_size; j++){
isTransitive = relations[i][j] && checkTransitivity(relations, j, array_size);
if (!isTransitive)
break;
}
}
return isTransitive;
}