如何找到使用 C++ 解决此问题的算法：给定整数 z<=10^100，找到包含数字 z 的帕斯卡三角形的最小行。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
例如，如果 z=6 => 结果在第 4 行。
描述问题的另一种方式：给定整数 z<=10^100，求最小整数 n：存在整数 k 使得 C(k,n) = z。
C(k,n) 是 n 个事物的组合，一次取 k 个，不重复
问问题
345 次
2 回答
4
编辑此解决方案需要对数时间，它是O(Log z). 或者也许O( (Log z)^2 )。
假设您正在寻找给定 z的n,k位置。Binomial(n,k)==z
每行在中间都有最大值，所以从
n=0你开始增加行号，n只要中间值小于给定的数字。实际上，10^100 并没有那么大，所以在第 340 行之前，您会找到n0,k0=n0/2三角形的值大于或等于 的位置z：Binomial(n0,k0)>=z您向左走，即减少列号
k，直到最终找到小于 的值z。如果该行中有匹配的值，那么您现在应该已经找到它了。k不是很大，小于 170，所以这一步不会比这更频繁地执行，也不会出现性能问题。从这里你往下走，增加
n。在这里，您会发现 的值稳步增加Binomial[n,k]。继续 3，直到值大于或等于z，然后转到 2。
编辑：当行号很大时，此步骤 3 可以循环很长时间，因此您可以对with进行二进制搜索n，而不是线性检查每个，然后它只需要时间。nnBinomial(n,k) >= z > Binomial(n-1,k)Log(n)
Python 实现看起来像这样，C++ 类似，但有点麻烦，因为您需要为任意精度整数使用额外的库：
# Calculate (n-k+1)* ... *n
def getnk( n, k ):
a = n
for u in range( n-k+1, n ):
a = a * u
return a
# Find n such that Binomial(n,k) >= z and Binomial(n-1,k) < z
def find_n( z, k, n0 ):
kfactorial = k
for u in range(2, k):
kfactorial *= u
xk = z * kfactorial
nk0 = getnk( n0, k )
n1=n0*2
nk1 = getnk( n1, k )
# duplicate n while the value is too small
while nk1 < xk:
nk0=nk1
n0=n1
n1*=2
nk1 = getnk( n1, k )
# do a binary search
while n1 > n0 + 1:
n2 = (n0+n1) // 2
nk2 = getnk( n2, k )
if nk2 < xk:
n0 = n2
nk0 = nk2
else:
n1 = n2
nk1 = nk2
return n1, nk1 // kfactorial
def find_pos( z ):
n=0
k=0
nk=1
# start by finding a row where the middle value is bigger than z
while nk < z:
# increase n
n = n + 1
nk = nk * n // (n-k)
if nk >= z:
break
# increase both n and k
n = n + 1
k = k + 1
nk = nk * n // k
# check all subsequent rows for a matching value
while nk != z:
if nk > z:
# decrease k
k = k - 1
nk = nk * (k+1) // (n-k)
else:
# increase n
# either linearly
# n = n + 1
# nk = nk * n // (n-k)
# or using binary search:
n, nk = find_n( z, k, n )
return n, k
z = 56476362530291763837811509925185051642180136064700011445902684545741089307844616509330834616
print( find_pos(z) )
它应该打印
(5864079763474581, 6)
于 2014-04-14T12:42:55.783 回答
1
斯特林估计 n! 可用于查找三角形中二项式系数大于或等于给定x的第一行。使用这个估计，我们可以得出下限和上限
然后通过观察，这是扩展 2n 的行中的最大系数：
P(2n, 0), P(2n, 1), P(2n, 2), ..., P(2n, 2n -1), P(2n, 2n)
我们可以找到最大二项式系数大于或等于给定x的第一行。这是x可以在其中查找的第一行，不可能在小于 this 的行中找到x。注意：这可能是正确的提示，在某些情况下会立即给出答案。目前，除了从这一行开始蛮力搜索外，我看不到其他方法。
template <class T>
T binomial_coefficient(unsigned long n, unsigned long k) {
unsigned long i;
T b;
if (0 == k || n == k) {
return 1;
}
if (k > n) {
return 0;
}
if (k > (n - k)) {
k = n - k;
}
if (1 == k) {
return n;
}
b = 1;
for (i = 1; i <= k; ++i) {
b *= (n - (k - i));
if (b < 0) return -1; /* Overflow */
b /= i;
}
return b;
}
斯特林：
double stirling_lower_bound( int n) {
double n_ = n / 2.0;
double res = pow( 2.0, 2 * n_);
res /= sqrt( n_ * M_PI);
return res * exp( ( -1.0) / ( 6 * n_));
}
double stirling_upper_bound( int n) {
double n_ = n / 2.0;
double res = pow( 2.0, 2 * n_) ;
res /= sqrt( n_ * M_PI);
return res * exp( 1.0 / ( 24 * n_));
}
int stirling_estimate( double x) {
int n = 1;
while ( stirling_lower_bound( n) <= x) {
if ( stirling_upper_bound( n) > x) return n;
++n;
}
return n;
}
用法：
long int search_coefficient( unsigned long int &n, unsigned long int x) {
unsigned long int k = n / 2;
long long middle_coefficient = binomial_coefficient<long long>( n, k);
if( middle_coefficient == x) return k;
unsigned long int right = binomial_coefficient<unsigned long>( n, ++k);
while ( x != right) {
while( x < right || x < ( right * ( n + 1) / ( k + 1))) {
right = right * ( n + 1) / ( ++k) - right;
}
if ( right == x) return k;
right = right * ( ++n) / ( ++k);
if( right > x) return -1;
}
return k;
}
/*
*
*/
int main(int argc, char** argv) {
long long x2 = 1365;
unsigned long int n = stirling_estimate( x2);
long int k = search_coefficient( n, x2);
std::cout << "row:" << n <<", column: " << k;
return 0;
}
输出：
行：15，列：11
于 2014-04-14T12:57:06.537 回答