c - 用 C 为所有可能的排列设计一个算法,包括零

标签 c algorithm combinations permutation

<分区>

我正在尝试用 C 语言设计和编写一种算法,以得出一个表格,列出 5 种不同成分的不同百分比。我需要得到一张看起来像这样的表格:

糖(50%).....盐(20%)....胡椒(10%)....辣椒(10%)....辣椒(10%) 糖(50%).....盐(50%)....胡椒(00%)....辣椒(00%)....辣椒(00%) 糖(00%).....盐(100%)...胡椒(00%)....辣椒(00%)....辣椒(00%) 糖(10%).....盐(00%)....胡椒(90%)....辣椒(00%)....辣椒(00%)

我需要捕获所有可能的排列,并注意 0% 是有效排列,如上所示。所有排列的总和必须始终为 100%。

我意识到以 1% 的粒度列出所有可能的排列将意味着大量的排列,因此我希望能够将一个变量传递给我的函数来定义粒度级别;粒度越高,表条目数越少。

我看过许多与此类似的问题,但我找不到处理以下情况的问题 1) 顺序不重要 2) 项目可以排除(在我的例子中,这意味着item 的值为 0); 3) 这个例子是用 C 写的。

[PS:我通过使用食物简化了事情,但这不是家庭作业......请参阅我的其他帖子。]

那么,我的问题是,我该如何编码呢?事实上,我已经尝试使用递归循环对此进行编码:

int variations[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
char names[][10] = { "sugar", "spice", "pepper", "cayenne", "salt", "" );
int componentCount = 5;

for (int i = 0; i < componentCount; ++i)
   for (int j = 1; j < componentCount; ++j)
     for (int k = 2; k < compoentCount; ++k)
        for (int l = 3; l < componentCount; ++l)
          for (int m = 4; m < componentCount; ++m)
              for (int x = 0; x < componentCount; ++x)
                   printf("%s=%d", names[x], variations[x]);

但这在捕获所有变化方面并没有做我需要做的事情,我没有早点发布这个,因为我认为我需要采取完全不同的方法,因此我的问题是:这怎么可能完成了吗?

最佳答案

你可以用递归来解决这个问题。请记住,每个递归函数都具有以下模式:

  • 我的情况很简单吗?如果是,解决简单的问题。
  • 我的情况更复杂吗?如果是这样,将问题分解为一个或多个更简单的问题。
  • 递归地解决每个更简单的问题。
  • 现在将较简单问题的解决方案组合成较难问题的解决方案。

总是从最简单的问题开始。你最简单的问题是什么?

  • 我有一个项目必须占总数的 x%。

解决方案是:该项目占总数的 x%。

现在假设您有 n 个项目必须占总数的 x%。你怎么做呢?将其分解为更简单的问题:

  • 假设第 1 项占总数的 0%。现在我有 n-1 个项目,占总数的 x%。列出所有这样做的方法。
  • 假设第 1 项占总数的 5%。现在我有 n-1 个项目,占总数的 x-5%。列出所有这样做的方法。
  • ...
  • 假设第 1 项占总数的 x%。现在我有 n-1 个项目,占总数的 0%。列出所有这样做的方法。

大功告成。

现在将其转化为代码。

关于c - 用 C 为所有可能的排列设计一个算法,包括零,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22998532/

相关文章:

algorithm - 使用 2 个数字求和的方法数

c - Unicode代码指向utf8和wctomb

c - c中使用结构的矩阵乘法

c - 如何更快地检查正则表达式列表

java - 如何创建字符串的所有元音组合并将每个组合添加到 ArrayList

python - 在 Python 中按元素总和对组合进行排序

c++ - 重叠的字符串

c - 在用户级线程库中实现join函数

java - 适用于这种特定情况的最佳数据结构和排序算法

c - 在c中用2个未知参数求解方程的最快算法?