横形探索はどのように組めばいいですか??
または、
見やすい横形探索の載っているホームページはないですか??
探しているのですがなかなか見つかりません。
(わかりやすいページが見つかりません。)

A 回答 (2件)

    • good
    • 0
この回答へのお礼

返事ありがとうございました。

お礼日時:2001/04/27 15:59

しまった。

「横形探索」に気をとられてた。CとLispのページだけど、適当に読み替えてね。>#1
    • good
    • 0
この回答へのお礼

ご丁寧に有難うございました。

お礼日時:2001/04/27 16:00

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

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

Q2分探索法 『成功・不成功探索一回の実行時間を求める』

C言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。

----------課題----------
整列されているN個のデータに対して、その中にvがあるかどうかを判断する2分探索プログラムを実行する
Nの値を10^6、5×10^6、10^7、5×10^7、10^8
と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。
このとき、Nと実行時間の関係はどのようになっているか(100字程度で)
  N  成功探索  不成功探索
 10^6  ***秒   ***秒
5×10^6  ***秒   ***秒
 10^7  ***秒   ***秒
5×10^7  ***秒   ***秒
 10^8  ***秒   ***秒
----------------------------------------

~↑を元に作成したプログラム(成功探索の場合)~
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T 1000000
#define N 100000000

int a[N];
int main(void)
{
clock_t t1,t2; int t;
int i;
int l, r, k, v, m;
for (i = 0; i < N; i++) a[i] = i;
t1=clock();
for (t = 0; t < T; t++) {
v = rand() % N;

l=0; r=N-1; k=-1;
while (r >= l) {
m = (l+r)/2;
if (v == a[m]) { k=m; break; }
if (v < a[m]) r = m-1; else l = m+1;
}

}
t2=clock();
printf("cpu time=%10.6f[micro sec]\n",(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T));

return 0;
}

↑a[i]すべてに0~N-1を代入し、vにランダムに0~N-1の値を代入する。2分探索法で、v=a[i]となったら終了する。
実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位:マイクロ秒


として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。

↑のプログラムをそれぞれのNで実行したところ
N=
 10^6で実行・・・1.016 0.891 0.969 1.155 1.14 [micro sec]
5×10^6で実行・・・1.422 1.500 1.563 1.250 1.406 1.297
 10^7で実行・・・1.750 1.360 1.37 1.407 1.672 1.531
5×10^7で実行・・・1.859 1.797 1.812 1.800
 10^8で実行・・・2.062 2.140 2.320 2.500

このような結果になりました。
これで正しいのでしょうか?もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか?
でも、Nが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。


次に
不成功探索では↑のプログラムの
乱数vのところを変化させて
v=rand() % N;という箇所を
v=N;としました。
a[i]には0~N-1が入っているので、v=Nとすれば必ず不成功になるはずですよね?
こうして実行してみると
N=
10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても
0.719 0.54 0.625 0.534 [micro sec]
に近い値ばかり出てしまい、正しい値とは到底思えません。

不成功探索は成功探索より時間がかかるはずですよね?なのになぜこのようになってしまったのでしょうか?



後、Nと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか?
こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。


長々とスイマセン。
少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。

C言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。

----------課題----------
整列されているN個のデータに対して、その中にvがあるかどうかを判断する2分探索プログラムを実行する
Nの値を10^6、5×10^6、10^7、5×10^7、10^8
と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。
このとき、Nと実行時間の関係はどのようになっているか(100字程度で)
  N  成功探索  不成功探...続きを読む

Aベストアンサー

ざっとプログラム見ましたが、特に問題は無いように見受けられます
そもそも探索ですから(N=16として)
1回目で見つかる場合もあるし、最悪4回目で見つかる、みつからないとなりますよね?(2分探索なので)
ですので平均を計算する必要があります
するとだいたい、o LOG nで検索できるとなります

ちなみに不成功探索ですがv=Nだと1回目の探索ですぐ「ないぞ」とわかってしまうのでだめです
a[i] = i*2;
とでもしておいて(データはすべて偶数)
v = N/2;
ならいいんじゃないですか?

Q経路探索の問題

http://www.i.u-tokyo.ac.jp/edu/course/m-i/pdf/2002imim.pdf
の、問題3について質問なのですが、
問1は、
 (1)
線形リストとして、n回で到達できるセルの情報を与えると、n+1回で到達できる線形リストを返す関数を考える。返すリストの作成方法は、n回で到達できるセルの前後左右を調べて、すでに調べたセルや障害物のセルでなければ、そのセルをn+1回で到達できるセルとしてメモし、返す線形リストに追加する。
 (2)
