С ! Магический квадрат
Магическим квадратом называют таблицу, в которой записаны числа 1,2,3,… по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечётной стороной (3×3,5×5,…).
Поставим число 1 в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа 2,3,4,…. Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с неё. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.
Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов 3×3 и 5×5 показаны на рисунках.
Входные данные
На вход подается одно натуральное нечётное число N, не превосходящее 30 — размер квадрата.
Выходные данные
Выведите числа, записанные в квадрате. Выравнивать числа по столбцам не обязательно. Обратите внимание: требуется вывести именно магический квадрат, полученный применением указанного метода.
Примеры
Ввод
Вывод
3
8 1 6
3 5 7
4 9 2
5
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
#include <iostream>
#include <vector>
#include <cstdint>
using namespace std; template <class T>
istream& operator>>(istream &in, vector<T> &vec) { for (auto &it : vec) in >> it; return in;
}
template <class T>
ostream& operator<<(ostream &out, vector<T> &vec) { for (auto &it : vec) out << it << ' '; return out;
}
template <class T, class U>
istream& operator>>(istream &in, pair<T, U> &pair) { in >> pair.first >> pair.second; return in;
}
template <class T, class U>
ostream& operator<<(ostream &out, pair<T, U> &pair) { out << pair.first << ' ' << pair.second; return out;
}
signed main(void) { int32_t n; cin >> n; vector<vector<int64_t>> a(n, vector<int64_t>(n,-1)); int64_t x = 0, y = n/2; a[x][y] = 1; for(int32_t i = 2; i <= n*n; ++i) { int _x = x, _y = y; if(!x) { x = n-1; } else { --x; } if(y == n-1) { y = 0; } else { ++y; } if(a[x][y] != -1) { x= _x, y = _y; while(a[x][y] != -1) { if(x == n-1) { x = 0; } else { ++x; } } } a[x][y] = i; } for(int32_t i = 0; i < n; ++i) { cout << a[i] << '\n'; } return 0; }
Объяснение: