Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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 <iostream> // for cout
#include <gmp.h>
#include <gmpxx.h>
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 <iostream> // for cout
#include <gmp.h>
#include <gmpxx.h>
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 <regex>
#include <string>
#include <gmp.h>
#include <gmpxx.h>
namespace my_lib {
bool is_int(std::string);
mpz_class fact(mpz_class);
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.