LINUX.ORG.RU

Заполнить матрицу по спирали

 , , , ,


2

2

Задача 2. Заполни матрицу

Олимпиада школьников по информатике 7-8(!!!) класс Задача 2. Заполни матрицу Научиться работать с матрицей, значит научиться, не только искать элементы, но и заполнять матрицу элементами Дано число n. Создайте матрицу A[2*n+1][2*n+1] и заполните ее по спирали, начиная с числа 0 в центральной клетке A[n+1][n+1]. Спираль выходит вверх, далее закручивается против часовой стрелки.

Формат входного файла Программа получает на вход одно число 1<n<255. Формат выходного файла Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Для n=2:

12 11 10 9 24

13 2 1 8 23

14 3 0 7 22

15 4 5 6 21

16 17 18 19 20

В принципе, решил. Но как-то мудрено для 7-8 класса.

int main (int   argc, char *argv[])
{
    int i;
    int j;

    int n=2;
    int size = 2*n+1;
    int (*data)[size] = malloc(sizeof(int[size][size]));

    memset(data, 0, sizeof(int[size][size]));

    int num = 0;
    i = j = n;

    for (int offset=1; offset<=size; offset++)
    {
        int sign = (offset % 2)?-1:1;

        for(int di=1; di<= offset; di++)
        {
            i += sign;
            if(i<0)
                goto exit_;
            data[i][j] = ++num;
        }

        for(int dj=1; dj<= offset; dj++)
        {
            j += sign;
            if(j<0)
                goto exit_;
            data[i][j] = ++num;
        }
    }
exit_:
    ;
    for(i=0;i<size;i++)
    {
        for(j=0;j<size;j++)
            printf("%3i ", data[i][j]);

        printf("\n");
    }

    free(data);
}

Как сделать проще и понятней для школьника 7-8 класса?


Код предельно понятен. Они ж там не совсем дебилы.

Chaser_Andrey ★★★★★ ()

c

олимпиада

здесь кроется главная проблема

f1u77y ★★★ ()

offset % 2

offset & 1 же

goto exit_

Сделай отдельную ф-ю которая печатает массив, вызывай ее и делай return 0. Или сделай offset = size + 1 и break. Все что угодно, но не goto.

C
malloc
указатели

А чем не угодил C++ и std::vector ?

for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
printf(«%3i », data[j]);

printf(«\n»);
}

А заодно это можно переписать будет через std::transform и std::accumulate

Balantay ()

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

Balantay ()
Ответ на: комментарий от Balantay

В условии чётко требуется:

заполните ее по спирали, начиная с числа 0 в центральной клетке

gag ★★★★★ ()
Ответ на: комментарий от Balantay

offset & 1 же

Это полезно только в самой часто исполняемой части кода, а так для лучшего понимания и меньшего количества ошибок с приоритетами лучше писать offset % 2. И ИМХО в данно случае лучше sign вынести за цикл, и на кажой итерации делать sign = -sign

Все что угодно, но не goto

goto бывает вполне полезно для выхода из вложенного цикла, что собсна и сделал ТС

f1u77y ★★★ ()
Ответ на: комментарий от gag

В условии чётко требуется вывести заполненную по спирали матрицу. А по поводу того, как ее получать, в условии ничего не сказано, так что он прав

f1u77y ★★★ ()
Ответ на: комментарий от Balantay

а остальные будут рать слишком много памяти

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

f1u77y ★★★ ()

за goto бить по рукам.

Простой алгоритм может выглядеть так: определяем последнее число в спирали, его положение, и направление движения. Идем по прямой в обратном порядке, когда натыкаемся на препятствие (край или уже заполненную клетку) - поворачиваем.

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

anonymous ()

нарешался в свое время подобных задачек - просто чтобы руку набить на разных языках. Помню что решал с переменной определяющей направление движения по матрице)))

saibogo ★★★ ()
Ответ на: комментарий от Balantay

offset % 2

offset & 1 же

Любой адекватный компилятор превращает первое во второе.

Все что угодно, но не goto.

От фобий надо лечиться.

utf8nowhere ★★ ()
Ответ на: комментарий от saibogo

Помню что решал с переменной определяющей направление движения по матрице)))

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

anonymous ()

Как сделать проще и понятней для школьника 7-8 класса?

Разбить на простые функции с понятными названиями.

anonymous ()
Ответ на: комментарий от f1u77y

Олимпиада школьников по информатике

здесь кроется главная проблема

