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 класса?


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

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

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

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

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

Не то, что PHP. Есть везде, где не погляди.

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

Как формат выходного файла отменяет четкие и конкретные указания на то, что должна делать программа?

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

Пусть решающий сам максимально решает что и как его программа должна делать, иначе мало творчества и смысла.

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

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

четкие и конкретные указания на то, что должна делать программа

сразу видно того, кто только понаслышке знает, что такое олимпиада школьников по информатике(это[знать только понаслышке] не есть что-то плохое)

f1u77y ★★★★
()
Последнее исправление: f1u77y (всего исправлений: 1)
Ответ на: комментарий от f1u77y

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

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

думаешь что все обязаны знать всё то, что ты знаешь

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

f1u77y ★★★★
()
Последнее исправление: f1u77y (всего исправлений: 1)
Ответ на: комментарий от f1u77y

При чем тут «понаслышке»? У нас конкретный текст конкетного задания. В этом задании четко указано, что нужно делать. Более того - это, очевидно, именно задание на то, чтобы описать алгоритм и не запутаться. Тот кто считил и дал простую реализацию - просто его не выполнил по факту.

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

В этом задании четко указано, что нужно делать

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

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

f1u77y ★★★★
()

А что тут объяснять? Если они не умеют программировать, начинай с задач попроще. Если умеют — ну код вроде без особых изысков, что тут может быть непонятного. Я бы по-другому сделал, внешний цикл идёт от 0 до m*m-1, а в теле цикла уже спиралью ползут координаты меняя направление, но суть та же.

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

насколько эти олимпиады вообще кому-то нужны в реальной жизни.

кстати, да: зачем в реальной жизни прыгать в длину 6 метров, в высоту 2 метра... или кидать копьё, вообще?

P.S. пользуясь случаем, предлагаю обсудить отличия спорта от физкультуры

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

Как формат выходного файла отменяет четкие и конкретные указания на то, что должна делать программа?

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

Pythagoras ★★
()
Последнее исправление: Pythagoras (всего исправлений: 2)
Ответ на: комментарий от Pythagoras

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

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

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

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

Их никогда не описывают

Но здесь они описаны.

так как весь смысл - найти правильный алгоритм

Здесь задача именно на написание алгоритма обхода по спирали. По-этому попытка вместо этого просто посчитать по формуле значения - это чит и невыполнение задачи.

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

Но здесь они описаны.

Это только так кажется.

Здесь задача именно на написание алгоритма обхода по спирали.

Нет, это только кажется. Олимпиадные зажачи всегда требуют смекалки и творческого подхода. Делать «в лоб» - не правильно.

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