Как преобразовать эту рекурсивную функцию в итеративную версию?

Этот код в основном вычисляет nCr для печати треугольника Паскаля.

 #include <stdio.h>

 int nCr(int n,int r){
     if (r == 0 || r == n || n == 1 || n == 0){
        return 1;
 }
 else{
    return nCr(n-1,r) + nCr(n-1,r-1);
 }
}

Как превратить эту функцию в итеративную версию?

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


c recursion binomial-coefficients pascals-triangle non-recursive
person azman    schedule 18.11.2017    source источник
comment
Просто подумайте, что происходит на каждом шаге рекурсии, и реализуйте цикл, который ведет себя именно так. Возможно, вам понадобится хранилище для хранения значений данных итерации. Эти данные хранятся в стеке при использовании рекурсии. Удачной инженерии!   -  person Tom Schardt    schedule 18.11.2017
comment
Начертите на листе бумаги треугольник Паскаля. Попробуйте пройти от его начала до определенного значения. Во время этой прогулки подумайте, какие ценности вам нужны на каждом этапе, и когда эти ценности перестанут служить своей цели и могут быть отброшены. Затем напишите эту прогулку с циклом и парой переменных.   -  person StoryTeller - Unslander Monica    schedule 18.11.2017

Ответы (1)


arrow_upward
0
arrow_downward 

#include <stdio.h>

int main(void) {

    int n,r;
    scanf("%d%d",&n,&r);

    int mem[n+1][r+1];

    int i,j;

    for(i=0;i<n+1;i++)
    {
        for(j=0;j<r+1;j++)
        {
            if (j == 0 || j == i || i == 1 || i == 0)
                mem[i][j]=1;
            else
                mem[i][j]=mem[i-1][j]+mem[i-1][j-1];
        }
    }

    printf("%d",mem[n][r]);


    return 0;
}

Я использовал 2D-массив для сохранения значений, чтобы я мог использовать их вместо того, чтобы снова и снова вызывать функцию. Я использовал концепцию Динамического программирования. Пожалуйста, изучите его, чтобы понять код.

person anupam691997    schedule 18.11.2017