我正在尝试编写一个程序,该程序将多个数字和一个基数作为参数,并通过按升序排列非零数字的数字向上计数.例如,在带有3位数的基数4中,它应该打印:
000 001 002 003 010 011 012 013 020 022 023 030 033 100 101 102 103 110 111 112 113 120 122 123 130 133 200 202 203 220 222 223 230 233 300 303 330 333
在4位数的基数3中应该打印:
0000 0001 0002 0010 0011 0012 0020 0022 0100 0101 0102 0110 0111 0112 0120 0122 0200 0202 0220 0222 1000 1001 1002 1010 1011 1012 1020 1022 1100 1101 1102 1110 1111 1112 1120 1122 1200 1202 1220 1222 2000 2002 2020 2022 2200 2202 2220 2222
我已成功完成此操作,但我的算法似乎不必要地复杂和耗时(时间对我的应用程序非常重要).有没有办法让它更快,或者如果速度无法提高就简化它？
这是程序:
public static void count(int base, int size)
{
int[] array = new int[size];
print(array); // private print method prints out the array
int index = 0;
while (index < array.length)
{
if (array[index] < base - 1)
{
// check whether we need to increase array[index] by extra to maintain the order
if (array[index] == 0)
{
int i;
// search for the next nonzero digit
// this search seems to take unnecessary time; is there a faster alternative?
for (i = index + 1; i < array.length && array[i] == 0; i++);
// check whether there was, in fact, some later nonzero digit
if (i < array.length) array[index] = array[i];
else array[index] = 1;
}
else array[index]++;
print(array);
index = 0;
}
// carry over to the next digit
else array[index++] = 0;
}
}
迟到了这个更快的答案：
Base 8
Size 20 digits
Current solution: 79 seconds (76~82)
Solution below: 23 seconds (22~24)
Possible numbers: 12245598208
没有印刷品。原则：
规则“一个数字后面可以跟一个 0 或一个数字 >= 前面的数字”对于（有效）数字组也有效：“一个数字组后面可以跟一组零，或者一组较小的数字 > = 前面组中的任何前面的组”。处理是在组级别而不是数字级别完成的。
给定 T 总大小和每组中 N 个较小的位数 (T % N == 0)，通过计算所有可能的 N 个数字组，然后可以将它们组装在一起（每个解决方案 T / N 组）。
预先计算小块（部分）的示例代码
static ArrayList<int[]> parts = new ArrayList<int[]>();
static ArrayList<ArrayList<Integer>> atleast = new ArrayList<ArrayList<Integer>>();
static ArrayList<Integer> maxi = new ArrayList<Integer>();
static int stick[];
static int base;
static long num = 0;
public static void makeParts(int min, int ptr)
{
int me = 0;
do {
array[ptr] = me;
if (ptr > 0) makeParts(Math.max(me,min), ptr-1);
else {
// add part
int[] newa = new int [array.length];
int i,mi,ma,last=array.length-1;
for (i=0 ; i<array.length ; i++) newa[i] = array[i];
parts.add(newa);
// maxi
for (i=0 ; i<=last && newa[i]==0 ; i++) /* */;
maxi.add(ma = i<=last ? newa[i] : 0);
// mini
for (i=last ; i>=0 && newa[i]==0 ; i--) /* */;
mi = i>=0 ? newa[i] : 0;
// add to atleast lists
int pi = parts.size() - 1;
ArrayList<Integer> l;
int imi = mi == 0 ? base-1 : mi;
for (i=0 ; i<=imi ; i++) {
if (i < atleast.size()) l = atleast.get(i);
else {
l = new ArrayList<Integer>();
atleast.add(i, l);
}
l.add(pi);
}
}
me = me == 0 ? (min > 0 ? min : 1) : me+1;
} while (me < base);
}
粘贴“零件”
public static void stickParts(int minv, int ptr)
{
// "atleast" gives indexes in "parts" of groups which min digit
// is at least "minv" (or only zeroes)
for (int pi: atleast.get(minv)) {
stick[ptr] = pi;
if (ptr > 0) {
stickParts(Math.max(minv,maxi.get(pi)), ptr-1);
}
else {
// count solutions
// the number is made of "parts" from indexes
// stored in "stick"
num++;
}
}
}
在“main”中调用它
base = 8;
int leng = 20;
int pleng = 4;
array = new int [pleng];
makeParts(0,array.length-1);
num = 0;
stick = new int [leng / pleng];
stickParts(0, (leng/pleng) - 1);
out.print(String.format("Got %d numbers\n", num));
例如，如果 T（总大小）是质数，则必须计算另一个特定组，例如对于大小 17，我们可以有 3 组（5 位数字）+ 一组两位数字。