Я работаю над проектом кодирования, и у меня проблема со скоростью программы. Программа принимает вход между 1 и 80, этот вход представляет собой ряд совпадений, и выводит, сколько разных чисел можно сделать с таким количеством совпадений.Efficiency Trouble
Пример: Число 1 может быть образованно с 2 спичечных палочками, а число 2 требует 5 матча палочку
Вот полное приглашение программы: http://i.imgur.com/z93R4Ia.png
приглашение программы
Вот мой код к алгоритму, который я придумал для вычисления всего возможного выхода, он работает достаточно хорошо для нижнего конца входов, хотя он становится крайне неэффективным для больших входов, таких как 80 часов, чтобы вычислить все возможности. Как я могу сократить это время до минимума? Предпочтительно, чтобы он мог выполнить через минуту. Мне сказали, что кэширование - это решение, хотя я не очень-то знаю о кешировании и о том, как его реализовать в этой задаче.
n представляет собой вход, и все Объектом счетчика является отслеживание каждого возможного числа, созданного
public class Lab1 {
/**
* Counts the number of possible different numbers that can be made with n
* number of match sticks.
*
* @param n
* represents the input number of match sticks.
* @param count
* Counter object that keeps track of the number of possible
* numbers that can be made.
* @param scaleValue
* accounts for multiple numbers being made out of the same
* number, n, match sticks.
*/
public static void digitCounter(int n, Counter count, int scaleValue) {
if (n < 2) {
// System.out.println(n + "matchs can create " + count.getCount()
// + " different scaleValuebers.");
} else {
if (count.getCount() == 0) {
// If there are enough match sticks to form it
// accounts for 0 only once
if (n >= 7) {
// counts 0
count.setCount(10);
// counts 1
digitCounter(n - 2, count, 1);
// count 4
digitCounter(n - 4, count, 1);
// counts 6
digitCounter(n - 6, count, 1);
// counts 7
digitCounter(n - 3, count, 1);
// counts 8
digitCounter(n - 7, count, 1);
// counts 2, 3, 5 and 9
digitCounter(n - 5, count, 4);
} else if (n == 6) {
count.setCount((16 * scaleValue));
} else if (n == 5) {
count.setCount((10 * scaleValue));
} else if (n == 4) {
count.setCount((4 * scaleValue));
} else if (n == 3) {
count.setCount((2 * scaleValue));
} else if (n == 2) {
count.setCount((1 * scaleValue));
}
}
// Accounts for every other scaleValueber after 0 is accounted for
// so
// scaleValuebers with leading 0's are not formed
// Ex: 001 is illegal
else {
if (n >= 7) {
count.setCount(count.getCount() + (10 * scaleValue));
digitCounter(n - 6, count, scaleValue);
digitCounter(n - 2, count, scaleValue);
digitCounter(n - 4, count, scaleValue);
digitCounter(n - 6, count, scaleValue);
digitCounter(n - 3, count, scaleValue);
digitCounter(n - 7, count, scaleValue);
digitCounter(n - 5, count, (scaleValue * 4));
} else if (n == 6) {
count.setCount(count.getCount() + (16 * scaleValue));
} else if (n == 5) {
count.setCount(count.getCount() + (10 * scaleValue));
} else if (n == 4) {
count.setCount(count.getCount() + (4 * scaleValue));
} else if (n == 3) {
count.setCount(count.getCount() + (2 * scaleValue));
} else if (n == 2) {
count.setCount(count.getCount() + (1 * scaleValue));
}
}
}
}
public static void main(String[] args) throws IOException {
Counter c = new Counter();
int scale = 1;
int input = Integer.parseInt(args[1]);
digitCounter(input, c, scale);
int output = c.getCount();
System.out.print("With a match stick number of " + input + ", "
+ output + " different numbers can be made");
}
}
«Динамическое программирование» является первым, что приходит на ум, который должен принести вас вниз к мизерной доле секунды даже на 8000, хотя я не могу помочь, но интересно, если есть ярлык даже для этого ... –
, подумав об этом за полчаса, нет очевидного ярлыка. Даже делать это с динамическим программированием сложно смутно, чтобы быть уверенным в его праве. По крайней мере, это третий год программирования в колледже. –
Вы можете оставлять результаты с 0 по 10 соответствий, чтобы мы могли проверить правильность ответов? (Вы уверены, что ваш текущий алгоритм достаточно корректен, чтобы подтвердить наши ответы?) –