给两个数列，求通项公式

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
还是很复杂，看的眼花缭乱的

云梦

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