Тема: Чим можна замінити реурсію
Є просте завдання. Визначити кількість можливих комбінацій елементів масиву, коли два сусідніх елементи не мають однакового значення. Найперше, що прийшло в голову:
#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);
}
  
  Але це займає дуже багато часу на обчислення. Чи існує якийсь інший варіант розв'язання даної задачі?




