mathe 发表于 2014-11-6 19:10:15

附件中程序对等价的树处理的不够好,这部分浪费的时间比较多,可以改善。
比如开始只有一个点的树,我们把这个点记为0,如果在0点添加五个节点,我们分别记为0.1,0.2,0.3,0.4,0.5,得到的新的6个点的对称关系可以通过{0.1,0.2,0.3,0.4,0.5}五个点的置换表示。
然后如果0.1,0.2,0.3再添加一个点,0.4,0.5各添加两个点,这些点位0.1.1,0.2.1,0.3.1,0.4.1,0.4.2,0.5.1,0.5.2,那么新的对称关系可以通过{0.1,0.2,0.3},{0.4,0.5},{0.4.1,0.4.2},{0.5.1,0.5.2}表示

hujunhua 发表于 2014-11-6 19:34:34

wayne 发表于 2014-11-6 19:36:47

mathe 写代码的功力好深厚,就为了这么一个题目,洋洋洒洒就是700行(代码格式化之后)!

mathe 发表于 2014-11-6 20:57:48

hujunhua的条件没有问题。 我现在好歹也是个职业程序员了。写个代码,算法前面都讨论过了,又不需要注释,不考虑可维护性,自然很快

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
页: 1 2 3 4 [5] 6 7
查看完整版本: 仓库管理员的最优入库方案问题