回文数通项公式

chyanog 发表于 2010-8-24 11:44:34

回文数一般人都不陌生，有关算法也不少。刚才在本论坛搜索，发现大都是关于回文素数的帖子。
我在暑假注意到原来回文数（目前只考虑十进制的）还可以有递归算法的，甚至可以写出通项公式。
由于三位的具有代表性又简单，以此为例：
f := If + 10, f + 101]]
http://zdu6vg.bay.livefilestore.com/y1pIJ26I5Y-DC8_oGhqYGmMJ3gXUOOzGmtejL8y4ZyvLxZPec80bTfVVGgFtYUYYAK01lcVynn9tU8hS1E1HI7q1S-AqcF0fDU8/palindrome.bmp?psid=1
这个式子能否继续化简还不确定。在网上也没有找到相关资料，估计可以归结为求解高阶差分方程，由于非数学背景，这方面我还没有接触过，不知道大家有多少研究。

chyanog 发表于 2010-8-25 21:16:40

真冷清，看来大家觉得这题没意思啦

wayne 发表于 2010-8-26 13:44:04

2# chyanog
那个递归算法只能说仅仅适用于1000以下，四位数及以上就不正确了。

wayne 发表于 2010-8-26 13:47:01

1# chyanog
通项公式是怎么得来的

chyanog 发表于 2010-8-26 19:26:56

谢谢wayne的关注！

chyanog 发表于 2010-8-26 19:32:55

我上面仅以三位为例,下面附上三位到六位的：
f3 :=
If + 10, f3 + 101]]

f4 :=
If + 110, f4 + 1001]]

f5 :=
If[n <= 1, 10001,
If + 100,
If + 1010, f5 + 10001]]]

f6 :=
If[n <= 1, 100001,
If + 1100,
If + 10010, f6 + 100001]]]

chyanog 发表于 2010-8-26 21:00:00

三位回文数：
#include <stdio.h>
#include <math.h>
#define Pi 2*asin(1.0)
double p3(double n)
{
   return (9045 + 1010*n - 5*cos(Pi*n) -
5*(1 + sqrt(5))*(cos((Pi*(2 - 9*n))/5.) + cos((Pi*(2 + n))/5.)) -
5*(-1 + sqrt(5))*(cos((Pi*(1 - 7*n))/5.) +
   cos((Pi*(1 + 3*n))/5.)) -
sqrt(50 - 10*sqrt(5))*(sin((2*Pi*(1 - 2*n))/5.) +
   sin((2*Pi*(1 + 3*n))/5.)) -
sqrt(50 + 10*sqrt(5))*(sin((Pi*(1 - 2*n))/5.) +
   sin((Pi*(1 + 8*n))/5.)))/100. ;
}
int main()
{
   for(int i=1;i<=90;i++)
   printf("%d\t",(int)p3(i));
   return 0;
}
四位回文数：
#include <stdio.h>
#include <math.h>
#define Pi 2*asin(1.0)
doublep4(double n)
{
   return (11*(8595 + 910*n + 45*(1 + sqrt(5))*cos(((2 - 9*n)*Pi)/5.) + 100*cos((4*n*Pi)/5.) + 45*cos(n*Pi) - 55*cos((6*n*Pi)/5.) +
   45*(1 + sqrt(5))*cos(((2 + n)*Pi)/5.) + 45*(-1 + sqrt(5))*cos((Pi - 7*n*Pi)/5.) + 45*(-1 + sqrt(5))*cos((Pi + 3*n*Pi)/5.) -
   25*sqrt(10 - 2*sqrt(5))*sin((4*n*Pi)/5.) + sqrt(50 - 10*sqrt(5))*
   (20*sin((2*(1 - 3*n)*Pi)/5.) - 11*sin((2*(1 - 2*n)*Pi)/5.) + 5*sin((4*n*Pi)/5.)) + 29*sqrt(5*(5 - 2*sqrt(5)))*sin((6*n*Pi)/5.) -
   sqrt(10*(5 + sqrt(5)))*(20*sin((2*(1 - 4*n)*Pi)/5.) + 20*sin((2*(-1 + n)*Pi)/5.) + 20*sin((2*n*Pi)/5.) - 20*sin((8*n*Pi)/5.) +
      20*sin((2*(1 + n)*Pi)/5.) - 20*sin((Pi - 8*n*Pi)/5.) + 11*sin((Pi - 2*n*Pi)/5.) -
      20*(sin((Pi + 2*n*Pi)/5.) + sin((2*(Pi + 4*n*Pi))/5.)) + 11*sin((Pi + 8*n*Pi)/5.))))/100.;
}
int main()
{
   for(int i=1;i<=90;i++)
   printf("%d\t",(int)p4(i));
   return 0;
}

chyanog 发表于 2010-8-26 21:04:36

4# wayne
估计你也能猜出来是用Mathematica算出来的，:loveliness:

wayne 发表于 2010-8-27 11:15:44

8# chyanog
n位回文数本质上就是n/2个数字的自由排列问题，
用递归相对来说还是低效了点。

chyanog 发表于 2010-8-27 13:00:51

9# wayne
数字的自由排列问题，不怎么了解，:Q: 。递归一般都比较低效，那么高效的方法应该是直接构造了吧：譬如
Table
Table
Flatten@Table
Flatten@Table
... ...

页: [1] 2 3

数学研发论坛's Archiver

回文数通项公式