英文:
Program does not show correct answers for higher values
问题
#include <stdio.h>
int main() {
// 在此处编写C代码
int n, r, a, b, c, i, fact;
scanf("%d %d", &n, &r);
fact = 1;
for (i = 1; i <= n; i++) {
fact = fact * i;
if (i == r) {
a = fact;
}
if (i == n - r) {
b = fact;
}
}
c = fact / (a * b);
printf("the ncr is %d", c);
return 0;
}
对于类似18C2的值,在在线编译器中编译时不会显示正确答案。
该程序对于小值(如12C5或5C3)显示正确答案。但对于较大的值,答案会显示为错误。例如,对于18C2,显示的答案是3。当我在同一编译器中执行(24 * 23) / 2
时,显示沉淀错误。
英文:
#include <stdio.h>
int main() {
//Write C code here
int n, r, a, b, c, i, fact;
scanf("%d %d", &n, &r);
fact = 1;
for (i = 1; i <= n; i++) {
fact = fact * i;
if (i == r) {
a = fact;
}
if (i == n - r) {
b = fact;
}
}
c = fact / (a * b);
printf("the ncr is %d", c);
return 0;
}
For values like 18C2 etc correct answer is not shown when compiled in an online compiler
The program shows correct answers for small values like 12C5 or 5C3
But for larger values the answer comes as wrong. For 18C2 the answer shown is 3.
When I used the same compiler to do (24 * 23) / 2
it shows sedimentation error.
答案1
得分: 3
这是一个糟糕的计算二项式的方法。18! 和 13! 都大于 2^31-1,因此会导致常规的 int
溢出。实际上,只需计算到 21! 就会导致 uint64_t
溢出。(不,这不是一个标签中所暗示的“编译器错误”。你没有理解数据类型的限制。)
你可以使用 int
类型计算得到更大的二项式,方法是永远不要将 n! 直接相乘。这里有很多项可以相互抵消。这也显示了为什么最好先手动计算一下,这样你可以看清楚发生了什么,而不是盲目地写代码。
例如,18C2 应该根本不是问题。它等于 18!/(16!2!),其中 18!/16! 就是 18 * 17。你应该选择 k 比较小,比如如果你有 18C16,你可以将其转换成等价的 18C2。然后 n!/(n-k)! 会消除至少一半的 n! 项。然后通过使用一些二项式恒等式,你可以在计算过程中消除分子和分母 (k!) 中的项,从而避免溢出和分数结果。
更好的方法,至少对于较小的 n,是可以只使用加法来填充帕斯卡三角形。同时将结果保存在内存中,这样速度会非常快。
以下是结合了帕斯卡三角形和直接计算的代码。它使用快速表查找直到 MAXN
,然后在那之后进行计算,可以返回小于 2^64 的任何二项式(除了 (2^64-1)C1,由于特殊的返回值会被视为溢出):
#include <stdint.h>
#include <limits.h>
// 二进制最大公约数算法。假设 a 和 b 为正数。
uint64_t gcd(uint64_t a, uint64_t b) {
int z = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
b -= a;
uint64_t m = (int64_t)b >> 63;
a += b & m;
b = (b + m) ^ m;
} while (b);
return a << z;
}
// 在溢出时返回 n C k,否则返回(uint64_t)-1。假设 1 < k <= n/2。
static uint64_t binom_calc(uint64_t n, uint64_t k) {
uint64_t c = n & 1 ? n * ((n - 1) >> 1) : (n >> 1) * (n - 1);
for (uint64_t i = 3; i <= k; i++) {
uint64_t m = n - i + 1;
uint64_t g = gcd(m, i);
m /= g;
c /= i / g;
if ((uint64_t)-1 / c < m)
return -1;
c *= m;
}
return c;
}
// MAXN 是表格使用的最大 n 值。特殊的 MAXN 值:
// 967 -- 仅对 k <= 7 使用 binom_calc()
// 1913 -- 仅对 k <= 6 使用 binom_calc()
// 4868 -- 仅对 k <= 5 使用 binom_calc()
// 18580 -- 仅对 k <= 4 使用 binom_calc()
#define MAXN 1913
static uint64_t binom_table[MAXN-3][32] = {0};
// 在溢出时返回 n C k,否则返回(uint64_t)-1。假设 0 < 2*k <= n+1。
static uint64_t binom_recur(uint64_t n, uint64_t k) {
if (n < (k << 1))
k--;
if (k == 1)
return n;
if (binom_table[n - 4][k - 2])
return binom_table[n - 4][k - 2];
uint64_t a = binom_recur(n - 1, k - 1);
uint64_t b = binom_recur(n - 1, k);
a += b;
return binom_table[n - 4][k - 2] = a < b ? (uint64_t)-1 : a;
}
// 返回 n C k,如果 k > n 则返回 0,如果溢出则返回(uint64_t)-1。如果不从主线程调用 binom_fill(),则此函数不是线程安全的。否则,表格将按需填充。
uint64_t binom(uint64_t n, uint64_t k) {
if (k > n)
return 0;
if (k > (n >> 1))
k = n - k;
if (k == 0)
return 1;
if (k == 1)
return n;
return n > MAXN ? binom_calc(n, k) : binom_recur(n, k);
}
// 填充二项式表格。如果你从主线程调用一次,那么 binom() 可以安全地同时从多个线程使用。对于 MAXN = 1913,这只需要大约 140 微秒。
void binom_fill(void) {
for (uint64_t n = MAXN, k = 2; n >= 4; n--)
for (; k <= (n << 1); k++)
if (binom_recur(n, k) + 1 == 0)
break;
}
要进一步发展,你可以突破 64 位限制并使用 bignum 库。
英文:
That is a terrible way to compute a binomial. 18!, as well as 13!, are larger than 2<sup>31</sup>-1, and so overflow the usual int
. In fact, you only need to go to 21! to overflow a uint64_t
. (No, this is not a "compiler error" as suggested in a tag. You are not understanding the limitations of the data types.)
You can compute much, much larger binomials even with just the int
type by never multiplying out n!. There is a lot of cancellation going on. This shows why it is a good idea to do a calculation by hand first, so that you can see what's going on, instead of just jumping in and writing code.
For example 18C2 should not be a problem at all. It is 18!/(16!2!), where 18!/16! is just 18 * 17. You should pick k to be small, e.g. if you had 18C16, you would change that to the equivalent 18C2. Then n!/(n-k)! will throw out at least half of the terms of n!. Then with what's left, and the use of some binomial identities, you can cancel terms in the numerator and denominator (k!) as you go along, avoiding overflows and fractional results.
Even better, at least for smaller n, you could do it with just additions by filling in Pascal's triangle. Along with saving the results in memory, this is super fast.
Here is code that combines Pascal's triangle with direct calculations. This uses fast table lookups up to MAXN
, and calculations after that, with the ability to return any binomial that is less than 2<sup>64</sup> (except for (2<sup>64</sup>-1)C1, which will appear to be an overflow due to the special return value):
#include <stdint.h>
#include <limits.h>
// Binary GCD algorithm. This assumes that a and b are positive.
uint64_t gcd(uint64_t a, uint64_t b) {
int z = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
b -= a;
uint64_t m = (int64_t)b >> 63;
a += b & m;
b = (b + m) ^ m;
} while (b);
return a << z;
}
// Return n C k or (uint64_t)-1 on overflow. This assumes that 1 < k <= n/2.
static uint64_t binom_calc(uint64_t n, uint64_t k) {
uint64_t c = n & 1 ? n * ((n - 1) >> 1) : (n >> 1) * (n - 1);
for (uint64_t i = 3; i <= k; i++) {
uint64_t m = n - i + 1;
uint64_t g = gcd(m, i);
m /= g;
c /= i / g;
if ((uint64_t)-1 / c < m)
return -1;
c *= m;
}
return c;
}
// MAXN is the maximum n for which the table is used. Special MAXN values:
// 967 -- binom_calc() only used for k <= 7
// 1913 -- binom_calc() only used for k <= 6
// 4868 -- binom_calc() only used for k <= 5
// 18580 -- binom_calc() only used for k <= 4
#define MAXN 1913
static uint64_t binom_table[MAXN-3][32] = {0};
// Return n C k or (uint64_t)-1 on overflow. This assumes that 0 < 2*k <= n+1.
static uint64_t binom_recur(uint64_t n, uint64_t k) {
if (n < (k << 1))
k--;
if (k == 1)
return n;
if (binom_table[n - 4][k - 2])
return binom_table[n - 4][k - 2];
uint64_t a = binom_recur(n - 1, k - 1);
uint64_t b = binom_recur(n - 1, k);
a += b;
return binom_table[n - 4][k - 2] = a < b ? (uint64_t)-1 : a;
}
// Return n C k, or 0 if k > n, or (uint64_t)-1 on overflow. This is not
// thread-safe unless and until binom_fill() is called. Otherwise, the table is
// filled in on an as-needed basis.
uint64_t binom(uint64_t n, uint64_t k) {
if (k > n)
return 0;
if (k > (n >> 1))
k = n - k;
if (k == 0)
return 1;
if (k == 1)
return n;
return n > MAXN ? binom_calc(n, k) : binom_recur(n, k);
}
// Fill in the binomial table. If you do this once from the main thread, then
// binom() can safely be used from multiple threads at the same time. This only
// takes about 140 microseconds on an Apple M1 for MAXN = 1913.
void binom_fill(void) {
for (uint64_t n = MAXN, k = 2; n >= 4; n--)
for (; k <= (n << 1); k++)
if (binom_recur(n, k) + 1 == 0)
break;
}
To go further, you can bust through the 64-bit barrier and use the bignum library.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论