Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.91/11: Рейтинг темы: голосов - 11, средняя оценка - 4.91
0 / 0 / 0
Регистрация: 18.03.2010
Сообщений: 4
1

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

18.03.2010, 16:15. Показов 1948. Ответов 6
Метки нет (Все метки)

Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент аij которой равен некоторому отрицательному числу, если город i не соединен напрямую дорогой с городом j и равен длине дороги в противном случае (i, j=1,...,n).
а) Для 1-го города найти кратчайшие маршруты в остальные города.

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

помогите решить
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.03.2010, 16:15
Ответы с готовыми решениями:

Найти дешевый замкнутый маршрут, проходящий через все населенные пункты
Помогите решить задачу, пожалуйста! Есть N населенных пунктов и известна стоимость проезда между...

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

Построить маршрут, проходящий точно 1 раз через все населенные пункты и возвращающийся в начальный
Прощу помочь сделать вот такую непростую задачку.... Заранее очень благодарен...=) Дана...

Найти путь, соединяющий города А и В и не проходящий через заданное множество городов
Задана система односторонних дорог. Найти путь, соединяющий города А и В и не проходящий через...

__________________
6
0 / 0 / 0
Регистрация: 18.03.2010
Сообщений: 4
21.03.2010, 16:46  [ТС] 2
Найти такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
0
0 / 0 / 0
Регистрация: 20.09.2016
Сообщений: 46
22.11.2016, 19:56 3
uli@, вы не нашли решение случайно?
0
Модератор
Эксперт по электронике
7519 / 3708 / 1455
Регистрация: 01.02.2015
Сообщений: 11,539
Записей в блоге: 2
23.11.2016, 01:38 4
blackjstyle, что вы... Случайно решение находил Эдсгер Дейкстра. И то - только к первой задаче.

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

А к третьей задаче - только перебор.
0
Модератор
8410 / 4161 / 2875
Регистрация: 17.08.2012
Сообщений: 13,267
23.11.2016, 05:33 5
blackjstyle, последний раз uli@ посещал форум 29.04.2012 в 17:26. И у него всего 4 сообщения. Вы полагаете, что uli@ следит за событиями на форуме до сих пор?

Так, на всякий случай, задачка про ферзей, простенький вариант, без рекурсии и подпрограмм:
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
const ny: array[boolean] of string[2] = ('. ', '# ');
var f: array[1..5] of integer;
    t: array[0..7, 0..7] of boolean;
    i, j, k, x, y, r: integer;
    s: boolean;
    ex: string;
begin
  writeln('Всего 352 решения.');
  r := 0;
  f[1] := 0;
  repeat
    f[2] := f[1] + 1;
    repeat
      f[3] := f[2] + 1;
      repeat
        f[4] := f[3] + 1;
        repeat
          f[5] := f[4] + 1;
          repeat
            for i := 0 to 7 do for j := 0 to 7 do t[i, j] := false;
            for k := 1 to 5 do
              begin
                x := f[k] div 8;
                y := f[k] mod 8;
                for i := 0 to 7 do
                  for j := 0 to 7 do
                    if (x <> i) or (y <> j) then t[i, j] := t[i, j] or (x = i) or (y = j) or (abs(x - i) = abs(y - j))
              end;
            s := true;
            for i := 0 to 7 do
              for j := 0 to 7 do
                begin
                  s := s and t[i, j];
                  if not s then break
                end;
            if s
              then begin
                inc(r);
                writeln('Решение ', r);
                for i := 0 to 7 do
                  begin
                    for j := 0 to 7 do
                      begin
                        s := false;
                        for k := 1 to 5 do
                          begin
                            s := i * 8 + j = f[k];
                            if s then break
                          end;
                        write(ny[s])
                      end;
                    writeln;
                  end;
                write('Exit? ');
                readln(ex);
                if ex = 'y' then halt
              end;
            inc(f[5])
          until f[5] = 64;
          inc(f[4])
        until f[4] = 63;
        inc(f[3])
      until f[3] = 62;
      inc(f[2])
    until f[2] = 61;
    inc(f[1])
  until f[1] = 60;
  write('Нажмите <Enter> для выхода.');
  readln
end.
0
Модератор
Эксперт по электронике
7519 / 3708 / 1455
Регистрация: 01.02.2015
Сообщений: 11,539
Записей в блоге: 2
23.11.2016, 09:14 6
И одна из реализаций алгоритма Дейкстры Алгоритм Дейкстра/ ошибка
0
Модератор
8410 / 4161 / 2875
Регистрация: 17.08.2012
Сообщений: 13,267
23.11.2016, 12:49 7
Да, насчёт ферзей... Замечу, что, вообще говоря, поле, на котором стоит фигура, фигурой этой не бьётся и фигура этому полю не угрожает. То есть, чтобы бились все поля доски, каждой фигуре должна обязательно угрожать другая фигура. Это решение и было мной написано, оно полностью соответствует условию задания. Чаще решается задача "расставить 5 ферзей, чтобы они били все свободные поля шахматной доски, но при этом не угрожали друг другу".
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.11.2016, 12:49

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Найти путь, соединяющий города A и B, и не проходящий через заданное множество городов
&quot;Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через...

Найти путь, соединяющей города А и В и не проходящий через заданное множество городов
Задана система односторонних дорог. Найти путь, соединяющей города А и В и не проходящий через...

Найти маршрут перелета из города А в город В, не содержащий города С
Нужна помощь с написанием программы про пути в ориентированном графе. Текст задания: Дан список...

Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города
Задача E. Тетрациклофобия Имя входного файла: phobia.in Имя выходного файла: phobia.out...


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

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

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