судя по треду на ЛОР: вот и выросло поколение, которое не понимает математику :-(

hint: числа в диагоналях легко рассчитываются, а вертикали/горизонтали +-1 от соседа.

MKuznetsov ★★★★★ ()
Ответ на: комментарий от XMs

Вот он

5.1.2.2.3 Program termination
1 If the return type of the main function is a type compatible with int, a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

utf8nowhere ★★ ()

а не проще, тупо четыре цикла сделать, без всяких sign, goto?

for (i = n; i >= 0; --i) {
  for (j = i; j < size - i - 1; ++j) data[i][size - j - 2] = ++num;
  for (j = i; j < size - i - 1; ++j) data[j + 1][i] = ++num;
  for (j = i; j < size - i - 1; ++j) data[size - i - 1][j + 1] = ++num;
  for (j = i; j < size - i - 1; ++j) data[size - j - 2][size - i - 1] = ++num;
}
anonymous ()

на паскакале такое делали. Да, в 8 классе. Решается просто.

anonymous ()
Ответ на: комментарий от f1u77y

Если задача решается с использованием О(1) памяти - то любое нормальное жюри олимпиады поставит как раз такие ограничения на память, чтобы n2 уж точно не прошел

Balantay ()
Ответ на: комментарий от Balantay

Смотря какая это по порядку задача, в общем-то, и на какой олимпиаде. В любом случае, даже если требуется решение за O(1) памяти, то это самый максимум уровня примерно 2 задачи региона. Не видел олимпиад по информатике конкретно для 7-8 класса, к слову

f1u77y ★★★ ()
Ответ на: комментарий от MKuznetsov

вот и выросло поколение, которое не понимает математику :-(

не юзает, когда явно не сказано(например, что у нас оч мало памяти) – не значит, что не знает

f1u77y ★★★ ()
int (*data)[size] = malloc(sizeof(int[size][size]));
memset(data, 0, sizeof(int[size][size]));

Если потом обнуляешь, то почему не calloc?

С другой стороны, memset не нужен, потому что ты всё равно все ячейки заполняешь.

Два внутренних цикла достаточно похожи, не думаешь объединить?

Deleted ()
Ответ на: комментарий от f1u77y

не юзает, когда явно не сказано(например, что у нас оч мало памяти) – не значит, что не знает

знают не значит что понимают и умеют применять...как гордая птица ёжЪ - «пока не пнёшь, не полетит» :-) Формулы как-раз они все помнят назубок, только куда эти ф-лы деть не знают

в алгоритме расходы по памяти в общем-то непричём..надо заполнить матрицу NxN - значит мин.ограничение по памяти N^2 :-) А подумать про то что диагонали и центральные вертикали/горизонтали элементарно вычисляются это сверх усилие..заметить симметрию это вообще за гранью реальности..вообще в асимптоматике должно получаться всего 2 вложенных цикла - i от 1 до n-1 ; и j от 1 до i

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

значит мин.ограничение по памяти N^2

Нет же, можно юзануть формулу (i, j) члена матрицы, и получить O(1) памяти

f1u77y ★★★ ()
Ответ на: комментарий от f1u77y

Нет же, можно юзануть формулу (i, j) члена матрицы, и получить O(1) памяти

задача - заполнить матрицу. Если положить что матрица выделяется извне(то есть задача вычислить и заполнить), то во всех вышеприведённых по памяти O(1)..чтобы стало больше это надо как-то умело извратится

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

задача – вывести заполненную матрицу, для чего вовсе необязательно ее заполнять,можно поэлементно выводить f(i, j)

f1u77y ★★★ ()
Ответ на: комментарий от f1u77y

задача – вывести заполненную матрицу, для чего вовсе необязательно ее заполнять,можно поэлементно выводить f(i, j)

не фантазируйте. В topic дано «Задача 2. Заполни матрицу Научиться работать с матрицей, значит научиться, не только искать элементы, но и заполнять матрицу элементами». Знать так оно и есть..то есть надо ещё читать ТЗ :-)

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

Формат входного файла

Формат выходного файла

это значит, что всем пофиг, что происходит в программе

f1u77y ★★★ ()
Ответ на: комментарий от MKuznetsov

Это школьная олимпиада. Там всегда всё просто: читаешь input.txt, выводишь в output.txt. Код никто не смотрит. Требования два: уложиться во время и уложиться в память. Что внутри — не важно, лишь бы было в стандартной библиотеке допустимого языка.

evilface ★★ ()

Где вообще такие задачи применяются в реальной работе?

SjZ ★★★★★ ()

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

zudwa ()
Ответ на: комментарий от zudwa

