构造变量嵌套循环的好方法是什么?
-
20-08-2019 - |
题
假设您正在使用具有可变长度数组的语言(例如和 A[i]
对全部 i
在 1..A.length
)并且必须编写一个例程 n
(n : 1..8
) 长度可变的数组中的项目的可变长度数组 n
, ,并且需要调用每个可能长度的过程 n
项目数组,其中第一个是从第一个数组中选择的,第二个是从第二个数组中选择的,依此类推。
如果您想要具体的东西可视化,想象一下您的例程必须获取如下数据:
[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]
并进行以下过程调用(以任何顺序):
try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
:
try_on ['derby','bolo',...'slippers']
这有时被称为中文菜单问题,并且需要修复 n
可以非常简单地编码(例如为了 n
= 3,伪代码)
procedure register_combination( items : array [1..3] of vararray of An_item)
for each i1 from items[1]
for each i2 from items[2]
for each i3 from items[3]
register( [ii,i2,i3] )
但如果 n
可以有所不同,给出如下签名:
procedure register_combination( items : vararray of vararray of An_item)
编写的代码包含一个丑陋的 case 语句,我用一个更简单的解决方案替换了它。但我不确定这是重构它的最佳(而且肯定不是唯一)方法。
你会怎么做?聪明和令人惊讶是好的,但清晰和可维护性更好——我只是通过这个代码,不想被回调。简洁、清晰 和 聪明将是理想的。
编辑:在其他人有机会做出回应后,我将在今天晚些时候发布我的解决方案。
预告片:我试图推销一种递归解决方案,但他们不肯接受,所以我不得不坚持在 HLL 中编写 Fortran。
我的答案发布在下面。
解决方案 3
因为他们反对递归(不要问),而我反对混乱的 case 语句(事实证明,这些语句隐藏了 一个错误)我这样做了:
procedure register_combination( items : vararray of vararray of An_item)
possible_combinations = 1
for each item_list in items
possible_combinations = possible_combinations * item_list.length
for i from 0 to possible_combinations-1
index = i
this_combination = []
for each item_list in items
item_from_this_list = index mod item_list.length
this_combination << item_list[item_from_this_list]
index = index div item_list.length
register_combination(this_combination)
基本上,我计算出有多少种组合,为每个组合分配一个数字,然后循环生成相应的组合的数字。我怀疑这不是一个新技巧,但却是一个值得了解的技巧。
它更短,适用于列表长度的任何实际组合(如果有超过 2^60 的组合,则会出现其他问题),不是递归的,并且没有 错误.
其他提示
无论是递归算法
procedure register_combination( items )
register_combination2( [], items [1:] )
procedure register_combination2( head, items)
if items == []
print head
else
for i in items[0]
register_combination2( head ++ i, items [1:] )
或具有优化了尾巴的呼叫,使用阵列的索引,并且递增的最后一个索引,直到它到达相应的阵列的长度,然后进行增量向上相同。
递归。
或者,更好的是,尝试使用堆状结构和while语句,以消除递归。
有关你的问题,你说(调用带有可变参数的函数),这完全取决于你的编码的编程语言;其中许多允许用于传递变量参数。