Форум программистов, компьютерный форум CyberForum.ru

Восьмимерка: поиск вектора в матрице - C++

Восстановить пароль Регистрация
 
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
02.12.2010, 20:06     Восьмимерка: поиск вектора в матрице #1
Дана матрица и вектор (могут быть любых размеров). Найти в матрице линейную последовательность элементов, совпадающих с элементами данного вектора, причем вектор может располагаться по любому из восьми направлений (по вертикалям, горизонталям, диагоналям). Сказали, что это аналогия какого-то известного ребуса.
ПОМОГИТЕ или хотя бы натолкните на идею решения
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.12.2010, 20:32     Восьмимерка: поиск вектора в матрице #2
Цитата Сообщение от starikNAD Посмотреть сообщение
аналогия какого-то известного ребуса.
Такую не знаю. Но то что из каждой точки матрицы придется рассматривать все восемь направлений - это точно.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.12.2010, 20:48     Восьмимерка: поиск вектора в матрице #3
Полный перебор - верный путь к решению... Только вот через сколько лет это решение будет получено - вопрос хороший)))
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
03.12.2010, 01:24  [ТС]     Восьмимерка: поиск вектора в матрице #4
Эту задачу задали парню в Национальном техническом университете г. Брно, Чехия. На решение дали три дня (до полуночи воскресенья надо отправить на сервер, иначе работа будет считаться не выполненной)
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.12.2010, 02:24     Восьмимерка: поиск вектора в матрице #5
Гон сиреневый. За три дня можно реализовать эту задачу тупо восьмю разными функциями, перебирающими все возможные варианты. Это не уровень чешского технологического университета. Только если кто-то решил приколоться или убедится, что абитуриент не полный баран.

Топором вырублено за несколько минут, но основная идея должна быть ясна. Прямой, ессессенно, перебор.
C++
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <sstream>
#include <limits>
#include <algorithm>
 
using namespace std;
 
int random_number() { return rand()%3+1; }
 
bool test(vector<vector<int> > &A, vector<int> &B, int a, int b, int iinc, int jinc)
{
    if ((a+iinc*B.size() >= A.size()) || (a+iinc*B.size() < 0) || (b+jinc*B.size() >= A[a].size()) || (b+jinc*B.size() < 0))
        return false;
    for (int i=a, j=b, c=0; c<B.size(); i+=iinc, j+=jinc, c++)
        if (A[i][j]!=B[c])
            return false;
    return true;
}
 
bool make_test(vector<vector<int> > &A, vector<int> &B, int a, int b)
{
    // тут надо бы извратиться и возвращать битовую маску направлений, их аккурат восемь.
    // оставлю на домашнее задание
    return test(A, B, a, b, -1, -1) || 
           test(A, B, a, b, -1,  0) ||
           test(A, B, a, b, -1,  1) ||
           test(A, B, a, b,  0,  1) ||
           test(A, B, a, b,  0, -1) ||
           test(A, B, a, b,  1, -1) ||
           test(A, B, a, b,  1,  0) ||
           test(A, B, a, b,  1,  1);
}
int main()
{
    srand(static_cast<unsigned int>(time(0)));
 
    int M = 10;
    int N = 10;
    int K = 3;
    vector<vector<int> > A(M, vector<int>(N));
    vector<int> B(K);
 
    for (int i=0; i<A.size(); i++)
        generate(A[i].begin(), A[i].end(), random_number);
    generate(B.begin(), B.end(), random_number);
 
    for (int i=0; i<A.size(); i++)
    {
        for (int j=0; j<A[i].size(); j++)
            cout << setw(3) << A[i][j];
        cout << endl;
    }
    cout << endl;
    for (int i=0; i<B.size(); i++)
        cout << setw(3) << B[i];
    cout << endl;
 
    for (int i=0; i<A.size(); i++)
    {
        for (int j=0; j<A[i].size(); j++)
            cout << setw(3) << make_test(A, B, i, j);
        cout << endl;
    }
 
    system("pause");
}
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
03.12.2010, 18:15  [ТС]     Восьмимерка: поиск вектора в матрице #6
Уважаемый lemegeton,
эту задачу задали моему знакомому парню в этом универе. Подозреваю, что они ожидают в решении рекурсию или что-то подобное. Это - третий из четырех проектов, и предыдущие были тоже не самые простые (например, вычислить гиперболический тангенс с наперед заданной точностью, не используя библиотечные функции - мы с ним решили такое двумя способами - с помощью рядов и с помощью цепных дробей). Причем при вычислении с помощью рядов препод сказал - надо было поставить еще проверку на NAN (not a number, такое введено в стандарте C99).
Так что вряд ли они ждут простого перебора. На решение дали неделю, но парень поздно обратился ко мне за советом.

