the_art_of_computer_programming
置換と階乗 非負整数に関して の階乗は以下のように定義される。 しかし、 が整数でない時には という記法は余り使われない。 その代わり、以下の記法を用いる。 この関数はガンマ関数と呼ばれ、次のように定義される。
1.2.4 整数関数と初等整数論 modについて (a) なら (b) なら (c) は の整数倍 となる。例えば、 となる。最後の式は を考えると、あまりは2,1,0,2,1,0となっているので-1を3で割った余りはその順序に従って2となる。なので、-2を3で割った余りは1となる。 mo…
1.2.3 総和と乗積 式(13)について この式の左辺の計算量はで、右辺はである。 この2つの計算量の違いは大きく、左辺はで、1億回の計算することになる(実際は5千万回ほど)。 しかし、左辺は同じでも計算回数は1万回(実際は1万回の計算が2回あるので2万回の計…
対数を使う場合コンピュータの分野では2進対数が用いられるが、 その最大の理由は、コンピュータアルゴリズムが2方向の分岐を多用するから。 if-elseに代表されるように大なり小なりの判定や、ある文字列sとtが同じ文字列かどうかの判定などはyesかnoの2方向…
1.2.1 数学的帰納法 数学的帰納法は以下の方法で証明を行う。 P(n)を整数nについての何らかの言明だとする。 (a) P(1) が真であることを証明する。 (b) [P(1), P(2), ... , P(n)が全て真なら、P(n + 1)も真である。]ことを証明する。 ただし、nを適当な数に…
1.1アルゴリズム アルゴリズムは単に特定のタイプの問題を解決するための一連の作業手順を定める有限個の規則という以上に、5種類の重要な特徴をもっている。 (1)有限性 アルゴリズムは有限回のステップを実行したあと、必ず終了しなければならない。 以下の…