hujunhua 发表于 2014-11-7 01:08:34

mathe 发表于 2014-11-7 09:58:25

hujunhua 发表于 2014-11-7 21:44:04

mathe 发表于 2014-11-8 16:10:23

如果仅仅对给定的m,n计数,还是13#的方法会更加有效,但是需要改进。

我们知道总层数为k的树,其中k-1层子树至少有两个。
为此,我们可以通过动态规划的方法计算给定黑白点组合和层数,子树的数目。13#给出了比较有效的计算顺序,只是那里的计算不包含层数,而这里应该再添加一个层数
由于最大层数为${m+n-1}/2$,而不同黑白点数目组合也不超过$2n$,所以只需要维护一个大小不超过$n(m+n-1)$的表格。
而13#方法的另外一个问题是从一个子树变换到另外一个子树时需要遍历那两个方程之一的解,复杂度很高,实际上这一步也可能通过动态规划来做,于是复杂度不会超过$O(mn)$,所以总时间复杂度不会超过$O(m^2n^2)$,而空间复杂为为$O(mn)$

mathe 发表于 2014-11-10 22:29:35

现在上面这个计数算法的c版本实现成功了,原先算法设计中有点bug,花费了不少时间查错。现在版本使用c中int类型,稍大规模就要溢出,还需要进一步完善

mathe 发表于 2014-11-11 08:29:56

2313424535666711782389479101061011235111255112131301131431591415774115161932016174862917181238671819317955192082306520212144505212256237562223148280742324392998972425104636890252627979345026277510654602728202344303228295469566585293014830871802303140330829030313210997241022132333006288624803334823779631721343522623663437463536622630603717836371716967749071437384743631352426238391312905437791263940363990257783343404110107480767171514142281098648349347542437828986221515605434421835027912963086444560978390985918906454617050869915598786246474773550907539264604748133794610004584228548493754194185716399992495010545233702911509534505129650945107763261531515283453838443384019701525323510568710188871958453546629389330022096274415455187095301509548242965255565284664207525664213829565714939085337180746355566575842263974955306727781419585911965880509493710569182059603390282115124238916887776061961243233639785344919176616227272627410957975822215966263774296548488994207799528463642199708932335931334524596564656253051174070076255649721465661778604296633077258895685066667506196780047997923896917090676814414665143909930796270896606869410702798372667574857410545169701170797508510906544798184072370713339337670242423628967220197571729529211771525776690577491774772732720606018355785536462601002047374777106520339207273555977107291747522207317336137056245565774599897576634902356628836149846037826294976771815966923322555431404539780935277785196299117734703809429265200823378791487513156390816446009712843139117980425993902725552870237427186803242808112204428496271557686420160186659378182349783060417046920290384545750318982831002866862462064499218233260708149483842876385156239338702326004686041018984858252893760639746349206675994290957785862368739325497689796702250751657060008687680105921158354015451394217097159564878819533528625270717672663348574979009358889561211317141116295861186945100156880789901612911452645301442839933096962199726090914636923646093660498543598053301410441291921333465253348801831547345542124958219609293383586157123256981968757440598369542228939411037502831208095420817262180170349854359495317689393002319888223077896619573882304495969146521863939247744757005452823121037239969726340746927568355448185930849816902815332979875878125200573260074116449602262928034021989921863471456865669172034171503264826388098599100630134658347465720563607281977639527019590

mathe 发表于 2014-11-11 08:34:10