Добавлено через 5 минут
и еще одно: все должно быть сделано на языке C (не C++), причем в соответствии со стандартом C99
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
03.12.2010, 18:49     Восьмимерка: поиск вектора в матрице #7
Цитата Сообщение от lemegeton Посмотреть сообщение
Гон сиреневый. За три дня можно реализовать эту задачу тупо восьмю разными функциями, перебирающими все возможные варианты.
Полностью согласен! Разве, что вариантов можно гораздо больше придумать...

Цитата Сообщение от starikNAD Посмотреть сообщение
Найти в матрице линейную последовательность элементов, совпадающих с элементами данного вектора, причем вектор может располагаться по любому из восьми направлений (по вертикалям, горизонталям, диагоналям).
Задание уточните - все элементы вектора должны совпасть, или серия в произвольном месте вектора должна совпасть с серией в произвольном месте строки/столбца/диагонали массива? А так в принципе - со строками вообще всё просто, а из столбцов и диагоналей проще создавать временный массив и memcmp() в руки...
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
03.12.2010, 19:19  [ТС]     Восьмимерка: поиск вектора в матрице #8
должны совпасть все элементы вектора. Вектор может располагаться по любой горизонтали, или вертикали, или диагонали. Например, в матрице
8 4 5 8 1 14 1
3 4 5 9 6 17 80
21 10 3 4 75 14 9
0 19 1 2 16 19 68
41 2 3 4 1 32 77
искомый вектор (1; 2; 3; 4) расположен, начиная с элемента (5;5) по диагонали вверх и влево

Добавлено через 1 минуту
в терминах языка С координаты начала вектора, конечно, [4][4]

Добавлено через 17 минут
lemegeton,
если Вы знаете по крайней мере 8 функций, покажите хоть одну! ... но в терминах C, а не C++, и не используя библиотечных функций и классов типа vector

Добавлено через 3 минуты
easybudda,
Вы модератор, я ценю Ваше время и не прошу заниматься моей задачей лично. Но, может, к кому-нибудь меня направите?
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.12.2010, 20:58     Восьмимерка: поиск вектора в матрице #9
Шутишь, да? Просил алгоритм, получил алгоритм. Теперь придираешься к языку, которого даже не указал. Что еще забыл указать?

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

(Назовем матрицу - А размером MхN, а вектор - B размером K)
Последовательный перебор в такой задаче навскидку кажется самым оптимальным решением, хоть и с высокой сложностью. В худшем случае, к каждому элементу матрицы будет M*N*K обращений.

Рекурсивный алгоритм вряд ли будет эффективен, поскольку для больших К будет излишне поедать ресурсы (стек+время вызова). Можно рассмотреть оптимизации для точек, находящихся ближе, чем на К единиц к границе матрицы.

А на С будет так. Заодно влепил направления.
C
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <math.h>
 
const int M = 20;
const int N = 20;
const int K = 3;
 
