LINUX.ORG.RU
ФорумTalks

Поиск всех путей на графе (Небольшой тест. Часть 2)

 


0

2

Только тем, у кого есть время. Есть однонапрвленный упорядоченный граф (надо найти все пути из a в z, но, видимо, программно):

a → b, c, d, z
b → d, e, f, z
c → d, e, f, z
d → e, f, z
e → f, z
f → g, h, j, z
g → h, i, j, z
h → i, j, k, z
i → j, k, l, z
j → k, m, z
k → l, n, o, z
l → m, z
m → n, o, z
n → o, z
o → p, z
p → q, z
q → r, z
r → s, z
s → t, u, z
t → u, v, z
u → v, w, z
v → w, z
w → x, y, z
x → y, z
y → z
z → (нет исходящих)

Свой результат пишу сразу ( даже не уверен, что 100% правильный, но все ж…): Все пути:

22061

Все пути в массивах. Вывод кода: https://filebin.net/ysidtdizjge50kjh

Код для проверки: https://gitflic.ru/project/dcc0/mix-c-89-php/blob?file=allways_more_20k.php



Последнее исправление: AnonymUser (всего исправлений: 7)

но, видимо, программно

Та так пишешь как будто тебе в школе дали такое задание и ты тут советуешься как его решать.

Считается без всяких программ на бумажке минут за 10 или меньше. Ответ верный да.

Видишь строчку «a -> b,c,d,z» - ставишь справа от строк b,c,d,z единицы.

Затем видишь строчку «b -> d,e,f,z 1» - прибавляешь эту единицу что справа к d,e,f,z (у d получается уже 2 т.к. ему единицу ещё раньше приписали).

Затем то же самое «c -> d,e,f,z 1».

Затем строка «d -> e,f,z 3» - прибавляешь тройку к e,f,z.

Итд.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от firkax

Да, какая школа в моем возрасте?! Интересно, кто как решает такое.

Ты хочешь сказать, что можно посчитать по какой-то формуле?! Не думал об этом. Строго вручную уж очень утомительно считать.

AnonymUser
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 3)
Ответ на: комментарий от firkax

Пора тебе всем Лором скинуться на второй Макбук Про.

AnonymUser
() автор топика
Ответ на: комментарий от AnonymUser

Ты хочешь сказать, что можно посчитать по какой-то формуле?!

Белов В. В., Воробьев Е. М., Шаталов В. Е. - Теория графов. — М.: Высш. школа, 1976.

Надо понимать, что всё уже придумано до нас.

Aceler ★★★★★
()
Ответ на: комментарий от AnonymUser

утомительно считать

Уроки в школе длятся по 40-60 минут, и как-то никого кроме двоечников не утомляют. А тут всего 10 минут, и вся арифметика уже в 3 классе должна быть полностью понятна (а без понимания и в 1 классе можно выполнить).

firkax ★★★★★
()
Ответ на: комментарий от firkax

ААаа… там вроде сумма размещений с вычитанием того, чего нет?!

AnonymUser
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)

Строго вручную уж очень утомительно считать.

Сервис с картинками, алгоритмами и обучающим видео для лентяев Graph Online © (graphonline.ru).

quickquest ★★★★★
()
Ответ на: комментарий от firkax

Аааа…. Т.е. ты таки хочешь сказать, что такие графы считаются простым сложением?! Я взял маленький граф и вроде получилось:

$a = array('b', 'c', 'd', 'e');
$b = array('c', 'd', 'e');
$c = array('d', 'e');
$d = array('e');
$е = array();

Методика: 4+3+1 Ответ: 8

AnonymUser
() автор топика
Ответ на: комментарий от AnonymUser

Нет, возведением в степень.

2 в третьей степени = 8.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Да. Действительно меньше 10 минут ушло простой арифметикой:

a → b, c, d, z		22061
b → d, e, f, z		8824
c → d, e, f, z		8824
d → e, f, z	        4412
e → f, z		2206
f → g, h, j, z		2205
g → h, i, j, z		1297
h → i, j, k, z		713
i → j, k, l, z		389
j → k, m, z		194
k → l, n, o, z		129
l → m, z		65
m → n, o, z		64
n → o, z		32
o → p, z		31
p → q, z		30
q → r, z		29
r → s, z		28
s → t, u, z 		27
t → u, v, z 		16
u → v, w, z 		10	
v → w, z    		5
w → x, y, z 		4 
x → y, z 		2 
y → z 			1
z → (нет исходящих) 0

P.S. Через матрицу смежности, как я понял, предлагается использовать степени. (Но там не очень ясно. Сети пишут, что на таких графах - степени - формальны). (Бегло если глянуть, то растет функция, и правда, как что-то близкое к степени двойки).

AnonymUser
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 4)
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)