|
|||||||||||||||||
| 用Lingo解决组合问题 |
|
|
原著：Jerry McManus 翻译：alphachi [问题] 有5张卡片，从中任取3张，列出所有可能的结果。 [分析] 输入卡片列表并确定最终组合列表的长度 ——〉计算组合的总数并生成组合列表 ——〉输出组合列表 [代码] 由于是有关排列组合的问题，必然会涉及到阶乘的计算。为了方便起见，可以先设计一个阶乘计算程序： on mGetFactorial ( me , num) factorial = 1 repeat with x = num down to 1 factorial = factorial * x end repeat return factorial end 接下来，就可以利用这个阶乘计算程序得到组合的总数： -- 计算阶乘 listFactorial = me .mGetFactorial(pListCount) subsetFactorial = me .mGetFactorial(pSubsetCount) listMinusSubsetFactorial = me .mGetFactorial(pListCount - pSubsetCount) -- 计算组合总数 pTotal = listFactorial / (subsetFactorial * (listMinusSubsetFactorial)) pNumLeft = pTotal 现在，借助一个索引数值，通过循环语句即可生成一个索引列表： on mGetCombination ( me ) -- 检测是否为第一次循环 if pNumLeft = pTotal then -- 是第一次循环，使用当前子列表 pNumLeft = pNumLeft - 1 else -- 不是第一次循环，获取新的子列表 x = pSubsetCount -- 在当前子列表中循环并增值 repeat while pCurrentSubset[ x ] = pListCount - pSubsetCount + x x = x - 1 end repeat pCurrentSubset[ x ] = pCurrentSubset[ x ] + 1 repeat with y = ( x + 1 ) to pSubsetCount pCurrentSubset[ y ] = pCurrentSubset[ x ] + y - x end repeat -- 获取新的子列表 pNumLeft = pNumLeft - 1 end if end 之所以没有直接对实际的卡片列表进行直接操作，是为了让程序拥有更强的适应性。因为只要拥有了索引列表，就可以对任何传入的实际列表进行“组合”操作，而不仅仅限于这个卡片列表。当然，只需再添加一些代码，即可生成实际的结果列表： -- 生成结果列表 combination = [] repeat with x = 1 to pSubsetCount combination. add (pItemList[pCurrentSubset[ x ]]) end repeat 下面的影片便是完成后的“组合生成器”：
这项技巧虽然比较简单，但使用的范围却非常广泛，例如卡片的随机抽取或数列的随机生成。此外，在许多涉及到需要列举组合结果的数学问题中都占有一席之地。 相关附件 |
|
| 上一篇:无 下一篇:Director 对象列表的调用与删除 |
| 大部分文章摘自网上，如有侵犯您的权益请与我们联系，我们会第一时间进行处理，谢谢! | [ 打印文章 ] [ 关闭窗口 ] |