Подсчет суммы рядов матрицы

[Token]

Дана матрица 3x3 и числа от 1 до 9. Написать алгоритм, размещающий эти чмсла в матрице так чтобы все вертикалбные, горизонтальные и диагональные ряды имели одинаковую сумму чисел в их ячейках.

[Azazello]

Работает для всех нечётных SIZE...
[code:1:0fb17d8c30]
#include <stdio.h>
#include <string.h>

#define SIZE 3
int
main(int argc, char *argv[])
{
int matrix[SIZE][SIZE];
int n, ii, jj, i = 0, j = SIZE >> 1;

memset(matrix, 0, sizeof(matrix));
for (n = 1; n <= SIZE * SIZE; ++n)
{
matrix[i][j] = n;
ii = (i > 0) ? i - 1 : SIZE - 1;
jj = (j + 1) % SIZE;
if (matrix[ii][jj])
{
ii = (i + 1) % SIZE;
jj = j;
}
i = ii;
j = jj;
}
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
{
printf("%3d", matrix[i][j]);
}
printf("\n");
}
return 0;

}
[/code:1:0fb17d8c30]

[Token]

Azazello, а вы не в курсе где можно найти сборник таких задач?

[FiL]

Azazello, а ПОЧЕМУ оно работает? Есть какое-то математическое доказательство того, что при таком алгоритме заполнения оно будет именно так как оно будет?
P.S. Подозреваю, что есть, но даже отдаленно не представляю как такой алгоритм мог родиться.

[Azazello]

Во-первых, я поправил баг - работало для 3, но не работало для остальных нечётных.
По поводу книжек - я уже не помню, где именно я увидел в первый раз задачу о магическом квадрате и её решение в общем виде для нечётных размерностей. По-моему, у Перельмана в "Живой математике", но может быть и у Кордемского в "Математической смекалке", а может и у Мартина Гарднера в одной из его книг.
Понятно, там приводилась не программа, а "рецепт", т.е. алгоритм. Исполнение на C - моё (c).
Ни в одной из перечисленных книг я не видел формального доказательства. Возможно, оно есть у Куранта и Роббинса ("Что такое математика"), но я не уверен. Просто это единственная книга из моего детства, где были хоть какие-то доказательства...
Естественно, за давностью лет я этого доказательства не помню, а думать сейчас лень - но могу попробовать на досуге - я когда-то неплохо умел доказывать простые теоремы....

[Token]

Так вы что еще давно этот алгоритм написали? Если нет то хотелось бы все-таки увидеть словестное описание алгоритма или идеи хотя-бы. Сам алгоритм совершенно не прозрачен.

[Azazello]

[quote:4a7ae9a4e3="Token"]Так вы что еще давно этот алгоритм написали? Если нет то хотелось бы все-таки увидеть словестное описание алгоритма или идеи хотя-бы. Сам алгоритм совершенно не прозрачен.[/quote:4a7ae9a4e3]
Словесное описание такое:
1. Представим себе, что квадрат окружён такими же (всего их будет - по одному примыкает к каждой стороне и ещё по одному - с углов. Назовём их дополнительными.
2. Ставим единицу в среднюю клетку верхнего ряда.
3. Следующее число ставим в клетку, находящуюся на единицу выше и правее предыдущей, если она пуста. Иначе - в клетку, находящуюся на единицу ниже предыдущей. Если мы вышли за пределы основного квадрата, скопируем число в основной квадрат из дополнительного, сохраняя координаты (выполним параллельный перенос) и продолжим с этого места.

[Token]

Так вы не сказали самого главного - почему именно на единицу выше и правее а если она не пуста то на единицу ниже? В этом то и заключается идея... только откуда она следует?

[Azazello]

КАК пришли к этому алгоритму я понятия не имею. Почему он работает - аналогично. Думаю, что смог бы доказать его корректность. Просто не было свободного часа на это ещё...

[Token]

Так что же никто не знает ответа? Я сам лично понятия не имею как можно прийти к такому алгоритму, но очень хочется узнать ответ...

[kot2002]

[quote:ed8d29a8a9="Token"]Дана матрица 3x3 и числа от 1 до 9. Написать алгоритм, размещающий эти чмсла в матрице так чтобы все вертикалбные, горизонтальные и диагональные ряды имели одинаковую сумму чисел в их ячейках.[/quote:ed8d29a8a9]

Решение (из него же алгоритм) даже без компа.
Сумма от 1 до 9 равна 45, след в каждой вертикали диагонали по 15.
Через центр проходит 4 линии.
Если в центре 1 то чтобы сумма была 15 нужны 4 пары по 14 а их всего 2 (9,5) и (8,6)
Не получается. Для 2 и 3 в центре тоже не 4 пары не построить.
Если в центре 4 то в остальных парах нет 1 (зато есть вторая 4)))
Остается в центре 5 а остальные пары дают в сумме по 10 (9,1) (8,2) (7,3) и (6,4).
Каждой матрице а(i,k) соответствует матрица 10-а(i,k), поэтому дальше 5 перебирать не стоит.
Таким образом в центре ТОЛЬКО 5!
Пусть одна диагональ 9,1, тогда никакая другая пара для диагонали не удовлетворит (сумма вертикали или горизонтали больше 15!)
Если диагональ 8,2 то вторая по той же причине не может быть 7,3 и остается только 6,4.
Все остальные 4 элемента легко вычисляются.
Сколько таких квадратов?
Для первой диагонали (8,2) 4 положения. 8 в 4х углах.
для второй диагонали остается 2 положения (6 в двух оставшихся углах)
Всего 8 вариантов магического квадрата.