给两个数列，求通项公式

wayne

Mathematica有解多维递推公式的，但是是针对一个方程的。而不是方程组。

plp626

11# wayne 我忽视了一点：公务员考试那种，默认通项中的系数都是整数形式的， 所以产生简单的多个通项的可能性很小。。 ----------------------- 拉格朗日插值是在实数域范围内进行， 有没有在整数范围内进行插值的技术....？？ 或者资料可供参考。。。？ 这方面资料很少，但是运用极多， 构造一个好的hash函数大量用到这方面技术。。

wayne

12# plp626 如果点是整数，那么，拉格朗日插值出来的公式的系数是 有理数

plp626

没错，只是随着点的增加， 分母可能非常大， 早已超过了32位； 现实中拉格朗日插值不怎么会超过4次的；

plp626

比如，给定一组数列(1，2，3，。。。12)->(31, 28, 31,30,31,30 31, 31, 30 ,31 , 30 , 31 ) 给个hash映射， 使用的运算量最少（仅使用C提供的运算符） 换做(1，2，3，。。。12)->(31, 29, 31,30,31,30 31, 31, 30 ,31 , 30 , 31 ) 又是怎样的。。。 大家知道是月份的。。。，，我就不多解释了。。。

KeyTo9_Fans

第$1$个数列终于找到一个简单的程序生成它了：

1. #include<cstdio>
   
2. 
   
3. const int n=51;
   
4. unsigned long long a[n],b[n],c[n],d[n];
   
5. int i,j;
   
6. 
   
7. int main()
   
8. {
   
9.         b[0]=1;
   
10.         b[1]=1;
    
11.         b[2]=1;
    
12.         b[3]=1;
    
13.         b[4]=2;
    
14.         c[0]=1;
    
15.         c[1]=1;
    
16.         c[2]=1;
    
17.         c[3]=1;
    
18.         c[4]=2;
    
19.         d[4]=1;
    
20.         for(i=5;i<n;i++)
    
21.         {
    
22.                 c[i]=c[i-1];
    
23.                 for(j=2;j<i-1;j++)
    
24.                         c[i]+=b[j-2]*c[i-j];
    
25.                 d[i]=d[i-1]+c[i];
    
26.                 b[i]=1;
    
27.                 for(j=0;j<i-3;j++)
    
28.                         b[i]+=b[j]*d[i-j];
    
29.         }
    
30.         for(i=1;i<n-3;i++)
    
31.         {
    
32.                 for(j=0;j<i;j++)
    
33.                         a[i]+=b[j]*(c[i-j+3]-c[i-j+2]);
    
34.                 printf("%2d:%21llu\n",i,a[i]);
    
35.         }
    
36.         return 0;
    
37. }

复制代码

该程序只用了$4$个一维数组：$a[]$、$b[]$、$c[]$、$d[]$，

以及$2$重循环：$i$、$j$。

其中数列$b$、$c$、$d$互相递推，$a$是根据$b$、$c$推出来的，

如下图所示：

$a\Leftarrow b\Leftrightarrow c\Leftrightarrow d$。

KeyTo9_Fans

根据上面的程序，第$1$个数列的递推式是： $a(n)=\sum_{i=0}^{n-1}b(i)*(c(n-i+3)-c(n-i+2))$ 当$n\leq 4$时，$b$、$c$、$d$的初值为： $b(0)=b(1)=b(2)=b(3)=c(0)=c(1)=c(2)=c(3)=1$ $b(4)=c(4)=2$ $d(0)=d(1)=d(2)=d(3)=0$ $d(4)=1$ 当$n>4$时，$b$、$c$、$d$的递推式为： $b(n)=1+\sum_{i=0}^{n-4}b(i)*d(n-i)$ $c(n)=c(n-1)+\sum_{i=2}^{n-2}b(i-2)*c(n-i)$ $d(n)=d(n-1)+c(n)$ 这下全是$1$维的数列了，如何求$a$的通项公式呢？

dianyancao

不知道用Mathematica怎么求解 下面代码报错,不允许方程组中的Sum 貌似数列和卷积的计算有关，能不能对数列做傅立叶变换来计算通项呢

1. RSolve[{b[n] == 1 + Sum[b[i]*d[n - i], {i, 0, n - 4}],
2. c[n] == c[n - 1] + Sum[b[i - 2]*c[n - i], {i, 2, n - 2}],
3. d[n] == d[n - 1] + c[n],
4. b[0] == 1,
5. b[1] == 1,
6. b[2] == 1,
7. b[3] == 1,
8. c[0] == 1,
9. c[1] == 1,
10. c[2] == 1,
11. c[3] == 1,
12. b[4] == 3,
13. c[4] == 3,
14. d[0] == 0,
15. d[1] == 0,
16. d[2] == 0,
17. d[3] == 0,
18. d[4] == 1
19. },
20. {b[n], c[n], d[n]}, n]

复制代码

错误提示： RSolve::piarg: All arguments in position 1 of b[n] should be either of the form + integer or q^integer . Mixtures of these forms are not allowed.

wayne

17# KeyTo9_Fans 还是很复杂，看的眼花缭乱的

云梦

不知道这两组数列有何意义、用途？原出处？ 类似的数列无穷无尽,不会只是数字游戏吧。