Итак, мне дан массив = [ 1 2 3 8 9 4 7 6 5 ], который представляет собой спиральный обход квадратной матрицы размера n x n. Что мне нужно было сделать, так это вычислить сумму первичных и вторичных диагоналей и распечатать ее. Мне удалось преобразовать этот одномерный массив в двумерный массив размером n*n и вычислить сумму обеих диагоналей следующим образом:
p.s.: массив примерно такой [[1, 2, 3], [6, 5, 8], [7, 4, 9]]
function spDiag(n,arr){
let mat = [];
let primary = 0, secondary = 0;
while(arr.length) mat.push(arr.splice(0, n));
for(let i = 0; i < n; i++){
for(let j = 0; j < n; j++){
if (i === j) primary += mat[i][j];
if ((i + j) === (n-1)) secondary += mat[i][j];
}
}
console.info(primary + secondary)
console.info(JSON.stringify(mat));
}
spDiag(3, [1,2,3,8,9,4,7,6,5])
@jabaa Это обобщенная формула? Я так не думаю, потому что для спиральной матрицы размера 4 x 4 это не выдерживает критики. Рассмотрим этот массив: [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
Сначала вы добавляете 4 раза n-1
. Затем вы добавляете 4 раза n-2
. Потом... Да можно просто обобщить.
Не могли бы вы уточнить немного больше? я не понял
Возьмите лист бумаги и начертите квадрат размером 3х3, обведите его по спирали и подсчитайте шаги. Вы пройдете 4 раза по 2 шага и один раз по 1 шагу. Попробуйте это с квадратом размером 4x4. Вы пройдете 4 раза по 3 шага, затем 4 раза по 2 шага и один раз по 1 шагу. Создайте квадрат размером 5x5. Вы пройдете 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1 шаги. Это общая закономерность. Это математическая головоломка. Вы должны сделать некоторые головоломки в первую очередь.
Возможно, в моем алгоритме есть ошибка, но вы должны быть в состоянии исправить.
Да, точно есть ошибка. Я постараюсь понять это. Кроме того, не могли бы вы подсказать, где я могу решить такие головоломки или что-то подобное?
Вам действительно не нужно превращать 1D-массив в 2D-массив, а также вам не нужно посещать значение каждый в массиве. Диагонали следуют простому шаблону, так как индексное расстояние между двумя последовательными элементами по диагонали следует шаблону.
См., например, матрицу 7x7, индексы спиральной последовательности которой находятся на диагонали:
0 . . . . . 6
. 24 . . . 28 .
. . 40 . 42 . .
. . . 48 . . .
. . 46 . 44 . .
. 36 . . . 32 .
18 . . . . . 12
Пробелы между двумя последовательными индексами, которые находятся на диагонали (в порядке индекса): 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2. Общий шаблон для этих промежутков : ?-1, ?-1, ?-1, ?-1, ?-3, ?-3, ?-3, ?-3,... и т.д.
Поскольку размер данного массива равен квадрату ?, я не понимаю, зачем вам нужно передавать ? в качестве аргумента. Это избыточная информация.
Так:
function sumDiagonals(arr) {
let n = Math.sqrt(arr.length);
if (n % 1) throw "Array size should be perfect square";
let sum = 0;
let len = n*2 - n%2; // The number of values on diagonals
for (let i = 0, j = 0; j < len; i += n - 1 - (j++ >> 2)*2) {
sum += arr[i];
}
return sum;
}
let arr = [1, 2, 3, 8, 9, 4, 7, 6, 5];
console.info(sumDiagonals(arr));
Посмотрите, какой будет ответ для примера массива, который я привел? Будет 30 не так ли? И код, который вы написали в соответствии с вашей логикой, дает результат как 25.
Если вы говорите, что это 30, это означает, что центральный элемент считается дважды. Это то, что вы хотите? Я понял, что значение должно считаться только один раз (когда оно находится по диагоналям). Вероятно, это другая интерпретация. Вы можете уточнить?
Извините, я просто проверял тестовые случаи, и на самом деле мой плохой ответ может быть принят, так что это не проблема. И я понимаю, что если мы не посчитаем средний элемент дважды, то ответом будет 25. Прохладно. Еще одна вещь, которую я не понимаю, это... Промежутки между двумя последовательными индексами, которые находятся на диагонали (в порядке индекса): 6, 6, 6, 6, 4, 4, 4, 4, 2, 2 , 2, 2. Общий шаблон для этих пробелов:
Первый индекс в спиральной последовательности матрицы 7x7 с числом, расположенным по диагонали, равен 0 (верхний левый угол матрицы). Следующий индекс в спиральной последовательности, имеющий число на диагонали, равен 6 (вверху справа от матрицы). Таким образом, от 0 до 6 — это расстояние (промежуток) 6, что равно n-1 (здесь n равно 7). Следующий индекс в спирали с числом по диагонали равен 12 (нижний правый угол матрицы), поэтому снова тот же пробел и т. д.
Ох! Теперь понял. И последнее, я много искал этот вопрос, хотя я не нашел никаких решений, но каждое обсуждение, которое я нашел, включает циклическое выполнение, например, взятие четырех переменных сверху, вниз, снизу и влево, а также четырех циклов for и т. д. и т. д. Но этот подход уникален. Вы узнали это сами или где-то прочитали, если можете мне сказать?
Я только что проанализировал это сам, и вот что я придумал. Я понимаю, что есть много способов приблизиться к этому. Если бы я посмотрел на это снова через два года, забыв об этом вопросе, я мог бы придумать еще один подход. Никто на самом деле не понимает, как наш мозг придумывает идеи ;-)
Вам не нужна матрица для вычисления суммы. Сумма
arr[0] + arr[2] + arr[4] + arr[6] + 2 * arr[8]
. То естьarr[0 * (n - 1)] + arr[1 * (n - 1)] + arr[2 * (n - 1)] + arr[3 * (n - 1)] + 2 * arr[arr.length - 1]
.