집 >백엔드 개발 >C#.Net 튜토리얼 >피보나치 수열도 이런 식으로 쓰여 있다는 사실이 밝혀졌습니다. 알고 계셨나요?

피보나치 수열도 이런 식으로 쓰여 있다는 사실이 밝혀졌습니다. 알고 계셨나요?

php是最好的语言원래의: 2018-07-27 10:49:011571검색

바이두에 "피보나치의 비재귀적 쓰기"에 대한 답변이 많이 있지만 만족스럽지 않습니다. 첫째, 이해하기 너무 어렵고, 둘째, 성능이 재귀와 거의 동일합니다.

피보나치 수열에 관해서라면 초보 프로그래머든 기술 베테랑이든 가장 먼저 떠오르는 것은 확실히 재귀적 작성 방법입니다. 그러면 기술 베테랑과 프로그램 초보자의 차이점은 반복 계산을 줄이기 위해 재귀 결과를 저장하려고 생각한다는 것입니다. 이는 매우 일반적인 작업이지만 피보나치 수열을 비재귀적인 방식으로 작성할 수 있다고 생각해 본 적이 있습니까?
바이두에 "피보나치의 비재귀적 쓰기"에 대한 답변이 많이 있지만 만족스럽지 않습니다. 첫째, 이해하기 너무 어렵고, 둘째, 성능이 재귀와 거의 동일합니다. 처음에는 재귀 호출의 호출 스택을 시뮬레이션하는 한 직접 작성하고 싶었지만 이 아이디어는 다소 당연하게 여겨지고 작성된 프로그램도 매우 복잡합니다. 무엇을 해야 할까요? 이때 트리의 깊이 우선 순회가 유용할 수 있습니다.
먼저 트리 노드를 정의합니다:

public class Node
        {
            public Node(long value, bool visited)
            {
                Value = value;
                Visited = visited;
            }

            public long Value { get; set; }//存放结点的值
            public bool Visited { get; set; }
        }

그런 다음 DFS 스택 작성 방법을 즐겁게 배울 수 있습니다.

  public static long Fblc(int n)
        {
            Stack<Node> s = new Stack<Node>();
            s.Push(new Node(n, false));
            long sum = 0;
            long[] childrenResultMemo = new long[n+1];
            childrenResultMemo[0] = 1;
            childrenResultMemo[1] = 1;
            //long children = 0;
            while (s.Any())
            {
                var cur = s.Pop();
             
                    if (cur.Visited == false)
                    {
                        if (childrenResultMemo[cur.Value] == 0)
                        {
                            cur.Visited = true;
                            if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
                            {
                                var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
                                childrenResultMemo[cur.Value] = result;
                                sum += result;
                                s.Push(cur);
                            }
                            else
                            {
                                s.Push(cur);
                                s.Push(new Node(cur.Value - 1, false));
                                s.Push(new Node(cur.Value - 2, false));
                            }
                        }
                        else
                        {
                            sum += childrenResultMemo[cur.Value];//保存子树结果的优化，会有个特殊情况要处理
                        }
                        
                    }
                   
                
            }

            return sum;
        }

위의 핵심 아이디어 알고리즘은 스택을 탐색하여 스택의 최상위 요소를 팝하는 것입니다. 방문한 경우(방문한 경우 true) 건너뜁니다(위 코드는 하위 트리 결과 저장 최적화를 사용하므로 처리할 특별한 경우가 있습니다). 자세한 내용은 아래에 설명되어 있습니다. 그렇지 않으면 현재 상위 노드의 방문을 true로 표시합니다. 즉, 방문했음을 의미하고 이를 스택에 푸시한 다음 모든 하위 노드를 스택에 푸시합니다.

이 아이디어를 따르면 작성하는 코드는 위의 코드와 같지 않을 것입니다. 그러나 알고리즘의 복잡성은 위의 코드와 유사합니다. 반복되는 계산이 있기 때문에 재귀적 쓰기입니다.

그럼 어떻게 해야 할까요? 공간을 시간으로 교환하고 해당 하위 트리의 결과를 저장하면 더 이상 해당 하위 트리로 이동하지 않습니다. 다음 수준의 깊이에서는 결과를 직접 사용합니다. 하위 트리 결과를 배열에 저장합니다:

long[] childrenResultMemo = new long[n+1];

일반적으로 하위 트리에 이미 결과가 있으면 논리적으로 해당 하위 트리를 방문했어야 합니다. 그러나 시작 부분에 하위 트리 0과 하위 트리 1이 있는 특별한 경우가 있습니다.

childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;

이 특별한 경우의 분기에 결과를 추가하기만 하면 됩니다.

sum += childrenResultMemo[cur.Value];

어떻게 될까요? 이런 글쓰기 방식이 흔하지 않나요? 실제로 피보나치 수열의 평가 과정은 트리의 깊이 우선 순회와 같습니다. 따라서 깊이 우선 순회를 구현하는 한 완전히 가능합니다.

피보나치 수열도 이런 식으로 쓰여 있다는 사실이 밝혀졌습니다. 알고 계셨나요?

관련 기사