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

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

Войти
Регистрация
Восстановить пароль
 
Corsair342
0 / 0 / 0
Регистрация: 14.01.2012
Сообщений: 6
#1

Использование переборных методов - C++

10.03.2012, 17:16. Просмотров 530. Ответов 3
Метки нет (Все метки)

Ребят! Помогите решить задачу!! Использование переборных методов разработка программы нахождения кратчайшего пути передвижения различных шахматных фигур по доске(ферзь,конь,король) соединяюшей два заданных поля шахматной доски
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.03.2012, 17:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Использование переборных методов (C++):

Использование шаблоных методов - C++
Есть код: class A { public: static void Set( unsigned param ) { GPIOA->ODR = param; }

Использование static методов - C++
Здравствуйте ,у меня есть код для очереди ,но мне хочется ,чтобы функции работали без создания объектов или как я помню из частичного курса...

Использование рекурсивных методов - C++
Потрібен приклади використання рекурсивних методів / надо примеры использование рекурсивных методов ..

Использование полей и методов в дочерних классах - C++
Возникла проблема class Subj { public: char name; char prepod; int hours; bool exam; bool credit;

Использование методов класса в самом классе - C++
Вообще есть класс нужно объедение все его методы в один метод. Пример: class Test{ public: int N; private: Test(){ ...

Использование массивов внутри методов класса - C++
Нужно сделать так, чтобы массив NextBrick можно было использовать в ShowNB. При этом Массив NextBrick может быть либо вне либо внутри ...

3
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.03.2012, 22:29 #2
Метод перебора будет не ээфективным здесь. Могу предложить другой метод, по-моему волновой алгоритм называется. Объясню его "на пальцах":
берем матрицу a[8][8]. Все элементы делаем равными -1. Затем конечную клетку где стоит фигура помечаем 0, заносим координаты этой клетки в очередь.
Далее делаем так:
Берем очередной элемент из очереди и смотрим куда из этой клетки можем пойти фигурой. Если есть клетка в которую мы можем пойти и она не помечена (равна -1), то заносим ее в очередь и помечаем значением на 1 больше чем значение у текущей точки.
По окончании очереди если значение начальной клетки осталось равным -1, то клетка не достижима. Если не равна -1, то достижима за кол-во ходов, которое записано в этой клетке.
Теперь сам кратчайший путь:
Начинаем с начальной клетки, ищем клетку в которую можно попасть этой фигурой со значением на 1 меньше. Переходим на нее, из нее делаем тоже самое. И т.д. пока не попадем в клетку со значением 0.
1
Corsair342
0 / 0 / 0
Регистрация: 14.01.2012
Сообщений: 6
11.03.2012, 07:27  [ТС] #3
Извиняюсь! можно код программы просто я не очень в нём понимаю!
0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.03.2012, 18:38 #4
Цитата Сообщение от Corsair342 Посмотреть сообщение
Извиняюсь! можно код программы просто я не очень в нём понимаю!
Это пример для вычисления кратчайшего пути коня (вводите координаты начала и конца пути от 1 до 8):
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
77
78
79
#include <stdio.h>
    struct tt{
        int x, y;
    };
int main()
{
 
    int a[8][8], i, j, i_st=0, i_end=1, x_st, y_st, x_end, y_end;
    tt Q[64];
    for(i=0; i<8; i++)
        for(j=0; j<8; j++)
            a[i][j]=-1;
    printf("Vvod koordinati starta:\nX= ");
    scanf("%d", &x_st);
    printf("Y= ");
    scanf("%d", &y_st);
    printf("Vvod koordinati finish:\nX= ");
    scanf("%d", &x_end);
    printf("Y= ");
    scanf("%d", &y_end);
    x_st--; y_st--; x_end--; y_end--;
    a[x_end][y_end]=0; Q[0].x=x_end; Q[0].y=y_end;
    while(i_st<i_end)
    {
        if(Q[i_st].x>1 && Q[i_st].y>0 && a[Q[i_st].x-2][Q[i_st].y-1]==-1)
        { a[Q[i_st].x-2][Q[i_st].y-1]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x-2; Q[i_end++].y=Q[i_st].y-1;}
        if(Q[i_st].x>1 && Q[i_st].y<7 && a[Q[i_st].x-2][Q[i_st].y+1]==-1)
        { a[Q[i_st].x-2][Q[i_st].y+1]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x-2; Q[i_end++].y=Q[i_st].y+1;}
        if(Q[i_st].x>0 && Q[i_st].y>1 && a[Q[i_st].x-1][Q[i_st].y-2]==-1)
        { a[Q[i_st].x-1][Q[i_st].y-2]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x-1; Q[i_end++].y=Q[i_st].y-2;}     
        if(Q[i_st].x>0 && Q[i_st].y<6 && a[Q[i_st].x-1][Q[i_st].y+2]==-1)
        { a[Q[i_st].x-1][Q[i_st].y+2]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x-1; Q[i_end++].y=Q[i_st].y+2;}
        if(Q[i_st].x<6 && Q[i_st].y>0 && a[Q[i_st].x+2][Q[i_st].y-1]==-1)
        { a[Q[i_st].x+2][Q[i_st].y-1]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x+2; Q[i_end++].y=Q[i_st].y-1;}
        if(Q[i_st].x<6 && Q[i_st].y<7 && a[Q[i_st].x+2][Q[i_st].y+1]==-1)
        { a[Q[i_st].x+2][Q[i_st].y+1]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x+2; Q[i_end++].y=Q[i_st].y+1;}
        if(Q[i_st].x<7 && Q[i_st].y>1 && a[Q[i_st].x+1][Q[i_st].y-2]==-1)
        { a[Q[i_st].x+1][Q[i_st].y-2]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x+1; Q[i_end++].y=Q[i_st].y-2;}
        if(Q[i_st].x<7 && Q[i_st].y<6 && a[Q[i_st].x+1][Q[i_st].y+2]==-1)
        { a[Q[i_st].x+1][Q[i_st].y+2]=a[Q[i_st].x][Q[i_st].y]+1; Q[i_end].x=Q[i_st].x+1; Q[i_end++].y=Q[i_st].y+2;}     
        i_st++;
    }
    if(a[x_st][y_st]==-1)
        printf("Nedostogaem pole");
    else
    {
        printf("Put':\n");
         do 
        {
            printf("%d %d\n", x_st+1, y_st+1);
            if(x_st>1 && y_st>0 && a[x_st-2][y_st-1]==a[x_st][y_st]-1)
            { x_st-=2; y_st--;}
            else
            if(x_st>1 && y_st<7 && a[x_st-2][y_st+1]==a[x_st][y_st]-1)
            { x_st-=2; y_st++;}
            else
            if(x_st>0 && y_st>1 && a[x_st-1][y_st-2]==a[x_st][y_st]-1)
            { x_st--; y_st-=2;}
            else
            if(x_st>0 && y_st<6 && a[x_st-1][y_st+2]==a[x_st][y_st]-1)
            { x_st--; y_st+=2;}
            else
            if(x_st<6 && y_st>0 && a[x_st+2][y_st-1]==a[x_st][y_st]-1)
            { x_st+=2; y_st--;}
            else
            if(x_st<6 && y_st<7 && a[x_st+2][y_st+1]==a[x_st][y_st]-1)
            { x_st+=2; y_st++;}
            else
            if(x_st<7 && y_st>1 && a[x_st+1][y_st-2]==a[x_st][y_st]-1)
            { x_st++; y_st-=2;}
            else
            if(x_st<7 && y_st<6 && a[x_st+1][y_st+2]==a[x_st][y_st]-1)
            { x_st++; y_st+=2;}
        }while(a[x_st][y_st]>0);
        printf("%d %d\n", x_end+1, y_end+1);
    }
    return 0;
 
}
0
11.03.2012, 18:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2012, 18:38
Привет! Вот еще темы с ответами:

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

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

Напишите реализацию методов, предоставляющих доступ к данным класса. Отобразите в программе работу этих методов - C++
Реализация методов класса. Напишите реализацию методов, предоставляющих доступ к данным класса. Отобразите в программе...

Работа с двумерными числовыми массивами. Использование указателей. Использование функций пользователя. - C++
Помогите пожалуйста!!!!!!! Сделать три варианта: первый вариант – передача данных между функциями с помощью глобального...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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