ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Задачка про поиск в матрице
28 сообщений из 28, показаны все 2 страниц
  все  
Задачка про поиск в матрице
    #39240938
cpp22
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cpp22
Гость
Здравствуйте.
Задача:
Есть матрица 6*6, нужно проверить есть ли в ней последовательность из 4-х одинаковых элементов. Последовательность может быть по вертикали/горизонтали/вертикали.

Мое решение представлено ниже:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
int Sequence(int N, int matrix[6][6])
{
	int k = 1;
	for (int i = 0; i < N; i++){
		for (int j = 0; j <= N - 4; j++){
			for (int dj = 1; dj <= 4; dj++){
				int j1 = j + dj;
				if (matrix[i][j] == matrix[i][j1])
					k++;
				else{
					k = 1;
					break;
				}
				if (k == 4)
					return 1;
			}
		}
	}
	for (int j = 0; j < N; j++){
		for (int i = 0; i <= N - 4; i++){
			for (int di = 1; di <= 4; di++){
				int i1 = i + di;
				if (matrix[i][j] == matrix[i1][j])
					k++;
				else{
					k = 1;
					break;
				}
				if (k == 4)
					return 2;
			}
		}
	}
	for (int i = 0; i <= N - 4; i++){
		for (int j = 0; j <= N - 4; j++){
			for (int dij = 1; dij <= 4; dij++){
				int i1 = i + dij;
				int j1 = j + dij;
				if (matrix[i][j] == matrix[i1][j1])
					k++;
				else{
					k = 1;
					break;
				}
				if (k == 4)
					return 3;
			}
		}
	}
	return 0;
}


Выводимые 1,2,3 говорят где найдена последовательность, 0 не найдена.
Я не учел побочную диагональ потому что уже не считаю это решение оптимальным, выходит слишком громоздко, но работает.

Я не прошу написать код за меня, достаточно указать в каком направлении копать.
...
Рейтинг: 0 / 0
22.05.2016, 17:48
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240951
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
cpp22достаточно указать в каком направлении копать.
А зачем куда-то копать? Если код работает - вот и чудненько. Если не работает - надо
отлаживать. В чём проблема-то?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.05.2016, 18:38
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240952
cpp22
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cpp22
Гость
Dimitry Sibiryakov, проблема в том что задача решается в <20 строк(преподаватель сказал), а значит мое решение не оптимально.
...
Рейтинг: 0 / 0
22.05.2016, 18:44
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240959
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
cpp22проблема в том что задача решается в <20 строк(преподаватель сказал), а значит мое решение не оптимально.
Вспоминая свой первый курс и придерживаясь методологии KISS, я бы написал так:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
bool hasSequence(int matrix[6][6])
{
  for (int i = 0; i < 6; i++)
    for (int j = 0; j < 6; j++)
      // проверяем цепочку вправо (или вниз, смотря как считать индексы в массиве)
      if ((i<2 && matrix[i][j] == matrix[i+1][j] && matrix[i][j] == matrix[i+2][j] && matrix[i][j] == matrix[i+3][j]) ||
      // проверяем цепочку вниз (или вправо)
          (j<2 && matrix[i][j] == matrix[i][j+1] && matrix[i][j] == matrix[i][j+2] && matrix[i][j] == matrix[i][j+3]) ||
      // проверяем цепочку вправо-вниз (или влево-вниз)
          (i<2 && j<2 && matrix[i][j] == matrix[i+1][j+1] && matrix[i][j] == matrix[i+2][j+2] && matrix[i][j] == matrix[i+3][j+3]) ||
      // проверяем цепочку влево-вниз (или вправо-вверх, что тоже пох)
          (i>3 && j<2 && matrix[i][j] == matrix[i-1][j+1] && matrix[i][j] == matrix[i-2][j+2] && matrix[i][j] == matrix[i-3][j+3]))
       return true;
  return false;
}


Итого 15 строк, включая комментарии и скобки.

PS: Меньшее число строк не всегда означает большую оптимальность.
...
Рейтинг: 0 / 0
22.05.2016, 19:06
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240962
cpp22
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cpp22
Гость
Dimitry Sibiryakov, спасибо, но Ваше решение не верно: Если последовательность имеется, например, в последней строке, то будет false.
...
Рейтинг: 0 / 0
22.05.2016, 19:31
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240964
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
cpp22Ваше решение не верно: Если последовательность имеется, например, в последней
строке, то будет false.
Уверен? Проверил?.. Думаешь, там зря что ли циклы по всей матрице?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.05.2016, 19:34
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240969
cpp22
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cpp22
Гость
Dimitry Sibiryakov, Вот такой пример, в самом конце 3 последовательности и все 3 не найдены.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	int matrix[6][6] = {
		{ 1, 2, 3, 4, 1, 0 },
		{ 0, 0, 0, 1, 0, 6 },
		{ 0, 9, 1, 1, 4, 1 },
		{ 6, 0, 1, 1, 0, 1 },
		{ 4, 0, 1, 8, 1, 1 },
		{ 0, 6, 1, 1, 1, 1 }};
