Я выполняю следующее упражнение по программированию: Мой друг изменяет? . Утверждение таково:
Мой друг берет последовательность чисел от 1 до n (где n> 0). В этой последовательности он выбирает два числа, a и b. Он говорит, что произведение a и b должно быть равно сумме всех чисел в последовательности, исключая a и b. Учитывая число n, не могли бы вы сказать мне числа, которые он исключил из последовательности?
Функция принимает параметр: n (n всегда строго больше 0) и возвращает массив или строку (в зависимости от язык) формы:
[(a, b), ...] или [[a, b], ...] или {{a, b}, ...} или или [ {a, b}, ...]
со всеми (a, b), которые являются возможными удаленными числами в последовательности от 1 до n.
[(a, b),. ..] или [[a, b], ...] или {{a, b}, ...} или ... будут отсортированы в порядке возрастания "a".
It бывает, что есть несколько возможных (а, б). Функция возвращает пустой массив (или пустую строку), если никакие возможные числа не найдены, что докажет, что мой друг не сказал правду! (Go: в этом случае вернуть nil).
Примеры:
removeNb (26) должно вернуть [[15, 21], [21, 15]]
Идея была:
Calculate sum of 1..n
For each number a
For each number b
if a*b=sum-(a+b)
add to result
И я написал следующий код:
import java.util.*;
import java.util.stream.*;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
System.out.println("n: "+n);
long sum = LongStream.rangeClosed(1,n).sum();
List<long[]> result = new ArrayList<>();
System.out.println("sum: "+sum);
for(int a = 1; a <= n && a <= sum; a++){
System.out.println("a: "+a);
long prodMax = a*n;
long sumMax = sum-(a+n);
if(prodMax < sumMax){
System.out.println("prodMax: "+prodMax);
System.out.println("sumMax: "+sumMax);
continue;
};
for(int b = 1; b <= n && a*b <= (sum-(a+b)); b++){
if(a==b) continue;
System.out.println("b: "+b);
if(a*b == sum-(a+b)){
result.add(new long[]{a,b});
System.out.println("result: "+Arrays.deepToString(result.toArray()));
}
}
}
System.out.println("result: "+Arrays.deepToString(result.toArray()));
return result;
}
}
Он проходит следующие тесты:
import static org.junit.Assert.*;
import java.util.List;
import java.util.ArrayList;
import org.junit.Test;
public class RemovedNumbersTest {
@Test
public void test12() {
List<long[]> res = new ArrayList<long[]>();
res.add(new long[] {15, 21});
res.add(new long[] {21, 15});
List<long[]> a = RemovedNumbers.removNb(26);
assertArrayEquals(res.get(0), a.get(0));
assertArrayEquals(res.get(1), a.get(1));
}
@Test
public void test14() {
List<long[]> res = new ArrayList<long[]>();
List<long[]> a = RemovedNumbers.removNb(100);
assertTrue(res.size() == a.size());
}
}
Для Пример для test12: трассировка:
n: 26
sum: 351
a: 1
prodMax: 26
sumMax: 324
a: 2
prodMax: 52
sumMax: 323
a: 3
prodMax: 78
sumMax: 322
a: 4
prodMax: 104
sumMax: 321
a: 5
prodMax: 130
sumMax: 320
a: 6
prodMax: 156
sumMax: 319
a: 7
prodMax: 182
sumMax: 318
a: 8
prodMax: 208
sumMax: 317
a: 9
prodMax: 234
sumMax: 316
a: 10
prodMax: 260
sumMax: 315
a: 11
prodMax: 286
sumMax: 314
a: 12
prodMax: 312
sumMax: 313
a: 13
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 14
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
b: 23
b: 24
a: 14
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
a: 15
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
result: [[15, 21]]
a: 16
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 17
b: 18
b: 19
a: 17
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 18
a: 18
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 17
a: 19
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
a: 20
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
a: 21
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
result: [[15, 21], [21, 15]]
a: 22
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
a: 23
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 24
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 25
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
a: 26
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
result: [[15, 21], [21, 15]]
Однако, когда входное значение является большим числом, например n = 1000003, оно истекает (время выполнения больше 16000 мс).
Я также прочитал:
Как мы могли бы улучшить этот алгоритм?