• 締切済み

再帰を用いた場合の計算量

nの階乗を再帰呼び出しを用いて計算する以下のプログラムの計算量はいくらになるのでしょうか？ 調べてみてもどこにも記述されていなくて困っています． int factorial(int n) { 　　if(n > 0) 　　　　return (n * factorial(n - 1)); 　　else 　　　　return (1); } また，できれば求め方も教えていただけると嬉しいです．

noname#95388
noname#95388

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.4

別っちゃ別だけど同じっちゃ同じ＞#3... って, わかっているとは思いますが. 「求め方は理解した」というなら, その「理解」に従って求めてみてください.

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

＞#1さん ＞また出ましたね。回答が付きませんでしたか？ 前の話は累乗で、今度の話は階乗です。別の話です。 ＞#2さん ＞プログラムの計算量とは何ですか？ 計算量という言葉から推測して、 Ｏ(1)とかＯ(n)とかＯ(nlogn)とかＯ(n^2)とかＯ(n^3)とかＯ(2^n)とか、 そういうたぐいの話だと思います。 別の話でしたら、フォローしてください。＞質問者さん

noname#95388
質問者

補足

わかりづらい質問で申し訳ございません． この方のおっしゃるとおり，計算量のオーダーがいくらになるのかという質問です． 前回の質問のプログラムでのオーダーの計算量の求め方は理解したのですが，今回の場合も同様に考えてO(n)でよいのでしょうか？

  • mk48a
  • ベストアンサー率56% (1133/2007)
回答No.2

プログラムの計算量とは何ですか？ nの階乗のプログラムでn回factorial()関数が呼び出されることになりますが、そういう意味では無いのですか？

  • Tasuke22
  • ベストアンサー率33% (1799/5383)
回答No.1

また出ましたね。回答が付きませんでしたか？ ちょっと質問の意味がよく分からないのですよね。 n>0のところをn>1にしたら結果は同じだけど呼出し が一回減る、とかそういう計算量ですか？

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 再帰呼び出しの計算量

    再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { 　　if(n == 0){ 　　　　return 1; 　　}else{ 　　　　return x * exponent(x, n-1); 　　} } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？

  • nCrの計算

    nCrの計算のプログラムを nCr=n!/(r!(n-r)!) を用いて再帰的関数を使って書いたのですが、もし nCr=n(n-1)(n-2)・・・(n-r+1)/r! であることを用いて、nからmまでの掛算を実現する2引数の関数を定義して、再帰的関数呼び出しを用いたnCrのプログラムを作成するとしたらどうなるでしょうか。 関数x!の定義は、関数の宣言をlong factorial(int x)として、 if (x==0) return(1); else return(x*factorial(x-1)); となることは分かるのですが、 2引数の関数m(m+1)・・・nはどう作れば良いのか全くわからないので、プログラムが書けない状態です。アドバイスお願いします。

  • 再帰について（C言語）

    今、再帰処理を勉強しています。 しかし、以下のプログラムがどうしても理解できません。 流れ的には一体どういう手順になっているのでしょうか？ return i * fact( i - 1 )の部分を考えると頭が こんがらがってしまいます。 #include <stdio.h> int main( void ){ 　printf("５の階乗は %d です", fact(5) ); 　return 0; } int fact( int i ){ 　if( i == 1 ) return 1; 　else return i * fact( i - 1 ); } --------実行結果---------- ５の階乗は 120 です

  • c言語の再帰で(関数呼び出し)+1がわからない

    再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }

  • return 1

    #include<stdio.h> int fact(int num); int main(void) { int i; printf("Input figure freely:"); scanf("%d", &i); printf("%d", fact(i)); return 0; } int fact(int num) { if(num>0){ return num * fact(num-1); }else{ return 1; } } -------------------------------------------- 上のプログラムは再帰呼び出しを使った階乗計算の プログラムです。 func()関数内のreturn 1の意味をどなたか教えて いただけないでしょうか？

  • 再帰呼び出し

    C++のクラスで n!=n(n-1)(n-2)...1 n!を求めるprogramを作らなくてはならないのですが 再帰を使わずに、関数factorial(n)を使わないといけません。 ちんぷんかんぷんです。 for（counterとcounter--を使った）物しか思いうかびません。 関数factorial(n)を使うというのはnに戻るつまり再帰というふうには ならないのですか？ 関数と再帰の意味を漠然としかわかっていないのですが。 よろしくお願いします。

  • 再帰・組み合わせ

    新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません 組み合わせの公式通り（nCk　→　n!/k!(n-k)!）、例えば4C2なら答えは6通りになるのはわかるのですが、 public static int combinations(int n, int k){ if(k==n){ return 1; }else if(k=1){ return n; }else if(0<k && k<n){ combinations(n-1, k-1) + combinations(n-1, k) ←これで出来るらしいのです } } combinations(n-1, k-1)は意味がわかるのですが、combinations(n-1, k)これが組み合わせの公式にどうあてはまっているのかがわからず、 そして何故足してるのかがよくわかりません。どなたかお解かりになればお願いします

    • ベストアンサー
    • Java
  • Rubyのプログラムについて

    Rubyのプログラムについて、宜しければ教えてください。 def fct(n, f=1) if n<=1 then f else fct(n-1, n*f) end end def factorial(n) (1..n).inject{|x,y| x*y} end def factorial(n) eval( [*(1..n)].join("*") ) end このプログラムが、階乗を計算するメソッドになっているみたいなのですが、なぜコレだけで階乗が計算できるのでしょうか？ 宜しければ教えてください＞＜

    • ベストアンサー
    • Ruby
  • 再帰処理を用いて階乗を求めるプログラム

    こんにちは 再帰処理を用いて階乗を求めるプログラムについて の質問です。 以下のように考えたのですが、 まったく駄目なようです。 どこをどのように直したらいいのか いまいちわかりません。 どなたか教えて下さい。お願いします。 Private Sub CommandButton1_Click() Dim n As Integer　階乗する数 Dim f As Integer　階乗する数の階乗した値 n = Val(TextBox1)　　 Do While f > 1 KEISAN n, f Loop TextBox2 = f End Function Function KEISAN(n, f) If n <= 1 Then f = 1 Else f = n * f(n - 1) End If End Function

  • 関数の再帰処理

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する