Математическое решение задачи о матрице «змейкой»

Настоящая статья продолжает тему предыдущей работы (https://habr.com/ru/post/560266/)  и также посвящается особо замудренным способам заполнения двухмерных массивов согласно определенному шаблону. Создание громоздких, неуклюжих формул, без применения таких милых сердцу программиста конструкций как циклы и условия оказалось увлекательным занятием. В связи с этим, автор, уподобляясь некоторым государственным чинам (вспоминаем бородатую шутку про разницу между депутатом и программистом),   решил потратить кучу драгоценного времени на очередной интересный, но, увы, бесполезный в практическом плане проект. Речь идет о вычислении математическим путем элементов массивов, заполняемых змееподобной траекторией, или проще говоря — «тещиных» матриц.

Различают два класса этих самых матриц: обычные (злобные) и диагональные (крайне злобные).

Первый класс двухмерных массивов (здесь и далее речь идет только о квадратных матрицах) заполняется натуральными числами от 1 до N2 с левого верхнего угла построчно:

Рисунок 1. Простое, горизонтальное (построчное) заполнениеРисунок 1. Простое, горизонтальное (построчное) заполнение

При этом, с учетом наличия у квадрата 4-х сторон, а у каждой стороны — 2-х углов, в данном классе содержится еще 7 видов, если подойти к этому вопросу основательно.

Второй класс тещиных матриц заполняется значениями от 1 до N2 с левого верхнего угла по диагоналям, и аналогично предыдущему, может иметь еще 7 видов (начинаться с любого из четырех углов в двух направлениях).  Однако, мы в качестве примеров будем рассматривать только наиболее удобные варианты, традиционно начинающиеся с левого верхнего угла.

Рисунок 2. Диагональное заполнениеРисунок 2. Диагональное заполнение

Итак, постараемся предельно четко сформулировать задачу: вывести математически «чистые» формулы вычисления значений элементов вышеуказанных матриц на основании их координат (I, J) и размерности (N). При этом, не допускается использовать условные переходы и заранее заготовленные наборы данных: массивы, словари, множества и т.д. Циклы используются только для перебора всех элементов матрицы и также не применяются непосредственно в вычислениях.  

Подготовка. Математический аппарат будет строиться параллельно с разработкой кода на языке С++. Для обеспечения программной реализации решений подготовим соответствующий скрипт, объявив в нем массив размером 5×5 (присвоим ему оригинальное наименование «a») и заполнив его нулевыми значениями. Формулы будут строиться и проверяться поэтапно в процессе их одновременной работы со всеми элементами матрицы, перебор которых производится традиционным способом двумя вложенными циклами от 1 до N.

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

Основной скрипт для обеих частей выглядит следующим образом:

#include 
using namespace std;
int main()
{
    int N = 5;          // задаем размер матрицы
    int a[N][N];        // и инициализируем ее
    for (int ik = 0; ik < N; ik++)
        for (int jk = 0; jk < N; jk++)
            a[ik][jk] = 0;          // заполнив для удобства нулями
                                      
    for (int ik = 0; ik < N; ik++){     //назовем его "Основной цикл"
        for (int jk = 0; jk < N; jk++){
        
            int i = ik + 1;     // Номера строк и столбцов приводим в удобный
            int j = jk + 1;     // в математическом плане вид (от 1 до N)  
            //  ... здесь будем вставлять основной код вычислений
     
        }   
    }     

   for (int ik = 0; ik < N; ik++){          //Блок "Вывод массива"
        for (int jk = 0; jk < N; jk++){
           printf( " %02d  " , a[ik][jk]);// дополняем число ведущими нулями
        }
        cout << endl;
    }  
    return 0;
}

1 класс матриц (в построчном исполнении)

В построчном виде достаточно легко вывести соответствующую формулу и применить ее для заполнения массива. В данной статье это решение приводится только в качестве небольшой разминки.

Итак, анализ расстановки элементов матрицы показывает (см. Рисунок 1), что наибольшими компонентами непрерывного изменения значений (цельные отрезки, где значения изменяются на +1 или -1) являются строки. Таким образом, номер строки будет играть ведущую роль, а номер столбца обеспечивать прирост/убывание значений элементов.

Для начала выведем число согласно порядковому номеру ячейки, который возрастает в привычном для нас направлении «слева-направо» и «сверху-вниз».

5f62ac1e0e681eddb597ec4d7a426cfd.png

Вводим соответствующий код в компиляторе:

…
a[ik][jk] = (i - 1) * N + j;
…

И получаем выходные данные:

Рисунок 3. Вариант «слева-направо»Рисунок 3. Вариант «слева-направо»

Как видим, от желаемого результата нас разделяют лишь четные строки, в которых прирост должен быть в обратном порядке.

Следовательно, выведем формулу для заполнения элементов в обратном порядке.

0dcae1f37aaa59da5d7e9c1274251c66.png

Введем соответствующий код в компиляторе:

…
a[ik][jk] = i  * N + 1 + j;
…

Рисунок 4. Вариант «справа-налево»Рисунок 4. Вариант «справа-налево»

Полагается, с учетом целевой аудитории, что детальных пояснений для этих простейших решений не требуется. На текущий момент важно, что мы имеем две разные формулы, которые необходимо объединить в одном уравнении, обеспечив их поочередную работу, в зависимости от четности/нечетности строки.

Для этого используем кусочно-заданную функцию, складывая  оба значения X, предварительно умножив каждый из них на остаток от целочисленного деления номера строки на 2. В случае X1 это (i mod 2), , а в случае X2это (i + 1) mod 2.

fe603f908d9fa76b21095a166dfb849e.png

Подставляем вместо X1 и X2 полные значения:

X=((i-1)*N+j)*(i mod 2)+(i*N+1-j)*((i+1)mod  2)

Переводим все это на С++ и наблюдаем конечный результат:

…
a[ik][jk] = ((i - 1) * N + j) * (i % 2) + (i * N + 1 - j) * ((i + 1) % 2);
…

Рисунок 5. Конечный результатРисунок 5. Конечный результат

2 класс матриц (в диагональном исполнении)

В диагональном исполнении задача является на порядок сложнее, требует значительно большего времени, а также разделения ее на несколько этапов. Однако, прежде чем приступить к штурму крепости, приведем некоторые, необходимые в дальнейшем, определения:

Главная диагональ — диагональ, проведённая из левого верхнего угла матрицы в правый нижний.

Побочная диагональ — диагональ, проведённая из левого нижнего угла матрицы в правый верхний (Рисунок 6).

Рисунок 6. Диагонали матрицы.Рисунок 6. Диагонали матрицы.

В данной задаче участками непрерывного изменения значений являются побочная и параллельные ей диагонали. Для удобства в будущем диагонали также будем именовать «блоками», а побочную диагональ «центральной» (не путать с «главной»).

1 этап. Итак, приступим. Общее количество блоков равно 2 * N — 1, где N — размер матрицы. В нашем случае при размерах матрицы 5×5 это будет 9. Далее, для наглядности выделим и пронумеруем эти диагонали (Рисунок 7).

Рисунок 7. Матрица с искомыми значениями.Рисунок 7. Матрица с искомыми значениями.

Следующим шагом приводим матрицу с адресами ее элементов, для удобного изучения их связи с желаемыми значениями (Рисунок 8).

Рисунок 8. Матрица с адресами значенийРисунок 8. Матрица с адресами значений

В данном случае явно наблюдаем зависимость порядкового номера диагонали от суммы номера строки и столбца. Т.е. D = i + j – 1.

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

Так, если в первой диагонали 1 элемент, во второй 2, в третьей 3, то у нас на лицо арифметическая прогрессия с разностью d = 1 и начальным значением a1 = 1.

В свою очередь, искомые значения элементов, представлены в следующих диапазонах: в блоке 1 — [1], в блоке 2 — [2…3], в блоке 3 — [4…6] и так далее до центральной диагонали включительно.  

Вычислить максимальное число в каждой диагонали возможно с помощью формулы суммы арифметической прогрессии:

8c6c63ca9c7deebc5ae1473bcaaad868.png

(Касательно знаков деления: с учетом особенностей текстового редактора Хабра, дробные выражения используются в отдельно стоящих формулах, а знак »/» в математических выражениях встречающихся непосредственно в тексте. Оба этих знака являются эквивалентами и означают деление в широком смысле, которое, однако, в настоящей работе всегда предполагает целочисленные результаты. В отдельных местах, где важно подчеркнуть именно операцию целочисленного деления используется знак »÷». Получение остатка  от целочисленного деления обозначается «mod». Прим автора.)

Поскольку в нашем случае a1 = 1 и d = 1, то формула немного упрощается, и ее единственным аргументом остается n — порядковый номер члена прогрессии:

20aea9603ea3dba00a0225cf73570e05.png

Таким образом, мы можем определить верхний предел значений (максимальное число) в каждой конкретной диагонали.

К примеру, в четвертой диагонали максимальное значение S4 = (4 + 42) / 2 = 10, в чем можно убедиться, взглянув на Рисунок 6. Однако данный подход будет работать только до центральной диагонали, поскольку после нее количество элементов в блоках начинает уменьшаться на единицу (отрицательный рост :)). В целом, все дальнейшие вычисления предполагают отдельный подход к значениям до и после побочной диагонали. Поэтому, для удобства, первую часть матрицы (все диагонали до центральной включительно) условно назовем сектором «А», а вторую сектором «В» (остальные элементы). Эти буквы также будут фигурировать в названиях некоторых переменных, в зависимости от их роли, как в математических формулах, так и непосредственно в коде программы.

