Матрица последовательных чисел

[Груша Вильямс]

Требуется определить общую формулу для чисел в ячейках матрицы `n times n` через соответствующие координаты ячеек `i` и `j`, где `i,j={0,1,2,...,n-1}`, при условии что числа последовательные и начинаются с 1.
Пример, матрица 3x3
123
456
789

@темы: Функции

Comments

[Дилетант]

Груша Вильямс, что-то я не поняла вопроса...
Вы вот про эту формулу?
`a_{ij}=n*i+(j+1)`

[Груша Вильямс]

Дилетант, быстро однако))) Про неё, а как её получить?

[Дилетант]

Груша Вильямс, как говорит All_ex, методом пристального вглядывания))
123
456
789
Мы видим, что для матрицы 3х3 элементы можно записать как:
0*3+1 0*3+2 0*3+3
1*3+1 1*3+2 1*3+3
2*3+1 2*3+2 2*3+3

Ну и делаем выводы )

[All_ex]

Дилетант,

...

как говорит All_ex, - ...

...

вглядывания - всматривания ...

[Дилетант]

All_ex,

всматривания ...

Ага. Пришла исправить, но не успела )))

[Груша Вильямс]

Дилетант, мощно конечно))
Да с этим поиском в ширину сижу всё, пытаюсь придумать как по-человечески его написать.
Проблема в том, что у меня идёт проверка каждой клетки, например, для 3x3, 9 проверок на возможный шаг, например, тот что под номером 2, затем опять 9 проверок на третий шаг и т.д. Просто ужасно, получается в общем случае n^2 проверок на шаг. А ужас ещё и в том, что у нас все так написали, где-то 50 человек
Хотя очевидно, что достаточно всего четырех проверок ведь начало то известно, а значит проверяем только соседей. Вот и пытаюсь что-то придумать. Идея следующая: создать еще одну матрицу, такую как тут (формула нужна собственно для того, чтоб не вручную числа в матрицу забивать, а по формуле в цикле), тогда у нас есть связь по и жи с исходной (попадаем в ту же ячейку) и с элементами самой матрицы(которые опять же имеют связь по и жи), потом думаю одномерный массив делать(там как раз эти 1,2,3, и тд) и между всеми этими вещами как-то манипулировать

[All_ex]

Груша Вильямс, Да с этим поиском в ширину сижу всё, пытаюсь придумать как по-человечески его написать.
когда-то на первом курсе писал программу с поиском в ширину... правда мне не число вариантов надо было искать, а просто кратчайший путь, но можно его модифицировать... использовал динамический массив ...
Заполняете матрицу нулями, а клетку начала единицей... и создаёте массив, котором сначала пишите номера (сточка;столбик) соседних с началом клеток...
Далее берёте элемент из очереди и добавляете в конец очереди её соседей с нулями... а в матрице для этой клетки пишите сумму всех соседей (их не более четырёх... тут нули ничего не испортят, а предшественники просуммируются)...
Далее этот элемент удаляется из очереди... так поступаете до тех пор пока не заполните клетку окончания...

простите, если объяснил опять неуклюже...

[All_ex]

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

[Груша Вильямс]

All_ex, хотелось бы без динамического массива, т.к. опыт работы с ним вблизи нуля, с другой стороны не так уж и отличается от обычного массива, а потому можно же и обычный объявить на n^2 элементов, чтоб наверняка? Переписать на динамический потом если что думаю проще пареной репы будет. Но честно говоря я так и не понял как это делают...и создаёте массив, котором сначала пишите номера (сточка;столбик) соседних с началом клеток то есть двумерный массив на 4 координаты правильно понимаю? Далее берёте элемент из очереди и добавляете в конец очереди её соседей с нулями а очередь это одномерный массив? Если да, то при инициализации туда нули пишем?

[Груша Вильямс]

All_ex, и создаёте массив, котором сначала пишите номера (сточка;столбик) соседних с началом клеток я понял так

[All_ex]

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

