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

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

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

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

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

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

Использование методов класса в самом классе C++
Напишите реализацию методов, предоставляющих доступ к данным класса. Отобразите в программе работу этих методов C++
C++ Использование полей и методов в дочерних классах
Использование шаблоных методов C++
C++ Использование рекурсивных методов
C++ Использование массивов внутри методов класса
Использование private-членов класса в сигнатуре методов C++
Использование static методов C++
C++ Использование статических методов класса в динамических библиотеках
Переопределение методов C++
C++ Наследование методов
C++ Массив методов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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++
 Аватар для valeriikozlov
4661 / 2487 / 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     Использование переборных методов
Ответ Создать тему
Опции темы

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