Skip to content
{{ message }}

Instantly share code, notes, and snippets.

komasaru/binomial_coefficients.cpp

Last active Sep 8, 2020
C++ source code to calculate binomial coefficients.
 /*************************************************************** Binomial coefficients by GMP(The GNU Multi Presicion Arithmetic Library). DATE AUTHOR VERSION 2020.08.24 mk-mode.com 1.00 新規作成 Copyright(C) 2020 mk-mode.com All Rights Reserved. ***************************************************************/ #include "common.hpp" #include "calc.hpp" #include // for cout #include #include int main(int argc, char* argv[]) { my_lib::Calc bc; mpz_class n; mpz_class r; std::string buf_n; std::string buf_r; try { while (true) { // n, r 入力＆チェック std::cout << "n? "; getline(std::cin, buf_n); if (buf_n.empty()) break; std::cout << "r? "; getline(std::cin, buf_r); if (buf_r.empty()) break; if (!my_lib::is_int(buf_n)) { std::cout << "n is not a integer !!" << std::endl; break; } n.set_str(buf_n, 10); if (!my_lib::is_int(buf_r)) { std::cout << "r is not a integer !!" << std::endl; break; } r.set_str(buf_r, 10); if (r < 0) { std::cout << "r < 0 !!" << std::endl; break; } if (n < r) { std::cout << "n < r !!" << std::endl; break; } if (r * 2 > n) r = n - r; // 計算 // （計算方法 1 - 4 から選ぶ） std::cout << "(" << n << " " << r << ") = " // << bc.binom_1(n, r) << std::endl; // << bc.binom_2(n, r) << std::endl; // <= too slow << bc.binom_3(n, r) << std::endl; // << bc.binom_4(n, r) << std::endl; std::cout << "---" << std::endl; } } catch (...) { std::cerr << "EXCEPTION!" << std::endl; return EXIT_FAILURE; } return EXIT_SUCCESS; }
 #include "calc.hpp" #include "common.hpp" namespace my_lib { /* * 二項係数の計算(1) * 計算式: (n r) = n! / r!(n -r)! * * @param n: n の値 * @param r: r の値 * @return : 二項係数 */ mpz_class Calc::binom_1(mpz_class n, mpz_class r) { try { if (r == 0 || r == n) return 1; return my_lib::fact(n) / (my_lib::fact(r) * my_lib::fact(n - r)); } catch (...) { throw; } } /* * 二項係数の計算(2) * 計算式: (n r) = ((n - 1) r) + ((n - 1) (k - 1)) * (recursively) * * @param n: n の値 * @param r: r の値 * @return : 二項係数 */ mpz_class Calc::binom_2(mpz_class n, mpz_class r) { try { if (r == 0 || r == n) return 1; return binom_2(n - 1, r) + binom_2(n - 1, r - 1); } catch (...) { throw; } } /* * 二項係数の計算(3) * 計算式: (n r) = (n / r) * ((n - 1) (k - 1)) * (recursively) * * @param n: n の値 * @param r: r の値 * @return : 二項係数 */ mpz_class Calc::binom_3(mpz_class n, mpz_class r) { try { if (r == 0 || r == n) return 1; return n * binom_3(n - 1, r - 1) / r; } catch (...) { throw; } } /* * 二項係数の計算(4) * 計算式: (n r) = Π(n - i + 1) / i (i = 1, ..., r) * * @param n: n の値 * @param r: r の値 * @return : 二項係数 */ mpz_class Calc::binom_4(mpz_class n, mpz_class r) { mpz_class a; int i; try { if (r == 0 || r == n) return 1; a = 1; for (i = 1; i <= r; i++) a = a * (n - i + 1) / i; return a; } catch (...) { throw; } } }
 #ifndef BINOMIAL_COEFFICIENTS_CALC_HPP_ #define BINOMIAL_COEFFICIENTS_CALC_HPP_ #include // for cout #include #include namespace my_lib { class Calc { public: mpz_class binom_1(mpz_class, mpz_class); mpz_class binom_2(mpz_class, mpz_class); mpz_class binom_3(mpz_class, mpz_class); mpz_class binom_4(mpz_class, mpz_class); }; } #endif
 #include "common.hpp" namespace my_lib { /* * Integer judgment */ bool is_int(std::string s) { std::smatch m; std::regex re("^[+-]?\\d+\$"); try { if (!std::regex_search(s, m, re)) return false; } catch (std::regex_error& e) { return false; } return true; } /* * Caculation of fatorial */ mpz_class fact(mpz_class n) { try { if (n == 0) return 1; return n * fact(n-1); } catch (...) { throw; } } }
 #ifndef BINOMIAL_COEFFICIENTS_COMMON_HPP_ #define BINOMIAL_COEFFICIENTS_COMMON_HPP_ #include #include #include #include namespace my_lib { bool is_int(std::string); mpz_class fact(mpz_class); } #endif
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.