編入試験アルゴリズム過去問の解答を教えてください

Question

筑波大学情報学群の編入試験の過去問です。アルゴリズムの問題で、リストの辞書の問題です。
この中の（3）以降が分からないです。計算時間はどこを見ればいいのでしょうか。
解答の回答をお願いします。
正答ではないかもですが、一応穴埋めを解いたものを載せておきます。
ア　struct dict_list
イ   return i;
ウ   new->next=bucket[i];
エ   bucket[i]=new;
オ   elm=elem->next;

tatsu99 · Accepted Answer

前回、以下の関数がNが十分、大きいとき、h3の戻り値が分散される旨を記述しましたが、
その理論的な考え方を提示していませんでしたので、以下に記述します。
int	h3(char *str){
	unsigned int i,v;
	int l = strlen(str);
	v = 0;
	for(i = 0;i <l;i++)
		v = v + (str[i] << ((i*7) % 31));
	return v % N;
}

ここで、 ((i*7) % 31))は、文字（コードの値）を左へ何ビットシフトするかを示しています。
i=0(1文字目)の時、 0ビット
i=1(2文字目)の時、 7ビット
i=2(3文字目)の時、 14ビット
i=3(4文字目)の時、 21ビット
i=4(5文字目)の時、 28ビット

ここで、4文字以内の場合を考慮すると、完全に全ての文字の組み合わせで、
完全にユニークな値（シノニムの発生なし）であることが、確認できます。
1文字の場合、a～z
2文字の場合、aa～zz
3文字の場合、aaa～zzz
4文字の場合、aaaa～zzzz
の文字列になりますが、
添付図①のようにa=0x61,z=0x7Aであるのでa～zの文字は7ビットの数値で表現されます。
h3の戻り値は
1文字目＋2文字目を７ビット左シフト＋３文字目を１４ビット左シフト＋4文字目を２１ビット左シフト
の結果をNで割った余りですが、Nが十分大きいので、
1文字目＋2文字目を７ビット左シフト＋３文字目を１４ビット左シフト＋4文字目を２１ビット左シフト
の結果となります。
この結果は、a～z,aa～zz,aaa～zzz,aaaa～zzzzの文字の組みあわせの場合、完全にユニークな値になります。
（1文字目から４文字目まで生成される値にビット重複がないのでユニークな値になります）
（添付図②を参照ください）

5文字目以降は、シフトの数が変わってくるので、理論上は、ビットの重複が発生し（回数は少ないはずですが）シノニムが発生する可能性があります。

tatsu99 · Answer

ちなみに、今回の問題のような文字列の管理方法をハッシュ法とハッシュ検索とか呼びます。
http://takatakamanbou.hatenablog.com/entry/2015/04/11/155405