342494516962522736598491659644961081154011100496012121163901314455408141691905721519666569916225235493217256842402518289304247681932411082398420361406734060214001502876903224415586976572234842088454641624529784607941582557629612454212026625112234664891327676427038784847328729163067814860642978462476518448854308412401109291203233190092547100872568832961357674233956235433102413858378071668164341089538232421663253653511562095071272365202573612258172282095310581683712963194127956059847925381369125077354368683201783914444906583868207754311640152119280310901175482857741160075883302405278553121442168129911736980075848669494317641180778826542834526895144184946676417145532511555986451936184757059151600200964799462025732240124602775300011431472116290556784426283954901176148220911542798884848404779311674492304459063592221187601976234375024011827664515902530418924505485125007283891998147344344561617545226012905738166496617144231134099532704116026984125181956859146572565428094637197481321218100302422506455291618549474849649961190042121748456302574263132655126473755472877951257313629755513631021263963151680333875832491193168525636571132990342912536159336447881145411216634425327128039475603481192284612320232832369870790173701613600772736096464298589254258296620143623721310752384916359353721077964584460463384412505030757335439091581586454363017643969503538822107319721203919530701104036540962028851980649546499553728449765401456642258179536294833489190093408170614490206743563299590218673435359129938922007269423684489133179314593654565864629176802043932816946245378383462440106608595377083561433983770476121731918090731549508857937025975455013971490087855519600675971771744465489939079851472504135535170658565770494962481101648374531907351841438003859042014528602863690928944354928174532958219459594441375137701844176103997598589755476235818122338611774283080481840337834851073765625955612260190136658227021251929736419297212775776387415176356158428225575195115231340852761778592915712922889941363258425966660924628979340512796084637555512748779609371256357760141434731399138062412587945532233636934942414398744992403476314008164001050906199036687415311008374834703101544057231826561426913836681731740092712525599529300161581001083672417349216920378417702664551252272785392787446036846889705308234790244305723281776308609993495943726708570562868360054215072775972555053824503042964267780468672251166918023838862512108721960331277900708982519364877396474892669311480756501953624359297052248585667295988756919332837735401288721827709555372396551218944436056897744787294960755982429870937218063537102956047347968709079213207139698022871679935384135880006134435502640998509181001306874079060315805253941996431870917162793205600613928281532699260213106806880175272780170789670660598756897893846421720011234206654601671753380265834494386543113196335948649885859429066840827061752603911437056974187004967341799588363614046156869479477417821203946280201229556902602125379690251474837189746969417734641306962167612357025475885518041979216602023489720046400180066220602056771782376661557228241498940924580986664889670605768247846844524269490990825442690332999604100392050587511384969394051363517188947692695073023022418

mathe 发表于 2014-11-11 08:39:08

4725143623673411847239624710791061198235121195511314213011416731591519477411622319320172544862918287123867193223179552035982306521398214450522439562375623482148280742452739299897255741046368902662327979345027674751065460287272023443032297825469566585308391483087180231898403308290303295910997241022133102230062886248034108782377963172135115422623663437463612236226306037178371294171696774907143813674743631352426239144213129054377912640151936399025778334341159810107480767171514216792810986483493475431762782898622151560544184721835027912963086451934609783909859189064620231705086991559878624721144773550907539264604822071337946100045842285492302375419418571639999250239910545233702911509534512498296509451077632615315225998345383844338401970153270223510568710188871958454280766293893300220962744155291418709530150954824296525630235284664207525664213829573134149390853371807463555665832474226397495530672778141959336211965880509493710569182060347933902821151242389168877761359896124323363978534491917662371927272627410957975822215966338427742965484889942077995284643967219970893233593133452459656540946253051174070076255649721466422317786042966330772588956850667435450619678004799792389691709068448714414665143909930796270896606946224107027983726675748574105451704759117079750851090654479818407237148983339337670242423628967220197572503995292117715257766905774917747735182272060601835578553646260100204745327777106520339207273555977107291755474222073173361370562455657745998976562363490235662883614984603782629497757741815966923322555431404539780935278592751962991177347038094292652008233796082148751315639081644600971284313911806239425993902725552870237427186803242816398122044284962715576864201601866593782655934978306041704692029038454575031898367221002866862462064499218233260708149484688728763851562393387023260046860410189857054825289376063974634920667599429095778672232368739325497689796702250751657060008773946801059211583540154513942170971595648875671953352862527071767266334857497900935897742561211317141116295861186945100156880790791916129114526453014428399330969621997260918098463692364609366049854359805330141044129282791333465253348801831547345542124958219609384623835861571232569819687574405983695422289486471103750283120809542081726218017034985435958834317689393002319888223077896619573882304496902391465218639392477447570054528231210372399792142634074692756835544818593084981690281533298940775878125200573260074116449602262928034021999602218634714568656691720341715032648263880985

mathe 发表于 2014-11-11 10:24:30

46#同A000055匹配,所以这个问题的解应该和序列A054924关联
我们还可以得出`f(n,n+1)=f(n+1,n^2-2)`,验证了17#hujunhua得出的关系
添加代码到附件:

hujunhua 发表于 2014-11-11 18:27:56

17#楼的缩减公式还可以得到以下推论:
`f(n+1,n^2-3)=f(n+1,2n)`
`f(n+1,n^2-4)=f(n+1,3n)`
......
`f(n+1,n^2-1-k)=f(n+1,kn),(1\le k\le n-2, \gcd(k,n+1)=1)`
页: 1 2 3 4 [5] 6
查看完整版本: 仓库管理员的最优入库方案问题