У Вас есть заполненная `(-1)` матрица (символ того, что клетки ещё не осмотрены...... и пока пустой одномерный массив...
Сначала в угол (начальная точка) ставится 1, а в очередь ставятся клетки `[1;0]` и `[0;1]` - попутно заполняя матрицу нулями на этих местах...
`((1,0,-1), (0,-1,-1), (-1,-1,-1))` и `([1;0]; \ [0;1])`...

Теперь берём первую клетку из очереди - (1;0) - и добавляем в очередь её соседей с минус единицами - `([0;1] ; \ [2;0]; \ [1;1])`...
Добавленные клетки заполняем нулями в матрице... `((1,0,-1), (0,0,-1), (0,-1,-1))`... и вычисляем сумму допустимых соседей для `[1;0]` ... `((1,0,-1), (1,0,-1), (0,-1,-1))`...

И так далее...

[Груша Вильямс]

All_ex, я Вас понял, подправил немного только
У Вас есть заполненная `(-1)` матрица (символ того, что клетки ещё не осмотрены...... и пока пустой одномерный массив...
Сначала в угол (начальная точка) ставится 1, а в очередь ставятся клетки `[1;0]` и `[0;1]` - попутно заполняя матрицу нулями на этих местах...
`((1,0,-1), (0,-1,-1), (-1,-1,-1))` и `([1;0]; \ [0;1])`...

Теперь берём первую клетку из очереди - (1;0) - и добавляем в очередь её соседей с минус единицами - `([0;2] ; \ [2;0]; \ [1;1])`...
Добавленные клетки заполняем нулями в матрице... `((1,0,0), (0,0,-1), (0,-1,-1))`... и вычисляем сумму допустимых соседей для `[1;0]` ... `((1,0,0), (1,0,-1), (0,-1,-1))`...
И так далее...
Но как это написать пока не знаю)
Зато придумал следующее:
- делаем функцию

соседей

(нэйбос по англ поэтому nerb назвал хотя пишется neighbors) (в ее задачу входит принять координаты старта, проверить соседей, поставить волны и слить их координаты в массив);
- теперь у нас есть массив с координатами и надо бы их как-то скармливать этой функции.
По сути рекурсия -- отправили координаты, получили новые, отправили их, опять получили новые и так до тех пор пока пустые соседи есть.

#include <stdio.h>
#include <locale.h>

int nerb(int x, int y, int matrix[4][4], int row1, int col1, int data[16][2], int row2, int col2){
	
		/* x = p = start[0] = 1
		   y = k = start[1] = 2 */
		  
		int point1[2] = {x - 1, y}; // тут записано что point1[2] = {0, 2} - то есть координаты клетки сверху
		int point2[2] = {x, y - 1}; // тут записано что point2[2] = {1, 1} - то есть координаты клетки слева
		int point3[2] = {x, y + 1}; // тут записано что point3[2] = {1, 3} - то есть координаты клетки справа
		int point4[2] = {x + 1, y}; // тут записано что point4[2] = {2, 2} - то есть координаты клетки снизу
		
		/* start-xy - волна вначале  */
		 
		int startxy = 0;
		int i = 1;
		int j = 0;
		if(matrix[point1[0]][point1[1]] == 0 && point1[0] >= 0){
			matrix[point1[0]][point1[1]] = startxy + 1;
			int done[1][2] = {point1[0], point1[1]};
			data[i][j] = done[0][0];
			data[i++][(j + 1) % 2] = done[0][1];
		}
		if(matrix[point2[0]][point2[1]] == 0 && point2[0] < 20){
			matrix[point2[0]][point2[1]] = startxy + 1;
			int done[1][2] = {point2[0], point2[1]};
			data[i][j] = done[0][0];
			data[i++][(j + 1) % 2] = done[0][1];
		}
		if(matrix[point3[0]][point3[1]] == 0 && point3[0] < 20){
			matrix[point3[0]][point3[1]] = startxy + 1;
			int done[1][2] = {point3[0], point3[1]};
			data[i][j] = done[0][0];
			data[i++][(j + 1) % 2] = done[0][1];
		}
		if(matrix[point4[0]][point4[1]] == 0 && point4[0] >= 0){
			matrix[point4[0]][point4[1]] = startxy + 1;
			int done[1][2] = {point4[0], point4[1]};
			data[i][j] = done[0][0];
			data[i++][(j + 1) % 2] = done[0][1];
			
		}
		printf("Matrix\n\n");
		for(i = 0; i < 4; i++)
			for(j = 0; j < 4; j++){
				printf("%d", matrix[i][j]);
				if((j+1)%4) printf("\t");
				else printf("\n");
			}
		printf("\n\nCoordinates\n\n");	
		for(i = 0; i < 16; i++)
			for(j = 0; j < 2; j++){
				printf("%d", data[i][j]);
				if((j+1)%2) printf("\t");
				else printf("\n");
			}
		
}

	
int main() {
	setlocale (LC_ALL, "Rus");
	
	int start[2] = {1, 2};
	int p,k;
	p = start[0];
	k = start[1];
		
		int u1 = 4;
		int v1 = 4;
		int array[u1][v1]; 
		int i,j;
		for(i = 0; i < u1; i++)
			for(j = 0; j < v1; j++) array[i][j] = 0;
		array[1][2] = -1;
			   
	int u = 16;
	int v = 2;
	int coordinates[u][v]; // Matrix 16
		coordinates[0][0] = start[0];
		coordinates[0][1] = start[1];
		for(i = 1; i < u; i++)
			for(j = 0; j < v; j++) coordinates[i][j] = 0;

	
	nerb(p, k, array, u1, v1, coordinates, u, v);
	
}

Первый шаг отлично вот выводит, только не понятно как вот тут сейчас иксу присвоить дэйта[1][0], а игрику дэйту[1][1] и в вайл бы прямо тут)

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

