c - 如何在没有嵌套循环的情况下实现三项式展开。

Question

我正在编写方程式简化程序。在这个程序中想用到二项式和三项式定理。

使用二项式展开:

(x+y)^r

求和(k -> r) x^[r-k] y^[k],

其中 k 为 0，r 为二项式的次数。

我可以这样做:

  for (k=0; k<=r; k++) {
      x_degree=r-k;
      y_degree=k;  
  } 

否则，如果我想实现三项式定理，我应该满足形式约束:

(a+b+c)^n

Sum(n 选择 i, j, k) a^i b^j c^k,

其中 n 是三项式的次数，i+j+k=n。

我想了一会儿，但我想不出比遍历所有可能的组合更好的方法，如下所示:

for (int i=0; i<=n; i++)
    for (int j=0; j<=n; j++)
        for (int k=0; k<=n; k++) {
            if((i+j+k)==n) {
                find_coefficient(i,j,k);
                set_degree_values(i,j,k);
                proceed();
            } 
        } 

所以我的问题是:如何在不遍历所有可能的度数组合的情况下实现三项式展开？

谢谢。

Answer 1

以四次为例，三个变量的幂可以列为

004, 013, 022, 031, 040, 
103, 112, 121, 130, 
202, 211, 220,
301, 310, 
400

逻辑是递减最右边的数字并递增它左边的数字。当后者到达 r 时，您将其左侧的数字递增并重置右侧数字(这是修改后的进位操作)。

这个方案可以通过n 计数器来实现，并推广到多项式定理。系数也可以递增计算，我不会感到惊讶。 (实际上，计数器将模拟嵌套循环。)