У меня есть алгоритм, такой как:
for(int i=1; i<=n; i++)
for(int j=1; j<=2*n; j=j+2)
for(int k=i; k<=j; k++)
instr;
Мне нужно найти формулу, которая будет определять, сколько раз будет выполняться инструкция "instr".
Я написал это. . Но я получаю неверные значения. Например, для n=4 "instr" будет выполнен 43 раза, но я получаю 40 из своей суммы.
Где я накосячил?
Из кода
int count = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=2*n; j=j+2)
for(int k=i; k<=j; k++)
count++;
можно преобразовать его в семантически эквивалентный:
int count = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=i; k<=2*j - 1; k++)
count++;
Если бы кто-то напечатал переменную count
в конце обеих версий кода, ее значения были бы:
| loop 1 | loop 2
________________________________
N = 1 | 1 | 1
N = 2 | 6 | 6
N = 3 | 19 | 19
N = 4 | 43 | 43
N = 5 | 82 | 82
Из второго цикла вы извлекли формулу:
Что имеет смысл на бумаге, однако есть одна загвоздка. Преобразование вашей формулы в код:
public static int third_loop(int n ){
int count = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
count += (2 * j - 1) - i + 1;
return count;
}
и показывая значения переменной count
:
| loop 1 | loop 2 | loop 3
____________________________________
N = 1 | 1 | 1 | 1
N = 2 | 6 | 6 | 6
N = 3 | 19 | 19 | 18
N = 4 | 43 | 43 | 40
N = 5 | 82 | 82 | 75
Значения count
теперь другие, и причина этого в том, что будут итерации, где (2 * j - 1) < i + 1, поэтому формула (2 * j - 1) - i + 1 даст отрицательные результаты, и добавьте эти результаты в переменную count
. Что-то, чего неявно избегали во втором цикле. Если изменить третий цикл на:
public static int fourth_loop(int n ){
int count = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
count += Math.max((2 * j - 1) - i + 1, 0);
return count;
}
можно было бы получить:
| loop 1 | loop 2 | loop 3 | loop 4
__________________________________________
N = 1 | 1 | 1 | 1 | 1
N = 2 | 6 | 6 | 6 | 6
N = 3 | 19 | 19 | 18 | 19
N = 4 | 43 | 43 | 40 | 43
N = 5 | 82 | 82 | 75 | 82
Таким образом, проблема с вашей формулой заключается в том, что она также учитывает отрицательные значения, а ваш код - нет. Поскольку у меня нет математических инструментов, чтобы дать вам точную формулу, я прошу ваших друзей из math.stackexchange сделать это.
Обновлено: Из вознаграждения, которое я предложил, Мэтью Тауэрс получил следующее точное выражение: