我正在编写一个程序来尝试解决数学问题。我需要生成一个唯一的列表,其中包含所有与另一个数字相加的数字。例如,所有 4 个数字加起来为 5 的唯一组合是:
5 0 0 0
4 1 0 0
3 2 0 0
3 1 1 0
2 2 1 0
2 1 1 1
这在 Perl 中很容易暴力破解,但我正在 C 中工作,并且希望找到一个更优雅的解决方案。
在 perl 中,我将在每列中生成 0-N 数字的所有可能组合,丢弃那些加起来不等于目标数字的数字,然后对每行中的数字进行排序并删除重复的行。
我整个早上都在尝试用 C 语言写这个,但似乎无法想出一个令人满意的解决方案。我需要它来达到最大 N 约为 25。你们有什么想法吗?
这是我一直在尝试的示例(这会产生重复的组合):
// target is the number each row should sum to.
// Don't worry about overflows, I am only using small values for target
void example(int target)
{
int row[4];
for (int a=target; a>=0; a--) {
row[0] = a;
for (int b=target-a; b>=0; b--) {
row[1] = b;
for (int c=target-(a+b); c>=0; c--) {
row[2] = c;
row[3] = target-(a+b+c);
printf ("%2d %2d %2d %2d sum: %d\n", row[0],row[1],row[2],row[3],
row[0]+row[1]+row[2]+row[3]);
}
}
}
}
这被称为分区问题 http://en.wikipedia.org/wiki/Partition_(number_theory)并讨论了方法here http://home.att.net/~numericana/answer/numbers.htm#partitions, here http://www.site.uottawa.ca/~ivan/F49-int-part.pdf and here http://arxiv.org/PS_cache/arxiv/pdf/0909/0909.2331v1.pdf.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)