- ベストアンサー
内部ハッシュ法
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
内部ハッシュ法はよく知りませんが， 式の方だけ分析してみましょう． stomachman さんのおっしゃるとおりなのですが， もう少し突っ込んでみましょう． 問題の式をから (m/B)^i という因子を引っ張り出すと (1) m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = (m/B)^i {f(m,i)/f(B,i)} の形になります． (2) f(n,i) = 1 (1-1/n) (1-2/n) ・・・ {1-(i-1)/n} 問題の近似式は {f(m,i)/f(B,i)}≒１ としているわけです． B,m >> i なら近似がよいのは直感的に明らかですが， 近似の程度を見てみましょう． (2)を展開して，最低次の項までとると (3) f(n,i) ≒ 1 - Σ(j=1～i-1) (j/n) ≒ 1 - i(i-1)/ 2n ですから (4) f(m,i)/f(B,i) ≒ 1 + i(i-1)/2 {1/B - 1/m} で近似の程度が明確になりました． ん，B=m だと最低次の補正項が消えるのか？ そりゃそうです． B=m なら (5) m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = 1 = (m/B)^i で，近似が正確な値を与えますから．
その他の回答 (1)
- stomachman
- ベストアンサー率57% (1014/1775)
m=8, i=8, B=9としてみれば左辺=0.11, 右辺=0.39。あんまり似てませんねえ。 この近似は、 m, Bがiに比べてうんと大きいときだけ有効なんですよ。 m/B≒(m-1)/(B-1)≒…(m-i+1)/(B-i+1) と近似して、 だから左辺≒(m/B)^i とやっただけのことです。
お礼
なるほど！！ わかりやすく教えていただき、ありがとうございましたm(_ _)m これでレポートもなんとかできそうです。
関連するQ&A
- ハッシュ法でのデータ管理について教えてください
ハッシュ法でのデータ管理をするプログラムを作りたいんですが長いことPASCALに触ってなかったせいか全く分かりません。 どなたか教えていただけないでしょうか？？問題の概要は以下のようなものです。 表に登録するデータについては、キーは英数字からなる長さ８までの文字列でデータ本体は整数（型名はintegerでよい）です。 ハッシュ表のサイズは１１とします。 ハッシュ関数は文字列xの各文字のASCIIコードの総和を１１で割った余りとします。 さらにメニュー表示として入力した文字により行う操作を決定します。 どの文字がどのような操作を行うのかは以下のとおりです。 's' の場合： ハッシュ表に登録されている全レコードを，ハッシュ関数値毎に(キーの値とデータの両方を)すべて表示します． 'r' の場合： さらに「キーの値」と「データ」を入力し，すでに同じキーをもつデータがあれば「二重登録」として検出し，そうでなければ，そのレコードをハッシュ表に登録します． 'e' の場合： さらに「キーの値」を入力し，そのキーをもつデータがハッシュ表に登録されているならば， そのデータを表示します．さらに削除するかどうかを入力させて，削除する選択をした場合にはそのレ コードを削除します．そのキーをもつデータがハッシュ表にない場合には「そのキーをもつレコードが ないこと」を出力しますが，ハッシュ表には操作を加えません． 'i' の場合： ハッシュ表に登録されている全レコードを，キーの値が小さい順に表示します．ここで「キー の値の順」とは，文字列の辞書順のことを意味します．Pascal では，文字列a,b に対して，a がb より 辞書的順序が先(小さい) ときには「a<b」で表現できます． 'd' の場合： 「'i' の場合」の逆で，キーの値が大きい順に表示します． 'q' の場合： プログラムを終了します．具体的には，実行文部の最後の「end.」の直前までジャンプし ます． 長くなってすいません。ちょっとしたヒントでもいいので教えていただければ幸いです。
- ベストアンサー
- その他（プログラミング・開発）
- ハッシュ法の質問
#include <stdlib.h> #include <stdio.h> #include <string.h> #define M 257 int zoo(char *v){ int x; x=0; while(*v) x = 256*x + (*v++); if (x<0) x=(-x); return(x%M);} #define CHARMAX 10000 static int chartop=0; static int charbtm=CHARMAX; static char charheap[CHARMAX]; char *goo(char *s){ char *cp; int i,j,len,result; cp =s; len=0; while(*cp++) len++; len++; if(charbtm - chartop < len){ printf("errrrrrrrrrrrrrrrrrrrr"); exit(1);} result = chartop; j=chartop; chartop += len; cp=s; for (i=0;i<len;i++) charheap[j+i]=(*cp++); return(&charheap[result]);} struct item {char *id; int info;}; static struct item table[M]; void initialize(){ int i; for(i=0; i<M; i++){ table[i].id=goo(" ");}} void enter(char *id1, int info1){ int x; x=zoo(id1); while(strcmp(table[x].id, " ")) x=(x+1)%M; table[x].id =goo(id1); table[x].info=info1;} int search(char *id1){ int x; x=zoo(id1); while(strcmp(table[x].id,id1)) x=(x+1)%M; return(table[x].info);} main(){ int t; initialize(); enter("takahasi",1234); enter("kato",2345); enter("saito",4532); printf("%d\n",search("takahasi")); printf("%d\n",search("kato")); printf("%d\n",search("saito")); } これは学生の学籍番号を登録し、登録した名前から番号を検索するプログラムです。 １．このプログラムでは何人まで登録できますか？ ２．その人数を超えた場合何が起こるか。 ３．配列charheap、配列tableには何が格納されているか という問題があたのですが上の３つの問題がわかりません。誰か教えてください。１・は１００００かなっておもいましたが違うようです。
- ベストアンサー
- C・C++・C#
- ハッシュ法
ハッシュ法で作ったデータ構造をファイルに書き込む、またファイルからの読み込みを行うにはどうしたら良いのでしょうか？？ 連結リストの場合、ファイルを開いてから下のようにすれば書き込める事が分かったので、下の操作をハッシュテーブルの大きさ分だけ繰り返せば良いのかな、と思ったのですができません(> <) for(pos = g_syain_head; pos != NULL; pos = pos->next) { offset = sizeof(Syain) * i; fseek(fp, offset, 0); fwrite(pos, sizeof(Syain), 1, fp); i++; } 誰か分かる方お願いします！！
- ベストアンサー
- C・C++・C#
- Jacobi法
Jacobi法のアルゴリズム x[i]_{m+1} = ( b[i] - Σ{j≠i} a[i][j] * x[j]_{m} ) i=1,2,…,n m=0,1,2,… を基にプログラム（JAVA）を組んでみました。 （質問に直接関係ないところは省いています） for( m=0; m<100; m++ ) { for( i=0; i<n; i++ ) { for( j=0; j<i; j++) { if( i != j ) { tmp = tmp + a[i][j] * x2[j]; } } x1[i] = (b[i] - tmp) / a[i][i]; } } もう１つ。 for( k=0; k<100; k++ ) { for( i=0; i<n; i++ ) { xnew[i] = b[i]; for( j=0; j<n; j++ ) { if( j != i ) { xnew[i] = xnew[i] - a[i][j] * xold[j]; } } xnew[i] = xnew[i] / a[i][i]; } 2つ目のプログラムの方が正確です。 1つ目のプログラムだと間違いでしょうか？ 私には2つ目のプログラムの xnew[i]=b[i]; の部分がどうしても理解できません。 これを行ってしまうと、アルゴリズムが x[i]_{m+1} = ( Σ{j≠i}b[i] - a[i][j] * x[j]_{m} ) になってしまわないでしょうか・・・？ どちらでも良いのでしょうか？ 納得いきません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 動的ハッシュを作って取り出したいのですが・・・
お世話になります。 フォームから送られてくるデータを動的に作ったハッシュで参照出来るように取り組んでるんですが、思ったように出来ず思い悩んでおります。 どうすれば、意図した形でデータを取り出すことが出来ますでしょうか my %FORM = ( 'd01' => 'あ', 'd02' => 'い', 'd03' => 'う', 'd04' => 'え', 'd05' => 'お', 'd06' => 'か', 'd07' => 'き', 'd08' => 'く', 'd09' => 'け', 'd10' => 'こ', ); for(sort { $FORM{$a} cmp $FORM{$b} } keys %FORM){ print "$_ = $FORM{$_} \n"; } $list="d01,d02,d03,d04,d05,d06,d07,d08,d09,d10,"; $i=-1; foreach (split/,/,$list){ $i++; $hash{$_}=$i; } for(sort { $hash{$a} <=> $hash{$b} } keys %hash){ print "$_ = $hash{$_} \n"; $view = ${"FORM$_"}; print "$view\n"; }; 最後のprint "$view\n";箇所で、 $list="d01,d02..." を split/,/,$list したので、 $FORM{d01} $FORM{d02} となるようにして、 「あ い う え お」と取り出したいのです。 ご教授のほど、よろしくお願い致します。
- ベストアンサー
- Perl
- バンドマトリクス法
大規模な行列の連立一次方程式を計算したいと考えています。バンドマトリクス法で解こうと考え、プログラムを書いたのですが、うまく動作しません。 どうやら、全身消去の過程においてアクセスする行を表す変数lのとる範囲がどうしても配列の範囲を超えてしまい，ここでエラーがでてしまうようです．範囲のとりかたが間違っているのでしょうか？分かる方よろしくお願いします。 以下はプログラムの全身消去～後退代入の部分です。 // 前進消去 for (k=1;k<=N-1;k++){ for (l=k+1;l<=k+Bw-1;l++){ for (m=k-l+2;m<=k+Bw-l;m++){ if (l <= N){ B[l][m] = B[l][m] - B[k][l-k+1]*B[k][l+m-k]/B[k][1]; } if (l <= N){ B[l][Bw+1] = B[l][Bw+1] - B[k][l-k+1]*B[k][Bw+1]/B[k][1]; } } } } // 前進消去結果の出力 for (i=1;i<=N;i++){ for (j=1;j<=Bw+1;j++){ printf("%3.2e ",B[i][j]); } printf("\n"); } printf("\n"); // 後退代入 x[N-1] = B[N][Bw+1]/B[N][1]; for (l=N-1;l>=1;l--){ n = 0; for (m=2;m<=Bw;m++){ n += B[l][m]*x[l+m-1]; } x[l] = (B[l][Bw+1] - n) / B[l][1]; } // 解の出力 for (i=0;i<N;i++){ printf("x[%d] = %e\n",i,x[i]); } return 0; }
- 締切済み
- C・C++・C#
- ハッシュのハッシュを値とキーでソートする方法
%array = ( 'A' => { 'a' => 7, 'b' => 3, 'c' => 9, 'd' => 1, }, 'B' => { 'a' => 3, 'b' => 8, 'c' => 3, },); のようなハッシュがあったとして、値の降順、1つ目のキー昇順、2つ目のキー昇順でソートし、下のような形で出力したいのですが、どのようにすればよいのでしょうか。 A c 9 B b 8 A a 7 A b 3 B a 3 B c 3 A d 1
- ベストアンサー
- Perl
- ハッシュ法が得意な人お願いします。
辞書検索プログラムが実行できません。どこがおかしいか教えてください。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define BUCKET_SIZE 100 typedef struct pointer { struct cell *chain; }pointer; struct cell{ char eng[20]; char jp[40]; struct cell *next; } table[BUCKET_SIZE]; int n; void read_dic(); void init_table(); int hash(char *tango); void main(); struct cell *find(char *tango); struct pointer bucket[BUCKET_SIZE]; void init_table() { int i; for (i=0;i<BUCKET_SIZE;i++){ strcpy(table[i].eng,"0"); strcpy(table[i].jp,"0"); } } void main() { int m; struct cell *p; char tango[20]; read_dic(); while(1){ printf("\n単語を入力： "); scanf("%s", tango); if (strcmp(tango, "*") == 0){ printf("検索を終了\n"); exit(0); } if((p= find(tango)) == NULL) printf("単語は見つかりませんでした\n"); else printf("訳語： %s \n", table[p].jp); } } まだ続きます。。。
- 締切済み
- C・C++・C#
お礼
詳しく教えていただき、ありがとうございましたm(_ _)m 順序があって、大変わかりやすかったです。 「なるほど・・・」と感動しました。 これからちゃんと理解しているか確認のためも含めて、 レポートを書いてみようと思います。