1 Востаннє редагувалося Kizyak (17.08.2016 23:23:00)

Тема: Чим можна замінити реурсію

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

#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);
}
  
  

Але це займає дуже багато часу на обчислення. Чи існує якийсь інший варіант розв'язання даної задачі?

2

Re: Чим можна замінити реурсію

Будь-яка рекурсія заміняється циклом, але часто доволі незграбним і коду буде більше. http://stackoverflow.com/questions/9317 … -iteration

Подякували: Kizyak, leofun012

3

Re: Чим можна замінити реурсію

sort і next_permutation в циклі не пробували?

Подякували: Kizyak, leofun012

4

Re: Чим можна замінити реурсію

Kizyak буде довго, якщо не розпаралелювати алгоритм, я б зробив щось накшталт цього

#include <iostream>
using namespace std;

void shift(size_t * arr, size_t n){
    size_t buf = arr[0];
    memcpy(arr, arr + 1, (n - 1)*sizeof(size_t));
    arr[n - 1] = buf;
}

void show (size_t *arr, size_t n){
    for( size_t i = 0; i < n; i++ )
        cout<<arr[i]<<" ";
    cout<<endl;
}

int main(){
    size_t i, j, k;
    size_t arr[] = {0, 1, 2, 3, 4, 5};
    size_t n     = sizeof(arr) / sizeof(arr[0]);
    for( i = 0; i < n; i++ )
    {
        shift(arr + i, n - i);
        for( j = 0; j < n; j++ )
        {
            shift(arr, n);
            show (arr, n);
        }
    }
    return 0;
}


http://codepad.org/pO8U1fZZ
потім цикл по j виніс у потік, можна й обидва цикли винести у потоки, проте синхронізація буде складною.

Подякували: Kizyak, leofun012

5 Востаннє редагувалося Regen (18.08.2016 19:29:26)

Re: Чим можна замінити реурсію

крім циклу іноді заміняють використанням власного стеку чи черги

Прихований текст

псс, чувак, я так сам робив

, погляньте на реалізації bfs, dfs і tree level-order traversing (статті самі знайдете, якщо захочете, приклади мають бути навіть у вікіпедії)
зверніть увагу, що рекурсія сама використовує стек для викликів

Подякували: Kizyak, leofun012

6

Re: Чим можна замінити реурсію

Якщо я правильно зрозумів задачу, потрібно знайти кількість різних масивів заданого розміру, в яких немає однакових сусідніх елементів і які складаються тільки з елементів заданої множини. Тоді задача має простий математичний розв'язок. Нехай n - задана довжина масиву, m - потужність множини, яка містить можливі елементи. Тоді є m варіантів вибору першого елемента, а для вибору кожного наступного - m-1 варіантів(не можемо вибрати тільки попередній елемент). Тоді відповідь - m*((m-1)^(n-1)).

Подякували: leofun01, Kizyak2