Конкурс: Заполнение матрицы диагональной змейкой
Требуется заполнить змейкой квадратную матрицу так, как показано на рисунке справа: заполнение происходит с единицы из левого верхнего угла и заканчивается в правом нижнем числом N2, где N – порядок матрицы. 
В выходной файл OUTPUT.TXT(или в консоль, это не важно вообще) выведите матрицу, заполненную числами от 1 до N2 змейкой, при этом между числами может быть любое количество пробелов.
Задача взята с моего любимого сайта по подобной тематике. Условие победы - НЕ САМЫЙ КОРОТКИЙ КОД!!!, такие конкурсы упираются в язык реализации и его стандартную библиотеку, мне они не кажутся интересными.
Поэтому правила следующие : Победителем становится тот участник, у кого в коде выполнено наименьшее кол-во операций алгоритма для матрицы 13*13(Условимся, что N = 13 для проверки кол-ва операций, однако программа должна работать для любого N <= 100). Разрешается использовать только собственноручно написанные функции и функции вывода(разрешается использовать те стандартные функции, без которых выполнение программы невозможно и они не влияют на кол-во операций)
Операциями считаются: сравнение, присваивание, инкремент/декремент , математические операции, логические операции, побитовые операции,тернарная операция(операция булевого выбора - считается за 1 операцию), операции по работе с указателями и памятью, операции взятия элемента по индексу(то есть mass[i] в с++,например, интерпретируется как 1 операция, а не как 2 а-ля: *(mass+i)).
Так же необходимо создать глобальную переменную, которая будет увеличиваться на 1 при каждом выполнении одной операции. И прикрепить её конечное значение для матрицы 13*13 с ответом. Операции с этой глобальной переменной не считаются как операции алгоритма.
Также не разрешается отлавливать случай для N == 13 отдельным условием. А уж тем более после этого условия создать хардокодом готовую матрицу и сразу её вывести. То есть алгоритм для 13 должен быть тот же, что и для 15 и для 23 и тп.
̶В̶А̶Ж̶Н̶О̶,̶ ̶я̶ ̶м̶о̶г̶ ̶ч̶т̶о̶-̶т̶о̶ ̶з̶а̶б̶ы̶т̶ь̶ ̶и̶ ̶ч̶т̶о̶-̶т̶о̶ ̶н̶е̶ ̶у̶ч̶е̶с̶т̶ь̶,̶ ̶с̶п̶р̶о̶с̶и̶т̶е̶ ̶э̶т̶о̶ ̶с̶р̶а̶з̶у̶,̶ ̶д̶л̶я̶ ̶у̶т̶о̶ч̶н̶е̶н̶и̶я̶ ̶и̶ ̶д̶о̶п̶о̶л̶н̶е̶н̶и̶я̶ ̶п̶р̶а̶в̶и̶л̶,̶ ̶п̶р̶е̶д̶л̶а̶г̶а̶ю̶ ̶н̶а̶ ̶э̶т̶о̶ ̶в̶ы̶д̶е̶л̶и̶т̶ь̶ ̶с̶е̶г̶о̶д̶н̶я̶ш̶н̶и̶й̶ ̶и̶ ̶з̶а̶в̶т̶р̶а̶ш̶н̶и̶й̶ ̶д̶е̶н̶ь̶.̶ ̶П̶о̶ж̶а̶л̶у̶й̶с̶т̶а̶ ̶н̶а̶п̶и̶ш̶и̶т̶е̶ ̶э̶т̶о̶ ̶с̶р̶а̶з̶у̶ ̶в̶ ̶к̶о̶м̶м̶е̶н̶т̶а̶р̶и̶я̶х̶,̶ ̶в̶е̶д̶ь̶ ̶л̶а̶з̶е̶й̶к̶у̶ ̶в̶ ̶п̶р̶а̶в̶и̶л̶а̶х̶ ̶в̶ ̶б̶у̶д̶у̶щ̶е̶м̶ ̶с̶м̶о̶ж̶е̶т̶е̶ ̶и̶с̶п̶о̶л̶ь̶з̶о̶в̶а̶т̶ь̶ ̶н̶е̶ ̶т̶о̶л̶ь̶к̶о̶ ̶в̶ы̶.̶С воскресенья(04.12) с 00-01 по МСК правила меняться не будут. С воскресенья (11.12) с 23-59 по МСК ответы не принимаются(отправленные не участвуют в конкурсе). Победитель получит 100 баллов репы. Успехов!
UPD 22-00 04.12 Никаких правок предложено не было. Правила вступают в силу Важно выполнить все правила и требования написанные выше для участия в конкурсе
Конкурс посвящается моему другу - Диме, передаю ему привет!!!
Ответы (4 шт):
Ну кой смысл ждать еще каких-то исправлений правил? :) считайте...
const int N = 13, N2 = N*N+1, NS = N*N/2+1, N_ = N - 1;
int M[N][N];
int x = 0, y = 0, s = 0;
for(int i = 1; i <= NS; ++i)
{
M[y][x] = i;
M[N_-y][N_-x] = N2-i;
if (s) { ++x; y -= (s = y != 0); }
else { ++y; x -= !(s = x == 0); }
}
А, да... На краткость кода по правилам acmp — тут.
У меня матрицы нет, ничего не хранится, по месту вычисляется число. [Online]
procedure FillZigzag(n: Integer);
var
ix, iy, nd, nn, n22, ny, oddb: Integer;
begin
nn := n * n;
for iy := 0 to n - 1 do begin
for ix := 0 to n - iy - 1 do begin
nd := ix + iy;
oddb := (nd and 1) * 2;
Write(nd * (nd + 1 + oddb) div 2 + 1 + iy * (1 - oddb) : 4);
end;
n22 := 2 * n - 2 - iy;
ny := n - iy - 1;
for ix := n - iy to n - 1 do begin
nd := n22 - ix;
oddb := (nd and 1) * 2;
Write(nn - nd * (nd + 1 + oddb) div 2 - ny*(1 - oddb) : 4)
end;
Writeln;
end;
end;
код реализован на PHP, счетчик операций встроенный, результат на скрине.
$_SERVER['n_count'] = 13;// размерность матрицы
$_SERVER['n_count']--;
$i = 0;
$j = 0;
$k = 1;
$arr[$i][$j] = $k++;
$_SERVER['operations_count'] = 5;
do{
step($i,$j,$arr,$k);
if($i == $j){
$_SERVER['operations_count']++;
break;
}
if($i > $j){
$_SERVER['operations_count']++;
moove_diagonal_right($i,$j,$arr,$k);
}
else{
$_SERVER['operations_count']++;
moove_diagonal_left($i,$j,$arr,$k);
}
$_SERVER['operations_count']++;
}while ($i != $j);
print_result($arr);
function step(&$i,&$j,&$arr,&$k){
if(($j == 0) or ($j == $_SERVER['n_count'])){
$step = moove_down($i,$j,$arr,$k);
$_SERVER['operations_count'] += 3;
}else{
$step = false;
$_SERVER['operations_count'] += 1;
}
if(!$step){
// if(($i == 0) or ($i == n))
moove_right($i,$j,$arr,$k);
$_SERVER['operations_count'] += 1;
}
}
function moove_down(&$i,$j,&$val,&$k){
if($i < $_SERVER['n_count']){
$i++;
$val[$i][$j] = $k++;
$_SERVER['operations_count'] += 4;
return true;
}else{
$_SERVER['operations_count'] += 1;
return false;
}
}
function moove_right($i,&$j,&$val,&$k){
if($j < $_SERVER['n_count']){
$j++;
$val[$i][$j] = $k++;
$_SERVER['operations_count'] += 4;
return true;
}else{
$_SERVER['operations_count'] += 1;
return false;
}
}
function moove_diagonal_right(&$i,&$j,&$val,&$k){
while ( ($i > 0) and ($j < $_SERVER['n_count'])){
$i--;$j++;
$val[$i][$j] = $k++;
$_SERVER['operations_count'] += 6;
}
}
function moove_diagonal_left(&$i,&$j,&$val,&$k){
while ( ($j > 0) and ($i < $_SERVER['n_count'])){
$i++;$j--;
$val[$i][$j] = $k++;
$_SERVER['operations_count'] += 6;
}
}
function print_result($arr){
foreach ($arr as $value) {
$rows[] = '<tr><td>'.implode('</td><td> ',$value).' </td></tr>';
}
echo 'размер матрицы = '.($_SERVER['n_count']+1).' x '.($_SERVER['n_count']+1);
echo '<br>матрица построена, количество операций = '.$_SERVER['operations_count'];
echo '<br><table>'.implode('',$rows).'</table>';
exit();
}
Вот такое чудовище получилось. Кол-во операций: 1336 (Но тут стоит перепроверить правильность суждений). Для сравнения: здесь я насчитал 1411 (Это число тоже требует перепроверки).
const int N = 13;
int countmin = 1;
int countmax = (N*N+N)/2+1;
int opcount = 6; // =, =, *, +, /, +
int M[N][N];
if (N%2) {
for (int i = 0; i < N; i++) {
opcount+=2; // i < N и (= на первой итерации и i++ на последующих)
bool dir = i%2;
opcount+=2; // i%2 и =
if (dir) {
M[i][0]=countmin++;
opcount+=4; // [], [], = и ++
int tmp = N-i;
opcount+=2; // N-i и =
if (i<tmp) {
for (int j = 1; j <= i; j++) {
opcount+=2; //j <= i и (= на первой итерации и j++ на последующих)
M[i-j][j]=countmin++;
M[i+j][N-j]=countmax++;
opcount+=11; // [],[],[],[], i-j, i+j, N-j, ++, ++, =, =
}
opcount+=2; //j <= i и j++ с той проверки где не было входа в цикл
for (int j = i+1; j < tmp; j++) {
opcount+=2; //j < tmp и (= на первой итерации и j++ на последующих)
M[i+j][N-j]=countmax++;
opcount+=6; // [], [], i+j, N-j, =, ++
}
opcount+=3; // j < tmp и j++ с той проверки
//где не было входа в цикл и i+1
} else {
for (int j = 1; j < tmp; j++) {
opcount+=2; //j < tmp и (= на первой итерации и j++ на последующих)
M[i-j][j]=countmin++;
M[i+j][N-j]=countmax++;
opcount+=11; // [],[],[],[], i-j, i+j, N-j, ++, ++, =, =
}
opcount+=2; // j < tmp и j++ с той проверки где не было входа в цикл
for (int j = tmp; j <= i; j++) {
opcount+=2; //j <= i и (= на первой итерации и j++ на последующих)
M[i-j][j]=countmin++;
opcount+=5; // [], [], i-j, =, ++
}
opcount+=2; // j <= i и j++ с той проверки где не было входа в цикл
}
opcount+=2; // if (i<tmp)
} else {
M[0][i]=countmin++;
opcount+=4; // [], [], = и ++
int tmp = N-i;
opcount+=2; // N-i и =
if (i<tmp) {
for (int j = 1; j <= i; j++) {
opcount+=2; //j <= i и (= на первой итерации и j++ на последующих)
M[j][i-j]=countmin++;
M[N-j][i+j]=countmax++;
opcount+=11; // [],[],[],[], i-j, i+j, N-j, ++, ++, =, =
}
opcount+=2; // j <= i и j++ с той проверки где не было входа в цикл
for (int j = i+1; j < tmp; j++) {
opcount+=2; //j < tmp и (= на первой итерации и j++ на последующих)
M[N-j][i+j]=countmax++;
opcount+=6; // [], [], i+j, N-j, =, ++
}
opcount+=3; // j < tmp и j++ с той проверки
//где не было входа в цикл и i+1
} else {
for (int j = 1; j < tmp; j++) {
opcount+=2; //j < tmp и (= на первой итерации и j++ на последующих)
M[j][i-j]=countmin++;
M[N-j][i+j]=countmax++;
opcount+=11; // [],[],[],[], i-j, i+j, N-j, ++, ++, =, =
}
opcount+=2; // j < tmp и j++ с той проверки где не было входа в цикл
for (int j = tmp; j <= i; j++) {
opcount+=2; //j <= i и (= на первой итерации и j++ на последующих)
M[j][i-j]=countmin++;
opcount+=5; // [], [], i-j, =, ++
}
opcount+=2; // j <= i и j++ с той проверки где не было входа в цикл
}
opcount+=2; // if (i<tmp)
}
opcount+=1; //if (dir)
}
opcount+=2; // i < N и i++ с той проверки где не было входа в цикл
} else {
for (int i = 0; i < N; i++) {
opcount+=2;
bool dir = i%2;
opcount+=2;
if (dir) {
M[i][0]=countmin++;
opcount+=4;
int tmp = N-i;
opcount+=2;
if (i<tmp) {
for (int j = 1; j <= i; j++) {
opcount+=2;
M[i-j][j]=countmin++;
M[N-j][i+j]=countmax++;
opcount+=11;
}
opcount+=2;
for (int j = i+1; j < tmp; j++) {
opcount+=2;
M[N-j][i+j]=countmax++;
opcount+=6;
}
opcount+=3;
} else {
for (int j = 1; j < tmp; j++) {
opcount+=2;
M[i-j][j]=countmin++;
M[N-j][i+j]=countmax++;
opcount+=11;
}
opcount+=2;
for (int j = tmp; j <= i; j++) {
opcount+=2;
M[i-j][j]=countmin++;
opcount+=5;
}
opcount+=2;
}
opcount+=2;
} else {
M[0][i]=countmin++;
opcount+=4;
int tmp = N-i;
opcount+=2;
if (i<tmp) {
for (int j = 1; j <= i; j++) {
opcount+=2;
M[j][i-j]=countmin++;
M[i+j][N-j]=countmax++;
opcount+=11;
}
opcount+=2;
for (int j = i+1; j < tmp; j++) {
opcount+=2;
M[i+j][N-j]=countmax++;
opcount+=6;
}
opcount+=3;
} else {
for (int j = 1; j < tmp; j++) {
opcount+=2;
M[j][i-j]=countmin++;
M[i+j][N-j]=countmax++;
opcount+=11;
}
opcount+=2;
for (int j = tmp; j <= i; j++) {
opcount+=2;
M[j][i-j]=countmin++;
opcount+=5;
}
opcount+=2;
}
opcount+=2;
}
opcount+=1;
}
opcount+=2;
}
opcount+=2; // N%2 и if