Использование одномерного массива в рекурсии

Question

Использование одномерного массива в рекурсии

Недавно я работал над проблемой раздела. Я провел исследование и обнаружил, что его можно решить с помощью алгоритма на вики-странице. Вот псевдоалгоритм:

   INPUT:  A list of integers S
OUTPUT: True if S can be partitioned into two subsets that have equal sum
1 function find_partition( S ):
2     N ← sum(S)
3     P ← empty boolean table of size (\lfloor N/2 \rfloor  +  1) by (n + 1)
4     initialize top row (P(0,x)) of P to True
5     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
6     for i from 1 to \lfloor N/2 \rfloor
7          for j from 1 to n
8          P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1)
9     return P(\lfloor N/2 \rfloor , n)

Используя рекурсию, вы можете вычислить, может ли быть достигнута определенная сумма из целых чисел в массиве, если она может быть достигнута, она возвращает true. Я начинаю с sumOfTheIntegers/2 и я возвращаюсь к 0, пока не найду решение. Когда я нашел максимально возможную сумму целых чисел, которая меньше или равна средней, я вычисляю разницу между двумя группами целых чисел с (average-lowestSumLowerorEqualtoAverage)*2,

Но тогда я сталкиваюсь с проблемой, как я могу включить одномерный массив в рекурсию?

Вот код, он, вероятно, должен работать, но я еще не проверял его из-за проблемы. Так что, возможно, код содержит небольшие ошибки. Но это не проблема, я исправлю это позже.

#include <iostream>
#include <cmath>
using namespace std;
bool matrix (int a, int b)
{
if(b == -1)  return true;
else if (a == -1) return false;
else if(matrix(a-1, b) == true) return true;
else if(matrix(a-1,b-numbers[a-1]) == true) return true;
else return false;
}
int main()
{
int number, sum = 0;
cin >> number;
int numbers[number];
for(int i = 0; i<number; i++)
{
cin >> numbers[i];
sum += numbers[i];
}
double average = sum/2.0;
for(int i = floor(sum/2); i!= 0; i--)
{
if(matrix(number+1, i) == true)
{
cout << abs(average-i)*2;
break;
}
}
return 0;
}

0

algorithm c++partitioning recursion

Решение

Другие решения

Передайте это как аргумент функции

bool matrix (int a, int b, int num_arr[])
{
...
matrix(a-1,b,num_arr);
...
}

0

Источник

Accepted Answer

Самый простой (но, конечно, не самый лучший) способ — ввести глобальную переменную:

#include <vector>
std::vector<int> numbers;

/* ... */

int main(){
int number;
cin >> number;
numbers.resize(number);
/* ... */
}

Другая возможность заключается в использовании дополнительного параметра:

bool matrix (int a, int b, const std::vector<int>& numbers)
{
if(b == -1)  return true;
else if (a == -1) return false;
else if(matrix(a-1, b,numbers) == true) return true;
else if(matrix(a-1,b-numbers[a-1],numbers) == true) return true;
else return false;
}

Обратите внимание, что int numbers[number] фактически использует специфичное для компилятора расширение (VLA) и не является частью стандарта C ++ (см. Поддерживает ли C ++ массивы переменной длины? а также Почему массивы переменной длины не являются частью стандарта C ++?).

1