- ベストアンサー
すべての木のパス(経路)を求めたいのですが
こんにちは。学校の課題のことで質問させてもらいます。 例えばAはB1,B2,B3,B4に接続されています。B1はC1,C2へ,B2はC3,C4へ,B3はC5,C6へ,B4はC7,C8へそれぞれ接続されています。このような木の経路は8種類で A→B1→C1 A→B1→C2 … A→B4→C7 A→B4→C8 ですよね?これですべての経路を画面に出力するようなプログラムを考えなければならないのですが、どのようにすすめていいか分からないです。AからBなどの接続はポインタによって接続されています。 コンピュータにポインタを辿らせると最初のA→B1→C1の経路しか選択しないので一度通った場所(ノード?)には通らないように目印を付けなければならないと思うのですが、その条件がよくわからないです。 またこのようなプログラムはfor文やwhile文を使うのではなく再帰呼び出しを使うのでしょうか? 補足質問もわかる範囲ならば答えたいと思います。 回答よろしくお願いします。
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- noocyte
- ベストアンサー率58% (171/291)
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
関連するQ&A
- 再帰呼び出しで求めたい経路を表示させたい!
以前も「すべての経路を求めるには」というような質問をして再帰呼び出しにより無事解決することが出来ました。 しかし、少しわからないところがあります。 例えばaはb1とb2に接続されていてb1とb2はそれぞれc1,c2とc3,c4に接続されているとします。すべての経路は全部で4本ですね。 これを再帰呼び出しの中にprintf文を用いて表示させたところ a->b1->c1 c2 b2->c3 c4 というような感じで表示されたと思います。これは再帰呼び出しの性質で分岐があった以前の場所へ戻って探索を続けるからだというのは理解できました。しかし、実際は a->b1->c1 a->b1->c2 a->b2->c3 a->b2->c4 というように表示させたいです。何かこれを記憶するための変数が必要だと思うのですが、それを用いて上のように表示させるほう方法が思いつきません。 さらに、a->b2->c3というように特定の経路だけを選択して表示させたいです。アドバイスよろしくお願いします!
- ベストアンサー
- C・C++・C#
- C:経路検索アルゴリズム
全経路検索について勉強中です。 「各ノードはポインタで繋がっている」という事は理解しましたが、それをどのように表せば良いのでしょう。 ダイクストラ法、深さ優先検索等の単語は見つかりましたが、どれを使用すれば良いのか…。 条件は、ノードの数は決まっておらず、つながり・出発,到着点は自由に決める事が出来ます。 例)1-2 1-4 2-4 2-3 3-5 4-5 開始,3 到着,5 距離は関係ありません。 今はリスト構造で、構造体(下のようにしています)は動的に確保し、 再帰で処理をするようにしていますが、上手くいかず不安になってきました。 struct data{ int x; /*ノード*/ struct data *next; /*次ノードへのつながり*/ }; よろしければ、何か些細な事でもヒントを下さると嬉しいです^^
- 締切済み
- C・C++・C#
- C言語のプログラムについて
C言語のプログラムについて 3桁の自然数の中で、自分自身を含めた約数が奇数になるものがいくつあるかを求めるプログラムを作りたいのですが、swich文を使って、6通りの方法で出そうとしていまして、 while 文、 for文、 do while文に加え、 for文のを、1つの関数として独立させたもの、 さらに、for文のを重ループ部分のそれぞれのループに対応して、2つの関数として独立させたもの、 そして、この2つの関数のどちらともをループを用いずに再帰呼び出しを用いたもの の6通りで出したいのですが、swich文を使うところは自力でできたのですが、あとの6つそれぞれのプログラムの組み方がわかりません。 教えていただけないでしょうか?ややこしい書き方をしてすいません・・・。
- 締切済み
- C・C++・C#
- メバロン酸経路と非メバロン酸経路
天然物化学についての質問です。 大学の授業でモノテルペン(C10)、ジテルペン(C10)、 セスタテルペン(C25)、カロチノイド(C40)は「非メバロン酸経路」で、 セスキテルペン(C15)、スクワレンやトリテルペン(C30)や ステロイドは「メバロン酸経路」と習いました。 メバロン酸経路と非メバロン酸経路を見分けるのは このように炭素の数で見分ければいいのでしょうか? その後、モノテルペンインドールアルカロイドは モノテルペンなのにも関わらず、シキミ酸経路と メバロン酸経路(非メバロン酸経路ではなくです。) と授業でやり混乱しております。 どなたか、テルペノイドがメバロン酸経路と非メバロン酸経路の どちらからできているか見分ける方法をご存じの方がいましたら、 回答をしてはいただけないでしょうか。 また、この教授とコミュニケーションをとることは 限りなく無理に等しいため、教授に質問に行くべきという回答は 申し訳ありませんが、やめてください。 よろしくお願い致します。
- ベストアンサー
- 化学
- VC++ 再帰呼び出しについて
VC++6.0にてプログラミングを行っているものですが、 関数の再帰呼び出しについて質問です。 再帰呼び出しの際にスタックに積まれる変数というのは、 再帰呼び出しをする関数に渡す引数のことですか? スタックオーバーフローを起こさないために、 staticなポインタにHeap領域上の 変数を割り当てるとよい。 と分かったのですが、 この意味は、例えば static int *a = new int; ということなのですか?
- ベストアンサー
- C・C++・C#
- pascalにおけるwhile文の条件について
「cがA,B,Cのどれかの場合はwhile文の内容を繰り返す」というプログラムは while c in ['A','B','C'] do begin ~ end; と書けますが、「cがA,B,Cのどれかで無い場合はwhile文の内容を繰り返す」というプログラムはどのように書けばよいのでしょうか。私は while not c in ['A','B','C'] do begin ~ end; だと思ったのですが、エラーが発生したのでどうやら違うようです。 わかる人がいれば教えてください。よろしくお願いします。
- 締切済み
- その他(プログラミング・開発)
- ネットワークの経路について、
ネットワークの経路について、 拠点Aと拠点B間はWANとVPNの2回線で接続されています。 Bにある特定のサーバへのルートをWANにする設定をAのルータにした場合、BへのリクエストはWANですが、レスポンスはどっちの経路になるのでしょうか? 初歩的な質問ですがお願いします。
- ベストアンサー
- ネットワーク
- 左再帰について
次のBNFが左再帰であるかないかを判定し、その根拠を説明せよ。 <A> ::=<B>|<C>|<C> <B> ::=if<C>then<A> <C> ::=a|b|c <D> ::=<A>while<C> これを簡単でいいので教えてください。 できれば左再帰とは何かも教えてください。
- ベストアンサー
- その他(プログラミング・開発)
- TreeViewコントロールについて
いつも参考にさせて頂いてます。 早速ですが、DBの値をTreeViewを使用して表示したいと思っています。 DBには、 CD 機能1 機能2 機能3 CD1 A1 B1 C1 CD1 A1 B2 C2 CD1 A1 B2 C3 CD2 A2 B3 C4 見たいな感じでデータが登録されています。 これをTreeViewに、 CD1 LA1 LB1 | LC1 LB2 LC2 LC3 CD2 LA2 LB3 LC4 と出力させたいのですが、どうしたらよいか見当もつきません。 いろいろ調べて再帰呼び出しで出来るんじゃないかと思うのですが、 再帰処理にに詳しくない為、先に進むことが出来ません。 どうしたら実現できるか、力をお貸しください。 宜しくお願い致します。
- ベストアンサー
- Visual Basic
お礼
回答ありがとうございます!! その経路が求めたい経路かどうかを判断できるのは終点に達した時点だから、通過した場所を記憶するものを用意しておけばよかったんですね。 自分でもどのようなことをすれば良いかイメージができてきました。 試行錯誤してプログラムを作ってみたいと思います! 参考になりました!!