Страница 1 из 1
Задача на линеаризацию и обход матрицы
Добавлено: 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.а что дальше делать не знаю..
Re: Задача на линеаризацию и обход матрицы.I Need Help!!!
Добавлено: 21 дек 2007, 11:34
WinMain
На самом деле алгоритм обхода матрицы зигзагом (или "змейкой") не такой уж сложный. Просто если у тебя нет опыта, то сам ты вряд ли его осилишь за короткое время. Лучше обратись к опытным программистам и за умеренную плату тебе сделают программу целиком.
Re: Задача на линеаризацию и обход матрицы.I Need Help!!!
Добавлено: 21 дек 2007, 12:17
Romeo
Если ты хочешь не готовую программу, а тебе важно разобраться самому, то вот один из вариантов решения, пришедших в голову сразу же:
- Должен быть цикл по t от 1 до n включительно.
- В цикле мы должны выделить два элемент матрицы [n-t][n-1] и [n-1][n-t] и обеспечить циклический проход от одного элемента до другого.
- Направление прохода зависит от чётности t.
- Во время прохода в цикле должны меняться i и j одновременно, один индекс увеличиваться, другой уменьшаться. Кто именно будет увеличиваться, а кто уменьшаться зависит от направления прохода.
- Этот алгоритм пройдёт половину матрицы (по вспомагательную диагональ включительно), анологичным образом нужно составить алгоритм для прохождения оставшихся элементов матрицы.
Если возникнут вопросы - обращайся.
Re: Задача на линеаризацию и обход матрицы.I Need Help!!!
Добавлено: 21 дек 2007, 12:45
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
Если тебе нужно обходить матрицу в обратном порядке, то можно просто вывести конечный массив в обратном порядке, т.е. начиная с последнего элемента...
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!!!
Добавлено: 21 дек 2007, 21:09
Artem18
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!!!
Добавлено: 25 дек 2007, 11:08
WinMain
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!!!
Добавлено: 18 май 2009, 10:07
Hose
У меня похожая проблема, но вывести нужно змейкой, предварительно отсортировав вставками.
Код: Выделить всё
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;
С выводом змейкой возникли проблемы.
Схема вывода в аттаче. Помогите, плиз