Ужасно интересная задача о которой вряд-ли кто слышал :)

← →
Step[B.M.] © (2003-09-28 23:21) [0]

Допустим у нас есть Таблица клиентов
ID_K NAME_K
1 Иванов
2 Петров
3 Сидоров
40 Крюков
5 Гаков
6 Тыков

и Табцица их знакомств в виде

ID_K1 IDK2
1 2 //Значит Иванов знаком и Петровым
2 1 //И Петров знаком и Ивановым
2 40 //Петров знаком с Крюковым
5 40 //И Гаков знаком с Крюковым
6 3 // И т.д.
6 5
40 6

ВНИМАНИЕ!!! ЗАДАЧА !!!
Построить алгоритм, которий бы показывал цепочку знакомств Иванова (1) и Гакова (5) (Если такова существует) К стати их может быть несколько. Да еще сделать так, чтобы не попасть в рекурсию.

← →
Юрий Зотов © (2003-09-28 23:29) [1]

Уточните:
1. Это таблица БД, или просто таблица?
2. Что значит "цепочка знакомств"? Дайте ее пример.
3. Может ли в таблице быть избыточность (если Иванов знаком с Петровым, то автоматически и Петров знаком с Ивановым, поэтому вторая строка избыточная). Или взаимное знакомство не автоматическое?
4. Это домашнее задание, лабораторка или уже курсовой?
:о)

← →
Alex Konshin © (2003-09-29 00:09) [2]

Типичная задача из теории графов. Дана матрица инциденций.

← →
Ihor Osov'yak © (2003-09-29 00:33) [3]

Волновый алгоритм.

Отведем каждому человеку ячейку.

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

шаг волна
1 1->2 (в ячейке 2 запомнили 1)
2 2->40 (на 1 не идем, так как 1 уже было под волной), в 40 запомнили 2
3 40->6 (в 6 запомнили 3)
4 6->3, 6->5 ( в 3 и 5 запомнили 4)

5 - конечная точка, значит построение волны оканчиваем..

Цепочку получаем, анализируя числа, которые запомнили в ячейках ( к ячейке в которой записано 4 волна пришла от ячейки, в которй записано 3, к ячейке с 3 - волна от ячейке с 2 и тд):

5-6-40-2-1

← →
Ihor Osov'yak © (2003-09-29 00:34) [4]

Зы - алгоритм этот слышал более двадцати лет назад.. Даже в некоторых практических задачах пришлось применять..

← →
Ihor Osov'yak © (2003-09-29 00:39) [5]

Кажется алгоритм именовался "Волновой алгоритм Ли"

← →
Toxyc (2003-09-29 00:44) [6]

procedure TForm1.Button1Click(Sender: TObject);
var t,i: integer;
begin
p:= StrToInt(Edit1.Text); //формируем пару знакомств
q:= StrToInt(Edit2.Text); //формируем пару знакомств
t:= id[p];
if t<>id[q] then begin
for i:= 0 to 9 do begin
if id[i]=t then id[i]:=id[q]; //разбиваем на группы связности
end;
end;
end;

в результате все, кто знаком друг с другом будут обознчаться одной цифрой

← →
SergP © (2003-09-29 08:53) [7]

> Ihor Osov"yak © (29.09.03 00:34) [4]
> Зы - алгоритм этот слышал более двадцати лет назад.. Даже
> в некоторых практических задачах пришлось применять..

А я когда-то пытался написать прогу для трассировки печатных плат используя этот алгоритм на.... Спектруме (это было еще в спектрумовские времена). Даже написал вполне работоспособный кусок проги...

Кстати никто не страдал аналогичными вещами на дельфи?

← →
asp © (2003-09-29 09:40) [8]

На DB2 решается одним запросом :)

Скажем проще, алгоритм Дейкстры, однако не тот который про поиск кратчайшего пути

данная задача решается на Прологе...

... одним предикатом (не считая исходных)

> Юрий Зотов © (28.09.03 23:29) [1]
>3. Может ли в таблице быть избыточность
Может быть. Вы ведь знаете Майкла Джексона, а он Вас, наверное, нет.
>4. Это домашнее задание, лабораторка или уже курсовой?
Ни одно из них :)

P.S. Для себя я эту задачу решил, правда, кривовато.
Но Всем большое спасибо за возможность узнать как это делают другие.

Действительно, МАСТЕРА.

Ужасно интересная задача о которой вряд-ли кто слышал :) Найти похожие ветки