グループ分けを行うプログラムを考えています.
具体的には,

A,B,C,D,Eがあったとき,
A-B,A-C,B-Dが1つのグループ(ペア)であれば,
A-B-C-Dを1つのグループ(群)とする.

このようなルールのもとで,グループ分けをおこないたいのですが,
どのようにしたらよいものかいい考えが浮かんできません.

なお,元データはそれぞれのペアが1行に1つずつあります.

A B
A C
B C
B D
: :
: :

どなたか良い考えが思いつかれた方がいれば,
些細なことでも結構ですので御教授よろしくお願いします.

このQ&Aに関連する最新のQ&A

A 回答 (2件)

う~ん, どこで悩んでいるかが分かればなぁ....


基本的にはアルゴリズムをそのまま実装するだけでいいです. ただし, 本当にそのまま実装するととてつもなく効率が悪くなる可能性があるのでその辺はちょっと考える:
1. 入力ータをグラフと思って隣接リストにする
2. すべての要素のグループを空にする
3. until すべての要素にグループが割り当てられる do
4. グループが割り当てられていない要素を 1つ見つける
5. その要素を始点として幅優先探索でも深さ優先探索でも好きな方で探索する
6. 探索中に見つかったすべての要素を始点と同じグループに割り当てる
7. end until
要素数を n, ペアの数を m とすると, よほど下手に組まない限り O(n^2+m) より悪くはできないはず. ちょっと頭を使えば O(n+m).
    • good
    • 0
この回答へのお礼

Tacosan さん

 ありがとうございます.
 とりあえず四苦八苦しながらではありますがやってみます.

お礼日時:2009/05/26 20:30

グラフを連結成分に分割しろ, ってことだよね?


素直に
「X-Y というペアがあって X がグループ a に入っていたら Y もグループ a に入れる」
というのをひたすら繰り返すだけでいいのでは?
特に悩むことはないと思いますが.
    • good
    • 0
この回答へのお礼

その通りなんですが・・・
どういう風にプログラムを書けばよいかを悩んでまして・・・

お礼日時:2009/05/25 07:14

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qオンライン英会話教室について教えてください。

先日、テレビでオンライン英会話教室でレッスンを受けている方を見て
自分もやりたくなり、ネットで検索して色んな学校を見てみたのですが
どこがいいのかわからなくなってしまい、質問させて頂く事にしました。

オンライン英会話はかなり前に習っていた事があるのですが、
その時はグループ制で先生が少しお題は出すけど
その後は生徒だけが話しているような感じのレッスンで、
私はうまく会話に入っていけずに聞いているだけと
いうような感じだったので、すぐに止めてしまいました。

口下手なのでマンツーマンのレッスンが希望です。
あと、今求職中なので授業料は安い方が嬉しいです。
先生の国籍は特に気にしません。訛りがあまりない方が嬉しいですが・・・。

おすすめのオンライン英会話教室をご存知の方、教えて下さい。
また、ここはあまり良くないよ、というような情報もお待ちしています。
よろしくお願い致します。

Aベストアンサー

私も3か月前からオンライン英会話を習い始めましたが、比較サイトから探し出しました。しかし、数が多くてどこが良いか見当がつきませんでした。

オンライン英会話は2つに分けられます。値段で勝負している会社と少ないですが、品質の高さを謳っているところです。

私は、上達するには、よい先生がいることろがよいと決めているので、値段が安いところは、除き、質が高いところで評判がよいところを探しました。

検索で、評判のよいオンライン英会話を探し、2社試してみました。

QQ、e4eです。

QQは、体験の先生が若くて元気があってよかったのですが、2人ともテンションが高過ぎて、疲れました。若い先生なので、元気なのでしょうが、フリートークでは、日本の質問ばかりでした。

e4eは、サポートの方が、丁寧でSkypeとメールであいさつをしてくれました。先生は、2人とも人柄と教え方ともとても良かったです。しっかり教えてもらえそうな印象を受けました。

数が少ないですが、e4eを選んで正解でした。入会後カウンセリングをしていただいて、いい先生を紹介してくれて、今は毎日楽しく習っています。

しかし、比較サイトで比較できない、これは問題です。みんな広告ばかりで、選びようがありません。ネットのクチコミをみて自分にあった会社を選んだらどうですか。

