Вместо грязного int a
и т. Д. Вы можете сделать
menu_statetop[(i + 1) % 5].pText;
menu_statetop[(i + 2) % 5].pText;
menu_statetop[(i + 3) % 5].pText;
и т. Д.
РЕДАКТИРОВАТЬ: Это также заботится о переполнении меню, гарантируя, что оно «оборачивается» обратно к началу. Помимо доступа к следующему пункту (пунктам) меню с помощью i + 1
и т. Д. Для этого используется оператор модуля (или остатка) %
.
Вот древний алгоритм, который точен и не переполняется, если результат не слишком велик для long long
unsigned long long
choose(unsigned long long n, unsigned long long k) {
if (k > n) {
return 0;
}
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d) {
r *= n--;
r /= d;
}
return r;
}
. Этот алгоритм также есть в книге Кнута «Искусство компьютерного программирования, 3-е издание, том 2: получисловые алгоритмы», я думаю.
ОБНОВЛЕНИЕ: Существует небольшая вероятность того, что алгоритм переполнится в строке:
r *= n--;
для очень большого n. Наивная верхняя граница - sqrt (std :: numeric_limits
, что означает n
меньше примерно 4 000 000 000.
Следующая процедура вычислит n-choose-k, используя рекурсивное определение и запоминание. Процедура чрезвычайно быстрая и точная:
inline unsigned long long n_choose_k(const unsigned long long& n,
const unsigned long long& k)
{
if (n < k) return 0;
if (0 == n) return 0;
if (0 == k) return 1;
if (n == k) return 1;
if (1 == k) return n;
typedef unsigned long long value_type;
value_type* table = new value_type[static_cast<std::size_t>(n * n)];
std::fill_n(table,n * n,0);
class n_choose_k_impl
{
public:
n_choose_k_impl(value_type* table,const value_type& dimension)
: table_(table),
dimension_(dimension)
{}
inline value_type& lookup(const value_type& n, const value_type& k)
{
return table_[dimension_ * n + k];
}
inline value_type compute(const value_type& n, const value_type& k)
{
if ((0 == k) || (k == n))
return 1;
value_type v1 = lookup(n - 1,k - 1);
if (0 == v1)
v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
value_type v2 = lookup(n - 1,k);
if (0 == v2)
v2 = lookup(n - 1,k) = compute(n - 1,k);
return v1 + v2;
}
value_type* table_;
value_type dimension_;
};
value_type result = n_choose_k_impl(table,n).compute(n,k);
delete [] table;
return result;
}
Ну, я должен ответить на свой вопрос. Я читал о треугольнике Паскаля и случайно заметил, что мы можем вычислить количество комбинаций с ним:
#include <iostream>
#include <boost/cstdint.hpp>
boost::uint64_t Combinations(unsigned int n, unsigned int r)
{
if (r > n)
return 0;
/** We can use Pascal's triange to determine the amount
* of combinations. To calculate a single line:
*
* v(r) = (n - r) / r
*
* Since the triangle is symmetrical, we only need to calculate
* until r -column.
*/
boost::uint64_t v = n--;
for (unsigned int i = 2; i < r + 1; ++i, --n)
v = v * n / i;
return v;
}
int main()
{
std::cout << Combinations(52, 5) << std::endl;
}
Используя грязный трюк с длинным двойником, можно получить ту же точность, что и Говард Хиннант (и, возможно, больше):
unsigned long long n_choose_k(int n, int k)
{
long double f = n;
for (int i = 1; i<k+1; i++)
f /= i;
for (int i=1; i<k; i++)
f *= n - i;
unsigned long long f_2 = std::round(f);
return f_2;
}
Идея состоит в том, чтобы сначала разделить на k! а затем умножить на n (n-1) ... (n-k + 1). Аппроксимации через двойное число можно избежать путем инвертирования порядка цикла for.
Помните, что
n! / (п - г)! = n * (n - 1) * .. * (n - r + 1)
, поэтому он намного меньше n !. Итак, решение состоит в том, чтобы оценить n * (n - 1) * ... * (n - r + 1) вместо того, чтобы сначала вычислять n! и затем разделить его.
Конечно, все зависит от относительной величины n и r - если r относительно велико по сравнению с n, то оно все равно не поместится.
Однако сначала упростите формулу. Вы не хотите делать длинное деление.
Если вы хотите быть на 100% уверены, что переполнения не произойдет, пока окончательный результат находится в пределах числового предела, вы можете просуммировать Треугольник Паскаля строка за строкой:
for (int i=0; i<n; i++) {
for (int j=0; j<=i; j++) {
if (j == 0) current_row[j] = 1;
else current_row[j] = prev_row[j] + prev_row[j-1];
}
prev_row = current_row; // assume they are vectors
}
// result is now in current_row[r-1]
Однако , этот алгоритм намного медленнее, чем алгоритм умножения. Так что, возможно, вы могли бы использовать умножение для генерации всех известных вам случаев, которые являются «безопасными», а затем использовать оттуда сложение. (.. или вы можете просто использовать библиотеку BigInt).