• 締切済み

二分探索木の深さについてです。

二分探索木の深さについてです。 この画像の式4.1から4.2への変換の解説・手順。また、式4.2から4.3への変換の解説・手順。最後に4.4への変換の説明をお願いします。 できるだけ詳しく書いていただけると助かります iD(i-1)をD(n-1)を用いて表そうとかんがえたのですが、出来ません。 http://34vv.net/drg/ できないです(T_T)

みんなの回答

回答No.2

式(4.1)は分解すれば良いのでは、 D(n)=1/n(n+1)ΣiD(i-1)+1/n(n+1)Σ(n-i+1)D(n-i)＋1/nΣ1　で2項目のΣはj=n-i+1と置けばΣjD(j-1) j=1～n　で、1項目と同じになる。 式(4.3)の導出は式(4.2)にn-1を代入したものに、(n-1)/(n+1)をかけたものを元のD(n)から引けば出ると思います。D(n)-(n-1)/(n+1)・D(n-1)

rararai01
質問者

お礼

なるほど。 大体の流れをつかめたのでやってみたいとおもいます！ ありがとうございます！

  • asuncion
  • ベストアンサー率33% (2126/6288)
回答No.1

いきなり一般的に考えるのではなく、 まずは、i に具体的な値（1～5くらい）を入れてみて、 そこから一般式を導いてみる、という方法はどうでしょうか。

rararai01
質問者

補足

