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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.96
SNROK
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
#1

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

25.12.2009, 17:33. Просмотров 3309. Ответов 4
Метки нет (Все метки)

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

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

Программа «поиск выхода из лабиринта» - C++
Открывать файл «карту», имя файла передавать как параметр командной строки. Считать, что в карте замкнутых контуров нет. Стенка — «1»....

Исправить поиск выхода из лабиринта - C++
Есть программа поиска выхода из лабиринта: #include <stdio.h> #include <io.h> #include <iostream> using namespace std; ...

Поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл - C++
Нужно провести поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл solution.txt. Карта лабиринта содержится в...

Нахождение выхода из лабиринта - C++
Нужна помощь.Может кто-нибудь видел туториал(или здесь,на форуме) по этой теме.Но хотелось бы,чтобы было объяснение.Собственно,любым...

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

4
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.12.2009, 17:53 #2
алгоритм простой.
1) определяешь все возможные направления движения
2) если после п.1 больше одного варианта движения, шагаешь в любую сторону остальные заносишь в буфер, и вновь п.1
если один вариант шагаешь по этому маршруту и п.1
если вариантов ноль, читаешь последный вариант из буфера и п.1
если вариантов ноль и буфер пуст, а цель не достигнута, то время паниковать
0
SNROK
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
25.12.2009, 18:19  [ТС] #3
хочу примерный код
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.12.2009, 18:25 #4
Цитата Сообщение от SNROK Посмотреть сообщение
хочу примерный код
а я хочу медленно потягивать коньяк сидя в кресло-качалке у камина в своём особняке и чтобы шкура белого медведя на полу. и кому щас легко?
0
SNROK
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
25.12.2009, 18:36  [ТС] #5
Pascal
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
const max_graf = 100;(максимальное число комнат в лабиринте}
type list =^elem;
         elem = record
                            num : integer;
                            next : list;
                      end;
var
Graf: array [1. . rnax_graf] of elem;
ref: list;
       n, i, a : integer;
       goal, go_on : boolean; {признаки достижения цели и необходимости продолжения}
      beg_num,end_num : integer;
      beg_st, end_st, elem_st : list; { начало, конец и элемент стека }
. . .
Procedure CreateGraf(n:integer);
{чтение исходных данных из текстового файла и формирование графа}
var
        sosed, sosed1 : list;
begin
        for i:=l to n do
          begin
                     new(sosed);
                     graf[i].next := sosed;
                    repeat
                              Readln(inf,a) ;
                              sosed^.num := a;
                              if а<>0 then
                              begin
                                         new(sosed1);
                                         sosed^.next := sosed1;
                                         sosed := sosed1
                              end
                    until a=0
          end
end;
 
  Формирование маршрута ведется с использованием стека. Процедуры Add и Del предназначены соответственно для добавления и удаления элементов стека.
 
Procedure Add (num: integer; var beg_st : list );
{ добавление элемента к стеку }
var
          elem_st : list;
begin
          new(elem_st); { выделили память под следующий элемент стека}
          elem_st^.next:=beg_st; {присоединили новый элемент к стеку }
                 elem_st^.num:=num; {занесли информацию)
                 beg_st:=elem_st {установили указатель на новое начало стека}
end;
 
Procedure Del (var begin_st : list ) ;
{ удалить элемент из стека }
var
        elem_st : list;
begin
        elem_st:=beg_st;
        beg_st:=beg_st^.next; { переносим указатель начала (вершины) стека на второй элемент}
        Dispose(elem_st) { освобождаем память, уничтожив первый элемент}
end;
 
  Основное действие алгоритма — это обработка очередной вершины графа, в результате чего мы либо добавляем к маршруту новую вершину, либо возвращаемся в предыдущую. Порядок просмотра соседей определяется порядком следования полей-ссылок в перечне вершин-соседей, который соответствует одной записи в текстовом файле.
 
Procedure Way (num_begin, num_end : integer); { номера вершин начала и конца пути }
var
      num : integer; { номер текущей вершины }
      flag : boolean; { признак необходимости продолжения пути }
begin
      Graf [num_begin] .num : = 1; { начальный этап }
      Add (num_begin, beg_st) ; {поместили начало пути в. стек }
      flag := true; {нужно продолжать построение пути }
      while flag and (not goal) do { строим очередной фронт }
      begin
             num := beg_st^.num ;
             { берем значение вершины стека }
             ref := graf [num].next;
          go_on := false; {признак того, что путь увеличился}
             repeat
                     a: =ref^ .num;
                     if а<>0 then
                             begin
                                        {обработка очередного соседа}
                                        if Graf[a]. num=0 {пометить вершину следующим фронтом}
                                        then begin
                                                      Graf [a].num := 1;
                                                      Add(a, beg_st) ;
                                                    go_on := true; {путь увеличился на шаг}
                                        end
 
                               else
                                       ref := ref^.next { переходим к следующему соседу }
                             end;
            until (a=0) or (go_on);
                 if Graf [num_end].num<>0 then goal :=true { дошли до цели. }
                  else
                    if not go_on then
                        begin
                             del (beg_st) ;
                             if beg_st=end_st then flag:=false
                                { стек пуст, задача неразрешима }
                        end
      end
end;
 
  Теперь программу поиска маршрута можно записать так (структура графа считывается из текстового файла):
 
program BackTracking;
. . .
begin
        for i:=1 to Max_Graf do Graf [i].num :=0;
        assign (inf, 'graf.txt');
        { в файле приведен пример, разобранный в тексте (рис.3)}
        reset (inf);
        readln (inf,n); { число вершин графа }
        CreateGraf (n) ;
        close (inf) ;
        new (elem_st) ; { инициализация стека }
        beg_st:=elem_st; { стек пока пуст,}
        end_st:=elem_st; { призак этого: beg_st = end_st}
        goal := false;
        Writeln;
        Writeln('Введите номер начальной и конечной вершины'};
        Readln (beg_num, end_num) ;
        Way (beg_num, end_num) ;
        if goal then
            { построение и печать маршрута }
      . . .
end.
как это на C++?
0
25.12.2009, 18:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2009, 18:36
Привет! Вот еще темы с ответами:

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

Разработать программу, осуществляющую поиск самого короткого и самого длинного слова во вводимом тексте - C++
Разработать программу, осуществляющую поиск самого короткого и самого длинного слова во вводимом тексте. С комментами)

С++ Выполнить поиск заданного элемента методом однородного бинарного поиска - C++
Приветствую друзья программисты. Нужна ваша неотъемлемая помощь. В отсортированном одномерном массиве X(100)выполнить поиск заданного...

Реализовать программу для поиска и замены символов в строке - C++
прошу помощи, задания : 1) Напишите функцию поиска символа в строке с такой сигнатурой: char *findSym(char str, char sym); Эта...


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

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

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