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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 79
#1

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

02.12.2010, 20:06. Просмотров 793. Ответов 12
Метки нет (Все метки)

Дана матрица и вектор (могут быть любых размеров). Найти в матрице линейную последовательность элементов, совпадающих с элементами данного вектора, причем вектор может располагаться по любому из восьми направлений (по вертикалям, горизонталям, диагоналям). Сказали, что это аналогия какого-то известного ребуса.
ПОМОГИТЕ или хотя бы натолкните на идею решения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2010, 20:06     Восьмимерка: поиск вектора в матрице
Посмотрите здесь:

Для каждого элемента вектора определить, сколько раз он встречается в матрице - C++
Дана целочисленная матрица A(N,M) и целочисленный вектор D(K). Для каждого элемента вектора определить, сколько раз он встречается в...

Поиск максимального элемента вектора - C++
Написала программу поиска максимального элемента вектора, только теперь её надо переделать немного с использованием указателей... ...

Поиск вектора, минимального по длине - C++
Даны m векторов х1 = (х11, х21, ...,хn1), ..., xm = (x1m, x2m, ...,xnm). Написать программу поиска вектора минимального по длине. ...

Поиск нескольких элементов массива/вектора - C++
Всем доброго времени суток. После нескольких часов безуспешного мозгового штурма и интернет-серфинга решил задать вопрос здесь. Попытаюсь...

Поиск среди пар элементов вектора - C++
В заданном векторе провести поиск среди пар его элементов и найти те пары, разность между элементами которых есть величина, наибольшая для...

Рекурсивный, линейный поиск с использованием вектора - C++
Изучаю C++ по книжке Дейтелов "Как прогарммировать на C++". Попалась задача на рекурсию: "(Поиск наименьшего значения в массиве) Напишите...

Поиск в матрице - C++
в матрице MхN найти номер ПЕРВОГО из столбцов в котором нет отрицательных элементов.... есть код но он находит все стоблцы....а мне нужно...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.12.2010, 20:32     Восьмимерка: поиск вектора в матрице #2
Цитата Сообщение от starikNAD Посмотреть сообщение
аналогия какого-то известного ребуса.
Такую не знаю. Но то что из каждой точки матрицы придется рассматривать все восемь направлений - это точно.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
02.12.2010, 20:48     Восьмимерка: поиск вектора в матрице #3
Полный перебор - верный путь к решению... Только вот через сколько лет это решение будет получено - вопрос хороший)))
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 79
03.12.2010, 01:24  [ТС]     Восьмимерка: поиск вектора в матрице #4
Эту задачу задали парню в Национальном техническом университете г. Брно, Чехия. На решение дали три дня (до полуночи воскресенья надо отправить на сервер, иначе работа будет считаться не выполненной)
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
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
Сообщений: 79
03.12.2010, 18:15  [ТС]     Восьмимерка: поиск вектора в матрице #6
Уважаемый lemegeton,
эту задачу задали моему знакомому парню в этом универе. Подозреваю, что они ожидают в решении рекурсию или что-то подобное. Это - третий из четырех проектов, и предыдущие были тоже не самые простые (например, вычислить гиперболический тангенс с наперед заданной точностью, не используя библиотечные функции - мы с ним решили такое двумя способами - с помощью рядов и с помощью цепных дробей). Причем при вычислении с помощью рядов препод сказал - надо было поставить еще проверку на NAN (not a number, такое введено в стандарте C99).
Так что вряд ли они ждут простого перебора. На решение дали неделю, но парень поздно обратился ко мне за советом.

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

Цитата Сообщение от starikNAD Посмотреть сообщение
Найти в матрице линейную последовательность элементов, совпадающих с элементами данного вектора, причем вектор может располагаться по любому из восьми направлений (по вертикалям, горизонталям, диагоналям).
Задание уточните - все элементы вектора должны совпасть, или серия в произвольном месте вектора должна совпасть с серией в произвольном месте строки/столбца/диагонали массива? А так в принципе - со строками вообще всё просто, а из столбцов и диагоналей проще создавать временный массив и memcmp() в руки...
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 79
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
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
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
Сообщений: 79
03.12.2010, 21:25  [ТС]     Восьмимерка: поиск вектора в матрице #10
lemegeton, большое спасибо!
и всем спасибо!
а насчет указания стандарта - в будущем буду аккуратнее
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
03.12.2010, 21:30     Восьмимерка: поиск вектора в матрице #11
перепутал описания направлений. Должно быть
C
1
"left-up", "up", "right-up", "left", "impossible", "right", "left-down", "down", "right-down"
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
04.12.2010, 12:21     Восьмимерка: поиск вектора в матрице #12
Цитата Сообщение от starikNAD Посмотреть сообщение
предыдущие были тоже не самые простые
Да ну? Это например вычисление тангенса с заданной точность (пусть хотя-бы гиперболического)? Знаете, сколько подобных "проектов" тут появляется каждую неделю? ИМХО, вы слишком переоцениваете сложность тех заданий, что задают в Чешском Технологическом...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2010, 17:11     Восьмимерка: поиск вектора в матрице
Еще ссылки по теме:

Поиск в матрице, задача - C++
Итак форум ваш мне очень понравился по тому как мало людей которые дают ненужные советы, а только дельные слова. Сама проблема...

Поиск матрицы в матрице - C++
Помогите, пожалуйста, исправить часть программы. Задание звучит следующим образом: &quot;В матрице MxM, заполненной случайными числами, найти...

Поиск островов в матрице - C++
Есть матрица A: 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 2 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | ...

поиск нулей в матрице - C++
написать программу, которая будет выводить &quot;ошибка&quot;, если один из строк или столбцов матрицы содержать нули

Поиск в матрице символов - C++
Здравствуйте! Необходимо найти в каждом столбце символьной матрицы количество знаков пунктуации и вывести это под каждым столбцом. ...


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

Или воспользуйтесь поиском по форуму:
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 79
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     Восьмимерка: поиск вектора в матрице
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru