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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Классы для чисел большой точности http://www.cyberforum.ru/cpp-beginners/thread79768.html
Доброго времени суток! Необходимо написать библиотеку классов для работы с числами большой точности. Необходимо использовать минимум 2 класса. Числа посоветовали хранить в массиве символов....
C++ Лаба по сортировку.Срочно! Помогите сделать лабу: Дан целый массив максимальной размерности 20*20. Провести сортировку по возрастанию отрицательных чисел в нечетных строках. Ввод исходного массива организовать из файла,... http://www.cyberforum.ru/cpp-beginners/thread79749.html
C++ Вычислить другую сумму.
Помогите пожалуйста решить задачку... На языке C++ http://img7.imageshost.ru/imgs/091225/8d2f18376d/1f769.jpg
Отформатировать текст по n символов в строке C++
Отформатировать текст по n символов в строке (встасить равномерно между словами пробелы, чтобы длина строк была равна n).
C++ Вычислить сумму. http://www.cyberforum.ru/cpp-beginners/thread79714.html
Помогите пожалуйста решить задачку... На языке C++ http://img7.imageshost.ru/imgs/091225/b7af95a38e/4888a.jpg
C++ Строки Здравствуйте.Возник следующий вопрос.Если имеется набор символов в виде массива s.Как составить строку St из этих символов? подробнее

Показать сообщение отдельно
SNROK
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
25.12.2009, 18:36  [ТС]
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru