Старый 17.10.2003, 20:16   #1   
Форумец
 
Сообщений: 118
Регистрация: 04.05.2003
Возраст: 37

Зиалот вне форума Не в сети
И еще задачка.:)

Задачка простенькая, но до меня не до конца доходит.
Дано n городов, дан двумерный массив n*n состоящий из 1 и 0.
1 - есть связь с городом, 0- нет.
например первый город будет связан со 2м городом и с 5тым
например второй только с 1ым.
0 1 0 0 1
1 0 0 0 0
0 0 0 1 1
0 0 1 0 0
1 0 1 0 0
нужно вычислить все ли города связаны.
в данном примере ответ будет ДА.
В общем я ее решил рекурсией...но это не рационально.
поскольку работает максимум на n=50.

Program ilk;
var n,i1,j1:byte;
a:array[1..50,1..50] of byte;
f:text;
mn:set of byte;
Procedure poisk(j:byte);
var i:byte;
begin
if mn<>[] then
for i:=1 to n do
if a[j,i]=1 then
begin
a[j,i]:=0;
a[i,j]:=0;
mn:=mn-[i];
poisk(i);
end;
end;

BEGIN
assign(f,'input.txt');
reset(f);
readln(f,n);
mn:=[2..n];
for i1:=1 to n do begin
for j1:=1 to n do
read(f,a[i1,j1]);
readln(f);
end;

poisk(1);
close(f);

assign(f,'output.txt');
rewrite(f);
if mn=[] then
write(f,'Da')
else
write(f,'Net');
close(f);
END.помогите плиз решить по-другому -не рекурсией. :confused:
  Ответить с цитированием
Старый 17.10.2003, 20:23   #2   
Форумец
 
Аватар для Noname
 
Сообщений: 10,696
Регистрация: 20.09.2002
Возраст: 34

Noname вне форума Не в сети
Зиалот задачу сформулируй нормально, я нихрена не понял.

Noname добавил [date]1066411679[/date]:
Зиалот и код твой читать невозможно, ни комментариев, ничего. И что такое mn?

Noname добавил [date]1066416107[/date]:
Код:
BOOL totalConnect(int link[][], int n)
{
/* counters */
int i;
int j;
int k;
/* repeat procedure n-1 times */
for (i=0;i<n-1;i++)
    for (j=1;j<n;j++)
	    /* if first town has connection with j-th*/
	    if (link[1][j])
		    /* add all connections of j-th town to 1st town */
		    for (k=1;k<n;k++)
			    link[1][k]|=link[j][k];
/* check if 1st town has connections with all other */
for (j=1;j<n;j++)
    if (!link[1][j]) return FALSE;
return TRUE;
}
код неоптимизированный. Его можно усложнить, чтобы все это работало побыстрее.
Идея ясна?

Noname добавил [date]1066416143[/date]:
народ, а как тут пробелы в начало строки добавить?а то некрасиво получается
  Ответить с цитированием
Старый 20.10.2003, 08:34   #3   
Форумец
 
Аватар для fishca
 
Сообщений: 708
Регистрация: 23.12.2002
Возраст: 50
Записей в дневнике: 1

fishca вне форума Не в сети
Тег Code и PHP

Подобный тегу QUOTE, используется для того чтобы сохранить форматирование текста. Этот код равнозначен тегу <pre» в HTML. Очень полезен для отображения программного код:

Код:
<script language="Javascript"»
<!--
alert("Hello world!");
//--»
</script»
В данном примере код автоматически преобразует текст в:

<script language="Javascript"»
<!--
alert("Hello world!");
//--»
</script»
Имеется специальный тег [PHP], для вставки php кода. Включив отрывок php кода в тег [php], этот код будет отфарматирован должным образом:

[php]
$myvar = "Hello World!";
for ($i=0; $i<10; $i++) {
echo $myvar."\n";
}
[/php]

Результат:

$myvar = "Hello World!";
for ($i=0; $i<10; $i++) {
echo $myvar."\n";
}
  Ответить с цитированием
Старый 20.10.2003, 12:39   #4   
Форумец
 
Сообщений: 118
Регистрация: 04.05.2003
Возраст: 37

Зиалот вне форума Не в сети
а на паскале можно?)
хотя уже не надо я уже придумал как сделать:

Program univalg;
var i,j,n,currenttown,c:integer;
f:text;
a:array[1..100,1..100] of byte;
line:array[1..100] of byte;
bool:array[1..100] of boolean;
flag:boolean;
begin
assign(f,'input.txt');
reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
for j:=1 to n do
begin
line[j]:=a[1,j];
bool[j]:=true;
end;
flag:=true;
i:=1;
currenttown:=0;
while flag do
begin
inc(currenttown);
for i:=1 to n do
if (line[i]=1)and(bool[i]) then
begin
c:=0;
bool[i]:=false;
for j:=1 to n do
begin
line[j]:=a[i,j] or line[j];
if line[j]=1 then
inc(c);
end;
end;
if (c=n)or(currenttown=n) then
flag:=false;
end;
assign(f,'output.txt');
rewrite(f);
if c=n then writeln(f,'Da')
else writeln(f,'Net');
close(f);


end.
Пасибо всем!
  Ответить с цитированием
Старый 22.10.2003, 07:57   #5   
gL2.U-_-)
 
Аватар для OveRMinD
 
Сообщений: 157
Регистрация: 18.04.2002

OveRMinD вне форума Не в сети
Зиалот язык принципиального значения не имеет... разберись в языковых конструкциях С и все попрет
  Ответить с цитированием
Старый 22.10.2003, 14:38   #6   
Форумец
 
Сообщений: 118
Регистрация: 04.05.2003
Возраст: 37

Зиалот вне форума Не в сети
OveRMinD а у мя книженции нету...
  Ответить с цитированием
Старый 22.10.2003, 22:01   #7   
Форумец
 
Сообщений: 1,696
Регистрация: 24.11.2002
Возраст: 39

LSL вне форума Не в сети
Зиалот Уж про что, а про Си++ полно литературы в интернете ! Ссылки у меня не проси, не знаю. Юзай поисковики...
  Ответить с цитированием
Старый 23.10.2003, 20:39   #8   
gL2.U-_-)
 
Аватар для OveRMinD
 
Сообщений: 157
Регистрация: 18.04.2002

OveRMinD вне форума Не в сети
Зиалот да в принципе тут и книженция то ни нужна....все и так понятно... ну ладно слушай LSL
он правильно говорит
  Ответить с цитированием
Поиск в теме: 


Опции темы

Быстрый переход:

  Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Support by DrIQ & Netwind