0

私はオブジェクトを持っています、それを「友達」と呼びましょう。このオブジェクトには、を返すメソッド「GetFriendsOfFriend」がありますList<Friend>。

たとえば5のユーザー入力が与えられた場合、すべての友達の友達と友達の友達の友達（あなたはポイントを取得します）をレベル5（これは最大20になる可能性があります）に下げます。

これは多くの計算になる可能性があるため、再帰が最善の解決策であるかどうかはわかりません。

誰かが1の賢い考えを持っていますか？この再帰関数を最もよくする方法は？2.再帰なしでそれを行う方法。

ありがとう！

4

2 に答える 2

3

再帰なしでこれを行うことは確かに可能ですが、あなたがやろうとしていることに特別な問題は見られません。物事がおかしくなるのを防ぐために、プログラムが死ぬのを防ぐために最大値を設定することは理にかなっているかもしれません。

public class Friend
{
    public static readonly int MaxDepth = 8; // prevent more than 8 recursions

    private List<Friend> myFriends_ = new List<Friend>();

    // private implementation
    private void InternalFriends(int depth, int currDepth, List<Friend> list)
    {
        // Add "us"
        if(currDepth > 1 && !list.Contains(this))
            list.Add(this);

        if(currDepth <= depth)
        {
            foreach(Friend f in myFriends_)
            {
                if(!list.Contains(f))
                    f.InternalFriends(depth, depth + 1, list); // we can all private functions here.
            }
        }
    } // eo InternalFriends


    public List<Friend> GetFriendsOfFriend(int depth)
    {
        List<Friend> ret = new List<Friend>();
        InternalFriends(depth < MaxDepth ? depth : MaxDepth, 1, ret);
        return ret;
    }  // eo getFriendsOfFriend
} // eo class Friend

編集：実際の友達が追加されず、「彼らの」友達だけが追加されるというコードのエラーを修正しました。これは、深さが「1」（最初の呼び出し）の後に友達を追加する場合にのみ必要です。Containsまた、重複をチェックするために利用しました。

于 2012-07-26T14:38:47.777 に答える
1

このコードの非再帰バージョンは次のとおりです。

public static void ProcessFriendsOf(string person) {
    var toVisit = new Queue<string>();
    var seen = new HashSet<string>();

    toVisit.Enqueue(person);
    seen.Add(person);           

    while(toVisit.Count > 0) {
        var current = toVisit.Dequeue();    

        //process this friend in some way

        foreach(var friend in GetFriendsOfFriend(current)) {
            if (!seen.Contains(friend)) {
                toVisit.Enqueue(friend);
                seen.Add(friend);
            }
        }
    }
}

すでに表示されているすべてのメンバーのHashSetを保持し、複数回処理されるメンバーを追加しないことで、無限ループを回避します。

幅優先探索と呼ばれる方法で、キューを使用して友人を訪問します。キューの代わりにスタックを使用すると、深さ優先探索になり、再帰的アプローチ（暗黙のスタック（呼び出しスタック）を使用）とほぼ同じように動作します。

于 2012-07-26T15:52:55.620 に答える