int make_one_test(int A[M][N], int B[K], int a, int b, int iinc, int jinc)
{
    if ((a+iinc*K>=M) || (a+iinc*K<0) || (b+jinc*K>=N) || (b+jinc*K<0))
        return 0;
    int i=a, j=b, c;
    for (c=0; d<K; i+=iinc,j+=jinc,d++)
        if (A[i][j]!=B[d])
            return 0;
    return (1<<(iinc+1)*3+jinc+1);
}
 
int make_tests(int A[M][N], int B[K], int a, int b)
{
    return  make_one_test(A, B, a, b, -1, -1) |
        make_one_test(A, B, a, b, -1,  0) |
        make_one_test(A, B, a, b, -1,  1) |
        make_one_test(A, B, a, b,  0, -1) |
        make_one_test(A, B, a, b,  0,  1) |
        make_one_test(A, B, a, b,  1, -1) |
        make_one_test(A, B, a, b,  1,  0) |
        make_one_test(A, B, a, b,  1,  1);
}
 
const char *dirname[9] =
    {"left-up", "up", "right-up", "right", "impossible", "right-down", "down", "left-down", "left"};
 
int main()
{
 
    int A[M][N];
    int B[K];
 
    int i, j;
    for (i=0; i<M; i++)
    {
        for (j=0; j<N; j++)
        {
            A[i][j] = rand()%3+1;
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
 
    printf("\n");
 
    for (i=0; i<K; i++)
    {
        B[i] = rand()%3+1;
        printf("%d ", B[i]);
    }
    printf("\n");
 
    for (i=0; i<M; i++)
        for (j=0; j<M; j++)
        {
            int r = make_tests(A, B, i, j);
            if (r>0)
            {
                printf("Found at (%d, %d): %d:", i, j, r);
                int z;
                for (z=0; z<9; z++)
                    if (r&(1<<z))
                        printf(" %swards", dirname[z]);
                printf(".\n");
            }
        }
 
    return 0;
}
Под "стандарт С99" сами подгоните. Ну, например, объявления счетчиков уберите в объявление циклов, что-там-еще...
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
03.12.2010, 21:25  [ТС]     Восьмимерка: поиск вектора в матрице #10
lemegeton, большое спасибо!
и всем спасибо!
а насчет указания стандарта - в будущем буду аккуратнее
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.12.2010, 21:30     Восьмимерка: поиск вектора в матрице #11
перепутал описания направлений. Должно быть
C
1
"left-up", "up", "right-up", "left", "impossible", "right", "left-down", "down", "right-down"
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.12.2010, 12:21     Восьмимерка: поиск вектора в матрице #12
Цитата Сообщение от starikNAD Посмотреть сообщение
предыдущие были тоже не самые простые
Да ну? Это например вычисление тангенса с заданной точность (пусть хотя-бы гиперболического)? Знаете, сколько подобных "проектов" тут появляется каждую неделю? ИМХО, вы слишком переоцениваете сложность тех заданий, что задают в Чешском Технологическом...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2010, 17:11     Восьмимерка: поиск вектора в матрице
Еще ссылки по теме:

C++ Поиск матрицы в матрице
C++ Поиск в матрице, задача
Поиск в матрице символов C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
04.12.2010, 17:11  [ТС]     Восьмимерка: поиск вектора в матрице #13
lemegeton, пожалуйста просветите!
1. в строках из вчерашнего кода (функция make_one_test)
C
1
2
3
4
for (c=0; d<K; i+=iinc,j+=jinc,d++)
  if (A[i][j]!=B[d])
    return 0;
  return (1<<(iinc+1)*3+jinc+1);[/quote]
1. какую роль играет число 3?
2. вместо d (эта переменная не объявлена) поставил с - правильно?
Моя программа не работает, но причина может быть не в Вашем коде: у меня массив создается динамически, и я мог ошибиться с указателями. Поэтому проверяю везде код.
Yandex
Объявления
04.12.2010, 17:11     Восьмимерка: поиск вектора в матрице
Ответ Создать тему
Опции темы

Текущее время: 08:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru