大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp 再帰 データ構造とプログラミング（８） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp.

Presentation on theme: "大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp 再帰 データ構造とプログラミング（８） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp."— Presentation transcript:

1 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp
再帰 データ構造とプログラミング（８） 大岩 元 慶応大学環境情報学部

2 再帰の例（三角数） 再帰公式 一般公式 プログラム triangle(n) = n + triangle(n-1)
triangle(n) = (n*n + n)/2 プログラム int triangle {if(n==1) return 1 else return(n + triangle(n-1))}

3 再帰の例（階乗） 再帰公式 プログラム n! = n*(n-1)! 0! = 1 int factorial(n)
{if(n==0) return 1 else return( n*factorial(n-1)}

4 アナグラム 文字列に含まれる文字から形成される同じ長さの文字列 ｎ文字から成る文字列の、全てのアナグラムを求めるには
右側の n-1 文字の全てのアナグラムを求める ｎ文字の文字列全体を１文字分回転する 以上をｎ回繰り返す

5 二分探索 int find(double searchKey) {int lowerBound = 0;
int upperBound = nElems -1; int curIn; while(true) { curIn = (lowerBound + upperBound)/2; if(a[curIn] == searchKey) return curIn;// 見つかった else if (lowerBound > upperBound) return nElms; // 見つからず else {if (a[curIn] < searchKey) lowerBound = curIn + 1; // 上半分を探索 else upperBound = curIn -1; // 下半分を探索 } // 範囲分割の終り } // while の終り　 } // find（）の終り

6 再帰による二分探索 int find(double searchKey, int lowerBound, int upperBound)
{ int curIn; curIn = (lowerBound + upperBound)/2; if(a[curIn]==searchKey) return curIn; // 見つかった else if(lowerBound > upperBound) return nElems; // 見つからない else // 範囲を半分にする {if (a[curIn] < searchKey) // 上半分を調べる return recfind(searchKey, curIn+1, upperbound); else // 下半分を調べる return recfind(searchKey, lowerBound, curIn-1); } // 範囲分割の終り } // recfind の終り