Тема: Чим можна замінити реурсію
Є просте завдання. Визначити кількість можливих комбінацій елементів масиву, коли два сусідніх елементи не мають однакового значення. Найперше, що прийшло в голову:
#include <iostream>
using namespace std;
// нехай буде лише три значення
// що може міститити елемент
static unsigned u3_combination[] = {0, 1, 2};
extern "C" unsigned max_combination (unsigned* u_array, unsigned pos,
unsigned* combination, unsigned combination_size,
unsigned last, unsigned shallow);
int main ( int argc, char **argv )
{
unsigned u_objects, res;
cin >> u_objects;
unsigned u_array[u_objects];
res = max_combination ( u_array, 0,
::u3_combination, 3,
/* random - not 0, 1, 2 */10, u_objects );
cout << res << endl;
return (0);
};
extern "C" unsigned
max_combination (unsigned* u_array,
unsigned pos,
unsigned* combination,
unsigned combination_size,
unsigned last,
unsigned shallow)
{
unsigned i, res = 0;
for ( i = 0; i < combination_size; ++i ) {
u_array[pos] = combination[i];
if (last == u_array[pos] )
continue;
if (shallow == 1)
res++;
else
res += max_combination ( u_array, pos + 1,
combination,
combination_size,
u_array[pos], shallow - 1 );
}
return (res);
}
Але це займає дуже багато часу на обчислення. Чи існує якийсь інший варіант розв'язання даної задачі?