Задача на линеаризацию и обход матрицы

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ
Обзор темы
   

Развернуть Обзор темы: Задача на линеаризацию и обход матрицы

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

Hose » 18 май 2009, 10:07

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

Код: Выделить всё

    
    int n = 5;
    int i, j, k, m, size, temp;
    int array[n][n];
    
    // задаем массив
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            array[i][j] = rand() % 10;
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    
    size = n*n; 
    
    // сортируем вставками
    for (i = 1; i < size; i++) {
	    temp = array[i/n][i%n];
	    for (j = i - 1; j >= 0; j--) {
	    	if (array[j/n][j%n] < temp) {
		    	break;
	         }
	         array[(j+1)/n][(j+1)%n] = array[j/n][j%n];
        }
	    array[(j+1)/n][(j+1)%n] = temp;
     }

    // выводим массив
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++)
            cout << array[i][j] << " ";
        cout << endl;
    }
    cout << endl;
С выводом змейкой возникли проблемы.
Схема вывода в аттаче. Помогите, плиз :)

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

WinMain » 25 дек 2007, 11:08

Artem18 писал(а): Как правильно изменить данный код, чтобы при вводе матрицы
7 4 2 1
11 8 5 3
14 12 9 6
16 15 13 10

выводилась строка 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ?

Код: Выделить всё

	// Обход матрицы зигзагом по диагонали c правого верхнего угла...
	int M[N*N], a = 0;	// массив чисел на выходе
	for (int L = 1, C = N; L < N*2; L++, C--)
	{
		int P = (L <= N)? L : 2*N-L;	// число элементов в диагонали
		for (int i = 0; i < P; i++)
		{
			if (L&1)	// если диагональ нечетная
			{
				M[a++] = (L <= N)? C+(P-i-1)*(N+1) : C+(N-i-1)*(N+1);		 
			} else
			{
				M[a++] = (L <= N)? C+i*(N+1) : C+(L-N+i)*(N+1);
			}
		}
	}
Можно не менять сам алгоритм, а предварительно перевернуть слева направо саму матрицу.

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

Artem18 » 21 дек 2007, 21:09

WinMain писал(а):Вот этот алгоритм...

Код: Выделить всё

#include <tchar.h>
#include <stdio.h>

const int N = 4;	// Размерность матрицы (N*N)

int _tmain(int argc, _TCHAR* argv[])
{
	// Исходная матрица...
	for (int y = 0; y < N; y++)
	{
		for (int x = 1; x <= N; x++)
		{
			_tprintf(_T("%2d  "), y*N+x);
		}
		_tprintf(_T("\n"));
	}
	_tprintf(_T("\n"));
	// Вывод чисел зигзагом по диагонали c левого верхнего угла...
	int M[N*N], a = 0;	// массив чисел на выходе
	for (int L = 1; L < N*2; L++)
	{
		int P = (L <= N)? L : 2*N-L;	// число элементов в диагонали
		for (int i = 0; i < P; i++)
		{
			if (L&1)	// если диагональ нечетная
			{
				M[a++] = (L <= N)? L+(P-i-1)*(N-1) : L+(N-i-1)*(N-1);		 
			} else
			{
				M[a++] = (L <= N)? L+i*(N-1) : L+(L-N+i)*(N-1);
			}
		}
	}
	// Вывод на экран...
	for (int n = 0; n < N*N; n++)
	{
		_tprintf(_T("%d "), M[n]);
	}
	_tprintf(_T("\n"));
	//
	return 0;
}
Результат работы программы будет таким:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

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

Как правильно изменить данный код, чтобы при вводе матрицы
7 4 2 1
11 8 5 3
14 12 9 6
16 15 13 10

выводилась строка 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ?

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

Илл » 21 дек 2007, 19:55

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

Код: Выделить всё