Теперь представим окончательное выражение, предварительно обозначив номер диагонали переменной D (вместо «n» из общей математической формулы), а максимальное значение — Ma (вместо Sn):

9b256cc86ac802cfb92cb36b3fe0a0c7.png

Пишем эти вычисления на языке С++ и наблюдаем результат (Рисунок 9):

…
int D = i + j - 1;
int Ma = (D * D + D) / 2;
a[ik][jk] = Ma;
… 

Рисунок 9. Сектор «А»Рисунок 9. Сектор «А»

Как и отмечалось выше, в секторе «А» появились необходимые значения. Вместе с тем, числа после центральной диагонали явным образом не соответствуют ожиданиям. Причиной этому является неспособность одновременного использования формулой прироста в секторе «А» (d = 1) и уменьшения в секторе «В» (d = -1). К примеру, в 6-ой диагонали она видит 6 элементов (в 7-ой 7 и т.д.), а реализация формулы в программном коде демонстрирует нам только 4 элемента со значением 21.

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

5a59814197fbe28ff2379962b82c7ff0.png

Здесь:

d = -1, убывание

n — порядковый номер члена прогрессии, а в нашем случае номер диагонали в секторе «В» относительно его начала, т.е. D — N,

a1 — длина первой диагонали в секторе «В», т.е. N — 1,

