Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на языке Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 2.943 RSS
←   Декабрь 2011   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/pascal
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

2.943 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на языке Pascal


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 8840
∙ повысить рейтинг » 		Орловский Дмитрий
Статус: Советник
Рейтинг: 6905
∙ повысить рейтинг » 		lamed
Статус: Академик
Рейтинг: 5650
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Pascal (Паскаль)

Номер выпуска:1220
Дата выхода:28.12.2011, 23:30
Администратор рассылки:Boriss (Академик)
Подписчиков / экспертов:159 / 171
Вопросов / ответов:1 / 1

Консультация # 184936: Уважаемые эксперты! требуется на Turbo Pascal выполнить следующее задание: написать программу на базе общей схемы алгоритма поиска с возвратом. Скрины варианты ниже:

Консультация # 184936:

Уважаемые эксперты! требуется на Turbo Pascal выполнить следующее задание: написать программу на базе общей схемы алгоритма поиска с возвратом.
Скрины варианты ниже:

Дата отправки: 23.12.2011, 23:15
Вопрос задал: Sanek (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Andrew Kovalchuk (Профессионал):

Здравствуйте, Sanek!
Предлагаю следующий вариант решения вашей задачи:

Код :
{
	написать программу на базе общей схемы алгоритма поиска с возвратом
	Найти кратчайший путь на графе от вершины 1 до вершины 35.
	Индекс - вершина источник.
	m,n; - данные для приемника, где m - вершина, n - расстояние.
}
uses
	crt; {Используем стандартный модуль Crt}

type
	TNode = record
		name: string;
		index,
		dfp: byte; {distance from parent}
	end;

const
	Dist: array[1..34] of string = ({массив переходов и их стоимости; индекс элемента узел-источник.}
{ 1}	'2,0;3,0;4,0;5,0;6,0;7,0;',
{ 2}	'8,10;9,13;',
{ 3}	'9,8;10,10;11,12;',
{ 4}	'10,7;11,8;',
{ 5}	'11,5;12;8;',
{ 6}	'12,3;13,5;14,7;',
{ 7}	'13,2;14,3;',
{ 8}	'15,13;16,12;',
{ 9}	'16,8;',
{10}	'16,8;17,8;18,15;',
{11}	'17,13;18,8;19,7;',
{12}	'19,3;',
{13}	'19,3;20,3;21,4;',
{14}	'21,4;', 
{15}	'22,9;', 
{16}	'22,10;23,10;', 
{17}	'22,9;23,15;24,11;25,14;', 
{18}	'25,4;', 
{19}	'25,5;26,5;', 
{20}	'25,4;26,7;27,6;28,9;', 
{21}	'28,8;', 
{22}	'29,10;', 
{23}	'29,11;30,15;', 
{24}	'29,13;30,14;', 
{25}	'30,14;31,10;', 
{26}	'32,6;33,4;', 
{27}	'32,8;33,9;', 
{28}	'33,9;34,5;', 
{29}	'35,0;', 
{30}	'35,0;', 
{31}	'35,0;', 
{32}	'35,0;', 
{33}	'35,0;', 
{34}	'35,0;');

var
	node: TNode; {элемент узел}
	candidat, vector: string; {предполагаемая и кратчайшая последовательности}
	S: byte; {стоимость кратчайшего пути}

procedure next(var st: string; var node:TNode); {получение следующего узла}
var
   data, name: string; {узел назначения и стоимость, имя узла в строковом виде}
   dist, code: integer; {стоимость перехода (расстояние), код преобразования строки в число}
   posch: byte; {позиция символа-разделителя}
begin
   posch := pos(';', st); {ищем вхождение разделителя узлов}
   data := copy(st, 1, posch-1); {копируем данные по узлу и стоимости}
   delete(st, 1, posch); {удаляем эти данные вместе с разделителем}
   posch := pos(',', data); {ищем вхождение разделителя данных по узлу}
   name := copy(data, 1, posch-1); {имя узла забираем}
   delete(data, 1, posch); {и удаляем}
   node.name := name; {запоминаем имя в структуре для доступа извне}
   val(name, node.index, code); {получаем номер узля назначения}
   val(data, node.dfp, code); {и расстояние до него}
end;


procedure solve(path:string; candidat:byte; child:byte); {поиск решения}
{формальные параметры: найденный путь, стоимость пути, рассматриваемый узел}
var
	nodes: string; {последовательность узлов назначения}
begin
	if (child = 35) then begin {если достигнут конечный узел назначения}
		if (candidat < S) then begin {найденный путь меньше эталонного наименьшего? да}
			S := candidat; {сохраним длину пути}
			vector := path; {и последовательность переходов}
		end;
	end else begin {иначе}
		nodes := Dist[child]; {достанем список узлов назначения из массива переходов}
		while (nodes > '') do begin {пока не просмотрены все варианты переходов}
			next(nodes, node); {получим очередной узел назначения}
			if ((candidat + node.dfp) < S) then {если уже найденный путь не превышает эталонного}
				solve(path + '>' + node.name, candidat + node.dfp, node.index); {поищем варианты для этого узла}
		end;
	end;
end;

begin
	clrscr; {очистка экрана}
	S := 255; {установим первоначальную эталонную стоимость заведомо большей любого из путей}
	solve('1', 0, 1); {будем рассматривать все подходяшие варианты начиная с первой вершины}
	writeln('Shortest path (', S, '): ', vector); {вывод информации о найденном кратчайшем пути}
	writeln('Done. Press any key...'); {сообщаем, что работа завершена}
	readkey; {ждем нажатия клавиши пользователем}
end.

Единственное отличие реализации от общей схемы алгоритма поиска с возвратом - не рассматриваются те варианты, которые в имеющейся своей части превышают по длине уже найденный вариант короткого пути (if ((candidat + node.dfp) < S) then). Если посчитаете это лишним - просто удалите приведенную строку из программы. В остальном решение не должно вызывать вопросов.

UPD: по просьбе автора вопроса добавлены комментарии.

Консультировал: Andrew Kovalchuk (Профессионал)
Дата отправки: 24.12.2011, 06:46

5
Большое спасибо, задача сделана на "отлично" ))
-----
Дата оценки: 28.12.2011, 13:03
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.33 от 10.09.2011
В избранное