遞歸調用而不是多個for循環調用C++

-1

在下面的例子中，用5個循環我能夠獲得訪問到多維陣列中的每個單獨的索引。如果我不知道數組的維數，實現和遞歸函數來訪問數組，那麼對於動態系統有什麼辦法嗎？ =>遞歸實現for循環。遞歸調用而不是多個for循環調用C++

例如：

index[3] = 0; //=> because it is 3 dimenional all are zero 

void recursiveIndexWalk(int i){ 
    a[0] = i; 
    recursiveIndexWalk(a[1]); 
    //on the inner last recursive call a[index[0]][index[1]][index[2]] = val; 

} 

main(){ 
//my goal is to perform instead of 3 for loops => only one recursive() called 
recursive(a[0]); 
}

// ========================

unsigned int dimensions = 3; //known 
unsigned int dimension_length = { 1, 2, 3}; //known 


int a[1][2][3]; 

int counter = 0; 
for (size_t r = 0; r < 1; r++) {   //| 
    for (size_t q = 0; q < 2; q++) {  //| 
     for (size_t p = 0; p < 4; p++) {  //|=>recursiveForCall(indexArray) 
      a[i][j][k] = counter++; 
     } 
     } 
     }

來源

2013-05-21 Alper

親愛的上帝，你爲什麼需要這麼多維度。 –

你的結構實際上是一棵樹。特殊情況下，同一級別上的每個節點具有相同數量的子節點，因此解決該問題的一個簡單方法是使用某種樹實現。像數組一樣[1] [2] ... - 如何獲得每個數組級別的元素數量？ –

解決方案可以用於遞歸方式的2D或3D。 – Alper

你可以，例如，創建一個包含所有索引標識的矢量，所以每次在每個遞歸調用您的遞歸函數然後從後面的列表中刪除之前的索引添加到列表中。

但是，它可能是一個更好的主意，放棄這裏的遞歸思想，而不是僅僅看使用迭代技術的所有排列。下面是概念的任意證明，這應該給你一些想法：

#include <stdio.h> 

const unsigned int dimensions = 3; 
const unsigned int dimension_size[dimensions] = { 2, 4, 3 }; 

// Get first permutation. 
inline void get_first_permutation(unsigned int * const permutation) 
{ 
    for (int i = 0; i < dimensions; ++i) 
     permutation[i] = 0; 
} 

// Returns false when there are no more permutations. 
inline bool next_permutation(unsigned int * const permutation) 
{ 
    int on_index = dimensions - 1; 
    while (on_index >= 0) 
    { 
     if (permutation[on_index] >= dimension_size[on_index]) 
     { 
      permutation[on_index] = 0; 
      --on_index; 
     } 
     else 
     { 
      ++permutation[on_index]; 
      return true; 
     } 
    } 
    return false; 
} 

// Print out a permutation. 
void print_permutation(const unsigned int * const permutation) 
{ 
    printf("["); 
    for (int i = 0; i < dimensions; ++i) 
     printf("%4d", permutation[i]); 
    printf("]\n"); 
} 

int main(int argc, char ** argv) 
{ 
    // Get first permutation. 
    unsigned int permutation[dimensions]; 
    get_first_permutation(permutation); 

    // Print all permutations. 
    bool more_permutations = true; 
    while (more_permutations) 
    { 
     print_permutation(permutation); 
     more_permutations = next_permutation(permutation); 
    } 

    return 0; 
}

這是當然，假設你真正需要知道的指數。如果你只是想更新所有的計數器，你可以循環索引0到索引dim_0*dim_1*...*dim_n

/* Defined somewhere. Don't know how this gets allocated but what-evs. :) */ 
unsigned int dimensions = 5; 
unsigned int dimension_length = { 1, 2, 4, 7, 6 }; 
int * int_array = ... 

/* Your loop code. */ 
unsigned int array_length = 0; 
for (unsigned int d = 0; d < dimensions; ++d) 
    array_length += dimension_length[d]; 
int *array_pointer = int_array; 
for (unsigned int i = 0; i < array_length; ++i, ++array_pointer) 
    array_pointer = counter++;

來源

2013-05-21 21:32:38 Anthony

不能achive正確的解決方案，如果它不是continuguos和索引從1或非零值開始在for循環等：爲（爲size_t R = 0; R <1; R ++）{對於（爲size_t Q = 1 ; q <2; q ++）{對於（爲size_t p = 3，p <4;的p ++）{... – Alper

多維數組被指定，這將是在存儲器中連續，但是這是一個有效點，如果它不是一個「陣列」而是某種類型的列表，該列表不保證該屬性。在這種情況下，我會建議迭代方法來獲取維度排列。 – Anthony

如果你不在遍歷數組時不需要索引，你可以把它看作一個簡單的數組。使用上面已知的大小示例：

int * ap = ****a; 
int n = 1 * 2 * 3 * 1 * 5; 
for (size_t i = 0; i < n; ++i) 
    *ap++ = counter++;

我不確定什麼遞歸實現會給你買。如果陣列很大，它可能會炸燬堆棧。

來源

2013-05-21 21:31:47

遞歸調用而不是多個for循環調用C++

回答

相關問題