-1

ツリー内の独立したセットの数を数えるアルゴリズムを書くのに問題があります。(独立集合とは、任意の 2 つのノード間にエッジがない場所です。)

ListNode の私の Java クラスは次のとおりです。

 1public class ListNode
 2{
 3    private Object data;
 4    private ListNode next;
 5
 6    public ListNode(Object data, ListNode next)
 7    {
 8        this.data = data;
 9        this.next = next;
10    }
11
12    public Object getData()  {return data;}
13    public ListNode getNext(){return next;}
14    public void setNext(ListNode n){next = n;}
15    public void setData(Object d){data = d;}
16    public boolean search(ListNode l, Object o)
17    {
18        while (l != null){
19            if (l.getData().equals(o))
20                return true;
21            l = l.getNext();
22        }
23        return false;
24    }
25    public static ListNode rev(ListNode curr)
26    {
27        ListNode rev = null;
28        while (curr != null){
29            rev = new ListNode(curr.getData(), rev);
30            curr = curr.getNext();
31        }
32        return rev;}}

そして、TreeNode の私の Java クラス:

1public class TreeNode
 2{   ListNode children = null;
 3    public void addChild(TreeNode t)
 4    {
 5        if (children == null)
 6            children = new ListNode(t, null);
 7        else{
 8            ListNode curr = children;
 9            while (curr.getNext() != null)
10                curr = curr.getNext();
11            curr.setNext(new ListNode(t, null));
12        }}
13    public void setChildren(ListNode t){this.children = t;}
14    public int numStableSet()
15    {
16
17        if (children == null || children.getNext() == null)
18            return 2;
19        else{
20            int count = 2;
21            setChildren(children.getNext());
22            count *= numStableSet();
23            return count;
24        }
25    }

メソッド numStableSet は、コーディングの助けが必要なメソッドです。今の設定なので、正解より1つ少なく出力されます。また、各ノードがツリー自体になる可能性がある場合もわかりませんでした。

助けていただければ幸いです

4

1 に答える 1

1

あなたのアルゴリズムが常に 1 ずれるとは思えません。最も単純なものから始めて、いくつかの例を考えてみましょう。

  • ノードなし => 1 つの独立集合、空集合
  • 1 つのノード => 2 つの独立した集合、空および 1 つのノード
  • 1 つの親とその唯一の子 => 3 つの独立したセット、空でいずれかのノード

あなたのコードは、単一のノードと単一の子を持つノードの両方で同じ結果 2 を返すように見えるので、コードが間違っていると思います。

適切なアルゴリズムを見つけるために、再帰的なケースを考えてみましょう。現在、特定のノードにアクセスしています。そのノードを安定セットに含めないことを決定し、そのすべての子にアクセスして、これらの任意の安定セットを選択することができます。または、現在のノードを含めることを決定することもできますが、それはそれ自身の親が含まれていない場合に限られ、子に再帰するときはそれらをカウントしないようにする必要があります。これらの選択肢を組み合わせる可能性のあるすべての方法を追跡してください。pythonic 疑似コードでは:

def combinationsWithoutCurrent(current):
  num = 1
  for child in current:
    num *= stableSet(child)
  return num

def combinationsWithCurrent(current):
  num = 1
  for child in current:
    num *= combinationsWithoutCurrent(child)
  return num

def stableSet(current):
  return (combinationsWithCurrent(current) +
          combinationsWithoutCurrent(current))

Java とあいまいな手作りのコンテナー クラスを好むので、データ構造がどのように意図されているかを推測するための Java コードを次に示します。ツリー トラバーサルを呼び出すことはgetDataないため、コードで実際に再帰が行われていることはわかりません。だから私の推測は間違っているかもしれません。

private int combinationsWithoutCurrent() {
  int num = 1;
  for (ListNode iter = children; iter != null; iter = iter.getNext())
    num *= ((TreeNode)iter.getData()).numStableSets();
  return num;
}

private int combinationsWithCurrent() {
  int num = 1;
  for (ListNode iter = children; iter != null; iter = iter.getNext())
    num *= ((TreeNode)iter.getData()).combinationsWithoutCurrent();
  return num;
}

public int numStableSet() {
  return combinationsWithCurrent() + combinationsWithoutCurrent();
}
于 2013-10-06T23:29:23.237 に答える