Однострочники в конце этого ответа, пояснение следующее: -)
Массив коэффициентов содержит: M элементов для первой строки (строка 0, в вашей индексации), (M-1) для второй (строка 1) и т. Д., В общей сложности M + (M-1) + & hellip; + 1 = M (M + 1) / 2 элемента.
Немного легче работать с конца, потому что массив коэффициентов всегда имеет 1 элемент для последней строки (строка M-1), 2 элемента для второй последней строки (строка M-2) ), 3 элемента для ряда М-3 и т. Д. Последние K строк занимают последние K (K + 1) / 2 позиции массива коэффициентов.
Теперь предположим, что вам дан индекс i в массиве коэффициентов. Есть элементы M (M + 1) / 2-1-i в положениях больше, чем i. Позвоните по этому номеру я; вы хотите найти наибольшее k такое, что k (k + 1) / 2 & le; я '. Форма этой проблемы является источником ваших страданий - насколько я понимаю, вы не можете избежать принятия квадратных корней: -)
Хорошо, давайте все равно сделаем это: k (k + 1) & le; 2i 'означает (k + 1/2) 2 - 1/4 & le; 2i 'или эквивалентно k & le; (SQRT (8i '+ 1) -1) / 2. Позвольте мне назвать наибольшее такое k как K, тогда есть K строк, которые являются более поздними (из общего количества M строк), поэтому row_index (i, M) равен M-1-K. Что касается индекса столбца, K (K + 1) / 2 элемента из i 'находятся в более поздних строках, поэтому в этой строке есть j' = i'-K (K + 1) / 2 более поздних элемента (который имеет K + 1 элементов), поэтому индекс столбца K-j '. [Или, что эквивалентно, эта строка начинается с (K + 1) (K + 2) / 2 с конца, поэтому нам просто нужно вычесть начальную позицию этой строки из i: i- [M (M + 1) / 2 - (К + 1) (К + 2) / 2]. Отрадно, что оба выражения дают один и тот же ответ!]
(Псевдо-) код [использование ii вместо i ', поскольку некоторые языки не допускают переменных с именами, такими как i'; -)]:
row_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return M-1-K
column_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return i - M(M+1)/2 + (K+1)(K+2)/2
Конечно, вы можете превратить их в однострочные, подставив выражения для ii и K. Возможно, вам следует быть осторожным с ошибками точности, но есть способы найти целочисленный квадратный корень, который не требует вычисления с плавающей запятой , Кроме того, процитирую Кнута: «Остерегайтесь ошибок в приведенном выше коде; я только доказал, что это правильно, а не пробовал».
Если я позволю себе сделать еще одно замечание: простое хранение всех значений в массиве M & times; M займет максимум в два раза больше памяти, и в зависимости от вашей проблемы коэффициент 2 может быть незначительным по сравнению с алгоритмическими улучшениями, и, возможно, стоит обменять, возможно, дорогостоящее вычисление квадратного корня на более простые выражения, которые у вас будут.
[Редактировать: Кстати, вы можете доказать, что floor ((sqrt (8ii + 1) -1) / 2) = (isqrt (8ii + 1) -1) / 2, где isqrt (x) = floor (sqrt ( x)) является целочисленным квадратным корнем, а деление является целочисленным делением (усечение; значение по умолчанию в C / C ++ / Java и т. д.), поэтому, если вас беспокоит проблема точности, вам нужно только беспокоиться о реализации правильного целочисленного квадрата корень.]