#include<stdio.h>
int i,j,n,t;
int k=1;
int m[10][10];
int b[100];
main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
scanf("%d",&m[i][j]);}
i=n;
j=n;
while((i!=1)&&(j!=1))
{
for(t=2;t<(n*n);t++)
{
if((i>n)&&(j<n))
{
i=i+1-k;
j=j-1;}
else if((i<n)&&(j<n))
{
i=i+k;
j=j+k;
k=k*(-1);}
else if((j>n)&&(i<n))
{
i=i-k;
j=j+1-k;
}
else if((i>n)&&(j>n))
{
i=i+1-k;
j=j-k;}
}
for(t=0;t<=(n*n);t++)
printf("%d",b[t]);
}}

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

WinMain » 21 дек 2007, 12:45

Вот этот алгоритм...

Код: Выделить всё

#include <tchar.h>
#include <stdio.h>

const int N = 4;	// Размерность матрицы (N*N)

int _tmain(int argc, _TCHAR* argv[])
{
	// Исходная матрица...
	for (int y = 0; y < N; y++)
	{
		for (int x = 1; x <= N; x++)
		{
			_tprintf(_T("%2d  "), y*N+x);
		}
		_tprintf(_T("\n"));
	}
	_tprintf(_T("\n"));
	// Вывод чисел зигзагом по диагонали c левого верхнего угла...
	int M[N*N], a = 0;	// массив чисел на выходе
	for (int L = 1; L < N*2; L++)
	{
		int P = (L <= N)? L : 2*N-L;	// число элементов в диагонали
		for (int i = 0; i < P; i++)
		{
			if (L&1)	// если диагональ нечетная
			{
				M[a++] = (L <= N)? L+(P-i-1)*(N-1) : L+(N-i-1)*(N-1);		 
			} else
			{
				M[a++] = (L <= N)? L+i*(N-1) : L+(L-N+i)*(N-1);
			}
		}
	}
	// Вывод на экран...
	for (int n = 0; n < N*N; n++)
	{
		_tprintf(_T("%d "), M[n]);
	}
	_tprintf(_T("\n"));
	//
	return 0;
}
Результат работы программы будет таким:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

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

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

Romeo » 21 дек 2007, 12:17

Если ты хочешь не готовую программу, а тебе важно разобраться самому, то вот один из вариантов решения, пришедших в голову сразу же:

- Должен быть цикл по t от 1 до n включительно.
- В цикле мы должны выделить два элемент матрицы [n-t][n-1] и [n-1][n-t] и обеспечить циклический проход от одного элемента до другого.
- Направление прохода зависит от чётности t.
- Во время прохода в цикле должны меняться i и j одновременно, один индекс увеличиваться, другой уменьшаться. Кто именно будет увеличиваться, а кто уменьшаться зависит от направления прохода.
- Этот алгоритм пройдёт половину матрицы (по вспомагательную диагональ включительно), анологичным образом нужно составить алгоритм для прохождения оставшихся элементов матрицы.

Если возникнут вопросы - обращайся.

Re: Задача на линеаризацию и обход матрицы.I Need Help!!!

WinMain » 21 дек 2007, 11:34

На самом деле алгоритм обхода матрицы зигзагом (или "змейкой") не такой уж сложный. Просто если у тебя нет опыта, то сам ты вряд ли его осилишь за короткое время. Лучше обратись к опытным программистам и за умеренную плату тебе сделают программу целиком.

Задача на линеаризацию и обход матрицы

Илл » 21 дек 2007, 11:17

здравствуйте!!
долго мучаюсь с программой, но никак не получается придумать как этот самый обход матрицы воспроизвести.
вообще программа должна считывать квадратную матрицу и выводить ее элементы в строку,в определенном порядке....
в моем случае при вводе матрицы:
16 15 11 10
14 12 9 4
13 8 5 3
7 6 2 1
выводиться должна строка 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16.
с вводом матрицы проблем не возникло:

Код: Выделить всё

#include<stdio.h>
#define N 100
long i,j,n,k;
main(){
long m[N][N];
scanf("%ld",&n);
getchar();
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
scanf("%ld\t",&m[i][j]);
getchar();}
наверное надо начинать с элемента 4,4.а что дальше делать не знаю.. :(

Вернуться к началу