Что не так с этим циклом triple for, который выражает тройное суммирование?

#javascript #for-loop

Вопрос:

В Руководстве по разработке алгоритмов, Глава 2, Упражнение 4, приведен следующий псевдокод

 function conundrum(n)
   r := 0
   for i := 1 to n do
      for j := i   1 to n do
         for k := i   j − 1 to n do
            r := r   1
   return(r)

Это можно выразить следующим тройным суммированием.

Замкнутая форма этой тройной суммы равна (1/2)(n-1)(n).

Мой код выглядит следующим образом. Для n > 3 мой тройной вложенный цикл for возвращает неверный результат, но я не могу понять, почему.>

 const conundrum = n => {
    let r = 0;
    for (let i = 1; i <= n; i  ) {
        for (let j = i 1; j <= n; j  ) {
            for (let k = i j-1; k <= n; k  ) {
                r  ;
            }
        }
    }
    return r;
}

const conundrumClosedForm = n => {
    return (1/2)*(n-1)*n;
}
console.log(conundrum(3) === conundrumClosedForm(3));
console.log(conundrum(4) === conundrumClosedForm(4));
console.log(conundrum(5) === conundrumClosedForm(5));

Вот ответ, который я читаю из chegg.com

Вот сам вопрос

1. Это неправильное уравнение замкнутой формы.

2. Это формула для суммы 1..n, а не суммы с тройной вложенностью.

3. @Barmar это ответ, который дает книга для уравнения замкнутой формы, и это то, что дает мне вольфрам альфа wolframalpha.com/input/…

4. также формула для 1..n равна n(n 1)/2

5. Это означает, что ваша закрытая форма представляет собой сумму 1..(n-1).

Ответ №1:

Похоже, вы смотрите не на те статьи, или ваше вольфрамальфа-фу сегодня не в настроении.

Следующий JavaScript показывает, что генерируемая последовательность соответствует последовательности, показанной на A173196, в которой указано, что n-й элемент задается a(n) = (4*n^3 6*n^2 - 4*n - 3 3*(-1)^n)/48 :

 function S(n) {
    let sum = 0
    for (let i = 1; i <= n; i  ) {
            for (let j = i 1; j <= n; j  ) {
                for (let k = i j-1; k <= n; k  ) {
                    sum  ;
                }
            }
        }

    return sum

}

function D(n) {
    return (4 * n * n * n   6 * n * n - 4 * n - 3   3 * Math.pow(-1, n)) / 48
}

for (let q = 0; q <= 10; q  ) {
    console.log(q   " "   S(q)   " "   D(q))
}

Ответ №2:

Почему вы уверены, что (1/2)(n-1)(n) правильно?

Давайте проверим суммы для n = 4:

 (1/2)(4-1)4=(1/2)*3*4=6

Давайте проверим петли:

итерация 1:

i = 1, j = 2, k = 2 — это составит r = 4

итерация 2:

i = 2, j = 3, k = 4 — это составит r = 16 > 6

Таким образом, после второй итерации наши суммы будут больше, чем (1/2)*(n-1)*n.