Как вбить маршруты в программу?

@ewqeqw · Регистрация: 26.04.2017

Студворк — интернет-сервис помощи студентам

Условие задачи

Кликните здесь для просмотра всего текста

Канадские авиалинии
CANADIAN AIRLINES

Описание
Вы победили в соревновании, организованном Канадскими авиалиниями. Приз - бесплатное путешествие по Канаде. Путешествие начинается с самого западного города, в который летают самолеты, проходит с запада на восток, пока не достигнет самого восточного города, в который летают самолеты. Затем путешествие продолжается обратно с востока на запад, пока не достигнет начального города.

Ни один из городов нельзя посещать более одного раза за исключением начального города, который надо посетить ровно дважды (в начале и в конце путешествия). Вам также нельзя пользоваться авиалиниями других компаний или другими способами передвижения.

Задача
Задача состоит в следующем: дан список городов и список прямых рейсов между парами городов; найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям.

Несколько наборов входных данных помещены в ASCII-файл ITIN.DAT. Каждый набор содержит:

в первой строке - количество городов N, в которые летают самолеты, и количество прямых рейсов V.
N - положительное целое число, меньшее или равное 100.
V - положительное целое число;

в каждой из следующих N строк - название города, в который летают самолеты. Названия упорядочены с запада на восток, то есть i-ый по порядку город находится восточнее j-го тогда и только тогда, когда i>j (не существует городов на одном меридиане). Название каждого города - строка, состоящая из не более, чем 15 цифр и/или латинских букв, например: AGR34 или BELA

в каждой из следующих V строк - названия двух городов из списка городов, разделенные пробелом. Если пара ГОРОД1 ГОРОД2 содержится в строке, это означает, что есть прямой рейс из ГОРОД1 в ГОРОД2, а также прямой рейс из ГОРОД2 в ГОРОД1.

Различные наборы входных данных разделены пустой строкой. После последнего набора данных пустой строки не будет. Входные данные корректны, и их проверка не требуется.

Решения, полученные для каждого набора входных данных, должны быть последовательно записаны в выходной ASCII-файлITIN.SOL следующим образом:

в первой строке - общее количество городов из входного файла;

в следующей строке - число M, равное количеству различных городов, посещаемых на маршруте;

в следующих M+1 строках - названия городов по одному в строке в порядке их посещения.

Обратите внимание, что исходный город должен быть также выведен последним. Если для набора входных данных не существует решения, то для этого набора в выходном файле ITIN.SOL должны быть только две записи: общее количество городов и сообщение "NO SOLUTION" (нет решения). Решения для разных наборов входных данных должны разделяться в выходном файле пустой строкой.

Например:

ITIN.DAT
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

5 5
C1
C2
C3
C4
C5
C5 C4
C2 C3
C3 C1
C4 C1
C5 C2

ITIN.SOL
8
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

5
NO SOLUTION

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
const n=8;
var
name: array[1..n] of string[15];
d,how: array [1..n, 1..n] of integer;
 
 
 
Procedure Way(i,j: integer);
begin
 if (i=1) and (j=1) then writeln(name[1])
 else 
   if i>=j then begin
     writeln(name[i]);
     Way(how[i,j],j);
   end
   else begin
     Way(i,how[i,j]);
     writeln(name[j]);
   end;
end;
 
 
procedure Solve;
var i,j,k: integer;
begin
 d[1,1]:= 1;
 for i:=2 to n do
  for j:=1 to i do
   if(i<>j) or(i=n) then
    for k:=1 to i-1 do
      if((k<>j) or (j=1)) and (d[k,j]<>0) and (d[k,j]+1>d[i,j]) then begin
        d[i,j]:= d[k,j]+1;
        d[j,i]:= d[i,j];
        how[i,j]:= k; 
        how[j,i]:= k;
      end;
      if d[n,n] = 0 then writeln('NO SOLUTIONS')
      else begin
       writeln(d[n,n] - Ord(n>1));
       Way(n,n);
       if n=1 then writeln(name[1]);
      end;
end;
 
begin
 
name[8]:= 'Vancouver';
name[7]:= 'Yellowknife';
name[6]:= 'Edmonton';
name[5]:= 'Calgary';
name[4]:= 'Winnipeg';
name[3]:= 'Toronto';
name[2]:= 'Montreal';
name[1]:= 'Halifax';
 
Solve;
 
end.

Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
Как вбить маршруты в программу?

@JuriiMW · 02.05.2017, 11:50

У вас изначально неверный подход!
Где чтение файла?

Нужно как-то так:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
begin
  var f : Text; Reset(f, 'ITIN.DAT');
  /// число городов и количество рейсов
  var n, v : Integer; ReadLn(f, n, v);
  /// список городов
  var city : array of string;
  SetLength(city, n);
  for var i := 0 to n-1 do ReadLn(f, city[i]);
  /// список рейсов
  var flight : array [,] of string;
  SetLength(flight, v, 2);
  var tmp : string;
  for var i := 0 to v-1 do
    begin
      ReadLn(f, tmp);
      var a := tmp.ToWords(' ');
      flight[i,0] := a[0]; flight[i,1] := a[1];
    end;
  Close(f);
  /// дальше делаем поиск
  ...
end.

@ewqeqw · 02.05.2017, 13:29 **[ТС]**

А куда записывать маршруты?

@JuriiMW · 03.05.2017, 05:36

Что значит „записывать“?
Они уже даны в файле.
А после выполнения моего куска программы, они находятся в массиве flight…

@ewqeqw · 03.05.2017, 07:50 **[ТС]**

А в моем случае куда записывать маршруты? В d? how?

@JuriiMW · 03.05.2017, 08:06

По чём я знаю?
Это же ваша программа и ваш алгоритм.
Я только ответил на вопрос

Сообщение от ewqeqw

Как вбить маршруты в программу?

У вас „d“ и „how“ — числовые массивы.
Вероятно, в них должны храниться индексы списков…

Новые блоги и статьи Все статьи Все блоги /
1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .

@ewqeqw 0 / 0 / 0 Регистрация: 26.04.2017 Сообщений: 19
	02.05.2017, 13:29 [ТС]
	А куда записывать маршруты? 0

@JuriiMW 5095 / 2661 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	03.05.2017, 05:36
	Что значит „записывать“? Они уже даны в файле. А после выполнения моего куска программы, они находятся в массиве flight… 0

@ewqeqw 0 / 0 / 0 Регистрация: 26.04.2017 Сообщений: 19
	03.05.2017, 07:50 [ТС]
	А в моем случае куда записывать маршруты? В d? how? 0