int l[M][N];//特定のセルまでの距離をメモする配列。最初にすべて-1をいれておく。障害物には-2を入れておく。
class list{
  int i,j;
  list *next;
  list(){
    next=0;
  }
}
//n回で到達できるセルのリストをpl、n+1階で到達できるセルのリストを返すポインタをnlとする。
void getNextCellsList(list *pl,list *nl){
  list *tt=pl;
  list *t;
  int i,j;
  nl=0;
  while(tt){
    i=tt->i;
    j=tt->j;
    if(i>0&&l[i-1][j]==-1){
      l[i-1][j]=l[i][j]+1;
      t=nl;
      nl=new list;
      nl->i=i-1;
      nl->j=j;
      nl->next=t;
    }
    if(j>0&&l[i][j-1]==-1){
      l[i][j-1]=l[i][j]+1;
      t=nl;
      nl=new list;
      nl->i=i;
      nl->j=j-1;
      nl->next=t;
    }
    if(i<M-1&&l[i+1][j]==-1){
      l[i+1][j]=l[i][j]+1;
      t=nl;
      nl=new list;
      nl->i=i+1;
      nl->j=j;
      nl->next=t;
    }
    if(j<N-1&&l[i][j+1]==-1){
      l[i][j+1]=l[i][j]+1;
      t=nl;
      nl=new list;
      nl->i=i;
      nl->j=j+1;
      nl->next=t;
    }
    tt=tt->next;
  }
}
と、したのですが、このgetNextCellsList関数を一回使う時間計算量は、O(n)としていいのでしょうか?
また、もしそうなら問2の時間計算量は、
(getNextCellsList関数を一回使う時間計算量)*M*N=O(n)*O(n^2)=O(n^3)
空間計算量は、
(セルまでの距離をメモする配列の数)+(n回で到達できるセルの情報)=O(n^2)+O(n)=O(n^2)
となるのでしょうか?
あと、この問題の(M,N,D)のオーダーで評価せよというのはどういう意味として捉えればいいのでしょうか?O(n^3)などと書いておくだけで良いのでしょうか?


問3の時間的及び空間的に効率化する方策としてはどのようなものが考えられるのでしょうか?これは、自力では全然ろくな方法が思い付きませんでした。。。

宜しくお願いします。

http://www.i.u-tokyo.ac.jp/edu/course/m-i/pdf/2002imim.pdf
の、問題3について質問なのですが、
問1は、
 (1)
線形リストとして、n回で到達できるセルの情報を与えると、n+1回で到達できる線形リストを返す関数を考える。返すリストの作成方法は、n回で到達できるセルの前後左右を調べて、すでに調べたセルや障害物のセルでなければ、そのセルをn+1回で到達できるセルとしてメモし、返す線形リストに追加する。
 (2)
int l[M][N];//特定のセルまでの距離をメモする配列。最初にすべて-1をいれておく。...続きを読む

Aベストアンサー

「A から C へいけばいい」ことがわかるので, それまでの情報は全てなかったことにして改めて A から C への最短経路を探す.

Qディレクトリ探索プログラム

ディレクトリを探索していき、ファイル一覧を表示していくような機能が欲しいのですが、自分でプログラムしたくてもどのように始めればよいのかわからず困っています。後々プログラミングの勉強にも使いたいですのでサンプルのプログラムなどがあれば見せていただきたいです。
できれば C もしくは C++ が希望です。

具体的な内容としましては、
『パソコンのCドライブなどから始めて、その中にあるディレクトリとファイル一覧を表示して、ディレクトリが存在すればその中に入り、またファイルとディレクトリの一覧を表示する。それを繰り返して行き、一番下まで行ったら、ひとつ上の階層に戻り同じことを繰り返す』
という感じです。再帰的なプログラムだと助かりますが、他にもよい方法があれば教えていただきたいです。

宜しくお願いします。

Aベストアンサー

http://www.doumo.jp/modules/general/CFindFile.html
とか参考にしてはどうですか?

再起的に取得するにはFindFirstFile(FindNextFile)で調べたパスを更にGetFileAttributes
でディレクトリかファイルを調べ
ディレクトリならまた自分自身を呼びます。

Q二分探索木への挿入

今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include <ctype.h>

typedef struct node Node;
struct node{
char *word;
int count;
Node *left,*right;
};

Node *root=NULL;
Node *compose(FILE *fp);
void inorder(Node *p);

int main(int argc, char *argv[])
{
FILE *fp;
Node *new;

fp=fopen(argv[1],"r");
if(fp==NULL){
puts("ファイルを開けません");
return(-1);
}
new=(Node *)malloc(sizeof(Node *));
new=compose(fp);
inorder(new);
return (0);
}

Node *compose(FILE *fp)
{
Node **p,*new;
char buf[20];
p=&root;
while(fscanf(fp,"%[-a-z-A-Z0-9_]",buf)!=EOF){

while(*p!=NULL){
(*p)->count=0;  /*countを0で初期化したいけどwhileの外にこの1行を出すとエラーが出る*/
buf[0]=tolower(buf[0]);
strdup(buf);
if(strcasecmp(buf,(*p)->word)==0){   /*if文にしかはいらない…*/
(*p)->count++;

printf("%d\n",(*p)->count);

}else if(strcasecmp(buf,(*p)->word)<0){
p=&(*p)->left;
}else{
p=&(*p)->right;
}
}
new=(Node *)malloc(sizeof(Node *));
new->left=NULL;
new->right=NULL;
new->word=buf;
*p=new;
fscanf(fp,"%*[^-a-z-A-Z0-9_]");
}
return(new);
}

void inorder(Node *p)
{
if(p==NULL)
return;

printf("%s",p->word);
if(p->count!=0){
printf("%d",p->count);
}
inorder(p->right);
inorder(p->left);

}

今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include <ctype.h>

typedef struct node Node;
struct node{
char *word;
int count;
Node *left,*right;
};

Node *root=NULL;
Node *compose(FI...続きを読む

Aベストアンサー

なんとなく動くようにしてみました。参考にしていただければ。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct node Node;
struct node{
 char *word;
 int count;
 Node *left,*right;
};
Node *root=NULL;
void compose(FILE *fp);
void inorder(Node *p);
void strlower(char *s);

int main(int argc, char *argv[]) {
 FILE *fp;
 Node *new;

 fp=fopen(argv[1],"r");
 if(fp==NULL){ puts("ファイルを開けません"); return(-1); }
 compose(fp);
 inorder(root);
 return (0);
}
/* 文字列を小文字にする */
void strlower(char *s) {
 while(*s!=NULL) { *s=tolower(*s); s++; }
}
/* 木を作る */
void compose(FILE *fp) {
 Node **p,*new;
 char buf[256];
 while(1) {
  fscanf(fp,"%[^a-zA-Z0-9]",buf); /* 英数字がくるまで読み飛ばす */
  if (fscanf(fp,"%[a-zA-Z0-9]",buf)==EOF) break; /* ファイルから単語らしきものを読み込む */
  strlower(buf); /* 文字列を小文字化 */
  if (root==NULL) { /* 最初の単語ならすぐ登録 */
   new=(Node *)malloc(sizeof(Node));
   new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
   root=new;
  } else { /* 最初でなければ大小比較して挿入場所を探す */
   *p=root; /* 注目ノードを根に設定 */
   while(1){
    if(strcmp(buf,(*p)->word)==0){ /* 同じデータがあればカウントアップして終わり */
     (*p)->count++; break;
    } else if(strcmp(buf,(*p)->word)<0){ /* 新単語が小さければ左を見る */
     if ((*p)->left==NULL) { /* 子がなければ新規登録 */
      new=(Node *)malloc(sizeof(Node));
      new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
      (*p)->left=new; break;
     } else { /* 左を探す */
      *p=(*p)->left;
     }
    } else { /* 新単語が大きければ右を見る */
     if ((*p)->right==NULL) { /* 子がなければ新規登録 */
      new=(Node *)malloc(sizeof(Node));
      new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
      (*p)->right=new; break;
     }else{ /* 右を探す */
      *p=(*p)->right;
     }
    }
   }
  }
 }
}
/* 小さい順に表示 */
void inorder(Node *p) {
 if (p==NULL) return;
 inorder(p->left);
 printf("%s %d\n",p->word, p->count);
 inorder(p->right);
}

なんとなく動くようにしてみました。参考にしていただければ。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct node Node;
struct node{
 char *word;
 int count;
 Node *left,*right;
};
Node *root=NULL;
void compose(FILE *fp);
void inorder(Node *p);
void strlower(char *s);

int main(int argc, char *argv[]) {
 FILE *fp;
 Node *new;

 fp=fopen(argv[1],"r");
 if(fp==NULL){ puts("ファイルを開けません"); return...続きを読む

Q編集距離空間探索法

文字列の類似度の指標として、編集距離というものがあります。文字列がリストで並んでいて、そこにある文字列との編集距離が最小になる問題を考えるような場合、シーケンシャルに文字列の編集距離を調べ、編集距離が最小になるアルゴリズムは効率が悪い。そこで、編集距離をノードの値としてもつ二分木というものを考えてみました。そこで質問なのですが、編集距離をノードの値として持つ二分木を用いて、編集距離が最小になるようなアルゴリズムは既に考案されているのでしょうか?

Aベストアンサー

問題の説明が変.
「文字列がリストで並んでいて, そこにある文字列との編集距離が最小になる問題を考える」っのはどんな問題を考えるんでしょうか? 「1つの文字列 s と 1つの文字列のリスト L があり, L の中から s との編集距離が最小となるものを見付ける」問題でいい?
で, そのあとで「編集距離をノードの値としてもつ二分木というものを考えてみました」と書いていますが, この「編集距離」はどのように得られたのですが? リストL 中の文字列を 1つずつ調べる? それとも編集距離はあらかじめ与えられていることを仮定する?
いずれにしても「編集距離が最小になるようなアルゴリズム」ってのは意味不明ですが.
「ソート」は余計かも>#1.


このカテゴリの人気Q&Aランキング

おすすめ情報