0

再帰的に実装する方法は 3 つあります。はい、これは学校向けですので、単純明快な回答は不要です。説明的な回答をいただければ幸いです。私はツリー構造が初めてです。

3つの方法は次のとおりです...

public class Zombies{
   public static int countPeople(Person p){...}
   // counts all the people in the tree structure 
   // starting with Person p. 

   public static int countZombies(Person p){...}
   // counts all the people in the tree structure
   // starting with Person p that are zombies

   public static void draw(Person p){...}
   // draws a diagram of the people in tree structure
   // starting with Person p.
   // each person will be denoted by a P and 
   // person that is a zombie will be denoted by a Z
   //
   // The diagram should illustrate the family tree
   // structure.  Each person will be drawn with 3 minus  
   // signs '-' for each level below p.

Person クラスを開始しましたが、いくつか質問があります。

1)私は私の個人クラスで正しい軌道に乗っていますか

2)メソッドの説明で言及されているツリー構造はバイナリツリーですか?

3）これらのメソッドを実装できるようにするために何が欠けていますか（何かがある場合、またはこのツリー構造に必要なビルディングブロックがある場合）

以下は私の Person クラスです。

public class Person{

    public int     id;     // some identification number unique to the person
    public boolean zombie; // true if the person is a zombie
    public char    state;  // p means human, z means zombie

    public ArrayList<Person> friends;  // list of friends

    public Person(int id, char state, boolean zombie){
        this.id = id;
        this.state = state;
        this.zombie = zombie;
    }

    public boolean isZombie() {
        if (state == 'p'){
            return zombie=false;
        }
        else if (state == 'z'){
            return zombie=true;
        }
        return zombie;  
    }
}

ツリーのタイプの出力例は次のとおりです。

P          (this is Person q)
---P       (this is a friend of q, say q1)
------P    (this is a friend of q1)
------Z    (this is another friend of q1, who is a zombie)
---Z       (this is a friend of q, say q2, who is a zombie)
------Z    (this is a friend of q1, who is also a zombie)
------P    (this is a friend of q1, who is not a zombie)

忍耐と助け/入力を前もって感謝します!

4

4 に答える 4

1

これにより、配列ベースのバイナリ ツリーの実装に関する洞察が得られることを願っています。

別の投稿から取得：

二分木を配列として記述する場合、通常ヒープと呼ばれるものを構築します。ヒープは十分に文書化されており、この記事ではヒープの実装方法について詳しく説明します。

http://en.wikipedia.org/wiki/Binary_heap

オリジナルへのリンク:

ArrayList ベースのバイナリ ツリー - Java

編集：

あなたがしているように見えるのは、クラス「Person」の人々のバイナリツリーを作成していることです。各「親」の人には、その「人」の子供になる「友達」がいます。「友達」の数が 2 に制限されている場合、これは二分木形式です。

ツリーは、データを保持するために使用される単なる組織構造です...そしてあなたの場合はさまざまな人々です。関係のないバイナリ ヒープの部分は、ヒープがノード値に基づいて編成されていることです。それについて心配する必要はありません。

したがって、クラス Zombie は、任意の人物オブジェクトとそれに関連付けられたすべての「友達」を取得して、人物またはゾンビの数などを決定できます。

人の各インスタンスには、その人からアクセスできる一種の友達のツリーがあります。

構造をツリーにするのは、親から子へのリンクです。したがって、person1 には、friend1 と friend2 の 2 人の友人がいます。次に、friend1 にアクセスし、友人がいるかどうかを確認します。もしそうなら、あなたはその友達の友達などをチェックします。これは、ツリーが情報をナビゲートするのに役立つ方法の非常に一般的な説明です。

基本的に、ツリー内の誰かに 2 人以上の友人がいる場合、それはバイナリ ツリーではなくなります。

これをチェックしてください：

http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Tree_traversal_algorithms_for_a_binary_tree

これは、トラバース ツリーの例です。ツリー内のゾンビまたは通常の人の数を取得するために、トラバースするときに値を増やすことができます。

説明が散らかっているようで申し訳ありませんが、あなたがやろうとしていることと組織を理解するのに苦労しています。

編集2:

わかりましたので、Zombie クラスから静的関数を呼び出します。その人とその友達全員を再帰的にチェックする必要があります。

