Остроты в конце этого ответа, объяснение следует за:-)

, массив коэффициентов имеет: M элементы для первой строки (строка 0, в Вашей индексации), (M-1) для второго (строка 1), и так далее, для в общей сложности M + (M-1) + … +1=M (M+1)/2 элементы.

немного легче работать от конца, потому что массив коэффициентов всегда имеет 1 элемент для последней строки (строка M-1), 2 элемента для предпоследней строки (строка M-2), 3 элемента для строки M-3, и так далее. Последние строки K поднимают последний K (K+1)/2 положения массива коэффициентов.

Теперь предполагают, что Вам дают индекс i в массиве коэффициентов. Существуют M (M+1)/2-1-i элементы в положениях, больше, чем я. Назовите этот номер i'; Вы хотите найти самый большой k таким образом что k (k+1)/2 ≤ я' . Форма этой проблемы является самым источником Вашего страдания - насколько я вижу, Вы не можете постараться не пускать квадратные корни:-)

Хорошо, давайте сделаем это так или иначе: k (k+1) ≤ 2i' означает (k+1/2) <глоток> 2 - 1/4 ≤ 2i', или эквивалентно k ≤ (sqrt (8i' +1)-1)/2. Позвольте мне назвать самое большое таким k как K, тогда существуют строки K, которые являются позже (из в общей сложности M строки), таким образом, row_index (я, M) является M-1-K. Что касается индекса столбца, K (K+1)/2 элементы из меня' находятся в более поздних строках, таким образом, существуют j' =i '-K (K+1)/2 более поздние элементы в этой строке (который имеет элементы K+1 всего), таким образом, индекс столбца является K-j'. [Или эквивалентно, эта строка запускается в (K+1)(K+2)/2 от конца, таким образом, мы просто должны вычесть стартовую позицию этой строки от меня: i-[M (M+1)/2-(K+1)(K+2)/2]. Это радостно, что оба выражения дают тот же ответ!]

(псевдо-) Код [использующий ii вместо меня', поскольку некоторые языки не позволяют переменные с именами как я';-)]:

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. Вам, вероятно, придется быть осторожно относительно ошибок точности, но существуют способы найти целочисленный квадратный корень, которые не требуют вычисления с плавающей точкой. Кроме того, для заключения в кавычки Knuth: "Остерегайтесь ошибок в вышеупомянутом коде; я только доказал, что это исправляет, не попробованный это".

, Если я могу рисковать сделать дальнейшее замечание: просто сохраняя все значения в M× M массив возьмет самое большее дважды память, и в зависимости от Вашей проблемы, фактор 2 мог бы быть незначительным по сравнению с алгоритмическими улучшениями и мог бы стоить торговать возможно дорогим вычислением квадратного корня для более простых выражений, которые Вы будете иметь.

[Редактирование: BTW, можно доказать, что пол ((sqrt (8ii+1)-1)/2) = (isqrt (8ii+1)-1)/2, где isqrt (x) =floor (sqrt (x)) является целочисленным квадратным корнем и подразделением, является целочисленным делением (усечение; значение по умолчанию в C/C ++/Java и т.д.) - поэтому, если Вы волнуетесь по поводу точности, выходит, только необходимо волноваться о реализации корректного целочисленного квадратного корня.]

Может быть умный один лайнер для них, но (минус любая проверка ошибок):

unsigned int row_index( unsigned int i, unsigned int M ){
    unsigned int row = 0;
    unsigned int delta = M - 1;
    for( unsigned int x = delta; x < i; x += delta-- ){
        row++;
    }
    return row;
}

unsigned int column_index( unsigned int i, unsigned int M ){
    unsigned int row = 0;
    unsigned int delta = M - 1;
    unsigned int x;
    for( x = delta; x < i; x += delta-- ){
        row++;
    }
    return M + i - x - 1;
}

Должно случиться так, что

i == col + row*(M-1)-row*(row-1)/2

Так один способ найти седло и строку должен выполнить итерации по возможным значениям строки:

for(row = 0; row < M; row++){
  col = i - row*(M-1)-row*(row-1)/2
  if (row <= col < M) return (row,column);
}

Это, по крайней мере, нерекурсивно, я не знаю, можно ли сделать это без повторения.

Как видно из этого и других ответов, в значительной степени необходимо вычислить строку для вычисления столбца, таким образом, могло быть умно сделать обоих в одной функции.

Взял меня некоторое время для понимания то, в чем Вы нуждались!:)

unsigned int row_index(int i, int m)
{
    int iCurrentRow = 0;
    int iTotalItems = 0;
    for(int j = m; j > 0; j--)
    {
        iTotalItems += j;

        if( (i+1) <= iTotalItems)
            return iCurrentRow;

        iCurrentRow ++;
    }

    return -1; // Not checking if "i" can be in a MxM matrix.
}

Жаль забыл другую функцию.....

unsigned int column_index(int i, int m)
{
    int iTotalItems = 0;
    for(int j = m; j > 0; j--)
    {
        iTotalItems += j;

        if( (i+1) <= iTotalItems)
            return m - (iTotalItems - i);
    }

    return -1; // Not checking if "i" can be in a MxM matrix.
}

Я немного подумал и получил следующий результат. Обратите внимание, что в одном кадре вы получаете как строку, так и столбцы.

Допущения: строки начинаются с 0. Столбцы начинаются с 0. Индекс начинается с 0

Обозначение

N = размер матрицы (был M в исходной задаче)

m = индекс элемента

Псевдо-код -

function ind2subTriu(m,N)
{
  d = 0;
  i = -1;
  while d < m
  {
    i = i + 1
    d = i*(N-1) - i*(i-1)/2
  }
  i0 = i-1;
  j0 = m - i0*(N-1) + i0*(i0-1)/2 + i0 + 1;
  return i0,j0
}

И немного кода октавы / матлаба

function [i0 j0]= ind2subTriu(m,N)
 I = 0:N-2;
 d = I*(N-1)-I.*(I-1)/2;
 i0 = I(find (d < m,1,'last'));
 j0 = m - d(i0+1) + i0 + 1;

Что вы думаете?

По состоянию на декабрь 2011 года в GNU / Octave был добавлен действительно хороший код для этого. Потенциально они будут расширять sub2ind и ind2sub. На данный момент код можно найти как частные функции ind2sub_tril и sub2ind_tril