...
Рейтинг: 0 / 0
22.05.2016, 19:47
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240971
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dimitry Sibiryakov(i>3&& j<2
Хотя да, ты прав, ограничения везде должны быть другими: >2 и <3 соответственно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.05.2016, 19:49
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39240974
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
cpp22все 3 не найдены.
Проблема не в том, что они в последней строке, а в том, что они все примыкают к краю.
Неправильные магические числа, как я и сказал.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.05.2016, 19:54
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241003
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Usman
Участник
cpp22Последовательность может быть по вертикали/горизонтали/вертикалидиагонали
...
Рейтинг: 0 / 0
22.05.2016, 21:36
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241397
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
cpp22Dimitry Sibiryakov, проблема в том что задача решается в <20 строк(преподаватель сказал), а значит мое решение не оптимально.

Это ничего не значит, не слушайте своего преподавателя.

Ваша функция имеет три блока по три цикла. Обратите внимание, что ваши блоки очень похожи друг на друга. Создайте одну функцию(auxilary_f(ps)), которая будет принимать в вашем случае около 12-15 параметров. Таким образом основная функция будет занимать три строчки с вызовом auxilary_f()
...
Рейтинг: 0 / 0
23.05.2016, 14:04
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241520
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Скушная задача. Давайте решим оригинально. В задаче ведь не сказано указать где они лежат.

Нам нужна просто функция-предикат которая говорит что дескыть есть 4 одинаковых. И все.
...
Рейтинг: 0 / 0
23.05.2016, 16:10
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241587
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСкушная задача. Давайте решим оригинально.
Саша почти решил 19207658 . Только с количеством параметров перестарался.
Достаточно трижды вызвать:
Код: plaintext
1.
if(f(my_array, 1, 0) || f(my_array, 0, 1) || f(my_array, 1, 1)) { // Есть 4 подряд
...
Рейтинг: 0 / 0
23.05.2016, 17:28
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241591
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте продиффиренцируем матричку. Вместо циклов сделаем рекурсии.

Короче... удивим старика.
...
Рейтинг: 0 / 0
23.05.2016, 17:32
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241616
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonДавайте продиффиренцируем матричку. Вместо циклов сделаем рекурсии.

Короче... удивим старика.

Длиннее получится, памяти потребуется больше ,
так как нужно будет хранить маршруты, что бы определять
когда нужно выныривать.
...
Рейтинг: 0 / 0
23.05.2016, 18:29
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241636
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДавайте продиффиренцируем матричку. Вместо циклов сделаем рекурсии.

Короче... удивим старика.
Да и сами удивимся. Наше все - заменить рекурсию на цикл, а тут все наоборот надо вывернуть.
 
Тут надо сильно постараться, помощники нужны
— Степан! У гостя карета сломалась.
— Вижу, барин. Ось полетела. И спицы менять надо.
— За сколько сделаешь?
— За день сделаю.
— А за два?
— Ну… За… Сделаем и за два.
— А за пять дней?
— Ну, ежели постараться — можно и за пять.
— А за десять?
— Ну, барин, ты задачи ставишь! За десять дён одному не справиться, тут помощник нужен — хомо сапиенс!
— Бери помощников, но чтобы не раньше!
...
Рейтинг: 0 / 0
23.05.2016, 18:58
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241667
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Какие вы неспортивные. Мне вот данная задачка напомнила алгоритмы японских кроссвордов
где надо отгадывать картинку на клеточном поле.

Вобщем в этой задаче "крест" из двух вертикальных и двух горизонтальных линий определяет
принципиальную возможность существования 4х одинаковых.

Вобщем подумайте...
...
Рейтинг: 0 / 0
23.05.2016, 19:30
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241834
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Поиск всех. С рекурсией.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
#include <stdio.h>

#define N 6

int matrix[N][N] = {
	{ 1, 2, 3, 4, 1, 0 },
	{ 0, 0, 0, 1, 0, 6 },
	{ 0, 9, 1, 1, 4, 1 },
	{ 6, 0, 1, 1, 0, 1 },
	{ 4, 0, 1, 8, 1, 1 },
	{ 0, 6, 1, 1, 1, 1 } };

bool check_point(int len, int x, int y, int dx, int dy) {
	if (x + dx >= N || y + dy >= N || matrix[x][y] != matrix[x + dx][y + dy]) return false;
	if (--len == 1) return true;
	return check_point(len, x + dx, y + dy, dx, dy);
}

int main(int argc, char**argv)
{
	for(int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(check_point(4, i, j, 1, 0)) printf("Found (%d, %d, Horizontal)\n", i, j);
			if(check_point(4, i, j, 0, 1)) printf("Found (%d, %d, Vertical)\n", i, j);
			if(check_point(4, i, j, 1, 1)) printf("Found (%d, %d, Diagonal)\n", i, j);
		}
	}
	return 0;
}

...
Рейтинг: 0 / 0
24.05.2016, 07:57
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241863
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
не учтена вторая диагональ
...
Рейтинг: 0 / 0
24.05.2016, 08:35
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241885
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
wstне учтена вторая диагональ
точно
 
добавил
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
#include <stdio.h>

#define N 6

int matrix[N][N] = {
	{ 1, 2, 3, 6, 1, 0 },
	{ 0, 0, 6, 1, 0, 6 },
	{ 0, 6, 1, 1, 4, 1 },
	{ 6, 0, 1, 1, 0, 1 },
	{ 4, 0, 1, 8, 1, 1 },
	{ 0, 6, 1, 1, 1, 1 } };

bool check_point(int len, int x, int y, int dx, int dy) {
	if (x + dx < 0 || y + dy < 0 || x + dx >= N || y + dy >= N || matrix[x][y] != matrix[x + dx][y + dy]) return false;
	if (--len == 1) return true;
	return check_point(len, x + dx, y + dy, dx, dy);
}

int main(int argc, char**argv) 
{
	for(int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(check_point(4, i, j, 1, 0)) printf("Found (%d, %d, Horizontal)\n", i, j);
			if(check_point(4, i, j, 0, 1)) printf("Found (%d, %d, Vertical)\n", i, j);
			if(check_point(4, i, j, 1, 1)) printf("Found (%d, %d, Diagonal)\n", i, j);
			if (check_point(4, i, j, -1, 1)) printf("Found (%d, %d, Diagonal)\n", i, j);
		}
	}
	return 0;
}

...
Рейтинг: 0 / 0
24.05.2016, 09:06
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39241997
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Эх не играли вы в морской бой.
...
Рейтинг: 0 / 0
24.05.2016, 11:11
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242675
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Но лучше всего идея видна на малых полях. В строке, где количество cells=12
я сразу не думая отмечаю центр. Шириной в 6 cells.

18-12 = 6

http://www.nonograms.org/nonograms/i/6954

В нашей постановке если центр занят меняющимися цифрами - то расположить
четверку одинаковых цифр невозможно.
...
Рейтинг: 0 / 0
24.05.2016, 19:22
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242679
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonВ нашей постановке если центр занят меняющимися цифрами - то расположить
четверку одинаковых цифр невозможно.
Проблема, однако, в том, что наличие повторяющихся цифр в центре не гарантирует наличие
таковой четвёрки. То есть мы за счёт увеличения сложности кода можем уменьшить время
выдачи отрицательного ответа в ряде случаев, но время выдачи положительного ответа при
этом вырастет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
24.05.2016, 19:29
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242701
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВ нашей постановке если центр занят меняющимися цифрами - то расположить
четверку одинаковых цифр невозможно.
покажи где твой центр
Код: plaintext
1.
2.
3.
4.
5.
1,1,1,1,1,1
2,3,4,5,6,7
8,9,0,1,2,3
4,5,6,7,8,9
0,1,2,3,4,5
6,7,8,9,0,1
...
Рейтинг: 0 / 0
24.05.2016, 20:19
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242703
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, ну во первых я забыл сказать что мои рассуждения касались только вертикалей и горизонталей.
Диагонали я просто игнорировал. А во вторых ну.... строки номер 3, 4 и столбцы C,D.
...
Рейтинг: 0 / 0
24.05.2016, 20:21
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242714
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, ну во первых я забыл сказать что мои рассуждения касались только вертикалей и горизонталей.
Диагонали я просто игнорировал. А во вторых ну.... строки номер 3, 4 и столбцы C,D.
Диагонали тоже можно учесть, но ты этим "крестом" покрыл 5/9 всего пространства, если поле увеличить, то твой крест все большую часть занимать будет. Т.е. КПД будет все хуже по сравнению с тупым перебором.
ИМХУ тут лучше перебора нет вариантов. Разве что при поле 100500*100500 перегнать все в таблицу и дальше SQL. Хотя тут тоже не уверен что возможны идеальные решения.
...
Рейтинг: 0 / 0
24.05.2016, 20:38
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242718
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Usman
Участник
mayton,

Можно повернуть на 45 o
...
Рейтинг: 0 / 0
24.05.2016, 20:48
| Ответить | Цитировать | Написать  
Задачка про поиск в матрице
    #39242769
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TДиагонали тоже можно учесть, но ты этим "крестом" покрыл 5/9 всего пространства, если поле увеличить, то твой крест все большую часть занимать будет. Т.е. КПД будет все хуже по сравнению с тупым перебором.
ИМХУ тут лучше перебора нет вариантов. Разве что при поле 100500*100500 перегнать все в таблицу и дальше SQL. Хотя тут тоже не уверен что возможны идеальные решения.
Дима. "Крест" дает быстрый ответ в случае негативного расклада исходных данных.
Но для утвердительного все равно нужно найти хотя-бы 1 первый попавшийся отрезок.

По поводу оптимизации. Если мы посмотрим на задачу под углом мат-статистики то поиск
отрезка нужно начинать не слева направо а от центра в разные стороны.
...
Рейтинг: 0 / 0
24.05.2016, 23:17
| Ответить | Цитировать | Написать  
28 сообщений из 28, показаны все 2 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Задачка про поиск в матрице
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]