C/C++の宿題を片付けます 104代目

C/C++の宿題を片付け� ..

■コピペモード
□スレを通常表示
□オプションモード
□このｽﾚｯﾄﾞのURL
■項目テキスト

68:デフォルトの名無しさん
 08/02/08 16:45:17 
これでかなり高速化できる 
あまりやりすぎると数式で求めろといわれそうだがｗｗｗ 
int ackermann(int m, int n) 
{ 
 if(m==0) return n+1; 
 if(m==1) return n+2; 
 if(m==2) return n*2+3; 
 if(n==0) return ackermann(m-1, 1); 
 return ackermann(m-1, ackermann(m, n-1)); 
}

69:66
 08/02/08 16:59:11 
やっと納得。 
　　 　　　　　　m=4, n=1　　m=3, n=12 
シンプル版　　　 　9.9sec　　　2.4sec 
キャッシュ版　　　41.4sec　　 10.3sec 
ショートカット版　　0.00sec　　 0.00sec 
 
ショートカット版は、mが1のときのアッカーマン関数を解いた結果を導入したもの。 
# 解く過程はこれ。 
ack(1, 0) ⇒ ack(0, 1) ⇒ 2 
ack(1, 1) ⇒ ack(0, ack(1, 0)) ⇒ ack(1, 0) + 1 ⇒ 3 
ack(1, 2) ⇒ ack(0, ack(1, 1)) ⇒ ack(1, 1) + 1 ⇒ 4 
ack(1, 3) ⇒ ack(0, ack(1, 2)) ⇒ ack(1, 2) + 1 ⇒ 5 
： 
： 
以下同様に。 
 
ソースは後で。

70:66
 08/02/08 17:02:37 
がーん、ソース貼られてたw しかも、m=2についても解いてあるし。 
 
>>67 
＞呼び出し回数は大して減らないって？ 
だから、>54の問題にあるようなキャッシュについてですがな。 
m=1について解いてしまえば早くなりましたがな。 
 
癪だから以下に。 
-- 
#include <stdio.h> 
#include <stdlib.h> 
// #include <stdbool.h> 
 
static int ack(unsigned m, unsigned n) 
{ 
//  static int a[4][16]; 
//  bool inRange = m < sizeof(a) / sizeof(* a) && n < sizeof(* a) / sizeof(** a); 
    int val; 
//  if (inRange && a[m][n] != 0) return a[m][n]; 
    if (m == 0) { 
        val = n + 1; 
    } else if (m == 1) {    // short cut for ack(1, n) 
        val = n + 2;    // ack(1, n) -> ack(0, ack(1, n-1)) -> ack(1, n-1) + 1 
    } else if (n == 0) { 
        val = ack(m - 1, 1); 
    } else { 
        val = ack(m - 1, ack(m, n - 1)); 
    } 
//  if (inRange) a[m][n] = val; 
    return val; 
} 
コメント部分を生かせばキャッシュされるけど、最早どうでもいいなぁw

次ページ