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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ rand() http://www.cyberforum.ru/cpp-beginners/thread202256.html
генератор случайных чисел rand() подскажите пожелуста как работает ета штука. что означает %200, %200-100. какой принцип роботы
C++ структуры вот нам на лекции дали эту прогу но когда вбиваю в ВС она не работает пытался разобраться не смог посмотрите пожалуйста и укажите на ошибки ) #include "stdafx.h" #include <stdio.h> #include <conio.h> #include <locale.h> #define MAXBOOKS 100 struct book { char title; http://www.cyberforum.ru/cpp-beginners/thread202243.html
C++ ребят!!простейшая программа!!
определить возможность существования треугольника,используя формулу герона!! у меня только без герона получаетсяя((
график функции C++
вот код программы: #include <stdio.h> #include <conio.h> #include <math.h> float dlina(float a,int n,float h); void main() {clrscr(); float a,b,h,s; int n; printf("vvedite a,b,h:\n");
C++ Сортировка в структуре http://www.cyberforum.ru/cpp-beginners/thread202226.html
Опеределить группу здоровых школьников, используя сотношение "рост"-100="вес" Вывести на экран фамилию и имя самого маленького по росту и самого тяжелого.
C++ Динамическое выделение памяти. Доброго времени суток. Помогите, пожалуйста, решить задачу. Задача тривиальна - поиск и замена подстроки. Суть в чем: необходимо реализовать динамическое выделение памяти, то есть строка может быть довольно большой. Никак не разберусь с malloc. Итак, когда если я задам, например, строку (char s), то в тестах может встретиться строка большей длины. Как сделать так, чтобы этого не произошло. подробнее

Показать сообщение отдельно
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
03.12.2010, 20:58     Восьмимерка: поиск вектора в матрице
Шутишь, да? Просил алгоритм, получил алгоритм. Теперь придираешься к языку, которого даже не указал. Что еще забыл указать?

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

(Назовем матрицу - А размером 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" сами подгоните. Ну, например, объявления счетчиков уберите в объявление циклов, что-там-еще...
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru