我试图按照字典顺序(例如,编号)生成编号为K
的给定整数N
的像样分区。对于N = 5, K = 3
我们得到:按其编号生成整数分区
5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5
,第三个是1 + 1 + 3
。 如何在不生成每个分区(使用C语言,但最重要的是我需要算法)的情况下生成此分区?
会发现在分区最大数量(假设我们可以发现分区d[i][j]
,数其中i
是数量和j
是它的分区的最大整数),则减少原来的号码和电话号码,我们所期待的。所以是的,我试图使用动态编程。仍在研究代码。
这并不在所有的工作:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
FILE *F1, *F2;
main()
{
long long i, j, p, n, k, l, m[102][102];
short c[102];
F1 = fopen("num2part.in", "r");
F2 = fopen ("num2part.out", "w");
n = 0;
fscanf (F1, "%lld %lld", &n, &k);
p = 0;
m[0][0] = 1;
for (i = 0; i <= n; i++)
{
for (j = 1; j <= i; j++)
{
m[i][j] = m[i - j][j] + m[i][j - 1];
}
for (j = i + 1; j <= n; j++)
{
m[i][j] = m[i][i];
}
}
l = n;
p = n;
j = n;
while (k > 0)
{
while (k < m[l][j])
{
if (j == 0)
{
while (l > 0)
{
c[p] = 1;
p--;
l--;
}
break;
}
j--;
}
k -=m[l][j];
c[p] = j + 1;
p--;
l -= c[p + 1];
}
//printing answer here, answer is contained in array from c[p] to c[n]
}
使用动态编程来发现的(N,K)-partitions数目对于n
zch
试图在分区中查找最大数目(假设我们可以找到分区数量'd [i] [j]',其中'i'是数字,'j'是其分区中的最大整数),然后减少原始数量并我们正在寻找的数量,仍然在努力。 – siziyman