h1,h2,h3等が返す値をハッシュ値と呼びますが、この値が重複しない関数が優秀なハッシュ値生成の関数です。(h3が最も優秀）
ハッシュ検索時は、同じハッシュ値が重複した時、それをシノニムと呼びます。
シノニムの数が少ないことが、ハッシュ検索で検索時間を少なくすることになります。
今回のケースでは、bucket[i]の単語の数－１がシノニムの数に該当します。

tatsu99 · Answer

（３）に関するソースです。 #include #include #define N (100) struct dict_list{ struct dict_list *next; //ア char *name; }; struct dict_list *bucket[N]; int strcmp_count; int h1(char *str){ return *str % N; } int h2(char *str){ return (str[0] + str[1]) % N; } int search(char *str){ struct dict_list *elem; int i; i = h1(str); elem = bucket[i]; while(elem){ strcmp_count++; if(!strcmp(elem->name,str)) return -1; elem = elem->next; } return i; //イ } int search2(char *str){ struct dict_list *elem; int i; i = h2(str); elem = bucket[i]; while(elem){ strcmp_count++; if(!strcmp(elem->name,str)) return -1; elem = elem->next; } return i; //イ } void insert(char *str){ struct dict_list *new; int i; i = search(str); if (i < 0) return; new = malloc(sizeof(struct dict_list)); new->next = bucket[i]; //ウ new->name = str; bucket[i] = new; //エ } void insert2(char *str){ struct dict_list *new; int i; i = search2(str); if (i < 0) return; new = malloc(sizeof(struct dict_list)); new->next = bucket[i]; //ウ new->name = str; bucket[i] = new; //エ } void display(void){ int i; struct dict_list *elem; for (i = 0; i < N; i++){ elem = bucket[i]; if (elem == NULL) continue; printf("bucket[%d]=>",i); while(elem){ printf("[%s]=>",elem->name); elem = elem->next; //オ } printf("[] "); } } int main() { char *data[] = {"hydrogen","belium","lithium","berylium","boron","carbon","nitrogen","oxygen","fluorine","neon"}; char *data1 = "natrium"; int no_elm = sizeof(data)/sizeof(char*); int i; printf("no_elm=%d ",no_elm); //bucketクリア for(i=0;i[fluorine]=>[] bucket[4]=>[hydrogen]=>[] bucket[8]=>[lithium]=>[] bucket[10]=>[natrium]=>[neon]=>[nitrogen]=>[] bucket[11]=>[oxygen]=>[] bucket[98]=>[boron]=>[berylium]=>[belium]=>[] bucket[99]=>[carbon]=>[] strcmp_count=0 bucket[7]=>[natrium]=>[] bucket[9]=>[boron]=>[] bucket[10]=>[fluorine]=>[] bucket[11]=>[neon]=>[] bucket[13]=>[lithium]=>[] bucket[15]=>[nitrogen]=>[] bucket[25]=>[hydrogen]=>[] bucket[31]=>[oxygen]=>[] bucket[96]=>[carbon]=>[] bucket[99]=>[berylium]=>[belium]=>[]

tatsu99 · Answer

以下、回答です。(ソースは次回提示)
（ア）：OK
（イ）：OK
（ウ）：OK
（エ）：OK
（オ）：elm=elem->next;ではなく、elem=elem->next;（elmという変数は存在しないので記述ミスと思われる）

(3)の回答　
h1=2回
h2=0回
上記は、実際に実行した結果(strcmp_countの印字結果)

上記の理論的根拠
h1は、１文字目を100で割った余りをbucket[i]の添え字として採用している。
従って、natriumと１文字目が同じものは、nitrogen,neonの2つがある。よって2回
h2は、1文字目と２文字目を加算した結果を100で割った余りをbucket[i]の添え字として採用している。
従って、１文字目=n 2文字目=aを加算すると、文字コードは、207となる。
1文字目＋2文字目=207となる他の組み合わせは、以下のとおりである。
n	m	l	k	j	i	h	g	f	e	d	c	b
a	b	c	d	e	f	g	h	i	j	k	l	m

1文字目と2文字目が上記の2文字の組み合わせとなるケースは、hydrogen～neonには存在しない。
よって、0回となる。
ちなみに、試みに、hydrogenをmbdrogenに変えて、実行してみれば、1回が表示されることで確認できる。

(4)の回答
Nが十分大きく、辞書に含まれる文字列の数（=登録された単語の数）が、十分大きいという前提なので、
N=10000000 登録した単語の数:Z=100000件とすると、
h1が返す値は、先頭の1文字のみで決まるので26通りとなる。
単語の先頭がaからzまで、均等に分散しているという前提であれば、
１つのbucket[i]に格納される単語の数は、Z/26=100000/26=3846個となる。
（もちろん、bucket[i]に格納される単語の数が0の箇所もあるが、その箇所は使われないので、それは除く）
（ちなみに、aの文字コード=97,zの文字コード=122なので、i=97～99,i=0～22の箇所が使用される）
一方、
h3が返す値は、h3を実際に呼び出してみればわかるが、非常にきれいに分散された値が返される。
つまり、単語の数:ZがNより小さければ、１つのbucket[i]に格納される単語の数は、ほぼ1個と考えて良い。
１つのbucket[i]に格納される単語の数は、1個である。

従って、検索時間の比＝１つのbucket[i]に格納される単語の数の比となるので、
h1の時間:h3の時間 =  Z/26:1となる。（Z=100000の場合 3846:1）

tatsu99 · Answer

残念ながら、提示された画像は、全く何が書かれているか判別できません。
私が回答できる保証はありませんが、もう一度鮮明な画像を再提示してください。

編入試験 アルゴリズム過去問の解答を教えてください

前回、以下の関数がNが十分、大きいとき、h3の戻り値が分散される旨を記述しましたが、

ちなみに、今回の問題のような文字列の管理方法をハッシュ法とハッシュ検索とか呼びます。

（３）に関するソースです。

以下、回答です。

残念ながら、提示された画像は、全く何が書かれているか判別できません。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

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

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

編入試験アルゴリズム過去問の解答を教えてください