Sцентр — максимальное значение элементов в центральной диагонали, т.е. (N2 + N) / 2.

Далее введем переменную Mb, которая будет содержать максимальные значения для диагоналей сектора «В» и заменим ей Sn.

В результате получаем следующее выражение:

e5aaa35ad068ffc5664fc1cbb8858de7.png

Раскрывая скобки, умножая, сокращая и совершая прочие математические извращения, выводим более компактную формулу:

f8282ec91220c132bca1a596f7bd8432.png

Кодируем ее и анализируем результаты:

…
int Mb =  (N * N + N) / 2 + ((3 * N – D - 1) * (D - N)) / 2;
a[ik][jk] = Mb;
…

Рисунок 10. Сектор «В»Рисунок 10. Сектор «В»

Как видим, сектор «В» в этот раз состоит из необходимых чисел, но в секторе «А» большинство элементов содержат неправильные значения. Проблема также решается с помощью кусочно-заданной функции.

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

2072ba9a0047e1c07644aeadff88c3f1.png

а вторая после:

a340b0a46a89700becb1c42aca16c849.png

Эти два выражения следует объединить в одной функции, с условием, чтобы каждое из них работало корректно в своем секторе. Приблизительно таким образом:

2f23b3abaef65345d4d202e7ae39eeac.png

Здесь функция  F1(x) принимает значение 1 в секторе «А» и 0 в секторе «В», а F2(x) наоборот. Получается некое подобие битовой маски.

Для реализации этого замысла применим целочисленное деление и разделим номер диагонали на порядок матрицы увеличенный на одну единицу:

54c0e7e5fef58d13454b0ece93aec782.png

Набираем в компиляторе и смотрим результат:

…
a[ik][jk] = D / (N + 1);
…

Рисунок 11. Единицы в секторе «В»Рисунок 11. Единицы в секторе «В»

Как видим сектор «А» в данном случае равняется нулю, а сектор «В» — 1. Эти результаты будем помещать в переменную Cb. Для того чтобы получить диаметрально противоположенные значения, достаточно инвертировать результаты следующим выражением:

e102e612d852acd0ee90226fae891e41.png

