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

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

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

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

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

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

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

Как проверить есть ли в матрице элементы совпадающие с каким-либо элементом вектора - C++
Как проверить есть ли в матрице элементы совпадающие с каким-либо элементом вектора

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

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

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

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

12
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.12.2010, 20:32 #2
Цитата Сообщение от starikNAD Посмотреть сообщение
аналогия какого-то известного ребуса.
Такую не знаю. Но то что из каждой точки матрицы придется рассматривать все восемь направлений - это точно.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
02.12.2010, 20:48 #3
Полный перебор - верный путь к решению... Только вот через сколько лет это решение будет получено - вопрос хороший)))
0
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 80
03.12.2010, 01:24  [ТС] #4
Эту задачу задали парню в Национальном техническом университете г. Брно, Чехия. На решение дали три дня (до полуночи воскресенья надо отправить на сервер, иначе работа будет считаться не выполненной)
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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");
}
0
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 80
03.12.2010, 18:15  [ТС] #6
Уважаемый lemegeton,
эту задачу задали моему знакомому парню в этом универе. Подозреваю, что они ожидают в решении рекурсию или что-то подобное. Это - третий из четырех проектов, и предыдущие были тоже не самые простые (например, вычислить гиперболический тангенс с наперед заданной точностью, не используя библиотечные функции - мы с ним решили такое двумя способами - с помощью рядов и с помощью цепных дробей). Причем при вычислении с помощью рядов препод сказал - надо было поставить еще проверку на NAN (not a number, такое введено в стандарте C99).
Так что вряд ли они ждут простого перебора. На решение дали неделю, но парень поздно обратился ко мне за советом.

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
13
Yandex
Объявления
04.12.2010, 17:11
Ответ Создать тему
Опции темы

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