アルゴリズムはSchemeコードで示されているため、注意してください：括弧！
制御構造
コンパイル時の関数アナログを取得したいです。 テンプレートのプログラミングでは、構造体は関数として機能し、そのテンプレートパラメータは関数の引数に対応し、定数の静的項は結果に対応します。
(define (fx) (* xx)) (f 10) ; => 100
同様のC ++コード：
template<int x> struct f { static const int value = x * x; };
このような関数の「呼び出し」は、テンプレートのインスタンス化を通じて発生します。
int main() { std::cout << f<10>::value << std::endl; // 100 }
C ++テンプレートを使用すると、テンプレートパラメータの一部の値を特別な方法で処理できます（特殊化）。 これにより、条件付き制御構造を整理できます。
(define (gx) (if (= x 0) 42 (* xx))) (g 10) ; => 100 (g 0) ; => 42
template<int x> struct g { static const int value = x * x; }; template<> struct g<0> { static const int value = 42; }; int main() { std::cout << g<10>::value << std::endl; // 100 std::cout << g<0>::value << std::endl; // 42 }
循環処理を整理するには、再帰を使用します。 上記の手法は、あらゆる機能を説明するのに十分です。
プライム計算
問題の声明
つまり、素数を返す関数を取得します。
int main() { std::cout << prime<0>::value << std::endl; // 2 std::cout << prime<1>::value << std::endl; // 3 std::cout << prime<2>::value << std::endl; // 5 std::cout << prime<3>::value << std::endl; // 7 // ... }
簡易テスト
そのような機能をすぐに実装することはできません。もっと簡単なものから始める必要があります。 最も簡単な方法は、nが素数であるかどうかを確認することです。 確認するために、nをn-1から1までのすべての数で除算した余りがゼロに等しくないことを確認します。
(define (is-prime n) (is-prime-rec n (- n 1))) (define (is-prime-rec n div) (if (or (= div 1) (= div 0)) #t (and (not (= 0 (remainder n div))) (is-prime-rec n (- div 1))))) (is-prime 2) ; => #t (is-prime 3) ; => #t (is-prime 4) ; => #f (is-prime 5) ; => #t
template<int n, int div> struct is_prime_rec { static const bool value = (n % div != 0) && is_prime_rec<n, div - 1>::value; }; template<int n> struct is_prime_rec<n, 1> { static const bool value = true; }; template<int n> struct is_prime_rec<n, 0> { static const bool value = true; }; template<int n> struct is_prime { static const bool value = is_prime_rec<n, n - 1>::value; }; int main() { std::cout << is_prime<1>::value << std::endl; // 1 std::cout << is_prime<2>::value << std::endl; // 1 std::cout << is_prime<3>::value << std::endl; // 1 std::cout << is_prime<4>::value << std::endl; // 0 std::cout << is_prime<5>::value << std::endl; // 1 std::cout << is_prime<6>::value << std::endl; // 0 std::cout << is_prime<7>::value << std::endl; // 1 }
1を素数と見なすかどうかの問題は未解決のままですが、この検証1の実装では単純と見なされます。
次の素数を見つける
与えられた素数（つまり、次のもの）より大きい最小の素数を見つける関数を定義します。
(define (next-prime n) (if (is-prime (+ n 1)) (+ n 1) (next-prime (+ n 1)))) (next-prime 2) ; => 3 (next-prime 3) ; => 5 (next-prime 5) ; => 7 (next-prime 7) ; => 11
template<int n> struct next_prime; template<int n, bool cond> struct next_prime_if { static const int value = n + 1; }; template<int n> struct next_prime_if<n, false> { static const int value = next_prime<n + 1>::value; }; template<int n> struct next_prime { static const int value = next_prime_if<n, is_prime<n + 1>::value>::value; }; int main() { std::cout << next_prime<1>::value << std::endl; // 2 std::cout << next_prime<2>::value << std::endl; // 3 std::cout << next_prime<3>::value << std::endl; // 5 std::cout << next_prime<4>::value << std::endl; // 5 std::cout << next_prime<5>::value << std::endl; // 7 std::cout << next_prime<6>::value << std::endl; // 7 std::cout << next_prime<7>::value << std::endl; // 11 }
数だけを見つける
すなわち素数とは何ですか？ これは（i-1）番目に続く：
(define (prime i) (if (= i 0) 2 (next-prime (prime (- i 1))))) (prime 0) ; => 2 (prime 1) ; => 3 (prime 2) ; => 5 (prime 3) ; => 7
template<int i> struct prime { static const int value = next_prime<prime<i - 1>::value >::value; }; template<> struct prime<0> { static const int value = 2; }; int main() { std::cout << prime<0>::value << std::endl; // 2 std::cout << prime<1>::value << std::endl; // 3 std::cout << prime<2>::value << std::endl; // 5 std::cout << prime<3>::value << std::endl; // 7 std::cout << prime<4>::value << std::endl; // 11 // ... }
完全なソースコード：
スキームpastebin.com/21VFjYt0
C ++ pastebin.com/cfSvBRNH