我非常不善于理解和尝试解决这个问题，假设我们有 3 个线程，每个线程都有 a、b、c 指令，我需要找到程序可以在顺序一致的架构上执行多少种不同的方式？H 我应该如何解决这个问题？
问问题
25 次
1 回答
0
你有 3 个线程。每个都处理一系列动作a、b和c。让我们为线程使用数字。要理解的关键点：每个线程 1 到 3 ... 必须按顺序处理其操作。变化只会发生，因为线程可以在许多组合中完成它们的工作。我们还假设我们的机器在任何时候都只能服务一个线程——并且动作在线程上下文切换发生之前完成。
你可以有：
1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c
1a, 2a, 1b, 1c, 2b, 2c, 3a, 3b, 3c
1a, 2a, 2b, 1b, 1c, 2c, 3a, 3b, 3c
1a, 2a, 2b, 2c, 1b, 1c, 3a, 3b, 3c
1a, 2a, 2b, 2c, 3a, 1b, 1c, 3b, 3c
1a, 2a, 2b, 2c, 3a, 3b, 1b, 1c, 3c
...
看着它，人们可以想出一种算法来构建一棵产生所有组合的树。您基本上选择了一个候选者，例如“1a”，然后您确定可以执行哪些后续步骤（在本例中为 1b、1c、2a、... 3c）。然后您可以开始构建路径：
1a-1b
1a-2a
...
等等。对于每条路径，您都会记住其上的元素。为了添加另一个元素，您可以查看“剩余”元素。每个剩余的对象定义另一个新路径。重复。
通过这样做，您应该能够定义一个计算所有可能路径的算法。
这将构成一个很好的编码 kata 练习——我的输入应该足以让你继续前进。如果您需要捷径，也许看这里。或者那里。
除此之外：显然，这也可以作为一个纯数学问题来解决：如果您只是将所有元素 1a，... 3c 放入一个列表中，并创建该列表的所有排列，您将得到 9！所以，362880 种可能性。但是当然，这不起作用，因为您的问题应该排除诸如 1b、1a 之类的排列（因为根据您的要求，a、b、c 将始终“按顺序”排列）。
所以（线程数+步数）！为您提供有效路径数量的上限。也许其他人过来并添加了更多数学来计算无效路径的数量。
（顺便说一句：这将是“打印”所有可能路径的另一种方法 - 只需创建 9 个元素的所有排列，并删除那些无效的）
免责声明：只有当我们假设底层机器只有一个“真实”线程时，上述所有内容才有意义。并且该线程执行和上下文切换发生在操作完成之后。如果你放弃这些假设，那么你就可以为：
1: aaaabbbbcccc
2: aaaabbbbcccc
3: aaaabbbbccc
换句话说：如果您考虑真实机器中的潜在路径，事情会变得更加复杂。
于 2017-11-29T10:29:05.070 回答