参考URL:http://www.e4e-english.com

私も3か月前からオンライン英会話を習い始めましたが、比較サイトから探し出しました。しかし、数が多くてどこが良いか見当がつきませんでした。

オンライン英会話は2つに分けられます。値段で勝負している会社と少ないですが、品質の高さを謳っているところです。

私は、上達するには、よい先生がいることろがよいと決めているので、値段が安いところは、除き、質が高いところで評判がよいところを探しました。

検索で、評判のよいオンライン英会話を探し、2社試してみました。

QQ、e4eです。

QQは、体験...続きを読む

Q2 ~ 200 の素数 a, b, c (a < b < c) が、b - a = c - b を満たすa,b,cをビット操作を用いて求め、すべてを表示せよ

ちょっと考えてみました。でも、分かりません・・・まず、int型のintvalに200bitを割り当てて、intval=0としたいのですが、どうしたらいいのでしょう??
とりあえず考えてみたプログラムを誰か見て下さい!!お願いします。
#define BYTESIZE 200
#define MAX 200
main()
{
int i,j,intval=0;
for(i=2;i<=MAX/2;i++)
{
if(intval&(1<<(i-1)){}
else for(j=i*2;j<=MAX;j+=i)intval|=(1<<(j-1));
}/*素数を0、それ以外を1に
for(i=2;i<=MAX/2;i++)
for(j=2;j<=(MAX-i)/2;j++)
if((intval&(1<<(i-1))&&(intval&(i+j-1))&&(intval&(1<<(i+2*j-1)))) print("%3d %3d %3d (%3d)\n",i,i+j,i+2*j,j);
}/*三つ子の素数を調べ出力

ちょっと考えてみました。でも、分かりません・・・まず、int型のintvalに200bitを割り当てて、intval=0としたいのですが、どうしたらいいのでしょう??
とりあえず考えてみたプログラムを誰か見て下さい!!お願いします。
#define BYTESIZE 200
#define MAX 200
main()
{
int i,j,intval=0;
for(i=2;i<=MAX/2;i++)
{
if(intval&(1<<(i-1)){}
else for(j=i*2;j<=MAX;j+=i)intval|=(1<<(j-1));
}/*素数を0、それ以外を1に
for(i=2;i<=MAX/2;i++)
for(j=2;j<=(MAX-i)/2;j++)
if((intval&...続きを読む

Aベストアンサー

まずint型は200ビットもありません。通常は32ビットです。
200ビット使いたければint型を7個用意する必要があります。
つまり
int intval[7];
宣言して、
intval[0] 0~31ビット
intval[1] 32~63ビット
intval[2] 64~95ビット
.
.
.
intval[6] 182~200ビット
として使います。

第iビットの情報を取り出すときは
(intval[i>>5]>>(i&31))&1

第iビットを1にするときは
intval[i>>5]|=1<<(i&31);

とすれば良いでしょう。
関数やマクロを用意することをお勧めします。
例えば
int get(int intval[],int i)
{
return (intval[i>>5]>>(i&31))&1;/*0か1が返って来る。*/
}

void on(int intval[],int i)
{
intval[i>>5]|=1<<(i&31);
}

という感じです。

まずint型は200ビットもありません。通常は32ビットです。
200ビット使いたければint型を7個用意する必要があります。
つまり
int intval[7];
宣言して、
intval[0] 0~31ビット
intval[1] 32~63ビット
intval[2] 64~95ビット
.
.
.
intval[6] 182~200ビット
として使います。

第iビットの情報を取り出すときは
(intval[i>>5]>>(i&31))&1

...続きを読む

Qオススメのオンライン英会話スクール

オススメのオンライン英会話スクール
仕事で英会話が必要になってきたので、英会話の勉強をはじめたいと思っているのですが、英会話学校に通うお金が無いため、オンライン英会話スクールを検討しております。英会話初心者でも丁寧に対応してもらえそうなところ、またレッスン時間の融通の利きそうなところ、低料金なところを探しております。どこあオススメのオンライン英会話スクールがあれば、是非教えてください。よろしくお願いします。

Aベストアンサー

体験談です。

私も以前は老舗の「レアジョブ」でしたが、
最近、急に先生のレベルが落ちてきたように思い、
いろんなオンライン英会話の無料レッスンを試してみました。

価格の安さもあるのですが、
問い合わせへのレスが早かったのと
日本語のできるマネージャーがつねに待機していることから
「スカイトーク」にしてみました。

先生のレベルは他社と比較しても高い人が多いですが、
私はプロフィールを見て、講師経験の長い先生を選んでいます。

フリートークだけなら「レアジョブ」でもいい気がしますが
英会話力の上達を望むなら「スカイトーク」がおすすめです。

月額とポイントを合わせて使えるので、
月額5000円(毎日1レッスン)と、
1日に何コマも使えるポイント(1万円42レッスン3ヵ月有効)を併用しています。

週末のみなら3000円です。

参考URL:http://skytalk.co.jp/

Qc#について質問があります。 a b c d など任意の文字を入れたら abcd とスペースを

c#について質問があります。
a b c d
など任意の文字を入れたら
abcd
とスペースをなくすプログラムを作成したいです。
任意の数字なので
string a=console.ReadLine()
とします。
この後から分かりません。
わかる方教えてください(´・_・`)

Aベストアンサー

No1の方の回答は、
a内のスペースを""(長さ0の文字列)に置き換える方法です。
この方法がシンプルでかつ速いため、実戦では、この方法を採用したほうが良いでしょう。
a内のスペースを取り除くことを自前で行うには、どうするかという観点で考えると、
以下のようになります。
----------------------------------
using System;
namespace goo
{
class Program
{
static void Main(string[] args)
{
Console.Write("文字列を入力してください:");
string a = Console.ReadLine();
string b = "";
int i;
for (i = 0; i < a.Length; i++)
{
if (a[i] != ' ')
{
b = b + a[i];
}
}
Console.WriteLine(b);
}
}
}
------------------------------------------------------
結果を格納する文字列として、bを用意しておき、
a内の空白でない文字をbへ加算していきます。
実行結果は以下のようになります。
文字列を入力してください:a b c h
abch

No1の方の回答は、
a内のスペースを""(長さ0の文字列)に置き換える方法です。
この方法がシンプルでかつ速いため、実戦では、この方法を採用したほうが良いでしょう。
a内のスペースを取り除くことを自前で行うには、どうするかという観点で考えると、
以下のようになります。
----------------------------------
using System;
namespace goo
{
class Program
{
static void Main(string[] args)
{
Console.Write("文字列を入力してください:");
string a = Console.ReadLine()...続きを読む

Qオンライン英会話スクールの選び方&使い方

オンライン英会話スクールの選び方&使い方

複数のオンライン英会話スクールの無料体験レッスンを受けてみました。
予約の時間帯や教師の特徴などを踏まえて現在、レアジョブ(毎晩25~50分)・e英会話(早朝と夜に毎日各30分)・イングリッシュタウン(プライベート週一夜40分でアメリカ人)の同時受講をして1ヶ月目です。
このままだと本来安いはずのオンライン英会話スクールが結局高くつくばかりかインプットの時間が欠けてしまい、お金をかけた割には身につかなかったという結果になりそうです> <
オンラインスクールで特定の講師をキープするのにも苦労しています。
レベルはまだまだ英検3級程度ですが、再来年に留学とインターンシップを計画しているので、オンラインスクールにあまりお金をかけすぎず貯金もしたいです。
宜しくお願い致します。

Aベストアンサー

まず、料金的にはフィリピン講師で十分です。
先生を選べば発音もOKです。
現地での若者のスラングまでもキャッチアップしたいなら別ですが・・・

あと、英語講師の資格をきちんと持っている講師を選んでください。
素人とはまったく違います。

あとは、毎回先生が変わる予約制ではなく、家庭教師制にしてみてください。

私もいろいろ彷徨いましたが、今のところは上記条件を満たすところです。

値段も月780円からと内容とは関係なく安いですし。

宣伝になるといけないと思うので、「オンライン英会話 家庭教師」とかで検索してみてください。

ここの提携スクールの講師はすごくレベル高いですよ。ビデオを観ればわかります。

Qマウスの位置でa,bの値が変化し、a,bの値が変化することでpx,pz

マウスの位置でa,bの値が変化し、a,bの値が変化することでpx,pzの値も変化し、車の座標が変わるようにしたいのですが、以下のようにするとマウスを動かしても反応がありません。
px = a; の部分を px = 10; にしてみると車の座標が変わるため、static void mouseの部分がおかしいと思うのですが、どう間違えているか分からないでしょうか?
文字数制限の関係上、関連する部分のみ抜粋します。


#include <stdlib.h>
#include <GL/glut.h>

#define W 6
#define D 9

int s,t,a,b;

static void display(void)
{
const static GLfloat lightpos[] = { 3.0, 4.0, 5.0, 1.0 }; /* 光源の位置 */
const static GLfloat yellow[] = { 0.8, 0.8, 0.2, 1.0 }; /* 車の色   */
static GLdouble px = 0.0, pz = 0.0; /* 車の位置  */
static GLdouble r = 0.0; /* 車の方向  */

px = a;
pz = b;

/* 画面クリア */
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

/* モデルビュー変換行列の初期化 */
glLoadIdentity();

/* 光源の位置を設定 */
glLightfv(GL_LIGHT0, GL_POSITION, lightpos);

/* 視点の移動(物体の方を奥に移す)*/
glTranslated(0.0, 0.0, -25.0);
glRotated(30.0, 1.0, 0.0, 0.0);

/* シーンの描画 */
myGround(0.0);
glPushMatrix();
glTranslated(px, 1.0, pz);
glRotated(r - 90.0, 0.0, 1.0, 0.0);
glMaterialfv(GL_FRONT, GL_DIFFUSE, yellow);
glutSolidTeapot(1.0);
glPopMatrix();

glFlush();
}

static void resize(int w, int h){
s = w/2;
t = h/2;
}

static void mouse(int u, int v) //
{
if((s - u) > 0){
a = 10;
}else if((s - u) < 0){
a = -10;
}
if((t - v) > 0){
b = 10;
}else if((t - v) < 0){
b = -10;
}

}

int main(int argc, char *argv[])
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_RGBA | GLUT_DEPTH);
glutCreateWindow(argv[0]);
glutDisplayFunc(display);
glutReshapeFunc(resize);
glutKeyboardFunc(keyboard);
init();
glutMainLoop();
glutPassiveMotionFunc(mouse);//マウスドラッグ時
return 0;
}

マウスの位置でa,bの値が変化し、a,bの値が変化することでpx,pzの値も変化し、車の座標が変わるようにしたいのですが、以下のようにするとマウスを動かしても反応がありません。
px = a; の部分を px = 10; にしてみると車の座標が変わるため、static void mouseの部分がおかしいと思うのですが、どう間違えているか分からないでしょうか?
文字数制限の関係上、関連する部分のみ抜粋します。


#include <stdlib.h>
#include <GL/glut.h>

#define W 6
#define D 9

int s,t,a,b;

static void display(void)
{
...続きを読む

Aベストアンサー

glutMainLoop();
glutPassiveMotionFunc(mouse);//マウスドラッグ時

どうしてglutMainLoopのあとでglutPassiveMotionFuncをコールしてるの?

Qオンラインの英会話スクール探してます

 こんにちは。英会話を勉強しようとして、オンラインの英会話スクールを探しております。
 勉強したい内容は、一からの英会話、基礎からのレベルから、リスニング、あと、できるなら、発音もできたらと、思っております。
 どなたか、オンラインの英会話スクールを利用したことあるかた、お勧めのスクールを知っている方がいらっしゃいましたら、アドバイスくださいませ。

Aベストアンサー

値段が気になりますよね。ひとつ紹介しておきます。
月4000円で使い放題です。オンラインだと英会話教室のような「緊張」がないのでとてもリラックスして楽しいですよ。

時間も都合をつけやすいし,毎日1セッションずつやれば短期間で相当レベルアップします。

お試し期間もあるので,まずはのぞいてみてはいかがでしょう(^^)

参考URL:http://px.a8.net/svt/ejp?a8mat=OH431+4Q9ZSI+E10+62MDF

Q15ピンD-sub(アナログVGA)より映像のフレームをキャプチャー :windows7,C/C++

映像監視システムを開発しています。
外部装置を15ピンD-sub(アナログVGA)またはBNCより映像信号のフレームをキャプチャー
する方法について、できるだけ簡易な方法をご教示ください。
開発環境は以下です。なお、入力映像のディスプレィ表示は作成するGUIアプリケーションの画面
で行ないます。

OS: Winodws7 professional
言語:C/C++
ライブラリ:OpenCV
フレームワーク: .NET Framework

Aベストアンサー

>外部装置を15ピンD-sub(アナログVGA)またはBNCより映像信号のフレームをキャプチャー
する方法について、できるだけ簡易な方法をご教示ください。

キャプチャーしたい信号に適合した、ビデオキャプチャーカード(たとえばSC-500N1/DVI ?)を使う。2,3万で入手可能と思います。

http://www.4gamer.net/games/017/G001762/20111024058/

Qオンライン英会話

オンライン英会話を受講したいのですが、数が多すぎてどこがよいのかがわかりません。
信頼できるオンライン英会話教室があれば教えてください。
よろしくお願いします。

Aベストアンサー

ぐんぐん英会話を使っています。毎月6000円で、2コマ連続受講(同じ講師)で毎日35分のレッスンが受けられます。信用できるかどうかは、『何に対して』でしょうか?講師は、どの教室もかなり在籍しておられますので、講師は当たり外れがあります。

乱暴な言い方ですが『当たり』に出会うまで、たくさんの講師の方に根気良く予約していくことです。しかし6000円のコースは一回に2コマ(1コマ15分)しか予約がとれないので、明日の予約は今日のレッスンが終わってからとなり、お目当ての講師の予約が三日後にしか空いていないからと慌ててとってしまうと、それまでの二日間は予約が取れないシステムが若干不満。

ですので、最初は一コマずつ、お二人の講師にお願いするなどして、山ほどいらっしゃる講師陣を消去法でしぼって行くのがいいですね。今のところ大きなハズレはありませんが、合わないなと感じるだけで講師に何か大きな落ち度があるということではありません。

各講師、得意な項目が書いてます。
■キッズ
■初心者お勧め
■TOEIC
■ビジネス
■日本語OK
■講師歴3年以上
などなど・・・・・。

100円英会話がうたい文句ですが、毎日受ければの話です。私はせこいので(笑)お気に入りの講師の予約がとれなくても、それも新しい講師にめぐり合うチャンスと思い、そういう時は適当に予約を入れて、いい講師がいればラッキーと思ってます。
合うと感じる講師は3人~5人くらいは見つけて置かれたほうがいいですね。当日だと予約が埋まってしまうので・・・。

日本語OKの講師は、日本語でばっかりしゃべって、まるでご自身が日本語を身につけるために在籍しておられるのかと思う人と、いいさじ加減で会話の詰まりをちょっとした日本語で流れを良くしてくださる方と分かれます。フリートークは本当にフリーですので受身の方にはしんどいかも。うまく会話を広げてくれる講師もいますが、わたし的には講師歴3年以上の方は、合わないなと思うこともありますが、授業はこちらの程度を見抜いて行ってくれるので手っ取り早いです。

機械的に授業を勧める人
フレンドリーな人
やたら明るい人

様々ですが、私は機械的に授業を進めてくださる方が合っています(笑)スカイプ等が繋がらなかったときは振替チケットを即発行してくださるようですが、スカイプもそんなにトラブルがないですよ。あくまでも私はですが。他にもたくさんのオンライン英会話があって私も試してみたいとは思いつつ、システムに慣れている、安い、特に質が悪いわけでもないので、ここに落ち着いてます。無料体験を受けまくって、ご自身が『使いやすいシステムだ』と感じる所で良いと思います。多少の値段に違いは余り講師の質に関係してこないかも・・・。

ぐんぐん英会話を使っています。毎月6000円で、2コマ連続受講(同じ講師)で毎日35分のレッスンが受けられます。信用できるかどうかは、『何に対して』でしょうか?講師は、どの教室もかなり在籍しておられますので、講師は当たり外れがあります。

乱暴な言い方ですが『当たり』に出会うまで、たくさんの講師の方に根気良く予約していくことです。しかし6000円のコースは一回に2コマ(1コマ15分)しか予約がとれないので、明日の予約は今日のレッスンが終わってからとなり、お目当ての講師の予約...続きを読む

QC言語でCLAMP(a,b,c)

と書けばこの値はどのような値になるでしょうか?

Aベストアンサー

CLAMPはgmacros.hで定義されているマクロです。
詳細はgmacros.hを見ればわかると思います。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング