小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？

mathematica

aimisiyou 发表于 2017-5-1 11:27
\(f(m)=f(m-1)+f(m-2)+f(m-3),(m>=4) 其中f(1)=1,f(2)=2,f(3)=4,f(4)=7……\)

土法炼钢,好办法,对于小学生容易明白

kastin

mathematica 发表于 2017-5-2 13:23
当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!

矩阵的幂本身计算就是根据相似矩阵（矩阵特征值）来计算的，也就是那些特征方程方程的根的幂的线性组合，本质上还是通项公式，只是没显式写出来而已。

wayne

kastin 发表于 2017-5-2 15:04
矩阵的幂本身计算就是根据相似矩阵（矩阵特征值）来计算的，也就是那些特征方程方程的根的幂的线性组合， ...

我自己简单写了一个 二分法求幂的函数。

1. Pow[a_,b_]:=Module[{x=a,y=b},Sow[b];If[b==0,1,If[Mod[b,2]==0,Pow[a,b/2]^2,Pow[a,(b-1)/2]^2*a]]]

复制代码

该函数 每调用一次就会记录当前所计算的幂的指数值。通过记录的一连串值，你可以跟踪到 计算一个较大的幂的时候 实际上是经过了多少次 函数调用。

运行

1. Reap[Pow[2,200000]]

复制代码

  

同样的，矩阵的幂运算也是这个道理， 也就是说，幂运算的复杂度是$O(lg(n))$

kastin

@mathe
除了一些内部纯粹是数值算法编写的函数其结果是数值的，其他MMA的函数带入的如果不是浮点数，结果都是符号结果（具体的数认为是无穷精度的，而不是浮点数，类似PI这种也一样认为是符号）。

比较一下如下程序所用时间

1. RecurrenceTable[{a[n]==a[n-1]+a[n-2]+a[n-3],a[1]==1,a[2]==2,a[3]==4},a,{n,1,5000}];//Timing
   
2. RecurrenceTable[{a[n]==a[n-1]+a[n-2]+a[n-3],a[1]==1.,a[2]==2.,a[3]==4.},a,{n,1,5000}];//Timing

复制代码

第一行时间比第二行长，尤其当5000变得更大时更为显著。因为第一行代码是符号计算结果，第二行是数值计算结果（因为初值后面给的是浮点整数，这才是正宗的数值计算，得到的结果就是数值结果）。

mathematica

http://bbs.emath.ac.cn/forum.php ... 555&fromuid=865
http://bbs.emath.ac.cn/forum.php ... 462&fromuid=865
@kastin 这个帖子看看有好处

kastin

mathematica 发表于 2017-5-3 13:30
http://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=2555&fromuid=865
http://bbs.emath.ac.cn/forum.p ...

这个东西我知道，我在2014年特地写过Matlab版的很多数论函数（这些都是MMA有但Matlab没有的）。例如，利用Montgomery快速幂模算法来实现模幂运算

1. function x=powermod(n,p,m)
   
2. % Montgomery快速幂模算法 x = n^p mod m
   
3. if p==0
   
4.     x=1;
   
5.     return;
   
6. end
   
7. r = mod(n,m);  
   
8. tmp = 1;
   
9. while p>1
   
10.     if rem(p,2)==1,tmp = mod(tmp*r,m); end
    
11.     r = mod(r*r,m);
    
12.     p =bitshift(p,-1);
    
13. end
    
14. x=mod(r*tmp,m);

复制代码

问题是MMA内部计算表达式用的不一定都是数值算法，不信你看

1. MatrixPower[{{1, 2}, {2, 3}}, 10^8]; // Timing (* 时间非常长 *)
   
2. MatrixPower[{{1., 2.}, {2., 3.}}, 10^8]; // Timing （* 纯数值算法计算，时间很短 *）

复制代码

要注意，Timing[expr] 仅包括在计算 expr 时花费的时间，不包括在结果的格式化或输出上的时间.。为了确保这一点，上面用分号省去了结果输出。

上面第二行后面加小数点表示数字是浮点整数，第一行表示符号整数。二者数值上是一样的，但是内部计算过程就不一样。

mathe

整数大数运算自然比浮点运算慢很多

wayne

kastin 发表于 2017-5-3 14:02
这个东西我知道，我在2014年特地写过Matlab版的很多数论函数（这些都是MMA有但Matlab没有的）。例如，利 ...

嗯,是的. 这个在Mathematica里面应该是做了算法自动切换的. 根据表达式确定 计算域, 进而选择不同的算法.


第一个是 任意精度(大数)运算.,第二个是 浮点运算.   第二个应该是有精度损失的,越大越不准.

但两个算法应该都用了二分法,不矛盾.  只是第一个算法的参与运算的存储结构是 高精度整数,  第二个参与运算的存储类型是 浮点数,

TSC999

【数学中国】网站 elim 推出的通项公式：



用上面这个通项公式算出的结果，对于所有的自然数进行计算，结果都是接近真实值（整数）的实数，所以取其最接近的那个整数的值，即得到精确的真实值，没有任何误差！

请问，对于本问题，在理论上是否存在某个通项公式，对于任何自然数 n ， 通项公式的计算结果都是一个精确的整数？ 就像斐波那契数列的通项公式一样，虽然公式中含有根式，但是展开后却是个没有任何误差的整数。

mathematica

TSC999 发表于 2017-5-12 09:09
【数学中国】网站 elim 推出的通项公式：

这个公式我在10楼提高过了呀

1. ToRadicals[
   
2. Root[-1 - #1 - #1^2 + #1^3 &, 1]^
   
3.    n Root[-1 + 12 #1 - 44 #1^2 + 44 #1^3 &, 1]]

复制代码

\[\frac{1}{44} \left(2 \sqrt[3]{11 \left(3 \sqrt{33}+77\right)}+\sqrt[3]{6776-264 \sqrt{33}}+44\right) 3^{-n-1} \left(\sqrt[3]{3 \sqrt{33}+19}+\sqrt[3]{19-3 \sqrt{33}}+1\right)^n\]