これをバイナリ ツリーの実装にしたい場合は、各人が 2 人までの友達を持つことができます。

二分木である必要がない場合、各人物の友人配列のサイズに制限はありません。

基本的に必要なことは、Zombie クラスの関数を使用して、すべての人 (友人、友人の友人など) がゾンビであるかどうかを確認することを繰り返すことです。それらが正しいかどうかがわかったら、出力して結果をコンソールに表示します。次に進みます。

上で投稿したツリーの繰り返しに関するリンクを見て、それを各人の友人の配列リストに適用してください。再帰的に反復するにはさまざまな方法があります...そのため、スタイルを選択し（順序どおりのトラバーサルが必要なようです）、その方法でチェック/印刷機能を実装します。

これはリードです。また行き詰まったらお知らせください。ツリーを理解するための抽象化は難しい場合があります。

于 2013-04-01T21:22:12.380 に答える
1

1）あなたが探しているものではないかもしれませんが、私はPerson.state. 人がゾンビであるかどうかを判断するために使用される 2 つの別個のフィールドがあると、混乱を招き、エラーが発生しやすくなります。zombieisと istrueとstateはどういう意味 pですか?

2) Miorel のコメントには、いくつかの良い洞察があります。あなたが私たちに与えたものからは、ツリーが何を表しているのか、なぜそれがツリーでなければならないのか、またはどのようにデータが取り込まれるのかが明確ではありません。

3) ある種の World オブジェクトが必要です。Zombies良い選択かもしれません。どこかに、どうやら、すべての人々の木が必要です。少なくとも、ある種の人々の集まりが必要です。そのコレクションは、宣言、インスタンス化、および設定する必要があります。Zombiesクラスのメンバーとしてそれを望むかもしれません。間違いなく、Personあなたが多く持つクラスのメンバーとしてではありません.

于 2013-04-01T21:26:30.473 に答える
0

  1. はい、あなたは正しい軌道に乗っていると思います。しかし、他の人が指摘したように、 と の両方を持つことchar stateはboolean zombie冗長です。個人的には、この場合、継承は非常にやり過ぎだと思います。おそらく、後で「ゾンビ」、「吸血鬼」、さらには「狼男」になり得る「人」が必要になる場合には理解できます。 「しかし、この場合は簡単に言えif (p.isZombie()) { ... }ば十分だと思いますが、これは古くからの設計上の議論であり、私は「継承よりも合成」陣営に属しているため、そのままにしておきます ( http://en.wikipedia.org/wiki/Composition_over_inheritance )

  2. これは確かにツリー構造ですが、仕様に基づいて二分木であることに非常に疑いがありますが、そうでない理由はありません。私には、これは N-Ary ツリーのように見えます。以前にこれらのツリーに触れたことがない場合、これらは単純な一般的なツリー構造であり、各ノードは任意の数の子ノードを持つことができます。このリンクはより良い説明を提供します: http://www.brpreiss.com/books/opus5/html/page257.html (これについては後で詳しく説明します)

  3. これらのメソッドを実装するために何かが欠けているわけではありません (私が知る限り、それはあなたの教授次第です - 彼らはこれをどのようにマークするつもりですか? 独自のテスト コードを実行しますか? あなたのコードを見てください? または、クライアント コードを提供していますか (これがどのように機能するかを示す main メソッド)? 彼らがテスト コードを実行している場合は、Person API が仕様と互換性があることを確認する必要があります)。

ここで理解しておくべき重要なことは、作成したデータ構造と、それが N 項ツリーをどのように表しているかです。クラスは Tree 内のPerson単一のノードを表し (任意のノードがルートになる可能性がありますが、重要ではありません) ArrayList<Person>、ノードに属する各子ノード (またはフレンド) を格納します。それは本質的に「リンク構造」です。このことを考慮：

class Node {
    public ArrayList<Node> children = new ArrayList<Node>();
}

このクラスには 0 個以上の子 ( に格納されているchildren) があり、各子はNode(0 個以上の子を持つ) です。

したがって、いくつかを簡単にNoderootNodeにして、その方法でツリーを構築できます。

Node root = new Node();
root.children.add(new Node());
root.children.add(new Node());
root.children.get(0).children.add(new Node());
root.children.get(0).children.add(new Node());

本質的に、これは次のように表現できるツリーを作成します。

    root
     /\
    /  \
   0    1
  / \
 /   \
0     1

さて、私が以前に「[バイナリ ツリー] になれない理由はない」と言った理由に気付くかもしれません。技術的に言えば、バイナリ ツリーは N=2 の N-Ary ツリーです。

実現することが重要なもう 1 つのこと (N-Ary ツリーに関する前のリンクで言及されています) は、各ノードを独自の N-Ary ツリーと見なすことができるということです。したがって、たとえば、draw(Person p)メソッドに関する限り、p実際にはツリー全体のルートであるか、ツリーの一部のサブツリーのルートであるかにかかわらず、常に N-Ary ツリーのルートになります。

お役に立てれば！少し前にこの質問を投稿したことは知っているので、これをうまく完了することができたか、手遅れではないことを願っています。そうでない場合は、他の誰かを助けるかもしれません:/

また、この種の問題 (アルゴリズムとデータ構造) に取り組むときに覚えておくべき重要なことは、無関係な詳細に行き詰まらないようにすることです。友達と一緒のゾンビかもしれません」など。それは私たちが探している抽象化ではありません! この種の関係を Tree で表現したいだけです。もちろん、常に最適なデータ構造が与えられるとは限らず、タスクを作成するためにさまざまなタイプのデータ構造を活用する必要があるため、現実の問題ではこれが難しくなります。

常に問題の根本を切り分けるようにして、そこから進んでください。多くの問題は、詳細やデータが追加された単なる別の単純な問題であることがよくあります。または、別の問題のわずかなバリエーションですらあります。

頑張ってください。

于 2013-04-30T01:28:02.020 に答える
0

Q1) 私は自分の個人クラスで正しい軌道に乗っていますか?