[All_ex]

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

С рекурсией - тоже не понял пока идеи... ... если Вы уже создали массив, то идёт просто перебор по всем клетками по очереди...

но всё же...

Но по итогу я бы рекомендовал познакомится с динамическими массивами... сложного там ничего нет...
Правда, я это делал 27 лет назад, и уже сам немного подзабыл порядок описания...
Создаёте новый тип, в котором есть поле со значением, и ссылка на массив ссылок (на соседей)... тут вам первое удобство - если ссылки на соседа нет, значит переход заблокирован... а, во-вторых, можно рассматривать произвольные графы, а не только матрицы... ведь алгоритм поиска никак не изменится...

Затем всё по описанному выше алгоритму... начальная клетка заполнена.... создали "очередь" из её соседей... у соседей нарисовали нули...
Дальше идёт цикл по "очереди соседей", пока очередь не закончится...
тут делаете три действия: 1) добавляем новых соседей в очередь, 2) обнуляем значения новых соседей, 3) вычисляем сумму для рассматриваемой клетки (тут просто суммируем по всем ссылкам на соседей) ...
переходим к новому элементу очереди...

[Груша Вильямс]

All_ex, создавать весь массив не шибко рационально... да я пока хочу просто осуществить это, выражаясь математически - показать, что код существует))
С рекурсией - тоже не понял пока идеи... а вот кстати написать удалось, правда штук 8 глобальных переменных добавить пришлось, но насколько я понимаю пока программирование, то если пишется на глобальных, значит пишется и на локальных, правда писал программы только по учебе и всегда вроде бы удавалось и так, и эдак. Собственно упростить код ещё не пытался (то есть полностью согласен, что он мягко говоря сыроват) и, более того, на правильность не проверял, но вроде б работает
Рекурсия

#include <stdio.h>
#include <locale.h>

/* Глобальные переменные */
int var = 1; // под итую координату массива координат 
int sar = 0; // под житую координату массива координат
int wave = 0; // под нумерацию волн
int flag = 0;
int shift = 0; // переменная сдвига
int count = 1; // счётчик волн
int memory = 0; // память 
int iterator = 0;