Теперь введем новую переменную Ca, поместим в нее результат работы последней формулы и внесем соответствующий код в скрипт:

…
int Ca = abs (D / (N + 1) - 1);
a[ik][jk] = Ca;
 …

Рисунок 12. Единицы в секторе «А»Рисунок 12. Единицы в секторе «А»

Таким образом, на текущий момент мы вооружились всеми необходимыми элементами для вычисления максимальных значений в диагоналях.

Остается собрать все отдельные компоненты в единое математическое выражение
M = Ma * Ca + Mb * Cb, и соответственно написать в С++ полный код по предыдущим действиям.

…
int D = i + j - 1;
int Ma = (D * D + D) / 2;
int Mb =  (N * N + N) / 2 + ((3 * N - D - 1) * (D - N)) / 2; 
int Ca = abs (D / (N + 1) - 1);
int Cb = D / (N + 1);
a[ik][jk] = Ca * Ma + Cb * Mb;
…

Рисунок 13. Максимальные значения в блокахРисунок 13. Максимальные значения в блоках

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

2 этап. Теперь необходимо завершить работу, превратив одинаковые значения в возрастающую группу чисел соответствующего диапазона в каждом блоке. Этого можно достичь вычитая из элементов определенные значения. Снова взглянем на матрицу с индексами.

Рисунок 14. Матрица с адресами значений.Рисунок 14. Матрица с адресами значений.

В секторе «А», индексы элементов в каждом блоке находятся в диапазоне от 1 до длины блока (которая эквивалентна номеру диагонали). Соответственно, вычитая из максимальных значений i или j увеличенный на 1, мы можем получить нужные числа. Однако, результирующие значения будут расположены в возрастающем порядке только с начала (сверху-вниз), либо только с конца блока (снизу-вверх).

При использовании j в качестве вычитаемого, направление прироста будет сверху-вниз:

f49a9a4197702d6285baf0987fc35f15.png

Следует отметить, что пока мы не будем затрагивать сектор «В».

Кодируем последнее выражение и любуемся результатом:

…
a[ik][jk] = Ca * (Ma - j + 1) + Mb * Cb;
…

Рисунок 15. Блоки в секторе «А» с односторонним приростом значений.Рисунок 15. Блоки в секторе «А» с односторонним приростом значений.

Отсюда можно сделать логический вывод, что заменив i на j, мы получим обратный результат в виде прироста снизу-вверх. Окончательный же вид змеевидной матрицы сформируется путем чередования направлений прироста «сверху-вниз» и «снизу-вверх».

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

Для этого введем две переменные: Co(odd numbers) для нечетных блоков и Ce (even numbers) для четных. Co вычислим выражением D mod 2 (при нечетном D он будет равняться 1, при четном 0) и Ce (D + 1) mod 2 (соответственно наоборот). Вставляем эти элементы в
формулу так, чтобы вычитание j происходило в четных диагоналях, а вычитание i в — нечетных:

2fcf2318838a6586942f279273390da7.png

Кодируем это и восхищаемся результатом:

…
int Co = D % 2;
int Ce = (D + 1) % 2;
a[ik][jk] = Ca *((Ma - j + 1)* Ce + (Ma - i + 1) * Co) + Cb * (Mb);
…

Рисунок 16. Половина змеи.Рисунок 16. Половина змеи.

Получается вот такая картина, то есть половина тещи змеи у нас уже готова.

Приведение в норму сектора «В» происходит похожим способом. Однако здесь простое вычитание номера строки или столбца не приведет к корректным результатам, так как i и j находятся в диапазоне 2…N. Для получения правильных значений в качестве вычитаемого используем разницу «N — i»   или «N — j». В первом случае у нас направление прироста будет сверху-вниз, а во втором — наоборот.

Расширим нашу предыдущую формулу:

96b135928283d9d0017ae47dd0566671.png

и реализуем ее в программном виде:

…
a[ik][jk] = Ca *((Ma - j + 1)* Ce + (Ma - i + 1) * Co) + Cb * (Mb - (N - i));
…

Рисунок 17. Вторая половина змеи.Рисунок 17. Вторая половина змеи.

Рисунок 17 демонстрирует, что осталось только скорректировать направления прироста по аналогии с сектором «А», в зависимости от четности номера диагонали используя уже готовые переменные Ce и Co:

161224ef3ade7478cbe7c5cb62b26d21.png

Кодируем и, в этот раз — по-взрослому, восхищаемся результатами:

…
a[ik][jk] = Ca *((Ma - j + 1)* Ce + (Ma - i + 1) * Co) 
                       + Cb * ((Mb - (N - i)) * Ce + (Mb - (N - j)) * Co);
…

Рисунок 18. Матрица, заполненная змейкойРисунок 18. Матрица, заполненная змейкой

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

Математика:

21213dc25d71b6fd97207964636ac877.png

Код на С++:

…
int D = i + j - 1;
int Ma = (D * D + D) / 2;
int Mb =  (N * N + N) / 2 + ((3 * N - D - 1) * (D - N)) / 2; 
int Ca = abs (D / (N + 1) - 1);
int Cb = D / (N + 1);
int Co = D % 2;
int Ce = (D + 1) % 2;
a[ik][jk] = Ca *((Ma - j + 1)* Ce + (Ma - i + 1) * Co) 
+ Cb * ((Mb - (N - i)) * Ce + (Mb - (N - j)) * Co);
…

3 этап. Сокращение. На предыдущем этапе мы вывели более или менее обоснованную формулу вычисления значений элементов, разъяснили каждый шаг. В то же время, не попытаться ее сократить, было бы проявлением неуважения к математике и всем знаменитым деятелям, которые развили эту науку до сегодняшнего состояния.

Итак, вернемся к моменту вычисления максимальных значений в секторе «В»:

5c9dab09c9cc27876bb267a27afeae80.png

раскроем здесь скобки,

ca2cc015f804c53644d9249832af60c4.png

и сократим

e3ec47233b1a644f991dd68bab974f84.png

Наше уравнение стало немного короче, хоть и не на столько, чтобы это имело существенное значение. Однако, если присмотреться можно узреть — D2 — D, часть выражения, которая является в некотором роде антагонистом Ma = (D2 + D) / 2, формулы вычисления максимальных значений в секторе «А». Возможно ли как-нибудь обратить »— D2 — D» из негатива в позитив? Конечно, если  его записать в виде »D2 + D — 2D2 — 2D», по сути, увеличив количество негатива в уравнении. Пробуем, предварительно собрав все D-элементы в начале выражения:

57454ad13eb60e99dc672b71e5ab299b.png

Теперь мы можем легко вычленить из общей дроби (D2 + D) / 2, при этом, не забывая инвертировать знаки в оставшейся части (так как мы выводим знак «минус» перед второй дробью):

ef071cfbbb556baf63e8b8bd15c90330.png

Разделим вторую дробь на 2:

96e168e9734bbcc5edd348ba68481e22.png

Таким образом, на данный момент формула отдельным членом содержит выражение
(D2 + D) / 2. То есть, мы на пути к тому, чтобы вместо двух уравнений для Ma и Mb использовать одно. Но и это еще не все, так как здесь припасен небольшой бонус. В частности, проанализировав вычитаемое (D2 + D + N2 — N + 2ND), можно увидеть многочлен квадратов суммы разницы (вспоминаем правило (a — b)2 = a2 — 2ab + b2), т.е. D2 — 2ND + N2. Собрав его (многочлен), получаем более компактное уравнение:

3c88fec3260639f864dd247dd11b4f77.png

Итак, наша новая формула в целом позволяет вычислить Mb, а также содержит выражение для вычисления Ma. Чтобы заставить ее работать на оба сектора корректно, достаточно умножить »(D — N)2 + (D — N)» на определитель сектора «В» Cb или D ÷ (N + 1). Теперь запишем окончательный вариант, используя вместо Mb просто M.

320278dd433866eda10870633f2f399b.png

Набираем соответствующую команду в компиляторе и наблюдаем результат:

…
int M = (D * D + D) / 2 - ((D - N) * (D - N) + (D - N)) * (D / (N + 1));
a[ik][jk] = M;
…

Рисунок 19. Максимальные значения более компактной формулойРисунок 19. Максимальные значения более компактной формулой

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

Возвращаемся к формуле:

1ca61a1745585cc4057aad059eb1cab7.png

Здесь для коррекции сектора «А» мы вычитали (j — 1), а для коррекции сектора «В» (N — i). Однако в том случае у каждого сектора были независимые вычисления. Теперь же придется прийти к какому-то общему выражению и согласовать »(j — 1)» и »(N — i)». Конечно, мы бы могли снова задействовать определители секторов Ca и Cb, но тогда длина формулы практически вернулась бы в исходное состояние, делая бессмысленными наши потуги ее сократить.

Далее, поработаем отдельно с сектором «В», добавив в него »(N — i)». При этом не забываем, что попадая внутрь скобок, перед которым стоит знак »-», знак непосредственно самого —
»(N — i)» инвертируется. Выделим нужный участок красным, также заменив D на i + j — 1.

58d394952b51cb1795bbb198a2c6aa06.png

Сокращаем ненужное и получаем:

eb9aa9a802c54a46d770712046b9f8d5.png

Пробуем в это в компиляторе:

…
int M = (D * D + D) / 2 - ((D - N) * (D - N) + (j - 1))* (D / (N + 1));
a[ik][jk] = M;
…

Рисунок 20. Сектор «В».Рисунок 20. Сектор «В».

В результате получаем корректные значения в секторе «В», с приростом «сверху-вниз».

Теперь же, чтобы распространить корректировку на всю матрицу, достаточно вытащить за скобки «j — 1», опять же, не забывая об инвертировании знаков.

0e870f36c4e61c35086386247e0bae84.png

Пробуем в С++:

…
a[ik][jk]  = (D * D + D) / 2 - ((D - N) * (D - N))* (D / (N + 1)) - j + 1;
…

Рисунок 21. Односторонний прирост.Рисунок 21. Односторонний прирост.

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

Наконец, приступим к последнему шагу — обеспечим чередование направлений. Это сделать очень легко — достаточно задействовать уже имеющиеся определители четности, чередуя вычитание i или j.

a4be4dcc0edc4c4d66c6b102c29ec85d.png

Набираем соответствующую команду в С++ и снова восхищаемся результатом:

…
a[ik][jk]  = (D * D + D)/2 - ((D - N) * (D - N))* (D / (N + 1)) - j * Ce - i * Co + 1; 
…

Рисунок 22. Конечный результат сокращенной формулой.Рисунок 22. Конечный результат сокращенной формулой.

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

Математика:

N = размер матрицы.

D = i + j — 1. (D — переменная, номер диагонали).

19a38642b87b8179e95ea2c15116d62d.png

Программный код:

…
int D = i + j - 1;
int R =  (D * D + D) / 2 - ((D - N) * (D - N))* (D / (N + 1)) 
                    - j * ((D + 1)%2)- i * (D % 2) + 1; 
a[ik][jk] = R;
…

Итого, нам удалось значительно сократить формулу, а также программный код.

Заключение.

Автор ни в коем случае не претендует на первенство в решении этой задачи приведенным способом, так как из миллионов программистов во всем мире наверняка нашлись бы и другие любители подметать ломом асфальт (или красить траву в зеленый цвет). Таким же образом признается отсутствие какого-либо практического применения полученных результатов. Кроме того, заполнение всей матрицы посредством привычных циклов и условий, вероятно, потребует гораздо меньшего времени, чем путем вычисления каждого элемента громоздким набором арифметических операций (хотя, эту гипотезу еще надо доказать).

Однако, рассматривая вопрос чисто с теоретической точки зрения, возможно отметить преимущество формулы перед традиционным «цикло-условным» решением. Для этого представим ситуацию, в которой не требуется заполнение всего массива, а необходимо вычисление значения только одной ячейки. Массив, в свою очередь,   огромен (ну скажем 10000×10000); координаты искомого элемента находятся где-нибудь в середине. В таком случае получить результат одной функцией будет гораздо быстрее, нежели проходить циклом со счетчиком до середины матрицы. Сложно, конечно, в реальности представить такую ситуацию, но на то она и теория.

В данном контексте можно сослаться на неустанно увеличивающиеся вычислительные мощности современных компьютеров, которые в какой-то мере нивелируют потребность в оптимизации алгоритмов и экономии ресурсов. Однако не следует забывать и о соответствующем росте объемов обрабатываемых данных. К тому же, процессоры используются не только в пользовательских компьютерах или даже огромных серверах, установленных в комфортных помещениях (речь идет о комфорте для вычислительной техники). В современном мире вычислительные машины больше и больше применяются за пределами обозначенных мест, где физические условия зачастую бывают экстремальными. Само собой это может ограничивать процессоры в размерах и других параметрах, в конечном счете, ограничивая их вычислительные возможности.

Таким образом, вопрос о решении различных задач кратчайшим и наименее затратным способом остается актуальным.

© Habrahabr.ru