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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наследование методов - C++
Может мне стоит книжку почитать или получше подумать над структурой, но вопрос вот: Есть у нас древо классов: base > s2 > s3 > s4 > ......

Распаралеливание методов - C++
У меня есть матрица, размеры вплоть до 4000 на 4000, она заполняется, потом у меня есть файл в котором около 50 строк, в каждой строке по 2...

Массив методов - C++
Вообщем такая проблемма, стоит задача реализовать меню для задания, это вызывает трудности, я сделал меню которое для функций работает...

Наследование методов C++ - C++
Подскажите, если у меня есть класс, в нём описан метод добавления элемента add_element(int number); который в свою очередь основан на...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.03.2012, 22:29     Использование переборных методов #2
Метод перебора будет не ээфективным здесь. Могу предложить другой метод, по-моему волновой алгоритм называется. Объясню его "на пальцах":
берем матрицу a[8][8]. Все элементы делаем равными -1. Затем конечную клетку где стоит фигура помечаем 0, заносим координаты этой клетки в очередь.
Далее делаем так:
Берем очередной элемент из очереди и смотрим куда из этой клетки можем пойти фигурой. Если есть клетка в которую мы можем пойти и она не помечена (равна -1), то заносим ее в очередь и помечаем значением на 1 больше чем значение у текущей точки.
По окончании очереди если значение начальной клетки осталось равным -1, то клетка не достижима. Если не равна -1, то достижима за кол-во ходов, которое записано в этой клетке.
Теперь сам кратчайший путь:
Начинаем с начальной клетки, ищем клетку в которую можно попасть этой фигурой со значением на 1 меньше. Переходим на нее, из нее делаем тоже самое. И т.д. пока не попадем в клетку со значением 0.
Corsair342
0 / 0 / 0
Регистрация: 14.01.2012
Сообщений: 6
11.03.2012, 07:27  [ТС]     Использование переборных методов #3
Извиняюсь! можно код программы просто я не очень в нём понимаю!
valeriikozlov
Эксперт C++
4669 / 2495 / 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;
 
}
Yandex
Объявления
11.03.2012, 18:38     Использование переборных методов
Ответ Создать тему
Опции темы

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