재귀 알고리즘을보다 간단하게 다시 작성 - Euler 15

이 알고리즘의 기능을 재귀 적으로 재 작성하여 ProjectEuler 문제 15을 해결하는 데 사용했습니다.재귀 알고리즘을보다 간단하게 다시 작성 - Euler 15

예, 실제 문제를 해결할 수있는 더 좋은 방법이 있다는 것을 알고 있지만, 가능한 한이 논리를 단순화하고 싶습니다.

public class SolveRecursion 
{ 
    public long Combination = 0; 
    public int GridSize; 

    public void CalculateCombination(int x = 0, int y = 0) 
    { 
     if (x < GridSize) 
     { 
      CalculateCombination(x + 1, y); 
     } 
     if (y < GridSize) 
     { 
      CalculateCombination(x, y + 1); 
     } 
     if (x == GridSize && y == GridSize) 
      Combination++; 
    } 
}

그리고 테스트 :

[Test] 
public void SolveRecursion_GivenThree_GivesAnswerOf20Routes() 
{ 
    solveRecursion.GridSize = 3; 
    solveRecursion.CalculateCombination(); 
    var result = solveRecursion.Combination; 
    Assert.AreEqual(20, result); 
} 

[Test] 
public void SolveRecursion_GivenFour_GivesAnswerOf70Routes() 
{ 
    solveRecursion.GridSize = 4; 
    solveRecursion.CalculateCombination(); 
    var result = solveRecursion.Combination; 
    Assert.AreEqual(70, result); 
}

편집 : 어떤 힌트를 주시면 감사하겠습니다

//recursion 
private int Factorial(int number) 
{ 
    if (number == 0) 
     return 1; 
    int returnedValue = Factorial(number - 1); 

    int result = number*returnedValue; 
    return result; 
} 

//loop 
private int FactorialAsLoop(int number) 
{ 
    //4*3*2*1 
    for (int i = number-1; i >= 1; i--) 
    { 
     number = number*i; 
    } 
    return number; 
}

: 다음 두 가지 방법으로 작성된 또 다른 간단한 함수입니다. 동적 프로그래밍 솔루션 (더 많은 수학 기반 접근법 사용)과 퍼즐을 성공적으로 풀 수있는 방정식을 시도했습니다.

궁금한 사항 -이 첫 번째 알고리즘을 간단히 비 재귀 적으로 만들 수 있습니까?

출처

2012-06-05 Dave Mateer

가능한 복제본 [재귀에서 반복으로 이동하는 방법] (http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) –

재귀 호출을 사용하지 않고 알고리즘을 유지하기를 원한다는 의미이므로 스택과 루프가 재귀를 모방하는 데 사용될 수 있지만 그렇게 할 시점은 없습니다. – tia

감사합니다 ... 스택 및 루프를 수행하면 작업이 단순 해지지 않을 것이라는 데 동의했습니다. –

비 재귀 용액이다

const int n = 4; 
int a[n + 2][n + 2] = {0}; 

a[0][0] = 1; 
for (int i = 0; i < n + 1; ++i) 
    for (int j = 0; j < n + 1; ++j) { 
     a[i][j + 1] += a[i][j]; 
     a[i + 1][j] += a[i][j]; 
    } 

std::cout << a[n][n] << std::endl;

단지 내용이 문제는 용지에 해결 했어야, N × M 개의 격자에 대한 대답은 C가 C (N + M, N)를 인 조합 기능 - http://en.wikipedia.org/wiki/Combination

출처

2013-08-26 17:20:46 frangulyan

재귀 알고리즘을보다 간단하게 다시 작성 - Euler 15

답변

관련 문제