やったのですが、結局その１つ下の式になるじゃないか！←当たり前 ってことで、そこから一般式を出すことがうまく出来ませんでした。 「なる」ということはわかるのですが、それをつかっていざ求めてみようとすると え？ ってなってしまいます。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 探索木の問題について

    探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします

  • 線形探索と二分探索

    線形探索と二分探索のプログラムを作成中です。 自力(本やwebに落ちているサンプルを参考にして)でここまで作りましたが正直自信がありません。どうかお願いします。 #include <stdio.h> #define ARRAYI1_MAX sizeof(array1) #define ARRAYI2_MAX sizeof(array2) //int binary_search(int*,int,int); //二分探索関数のプロトタイプ宣言 int liner_search(int*,int,int); //線形探索関数のプロトタイプ宣言 void main(void) { int array1[]={2,3,5,8,12,20,32,52}; int array2[]={22,34,65,66,12,33,43,5,1}; int result,key; printf("探す文字を入力して下さい。\n"); sacnf("%d",&key); result=liner_search(array1,ARRAYI1_MAX,key); if(result<0){ printf("見つかりませんでした\n");} else{ printf("%d番目に見つかりました\n",result);} } //線形探索 int liner_search(int*array,int num_array,int key) { int i=0; for(i=0;i<result;i++) } /*二分探索 int binary_search(int*array,int num_array,int key) { }*/

  • 線形探索について

    C言語の線形探索の課題なんですが ５つの整数を入力して その入力した値からみつけたい値を探索する課題なのですが #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) return (-1); /* 探索失敗 */ if (a[i] == key) return (i); /* 探索成功 */ i++; } } int main(void) { int i, ky, idx; int x[4]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); } printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); } ここまではわかるのですが、 x[0]=99 x[1]=99 x[2]=88 x[3]=99 x[4]=22 と入力したときに 99は 1番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？

  • c言語で2分探索木のを2分木に変えたい

    2分木のプログラムを書いているのですが、ある数列を2分木にしたいのです。 2分探索木のプログラムを参考に書いていて、その一部が typedef int BSTREE_K_TYPE; typedef int BSTREE_V_TYPE; struct bsnode { BSTREE_K_TYPE key; BSTREE_V_TYPE value; struct bsnode *left; struct bsnode *right; }; typedef struct bsnode BSTREE_NODE; int gShortFormat = 1; void error(char *msg){ fflush(stdout); fprintf(stderr, "%s\n", msg); exit(1); } BSTREE_NODE *createNode(BSTREE_K_TYPE x){ BSTREE_NODE *new; new = malloc(sizeof(BSTREE_NODE)); if(new == NULL) error("createNode:　メモがありません"); new->key = x; new->value = 0; new->left = NULL; new->right = NULL; return new; } BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){ if (p == NULL){ } else if (p->key == x){ error("insertNode: 指定キーのノードが含まれています"); } else if (p->key > x){ p->left = insertNode(p->left, x); } else { p->right = insertNode(p->right, x); } return p; } BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){ BSTREE_K_TYPE x; int i, n = 0; for(i = 0; i < len; i++){ if(!strcmp(str[i], "--")) break; x = atoi(str[i]); if(btree == NULL) btree = createNode(x); else btree = insertNode(btree, x); n++; } *end = n; return btree; } このinsertNodeのifの条件を変えればいいのかと思い、いろいろ試してみたのですが、 左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした もう何時間も悩んだのですが自分の知識では手づまりです どうかよろしくお願いします。

  • 二分探索木への挿入

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

  • 多分探索木の昇順出力

    多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが 途中でセグメントエラーが起きてしまいます。 void out_MS(NODE *p){ int i,n=0 ; for(i = 0; i <= p->nkeys; ++i) if (p->refs[i] != NULL) out_MS(p->refs[i]) ; while(p->keys[n+1]!='\0'){ printf("No:%3d \"%s\"\n",count,p->keys[n]) ; count++; n++; } } この、多分木に使われている、構造体は以下のとおりです #define KK 16 typedef struct node{ // 多分探索木、B(B*)木構造体 char *keys[KK] ; // キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[KK + 1] ; // 子への参照欄 } NODE ; この構造体に以下の関数で、10万要素の単語（ランダム）に追加していきます。 int add(NODE *root, char *inv) { NODE *now , // 当該節 *prnt ; // nowの親節 int pos ; // 節内のキーの追加位置 prnt = now = root ; while(now != NULL) { // キーの探索 pos = binsearch(now->keys, now->nkeys, inv) ; // 二分探索 if (pos < now->nkeys && strcmp(inv,now->keys[pos])==0) // 探索値はある return FLS ; // 追加の必要なし if (now->nkeys == KK) { // 当該節に無い、節内に空きが無い prnt = now ; now = now->refs[pos] ; // 子の節へ }else if (pos <= now->nkeys) // 当該節に無い－追加位置が範囲内 break ; } if (now != NULL) // 当該節は在る store_key(now, inv, pos, &(now->nkeys)) ; // 当該節にキーを追加格納 else { // 当該節は無い－新規生成 if (now != root) { // nowは根ではない now = set_key(KK, inv) ; // キーを新節に格納 prnt->refs[pos] = now ; // 親節の参照欄に新節の番地を格納 }else return FLS ; } return 1 ; } 上記の関数で使われている、store_key set_key binserch の関数は以下のとおりです void store_key(NODE *trgt, char *inv, int pos, int *nkeys) { if (trgt->keys[pos] == INTV) // 当該位置は空 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 else { // 当該位置に入っている shift_element(trgt, 'R', pos, *nkeys) ; // 要素を移動 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 } ++*nkeys ; return ; } int binsearch(char *array[], int size, char *inv){ // 二分探索 int mid, // 当該位置 low, // 探索範囲の下限 high ; // 探索範囲の下限 if (size == 0) // キーは格納されていない return 0 ; if (strcmp(inv,array[0])<0) // 探索範囲以下 return 0 ; if (0 < strcmp(inv,array[size - 1] )) // 探索範囲以上 return size ; low = 0 ; // 下限設定 high= size - 1 ; // 上限設定 while(0 <= high - low) { // 二分探索本体 mid = (high + low) >> 1 ; // 中間位置を調べる if (strcmp(inv,array[mid])==0) // 入力値が一致したとき return mid ; if (strcmp(inv,array[mid])<0) // 入力値が小さいとき high = mid - 1; else // 入力値が大きいとき low = mid + 1 ; } return low ; } NODE *set_key(int size, char *key) { NODE *new ; new = crt_node(size) ; // 節の生成 new->keys[0] = strdup(key) ; // 配列の先頭に入力値を格納 new->nkeys = 1 ; // 節内の実際の要素数 return new ; } ぜひ、お力をお貸しください。よろしくお願いします。

  • 線形探索のエラーがでて困っています

    線形探索を用いて表を作るプログラムを作ったのですが、データの数が１００００ならば作動するのですが、それ以上になってしまうとセグメントエラーが起こります。なぜだが教えていただけないでしょうか？ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 1000000 #define M 10 typedef int Key; typedef struct item{ Key key; }Item; struct table { int n; Item item[N]; }; typedef struct table *Table; Item *lookup_item(Table table ,Key key){ int i=0; while(1){ if(i==table->n) return (0); if(table->item[i].key==key) return &(table->item[i]); i++; } return 0; } int add_item(Table table, Item item){ int i; int n=table->n; if(lookup_item(table ,item.key)!=0) return (0); else { table->item[n].key=item.key; table->n++; return (1); } } Table new_table(){ Table table; table = (Table)malloc(sizeof(table)); return table; } int remove_item(Table table, Key key){ int i=0; int n=table->n; if(lookup_item(table,key)!=0) { while(1){ if(table->item[i].key==key){ table->item[i].key=table->item[n-1].key; table->n--; return 1; } i++; } } else return (0); } Key keys[N]; int main() { Table table; Item item; clock_t t1, t2; char buff[128]; int i, j, n; /* ファイルからキーを読み込み keys[] に格納する。*/ for (n=0; n<N && fgets(buff, 128, stdin)!=NULL; n++) { keys[n] = atoi(buff); } /* 表を用意する。*/ table = new_table(); /* 追加項目数と全項目の追加に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { item.key = keys[i]; j += add_item(table, item); } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); /* 探索成功数と全項目の探索に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { if (lookup_item(table, keys[i])!=NULL) j++; } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); /* 削除項目数と全項目の削除に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { j += remove_item(table, keys[i]); } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); return 0; } よろしくお願いします。

  • C言語の二分探索法について質問です。

    C言語の２分探索法について質問です。 以下のようなプログラムを作りたいのですが，途中でよく分からなくなってしまいました。添削お願いします。 入力された整数を配列に順次格納する(必ず昇順になるように入力)。0が入力された時に整数の入力を終了し， 次に入力された数字を二分探索によって配列から探索し，その配列の添字番号を出力するプログラムを作成せよ。 実行例 (例1) (例2) 9 ←入力 1 ←入力 7 ←入力 42 ←入力 69 ←入力 99 ←入力 31 ←入力 13 ←入力 93 ←入力 0 ←入力 59 ←入力 5 ←入力 17 ←入力 not found ←出力 0 ←入力 7 ←入力 2 ←出力 プログラム #include <stdio.h> #include <stdlib.h> #define ARRAY_SIZE 10 int swap(int a, int b) { int c; c = a; a = b; b = a; } int main(void) { int array[] ; int low = 0; int high = n - 1; int mid; int key; int i, j, n; int data; struct node *p; puts("整数を入力して下さい。"); for(i = 0; i < ARRAY_SIZE && scanf("%d", array + i) == 1; ++i){ if(array[i] == 0) break; for(j = i; j > 0 && array[j-1] > array[j]; j--) swap(array[j-1], array[j]); } n = i; puts( "探索する値を入力して下さい" ); scanf( "%d", &key ); while( low <= high ) / { mid = (low + high) / 2; if( array[mid] == key ) { return ; } else if( array[mid] < key ) { low = mid + 1; } else { high = mid - 1; } } puts( "not found" ); return 0; }

  • 二分探索プログラムの添削願い

    方程式の解を求める以下のプログラムの添削やアドバイスをお願いします。プログラムが行う処理手順の概要は、以下の通りです。解くべき方程式はmainの２行目に(i)と示されています。 (1)方程式を表示し、ユーザーに関数fのパラメーターを入力させる。 (2)関数の次数に応じて処理が分岐し、fが”定数項が0でない三次式”の場合は(4)へ飛ぶ。それ以外は(3)へ。 (3)解の公式などを用いて虚数解を含むすべての解を求めて表示し、終了。 (4)二分法を用いて解を求める。二分法の区間を入力するようユーザーを誘導する。 (5)設定された区間をさらに1000等分してそれぞれの区間に対して（上限値に近いほうから順番に）二分法を用い、見つけられるだけの実数解を探索し、結果を表示して終了。 ・・・以上です。載せているソースコードは前文ではなく抜粋です。本当はソースコードを全部載せたかったのですが、字数制限の都合上かなり省略があります。 実際には、*には方程式のパラメータ入力への誘導部が、**には二分法の区間設定への誘導が省略されています。これらの部分で、関数のパラメータをa,b,c,dに、二分法の区間をupper,lowerに格納します。 　また、ユーザーを誘導するメッセージ、求めた方程式の解を表示するメッセージなども全て省略しています。途中に出てくるメソッドですが、 ・checkDegree（コードは省略されています。） fのパラメータを渡すと、fの次数をdegreeに返す。 ・soluteEq（コードは省略されています。） fの次数とパラメータを渡すと、a=0かつd=0の場合を除き(i)の解を全て表示し、終了フラグを立てる。 ・foo（省略されています。） 変数xと、方程式のパラメータを与えると、fの値を返す。 ・doBisection 二分法の区間と方程式のパラメータを渡すとその区間を1000等分して新たな区間を 1000個作成し、それぞれの区間に（上限値に近いほうから）二分法を実行。見つけられた解の個数を返す。 となっています。 自分が作成したプログラムをEclipse上で動かしてみると、一応正確な答えは帰ってきました。 ただ自分の作ったプログラムの問題として、doBisectionの処理において、たまたまn番目の区間の下限値が方程式(i)の解だった場合、n+1番目の区間に対して二分法処理が行われないことです。 これはn番目の区間の下限値が、n+1番目の区間の上限値になってしまうためなのですが、何か良い解決策をご提示願えないでしょうか。 また他にも、ソースコードをより可読的にするための改善点などありましたら、 ご提案願えないでしょうか。プログラミング初学者なのですが、独学でやっていますので 変な癖がついたりするのが結構不安です。 以下ソースコード抜粋を貼ります。皆様のお言葉、お待ちしております・・・ （自分は返信をスルーすることはありません。ベストアンサーも必ず指定して質問を完結させます。） //以下main methodの中身 double a = 0, b = 0, c = 0, d = 0, upper = 1, lower = 0; System.out.println("f(x) = a * x^3 + b * x^2 + c * x + d = 0 ・・・(i).");//* int degree = checkDegree(a,b,c,d); int endflag = soluteEq(degree,a,b,c,d); if(endflag == 1){return;}//** if(upper == lower){return;} if(upper < lower){ double change = lower; lower = upper; upper = change; } int find = doBisection(upper,lower,a,b,c,d); }//main以上 //以下doBisection int i = 0, find = 0; while(true){ double u = (1 - 0.001*i)*upper + 0.001*i*lower; double l = (1 - 0.001*(i+1))*upper + 0.001*(i+1)*lower; if(find == 3){break;} if(i == 999){break;} while(true){ double fl = foo(l,a,b,c,d); double fu = foo(u,a,b,c,d); if(fu*fl > 0){ i++; break;} if(fl == 0){ find++; i++; break;} if(fu == 0){ System.out.println("x = "+ u +"\r\nは方程式(i)の解です。"); find++; i++; break;} if(u - l < 10E-10){ i++; find++; break;} double m = (u + l) / 2; double fm = foo(m,a,b,c,d); if(fm == 0){ find++; i++; break;} if(fu*fm > 0){u = m;} if(fl*fm > 0){l = m;} } } return find; }//doBisection以上。

    • ベストアンサー
    • Java
  • アルゴリズムについて

    画像の問題の解答は 手順1 n←1,i←1 手順2 i≦10であるあいだ、手順3,4を繰り返す 手順3 n←n×i 手順4 i←i+1 であっていますか？お願いします！

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する