C言語のことについての質問です。
1,2,3,という駅があるとします。
数字を2つ入力して、例えば1と2を入力して、「1と2を繋げました」と出力します。
次に2と3を入力して、「2と3を繋げました」と出力します。
そして、1と3を入力したときに、前の状態で1と3は2を通じて繋がっています。なので「1と3は繋がっている」と出力させたいのですが、このプログラムの組み方が分かりません。文字の入力、出力方法は分かっています。1、2、3の繋がりのところが分かりません。もしよろしかったら駅の数を増やした状態も教えていただけるとありがたいです。
できればプログラムのソースを・・・
質問です。
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 14年前
- 住所: 東海地方
- 連絡を取る:
Re: 質問です。
知恵袋に非常に似た質問有るのですが、同じ方ですか?
「C言語のことについての質問です。 1,2,3,という駅があるとします。 数字を2つ入力... - Yahoo!知恵袋」
http://detail.chiebukuro.yahoo.co.jp/qa ... 1260676307
「C言語のことについての質問です。 1,2,3,という駅があるとします。 数字を2つ入力... - Yahoo!知恵袋」
http://detail.chiebukuro.yahoo.co.jp/qa ... 1260676307
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 14年前
- 住所: 東海地方
- 連絡を取る:
Re: 質問です。
こちらでは、直接ソースコードを提示するより考え方とかアルゴリズムとかでアドバイスしています。
ソースコードを提示してもらえば、ソース自体のアドバイスも出来ます。
詳しくは、フォーラムルールを御覧ください。
http://dixq.net/board/board.html
ソースコードを提示してもらえば、ソース自体のアドバイスも出来ます。
詳しくは、フォーラムルールを御覧ください。
http://dixq.net/board/board.html
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
Re: 質問です。
入力された数がグループになっているかどうかを判定する。という風に読み替えてみるとunion-findというデータ構造を使うだけで済みます
http://algorithms.blog55.fc2.com/blog-entry-46.html
http://www.prefield.com/algorithm/conta ... _find.html
ここらを参考にするといいと思います。
【追記】
C言語という条件を見逃していました。
簡単に書いたのでこちらも参考にしてみてください
グループの判定をより高速にするためにグループのリーダーを使うようにしています。
http://algorithms.blog55.fc2.com/blog-entry-46.html
http://www.prefield.com/algorithm/conta ... _find.html
ここらを参考にするといいと思います。
【追記】
C言語という条件を見逃していました。
簡単に書いたのでこちらも参考にしてみてください
グループの判定をより高速にするためにグループのリーダーを使うようにしています。
#define MAX 3
int p[MAX];
/* union-findの初期化 */
void union_init(void)
{
int i;
for(i=0;i<MAX;i++){
p[i] = i; /* グループが自分のみの状態にする */
}
}
/* aのリーダーを返す */
int root(int a)
{
/* グループのリーダーの場合 */
if(p[a] == a) return a; /* リーダーの番号を返す */
return p[a]=root(p[a]); /* どこのグループに属しているか分かれば十分なのでリーダーを書き換える */
}
/* aとbが同じグループか */
int same(int a,int b)
{
return root(a)==root(b);
}
/* aとbを同じグループにする */
void merge(int a,int b)
{
/* aのリーダーをbのリーダーにする */
p[root(a)]=root(b);
}
最後に編集したユーザー xxx on 2011年4月22日(金) 20:04 [ 編集 1 回目 ]
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 14年前
- 住所: 東海地方
- 連絡を取る:
Re: 質問です。
それ実装がC++だと思いますよ。roxion1377 さんが書きました:入力された数がグループになっているかどうかを判定する。という風に読み替えてみるとunion-findというデータ構造を使うだけで済みます
http://algorithms.blog55.fc2.com/blog-entry-46.html
http://www.prefield.com/algorithm/conta ... _find.html
ここらを参考にするといいと思います。
>>きおさん。
自分の今出来る範囲でプログラムを組んでもらうとアドバイスしやすいです。
あと知恵袋のjjacksspanさんのアルゴリズムは実は問題があります。
1-2と3-4が接続していると入力するだけで、1-4は接続していると見なされてれてしまいます。
問題自体にも不明点があって、
・最大駅は幾つまでなのか?mallocを使って良いのか?
・路線は1つだけなのか?それとも山手線と中央線の関係のように複数の路線を想定するのか?
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。