Сформулирую вопрос по другому. Допустим, человек работает веб-программистом. Где в реальной рабочей задаче ему понадобится применить такой алгоритм и при этом еще и оказаться в такой ситуации, что метода, реализующего данный алгоритм, среди стандартных методов из библиотеки ЯП не окажется?

SjZ ★★★★★ ()
Ответ на: комментарий от SjZ

Сформулирую вопрос по другому. Допустим, человек работает веб-программистом. Где в реальной рабочей задаче ему понадобится применить такой алгоритм и при этом еще и оказаться в такой ситуации, что метода, реализующего данный алгоритм, среди стандартных методов из библиотеки ЯП не окажется?

сформулирую вопрос совсем по другому : в которых библиотеках и каких ЯП есть стандартные методы реализующие такой алгоритм ? Особенно для веб :-)

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

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

Про стандартные это уже так, посредственный вопрос.

в которых библиотеках и каких ЯП есть стандартные методы реализующие такой алгоритм ?

Может быть на ruby можно написать такой гем и подключить его, есть ли в других ЯП подобная система - я точно не знаю, но, вероятно, есть (откуда-то явно сперли).

Главный то вопрос в другом.

SjZ ★★★★★ ()
Ответ на: комментарий от MKuznetsov

В topic дано

( f1u77y)

И мне так показалось. Надеялся, что ТС прокомментирует. Ведь можно было бы написать:

и заполните ее Матрица заполняется по спирали, начиная с числа 0 в центральной клетке A[n+1][n+1]

Сразу понятно, что это правило заполнения, но не требование делать точь-в-точь. А иначе воспринимается именно как требование.

gag ★★★★★ ()
Ответ на: комментарий от f1u77y

Интересно, а можно без формулы, но с curses.

gag ★★★★★ ()
Ответ на: комментарий от evilface

Жюри, которое дает столько памяти, ИМХО не должно проводить ничего и никогда. Хорошие ограничения по памяти позволяют отсечь не то что O(n2) при правильном О(1) - они ловят О(log n) vs О(1)

Balantay ()
Ответ на: комментарий от Balantay

при правильном О(1) - они ловят О(log n) vs О(1)

Какие-то у вас очень странные фантазии :)

Разница между O(1) и O(log N) десять раз покроется разницей между noop-программой на c и noop-программой на питоне.

vzzo ★★★ ()
Ответ на: комментарий от vzzo

А кто мешает сделать ограничение по времени, скажем, 10 секунд и дать тест с n ~ 1 000 000 ? На каждую хитрую гайку найдется своя контрагайка.

Balantay ()
Ответ на: комментарий от Balantay

То, что log(N) для миллиона это 20?

Или тут имеется в виду какое-нибудь O(K) vs O(KlogN), где K по условию задачи оценивается в десяток мегабайт?

Тогда мне нужен хотя бы отдалённый пример такой задачи. Единственная задача, содержательно зарезающая память, которую я знаю — это вот эта: https://www.e-olymp.com/ru/problems/3161. И ещё больше я знаю неудачных попыток её настроить так, чтобы неправильные решения не проходили, а правильные проходили.

vzzo ★★★ ()
Ответ на: комментарий от vzzo

Или тут имеется в виду какое-нибудь O(K) vs O(KlogN), где K по условию задачи оценивается в десяток мегабайт?

Да, имел в виду примерно это, просто неправильно сформулировал.

Пример задачи сходу на ум не приходит - олимпиадами давно уже не занимаюсь, но если вспомню - напишу.

Кстати, помнится задача похожая на ту, о которой этот топик на acmp.ru (вроде там, но не уверен) как раз таки падает если работать с массивом а не по формуле делать.

Balantay ()
Ответ на: комментарий от Balantay

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

evilface ★★ ()
Ответ на: комментарий от Balantay

Жюри, которое дает столько памяти, ИМХО не должно проводить ничего и никогда. Хорошие ограничения по памяти позволяют отсечь не то что O(n2) при правильном О(1) - они ловят О(log n) vs О(1)

I lold so hard!! ;3

Waterlaz ★★★★ ()
Ответ на: комментарий от Balantay

не должно проводить ничего и никогда

на олимпиадах для 7-8 классов не должно быть утешительных задач? или хотя бы баллов?

f1u77y ★★★ ()
Ответ на: комментарий от f1u77y

В условии чётко требуется вывести заполненную по спирали матрицу. А по поводу того, как ее получать, в условии ничего не сказано, так что он прав

Читать разучился?

Создайте матрицу A[2*n+1][2*n+1] и заполните ее по спирали, начиная с числа 0 в центральной клетке A[n+1][n+1].

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.