| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Ema
Forumaš(ica)
Pridružen/a: 01. 02. 2005. (12:44:59)
Postovi: (9C)16
|
 Postano: 19:27 sub, 11. 2. 2006 Naslov: Zadatak s roka 19.04.05. RELATION |
    |
|
|
Dana je binarna relacija R kod koje je domain1=domain2={1,2,...,n}. Neovisno o implementaciji atp-ova napisite
a) funkciju sa prototipom int tranzitivna (RELATION R, int n) koja vraca 1 ako je R tranzitivna relacija,a 0 u protivnom.
b) funkciju sa prototipom void ispis_klase (RELATION R, int n) koja ispisuje sve klase ekvivalencije relacije R (u ovom podzadatku R je relacije ekvivalencije), svaku klase treba ispisati samo jednom.
smijete koristiti pomocne a.t.p.ove ali ne i dodatna polja.
kako provjeriti da je R binarna relacija, tj kako pogledati da li za svaki element iz domain 1 nesto vrijedi? (elementi nisu nikako sortirani?)
Dana je binarna relacija R kod koje je domain1=domain2={1,2,...,n}. Neovisno o implementaciji atp-ova napisite
a) funkciju sa prototipom int tranzitivna (RELATION R, int n) koja vraca 1 ako je R tranzitivna relacija,a 0 u protivnom.
b) funkciju sa prototipom void ispis_klase (RELATION R, int n) koja ispisuje sve klase ekvivalencije relacije R (u ovom podzadatku R je relacije ekvivalencije), svaku klase treba ispisati samo jednom.
smijete koristiti pomocne a.t.p.ove ali ne i dodatna polja.
kako provjeriti da je R binarna relacija, tj kako pogledati da li za svaki element iz domain 1 nesto vrijedi? (elementi nisu nikako sortirani?)
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 19:38 sub, 11. 2. 2006 Naslov: Re: Zadatak s roka 19.04.05. RELATION |
|
|
|
[quote="Ema"]kako provjeriti da je R [color=red]binarna[/color] relacija, tj kako pogledati da li za svaki element iz domain 1 nesto vrijedi? (elementi nisu nikako sortirani?)[/quote]
Vjerojatno mislis na [b]tranzitivnu[/b] operaciju. ;)
Ja bih to tvrdom islom:
[code:1]for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
if ((i,j) € R i (j,k)€ R i NIJE (i,k)€R) return 0;
return 1;[/code:1]
Ili, sitno optimizirano:
[code:1]for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if ((i,j) € R)
for(k = 1; k <= n; k++)
if ((j,k)€ R i NIJE (i,k)€R) return 0;
return 1;[/code:1]
Sorry, ne znam napamet kako se zovu funkcije, ali i ovo bi trebalo pomoci (€ mi je pripadnost relaciji). ;)
Pod b) (uz pretpostavku da je R relacija ekvivalencije; dakle, to ne provjeravamo):
[code:1]for(i = 1; i <= n; i++) {
LISTA = prazna; (moze i stog ili bilo sto drugo za cuvanje niza elemenata)
for(j = 1; j <= n; j++)
if ((i,j) € R)
if (j<i) break; else dodaj j u listu LISTA;
if (LISTA nije prazna) ispisi listu LISTA;
}[/code:1]
:wave:
| Ema (napisa): | | kako provjeriti da je R binarna relacija, tj kako pogledati da li za svaki element iz domain 1 nesto vrijedi? (elementi nisu nikako sortirani?) |
Vjerojatno mislis na tranzitivnu operaciju. 
Ja bih to tvrdom islom:
| Kod: | for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
if ((i,j) € R i (j,k)€ R i NIJE (i,k)€R) return 0;
return 1; |
Ili, sitno optimizirano:
| Kod: | for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if ((i,j) € R)
for(k = 1; k <= n; k++)
if ((j,k)€ R i NIJE (i,k)€R) return 0;
return 1; |
Sorry, ne znam napamet kako se zovu funkcije, ali i ovo bi trebalo pomoci (€ mi je pripadnost relaciji).
Pod b) (uz pretpostavku da je R relacija ekvivalencije; dakle, to ne provjeravamo):
| Kod: | for(i = 1; i <= n; i++) {
LISTA = prazna; (moze i stog ili bilo sto drugo za cuvanje niza elemenata)
for(j = 1; j <= n; j++)
if ((i,j) € R)
if (j<i) break; else dodaj j u listu LISTA;
if (LISTA nije prazna) ispisi listu LISTA;
} |
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
Zvone
Forumaš(ica)
Pridružen/a: 01. 07. 2003. (13:09:44)
Postovi: (9D)16
|
| Postano: 0:37 ned, 12. 2. 2006 Naslov: |
|
|
|
[quote]Sorry, ne znam napamet kako se zovu funkcije, ali i ovo bi trebalo pomoci (€ mi je pripadnost relaciji).[/quote]
Nazalost bas zbog ovog (po meni) propusta u definiciji atp-a RELATION stvar se jos mrvicu zakomplicira. Naime, u definiciji atp-a _ne postoji_ funkcija poput in_relation(RELATION R, domain1 a, domain2 b) koja vraca 1 ako su a i b u relaciji R, a 0 ako nisu. Zbog toga trebamo sami napisati nesto slicno:
[code:1]int in_relation (RELATION R, domain1 a, domain2 b)
{
SET temp; // elementtype od ovog set-a je domain2
COMPUTE2 (R, a, &temp);
if (MEMBER(b, temp))
return 1;
else
return 0;
}[/code:1]
i onda umjesto if (aRb) pisati if (in_relation(R, a, b)).
Cini mi se da se ljudi najvise boje relacija bas zbog toga sto su u definiciji atp-a kripticne COMPUTE1 i COMPUTE2 umjesto puno jednostavnije funkcije in_relation...
(npr. COMPUTE2(RELATION R, domain1 a, SET* S) postavlja *S=[latex]\{b\in domain2\;:\;(a,\;b)\in R\}[/latex])
| Citat: | | Sorry, ne znam napamet kako se zovu funkcije, ali i ovo bi trebalo pomoci (€ mi je pripadnost relaciji). |
Nazalost bas zbog ovog (po meni) propusta u definiciji atp-a RELATION stvar se jos mrvicu zakomplicira. Naime, u definiciji atp-a _ne postoji_ funkcija poput in_relation(RELATION R, domain1 a, domain2 b) koja vraca 1 ako su a i b u relaciji R, a 0 ako nisu. Zbog toga trebamo sami napisati nesto slicno:
| Kod: | int in_relation (RELATION R, domain1 a, domain2 b)
{
SET temp; // elementtype od ovog set-a je domain2
COMPUTE2 (R, a, &temp);
if (MEMBER(b, temp))
return 1;
else
return 0;
} |
i onda umjesto if (aRb) pisati if (in_relation(R, a, b)).
Cini mi se da se ljudi najvise boje relacija bas zbog toga sto su u definiciji atp-a kripticne COMPUTE1 i COMPUTE2 umjesto puno jednostavnije funkcije in_relation...
(npr. COMPUTE2(RELATION R, domain1 a, SET* S) postavlja *S= )
|
|
| [Vrh] |
|
|