私の観点から言えば、ノーと言わざるを得ません。

何が問題なのですか？

冗長なロジックがあります。フィールドzombieとstateは、人間の可能性の同じ状態を指します。

この時点で、何がゾンビで何が人間かを判断する必要があります。その行為を行い、同じように振る舞いますか? 私の観察によると、それらにはいくつかの共通の特徴がありますが、表現の非常に異なる要素もあります。それを証明するために、私たちが人間の前に立って、時間を尋ねると想像してみましょう。おそらく彼は論理的な答えをくれるでしょう。もう一方の手からのゾンビは、私たちが質問を終える前に、確かに私たちの脳を食べようとします.

そのため、ステータスを導入する代わりに (btw は列挙型にする必要があります)、継承メカニズムを使用します。

public class Person {

  private final int id;

  public Person(int id) {
   this.id = id;

  }

  public int hashCode() {
     return id;
  }

  public boolean equals(Object object) {

    if(object instance of Person) {
       return this.id == ((Person) object).id;
    }

    return false;
  }
}

public class Zombie : Person {

   public Zombie(int id) {
      super(id);
   }
)

友達が人間かゾンビかを示す方法は?

この目的のために、メソッドを使用しisZombieました。現在、このメソッドを持つ 2 つのクラスがあるため、不合理です。クラスZombieはゾンビとHuman. そのため、 のようなコードを使用するとif(human.isZombie())、奇妙に見えます。

そして、ここで OOP の力が発揮されます。オブジェクトがこのタイプまたは別のタイプであることを検出しても、挿入されません。私たちが望むのは、このオブジェクトが人間またはゾンビであることをユーザーに知らせる有効な文字 (この場合) をコンソールに表示することです。

これを可能にするには、クラス Human にメソッドを追加し、それをクラス Zombie で [オーバーライド] する必要があります。このメソッドは、有効な char を返す責任があります。

public class Person {

  //...   

  public char howDoOtherSeeMe() {

    return 'P';

  } 
}

public class Zombie : Person {

   //...

   @override
   public char howDoOtherSeeMe() {

    return 'Z';

  } 
}

Q2) メソッドの説明に記載されている木構造は二分木ですか?

A2. いいえ。定義からのバイナリ ツリーは 2 つのノードしか持つことができず、サイクルを持つことはできません。また、Person クラス内の構造を結合すると、クラスが制御なしで急速に成長する可能性があります。

于 2013-04-02T13:17:55.490 に答える