/* Функция соседей */
int nerb(int x, int y, int matrix[4][4], int row1, int col1, int data[16][2], int row2, int col2){
	
		/* x = p = start[0] = 1
		   y = k = start[1] = 2 */
		  
		int point1[2] = {x - 1, y}; // тут записано что point1[2] = {0, 2} - то есть координаты клетки сверху
		int point2[2] = {x, y - 1}; // тут записано что point2[2] = {1, 1} - то есть координаты клетки слева
		int point3[2] = {x, y + 1}; // тут записано что point3[2] = {1, 3} - то есть координаты клетки справа
		int point4[2] = {x + 1, y}; // тут записано что point4[2] = {2, 2} - то есть координаты клетки снизу
		
		
		int allwave = 0;
		
		if(matrix[point1[0]][point1[1]] == 0 && point1[0] >= 0){
			matrix[point1[0]][point1[1]] = wave + 1;
			allwave++;
			int done[1][2] = {point1[0], point1[1]};
			data[var][sar] = done[0][0];
			data[var][(sar + 1) % 2] = done[0][1];
			var++;
		}
		if(matrix[point2[0]][point2[1]] == 0 && point2[1] >= 0){
			matrix[point2[0]][point2[1]] = wave + 1;
			allwave++;
			int done[1][2] = {point2[0], point2[1]};
			data[var][sar] = done[0][0];
			data[var][(sar + 1) % 2] = done[0][1];
			var++;
		}
		if(matrix[point3[0]][point3[1]] == 0 && point3[1] < 4){
			matrix[point3[0]][point3[1]] = wave + 1;
			allwave++;
			int done[1][2] = {point3[0], point3[1]};
			data[var][sar] = done[0][0];
			data[var][(sar + 1) % 2] = done[0][1];
			var++;
		}
		if(matrix[point4[0]][point4[1]] == 0 && point4[0] < 4){
			matrix[point4[0]][point4[1]] = wave + 1;
			allwave++;
			int done[1][2] = {point4[0], point4[1]};
			data[var][sar] = done[0][0];
			data[var][(sar + 1) % 2] = done[0][1]; 
			var++;	
		}
		if((iterator - shift) % count == 0){
			wave++; 
			if(flag == 0){
				count = allwave;
				flag = 1;
			} 
			else {
				shift = count;
				memory = memory + allwave;
				count = memory;
				memory = 0;
			}
		} 
		else memory = memory + allwave;
		
		iterator++;
		
		int i,j;
		printf("Matrix\n\n");
		for(i = 0; i < 4; i++)
			for(j = 0; j < 4; j++){
				printf("%d", matrix[i][j]);
				if((j+1)%4) printf("\t");
				else printf("\n");
			}
		printf("\n\nCoordinates\n\n");	
		for(i = 0; i < 16; i++)
			for(j = 0; j < 2; j++){
				printf("%d", data[i][j]);
				if((j+1)%2) printf("\t");
				else printf("\n");
			}
		
}

	
int main() {
	setlocale (LC_ALL, "Rus");
	
	int start[2] = {1, 2};
	int p,k;
	p = start[0];
	k = start[1];
		
		int u1 = 4;
		int v1 = 4;
		int array[u1][v1]; 
		int i,j;
		for(i = 0; i < u1; i++)
			for(j = 0; j < v1; j++) array[i][j] = 0;
		array[1][2] = -1;
			   
	int u = 16;
	int v = 2;
	int coordinates[u][v]; // Matrix 16
		coordinates[0][0] = start[0];
		coordinates[0][1] = start[1];
		for(i = 1; i < u; i++)
			for(j = 0; j < v; j++) coordinates[i][j] = 0;

	
	//nerb(p, k, array, u1, v1, coordinates, u, v);
	
	for(i = 0; i < 12; i++)
		for(j = 0; j < 1; j++)
			nerb(coordinates[i][j], coordinates[i][(j + 1) % 2], array, u1, v1, coordinates, u, v);
			
}

[All_ex]

Груша Вильямс, Собственно упростить код ещё не пытался (то есть полностью согласен, что он мягко говоря сыроват)
Честно признаться, я так и не выучил С++ (писал на паскале)... ... поэтому с моей стороны тут критики нет...