Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Задачка про поиск в матрице / 25 сообщений из 28, страница 1 из 2
  1  все
22.05.2016, 17:48
    #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, 18:38
    #39240951
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
cpp22достаточно указать в каком направлении копать.
А зачем куда-то копать? Если код работает - вот и чудненько. Если не работает - надо
отлаживать. В чём проблема-то?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.05.2016, 18:44
    #39240952
cpp22
cpp22
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Dimitry Sibiryakov, проблема в том что задача решается в <20 строк(преподаватель сказал), а значит мое решение не оптимально.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.05.2016, 19:06
    #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:31
    #39240962
cpp22
cpp22
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Dimitry Sibiryakov, спасибо, но Ваше решение не верно: Если последовательность имеется, например, в последней строке, то будет false.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.05.2016, 19:34
    #39240964
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
cpp22Ваше решение не верно: Если последовательность имеется, например, в последней
строке, то будет false.
Уверен? Проверил?.. Думаешь, там зря что ли циклы по всей матрице?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.05.2016, 19:47
    #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:49
    #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:54
    #39240974
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
cpp22все 3 не найдены.
Проблема не в том, что они в последней строке, а в том, что они все примыкают к краю.
Неправильные магические числа, как я и сказал.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.05.2016, 21:36
    #39241003
Usman
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
cpp22Последовательность может быть по вертикали/горизонтали/вертикалидиагонали
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.05.2016, 14:04
    #39241397
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
cpp22Dimitry Sibiryakov, проблема в том что задача решается в <20 строк(преподаватель сказал), а значит мое решение не оптимально.

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

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

Нам нужна просто функция-предикат которая говорит что дескыть есть 4 одинаковых. И все.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.05.2016, 17:28
    #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:32
    #39241591
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Давайте продиффиренцируем матричку. Вместо циклов сделаем рекурсии.

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

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

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

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

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

Вобщем подумайте...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.05.2016, 07:57
    #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, 08:35
    #39241863
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
не учтена вторая диагональ
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.05.2016, 09:06
    #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, 11:11
    #39241997
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Эх не играли вы в морской бой.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.05.2016, 19:22
    #39242675
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Но лучше всего идея видна на малых полях. В строке, где количество cells=12
я сразу не думая отмечаю центр. Шириной в 6 cells.

18-12 = 6

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

В нашей постановке если центр занят меняющимися цифрами - то расположить
четверку одинаковых цифр невозможно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.05.2016, 19:29
    #39242679
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
maytonВ нашей постановке если центр занят меняющимися цифрами - то расположить
четверку одинаковых цифр невозможно.
Проблема, однако, в том, что наличие повторяющихся цифр в центре не гарантирует наличие
таковой четвёрки. То есть мы за счёт увеличения сложности кода можем уменьшить время
выдачи отрицательного ответа в ряде случаев, но время выдачи положительного ответа при
этом вырастет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.05.2016, 20:19
    #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:21
    #39242703
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачка про поиск в матрице
Dima T, ну во первых я забыл сказать что мои рассуждения касались только вертикалей и горизонталей.
Диагонали я просто игнорировал. А во вторых ну.... строки номер 3, 4 и столбцы C,D.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Задачка про поиск в матрице / 25 сообщений из 28, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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