Помогите пожалуйста с задачей по С

-Alexey- · 23.04.2009

Помогите пожалуйста с задачей по С

Такая вот задачка:
Создать квадратную матрицу целых чисел размером 9х9. Заполнить матрицу линейной последовательностью (имеется в виду последовательность: 1, 2, 3,), от центра по спирали: влево - вниз - вправо - вверх.
Посилання видалено

AposTol · 23.04.2009

Я бы сделал так:
1. Определить последнюю цифру (будем двигаться с конца)
2. Заполнить массив нулями
3. Задать действия для движения в любом из направлений
3.1. Для каждого направления заполнять массив числом из счётчика, постепенно уменьшая его значение. Крутить цикл до тех пор, пока следующее значение ячейки не будет >0 или пока не достигнут край массива. Затем сменить направление и повторить теже действия.
4. Определить последовательность поворотов: на рисунке видно, что заполнение идёт против часовой стрелки (двигаясь с конца, заполнение будет идти по часовой, соответственно). Таким образом, есть чёткая последовательность направлений, одинаковая на каждом шаге.

Ну, это в принципе и всё.. По крайней мере я это себе так представляю...

BFG-9000 · 23.04.2009

Код:

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

int main(int argc, char* argv[])
{
	int m[9][9];
	
	int ir,il,jt,jb,i,j;
	ir=il=jt=jb=i=j=4;
	int cnt=1;
	m[j][i] = cnt; cnt++;
	for (;il>0 && ir<8 && jt>0 && jb<8;)
	{
	    il--;
	    for (i--;i>=il; i--) { m[j][i] = cnt; cnt++; }
	    i++;
	    jb++;
	    for (j++;j<=jb; j++) { m[j][i] = cnt; cnt++; }
	    j--;
	    ir++;
	    for (i++;i<=ir; i++) { m[j][i] = cnt; cnt++; }
	    i--;
	    jt--;
	    for (j--;j>=jt; j--) { m[j][i] = cnt; cnt++; }
	    j++;
	}
        for (i--;i>=il; i--) { m[j][i] = cnt; cnt++; }


	for (int q=0; q<9; q++) 
	{
		for (int w=0; w<9; w++) printf("%2d  ",m[q][w]);
		printf("\n");
	}
	getchar();
	return 0;
}

eyeland · 25.04.2009

Код:

#include <stdio.h>

int main (int argc, char* argv[])
{
    int m[9][9];
    int n = 81;
    int a, i, j, x;
    int xy[2] = {0, 0};
    int id[2] = {1, -1};

    for(x = 8; x > 0; x-=2) {  
        for(i = 0; i < 2; i++)
            for(j = 0; j < 2; j++)
                for(a = 0; a < x; a++) {  
                    m[xy[1]][xy[0]] = n--;
                    xy[j] += id[i];
                }
        xy[0]++;
        xy[1]++;
    }

    m[4][4] = 1; // последний штрих =)

    for(i = 0; i < 9; i++) {  
        for(j = 0; j < 9; j++)
            printf("%02d ", m[i][j]);
        printf("\n");
    }
    getchar();
    return(0);
}

попробуй разберись как он работает =) такое проще написать чем прочитать =)))

One_from_PPL · 25.04.2009

-Alexey-, а где же Ваш вариант решения/размышления по этой лабе первого курса?

-Alexey- · 26.05.2009

Теперь ту же программу надо переделать под указатели, чтоб работала с матрицей любой размерности.
Я переделал, но работает не совсем корректно (например с размерностью 11). Помогите найти ошибку.

Код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>


int main()
{
    int razmer=0;
	int** m;
	int cnt=1;
	int ir,il,jt,jb,i,j,w,q;

	clrscr();
	printf("Vvedite razmer:");
	scanf("%d", &razmer);
	m=(int**)malloc(razmer);
	ir=il=jt=jb=i=j=razmer/2;

	m[j][i] = cnt; cnt++;
	for (;il>0 && ir<razmer-1 && jt>0 && jb<razmer-1;)
	{
	    il--;
	    for (i--;i>=il; i--) { m[j][i] = cnt; cnt++; }
	    i++;
	    jb++;
	    for (j++;j<=jb; j++) { m[j][i] = cnt; cnt++; }
	    j--;
	    ir++;
	    for (i++;i<=ir; i++) { m[j][i] = cnt; cnt++; }
	    i--;
	    jt--;
	    for (j--;j>=jt; j--) { m[j][i] = cnt; cnt++; }
	    j++;
	}
	for (i--;i>=il; i--) { m[j][i] = cnt; cnt++; }


	for (q=0; q<razmer; q++)
	{
		for (w=0; w<razmer; w++) printf("%2d  ",m[q][w]);
		printf("\n");
	}
	getch();
	free (m);
	return 0;
}

BFG-9000 · 27.05.2009

Она у тебя с любой матрицей работать не будет, не только с размерностью 11.
Проблема в недостаточном понимании сути указателей, указателей на указатели и разадресации указателей квадратными скобками

Ну а выделение блока памяти размером в razmer БАЙТОВ - это вообще писец.

Херня началась вот тут:
m=(int**)malloc(razmer);
Функция выделяет область в БАЙТАХ. А тебе надо выделить razmer УКАЗАТЕЛЕЙ (4-хбайтных чисел) на инты (от того что ты привел результат к указателю на указатель - размер блока памяти больше не стал):
m=(int**)malloc(razmer*sizeof(int *));
НО! Это только массив указателей на те места, в которых будут лежать строки нашего массива, т.е. выделяем еще отдельно каждую строку:
for(i=0; i<razmer; i++) m = (int *) malloc(razmer*sizeof(int));

Не забудь прочесть про функцию free() и освободить память.

Зато теперь мне легко и спокойно за свое будущее - с таким подрастающим поколением без куска хлеба не останусь и в глубокой старости

-Alexey- · 27.05.2009

Спасибо, буду разбираться...

eyeland · 27.05.2009

BFG-9000 сказав(ла):
Зато теперь мне легко и спокойно за свое будущее - с таким подрастающим поколением без куска хлеба не останусь и в глубокой старости

чтоб было спокойнее дадим готовое решение лол

Код:

int main (int argc, char* argv[])
{
    int razmer = atoi(argv[1]);
    int **m;
    int n = razmer * razmer;
    int a, i, j, x;
    int xy[2] = {0, 0};
    int id[2] = {1, -1};

    m = malloc(razmer * sizeof(int));
    for(i=0; i<razmer; i++)
        m[i] = malloc(razmer * sizeof(int));

    for(x = razmer - 1; x > 0; x-=2) {  
        for(i = 0; i < 2; i++)
            for(j = 0; j < 2; j++)
                for(a = 0; a < x; a++) {  
                    m[xy[1]][xy[0]] = n--;
                    xy[j] += id[i];
                }
        xy[0]++;
        xy[1]++;
    }

    m[razmer/2][razmer/2 - 1 + razmer % 2] = 1; // последний штрих =)

    for(i = 0; i < razmer; i++) {  
        for(j = 0; j < razmer; j++)
            printf("%02d ", m[i][j]);
        printf("\n");
    }
    getchar();
    return(0);
}

Дагот ур · 27.05.2009

о, конец года, сдаем курсачи...

ASokol · 27.05.2009

Вот вам еще решение, кто сделает изящнее?

Код:

int main(int argc, char *argv[])
{
  if (argc == 1) return 0;   
  int size = atoi(argv[1]) | 1;
  int array[size][size];  
  int indexx, indexy;
  int counter, step, iterator;

  indexx = indexy = (size / 2);
  counter = step = array[indexx][indexy] = 1;   
  
  while (counter <= size * size)
  {
        for (iterator = 0; iterator < step; iterator++)
            array[indexy][step & 1 ? --indexx : ++indexx] = ++counter;
        if (counter > size * size) break;
        for (iterator = 0; iterator < step; iterator++)
            array[step & 1 ? ++indexy : --indexy][indexx] = ++counter;
        step++;
  }
  
  for(indexx = 0; indexx < size; indexx++)
  {
               for(indexy = 0; indexy < size; indexy++)
                          printf("%02d ", array[indexx][indexy]);
               printf("\n");
  }
  system("pause");
  return 0;
}

Tempory Mea · 27.05.2009

ASokol сказав(ла):
...

Код:

... int size = atoi(argv[1]) | 1; int array[size][size]; ... }

Такое разве возможно? Лексический анализатор будет матерится на "невозможность использования в качестве значения размера массива неконстантного значения". Ну, или что-то в этом роде...
Надо так:

Код:

...
  int size=atoi(argv[1])|1;
  int* array=new(int[size][size]);
...

PS: А вообще - код классный, даже тернарные операции всунули

ASokol · 27.05.2009

Такое разве возможно?

Еще как возможно

Tempory Mea · 27.05.2009

Ну уже ж не один раз проверено

... Не знает компилятор, сколько ему памяти в стеке отпахать при инициализации приложения, не знает. Только динамически.
PS: Подразумевается "чистый" С или СРР.

ASokol · 27.05.2009

Tempory Mea сказав(ла):
Ну уже ж не один раз проверено... Не знает компилятор, сколько ему памяти в стеке отпахать при инициализации приложения, не знает. Только динамически.
PS: Подразумевается "чистый" С или СРР.

А кто сказал, что память должна выделяться при инициализации приложения? Тем более я массив через стек и не пихаю никуда. А вообще по хорошему, если нужна стабильная и неубиваемая программа, то ее нада переписать. Просто мне был интересен сам алгоритм заполнения.

А эта программа собирается и успешно выполняется с размерами массива до 10000 тысяч элементов (дальше уже падает где-то там). Компилятор MinGW.

Tempory Mea · 27.05.2009

ASokol сказав(ла):
А кто сказал, что память должна выделяться при инициализации приложения?..

Ваш же код и сказал. Ни K&R, ни VC++, ни GCC не позволил бы такое сделать.

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

Понятное дело, что значит в компиляторе дело... Интересно его препарировать как-то. Я так поняла, что этот MinGV ГНУтый, то есть добыть и пользовать можно бесплатно?

ASokol · 27.05.2009

Tempory Mea сказав(ла):
Ваш же код и сказал. Ни K&R, ни VC++, ни GCC не позволил бы такое сделать.

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

Проверил: Borland C++ Builder, MS Visual Studio начали ругаться. Честно говоря, все зависит от компилятора, а если еще С++ то и реализации конструктора.

Понятное дело, что значит в компиляторе дело... Интересно его препарировать как-то. Я так поняла, что этот MinGV ГНУтый, то есть добыть и пользовать можно бесплатно?

Можно, если вам для Windows, то есть Dev-C++ (офсайт компилятора Посилання видалено), в котором я это и написал. Для Linux - это gcc.

P.S. Дома ради интереса попробую скомпилить в gcc.

По сути, в винде у процесса есть 2 гигабайта пользовательской памяти, без всяких запросов на выделение памяти мы можем прочитать и записать любые данные в этом пространстве (если знаете, что делаете). А элемент массива в С, насколько я понимаю, лежит по адресу равному адресу первого элемента плюс смещение на количество элементов умноженных на размер элемента. Если будем делать это, как в моем примере, то компилятор вам не гарантирует сохранности этих данных, но нам ведь этого и не надо.

Tempory Mea · 27.05.2009

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

Runtime С выделяет для глобальных переменных (объявленных до открывающих скобок функции Маня) отдельные страницы памяти (сегмент __TEXT), а для того, что находится в скобках - в текущем стеке. Область данных чаще всего не трогается в течении всего времени выполнения, а вот стек - сами понимаете...

ASokol · 27.05.2009

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

Как и обещал, собрал в gcc вот это:

Код:

int main(int argc, char *argv[])
{
  if (argc == 1) return 0;   
  int size = atoi(argv[1]) | 1;
  int array[size][size];  
  int indexx, indexy;
  int counter, step, iterator;

  indexx = indexy = (size / 2);
  counter = step = array[indexx][indexy] = 1;   
  
  while (counter <= size * size)
  {
        for (iterator = 0; iterator < step; iterator++)
            array[indexy][step & 1 ? --indexx : ++indexx] = ++counter;
        if (counter > size * size) break;
        for (iterator = 0; iterator < step; iterator++)
            array[step & 1 ? ++indexy : --indexy][indexx] = ++counter;
        step++;
  }
  
  for(indexx = 0; indexx < size; indexx++)
  {
               for(indexy = 0; indexy < size; indexy++)
                          printf("%02d ", array[indexx][indexy]);
               printf("\n");
  }
  system("pause");
  return 0;
}

Собрал успешно, программа работает. Разница лишь в том, что винда выкатывает ошибку доступа к памяти уже в районе 20000 элементов, а линуха ошибку сегментирования послем миллиона. Еще пришлось включить stdlib.h и stdio.h в исходник: MinGW собирал и без них.
Система: Gentoo Linux (kernel 2.6.28-r1)
Компилятор: i686-pc-linux-gnu-4.1.2

BFG-9000 · 28.05.2009

Эххх, студиозусы. Вот наглядный пример зашоренного мышления, когда изгаляются над префиксно-постфиксными операторами, краткой записью проверки и т.д. вместо кардинального улучшения.
И даже в голову не приходит, как действительно сделать лучше.
Подсказываю - ПРЯМОЕ вычисление значений элементов, а не ерзанье по массиву