找回密码
 欢迎注册
楼主: medie2005

[求助] 一个计数问题

[复制链接]
发表于 2008-5-12 19:56:27 | 显示全部楼层
$O(n^3)$次乘法的复杂度,数值计算还是简单的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-12 20:02:34 | 显示全部楼层
题目要求公式,这个可以用生成函数来做,但是,不一定可以解出来.
呵呵,生成函数我不太会.谁要是会的话,做做看能不能解出来.如果解不出,求个渐进解也可以.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-12 21:16:35 | 显示全部楼层
先给个程序,计算第到199项,用HugeCalc:
  1. #if 1
  2.     #define _Test_HI
  3.     #define integer CHugeInt
  4. #else
  5.     #define _Test_HX
  6.     #define integer CHugeIntX
  7. #endif

  8. #define MAX_N  200
  9. integer a[MAX_N];

  10. int main(int argc, char* argv[])
  11. {
  12.     int i,j;
  13.     int k;
  14.     a[2]=1;
  15.     a[3]=1;
  16.     a[4]=3;
  17.     printf("s[3]=1\ns[4]=3\n");
  18.     for(i=5;i<MAX_N;i++){
  19.         integer s(0);
  20.         for(j=2;j<=i-1;j++){
  21.             s+=a[j]*a[i+1-j];
  22.         }
  23.         for(j=3;j<=i-3;j++){
  24.             s+=2*a[j]*a[i-j];
  25.         }
  26.         for(j=2;j<=i-2;j++){
  27.             s+=a[j]*a[i-j];
  28.         }
  29.         for(j=3;j<=i-4;j++){
  30.             for(k=3;j+k<=i-1;k++){
  31.                 s+=a[k]*a[j]*a[i+2-j-k];
  32.             }
  33.         }
  34.         s+=a[i-2];
  35.         a[i]=s;
  36.         printf("f[%d]=%s\n",i,s.GetStrA(FS_NORMAL));
  37.     }

  38.     return 0;
  39. }
复制代码
...
f[197]=11098388607679049922784856861174712980445135599410805814343936736168586799658634862065119439605655074298721447133533462171951086295291460040
f[198]=59475002686299682112461821904032700964129061579974910593128350973093786015287678376730106305411105851387244504428968884408342547739488696840
f[199]=318732125980056493100949536723645898194002586243433747563670398525797268090081459278049422828315128412975229310568707272894999874690598185840
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-12 21:22:05 | 显示全部楼层
原帖由 medie2005 于 2008-5-12 20:02 发表
题目要求公式,这个可以用生成函数来做,但是,不一定可以解出来.
呵呵,生成函数我不太会.谁要是会的话,做做看能不能解出来.如果解不出,求个渐进解也可以.

生成函数前面的链接里面有,有了这个结果,验证一下是很简单的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-12 22:19:39 | 显示全部楼层
f[999]=231266893393026464995178230974940141719885668328008586021281799022066498502376256035657167205644776336603283727663662064557277595133908791690550554899156279948682461229493762192868136335830880275690304074310930012430103756390842890446202610175363631665621603026390278350908567042095135944749163145184739094845402956510183027756539036228578215413170479931074942246216459521135241357435058821196260239957324489109358564841270112799596585299696048223690581318771252786477638996500389699284169609254935863872653096748740665135612005485931627323893684152924782424098776736795217269179990844888746324985616453257321857108114429304156567254086094608174150783540695708400905151396317061672596369752794679046299855034116506765626955200
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-13 08:24:03 | 显示全部楼层
zgg__给定的链接里面有个公式计算很好用:
$5n(n+1) * a(n) = 11n(2n-1) * a(n-1) + 3(3n-2)(3n-4) * a(n-2)$
其中$a(n)$表示n+2边形的划分数目
用这个可以比较快速的计算比如:
f[2000]=1090602909089746111452104751154266485030146921711692771816176083878832474715609893383166693863218771066630553737202122470242937794758640406495004220350860926534452318037389226696604405548578300761713002768555803533600784623097553107142903334081304341697106538947184244115776961753412805577426844543190681119050427288677202255672849495111046581297958157824122279162723042261650136121571956358198924502343324719451312110134500502172201913562722817640375622604514902606497097316158635709815186977446555093809702430605027277643328886576562636392331957086949011065720685302156965766125890689011709279256490640865482972551031789762377927870778907174912007316248904523055222368326366395025722520606677046900919857113357161963718006503948666486374378885230529616849762686631980137265765928912298825824542942910253574643093995403756857469333768093909958970880659560073249777613241210185452494206659231660395372705153630998226970896845576101674432825443981055196279705713168155022528777938793043561111655291910784157131277724943038104627889142138597517797894587523019090587695226358242113256386084413438901776129239634706672017247398861514986881781891592964907257615153604736340012803898537332346643407277068768989466233748340816015275799135228944056186922189385339541523411412703302381149525395998324500161915438547082932777945344346215397201507635690814837925851956283096597174234960387144153436981963995618828717030857766210307308986518239850453260129942590814752000
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-13 08:46:45 | 显示全部楼层
这个问题原本是在 CSDN 上提出的,但尚未得到有价值的回复;
转到本坛后,很快就从公式推导、算法分析到程序设计一条龙地全面完成,
体现了本论坛的专业。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-13 08:56:55 | 显示全部楼层
呵呵,mathe给出的方法对计算来说确实很方便.
我现在的疑问是是否存在精确表示n边形的划分数目的公式(而不是递推式)?
这个可以解生成函数来求,但是,我不太会生成函数,所以,还请mathe看看能不能解出来.
如果解不出来,求一个渐进公式也可以.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-13 09:04:40 | 显示全部楼层
生成函数可以设
$F(x)=x^2+f(3)x^3+...+f(n)x^n+...$
根据前面我给出的递推式可以得出:
$F(x) = {F(x)^2}/x + 2 (F(x)-x^2)^2 + F(x)^2 + {(F(x)-x^2)^3}/{x^2}$
所以
$x F^2 + 3x^2 F^2-4x^4 F + 2x^4 + F^3 - 3x^2F^2+3x^4F-x^6 -x^2F=0$
或者$F(x)^3 + xF(x)^2 -x^2(x^2+1)F(x) +x^4(2-x^2)=0$
不过生成函数我不觉得有很大的意义
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-13 12:54:16 | 显示全部楼层
zgg的链接不是很清楚了吗?
隐式的递推mathe已经应用过
显示的如:
$a(n)=sum_{k=0}^{[n/2]}1/(n+1)*C_{2*n-k}^{n+k}*C_{n+k}^k$
medie2005还有啥不明白呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 20:44 , Processed in 0.050585 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表