andreamix

User info:

Registered: May 2005
Posts: 9 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 8:23:36 [...]
Status: Offline

Post actions:

ciao ragazzi..ho dei problemi con degli esercizi di alcuni appelli recenti..metto di seguito i testi..se qualcuno li sa risolvere può mettre le soluzioni?grazie

1)descrivere un algoritmo x il seguente problema
istanza: un grafo nn orientato G=<V,E> rappresentato da liste di adiacenza
soluzione: il valore 1 se G è una foresta,0 altrimenti

2)descrivere un algoritmo x il seguente problema
istanza: un grafo orientato G=<V,E> rappresentato da liste di adiacenza
soluzione: il valore 1 se G possiede un ciclo,0 altrimenti

3)descrivere un algoritmo divide et impera che su input n,k,b1,b2,..,bn calcola il valore F(n,k,b) = k^b1+k^b2+...+k^bn
dove la b nella parentesi è un vettore.

NoWhereMan

.illuminato.

User info:

Registered: Jul 2003
Posts: 222 (0.03 al dì)
Location: Segrate (MI)
Corso: Dottorato in Informatica
Anno:
Time Online: 1 Day, 21:56:46 [...]
Status: Offline

Post actions:

1) fai un ciclo for sul vettore dei vertici chiamando una procedura VISITA(v), dopo averli segnati come NUOVI.
VISTA(v) cerca i cicli. Se trovi un ciclo interrompi subito la procedura, perché una foresta non contiene cicli.

Si ha un ciclo se (ad esempio) la lista di adiacenza del nodo v contiene un nodo già visitato che NON è padre del nodo V

Cioè, se il vertice A ha nella sua lista B e B ha nella sua lista C, se C ha nella sua lista A (B ci sarà per forza) hai un ciclo. Ritorni 0, fine.

2) Credo sia più facile, perché il grafo è ORIENTATO, ma il principio è lo stesso. Se il grafo è orientato non dovresti (se non erro) avere nemmeno il problema di verificare il padre, perché se nella lista di adiacenza hai il padre significherebbe che hai un cappio. Correggetemi se sbaglio!! Quindi in questo caso ti basta sapere se il nodo è già stato visitato, in quel caso vuol dire già che hai un ciclo (un cappio è considerabile un ciclo... o no?), ritorni 1

3)Potrebbe essere così?

code:

leggi n
leggi k
leggi B
Calcola(1, n)

procedura Potenza(x,y)
begin

  if (y=2)
     return x*x
  else
    u = parte_intera_inf(y/2)
    a = Potenza(x, u)
    b = Potenza(x, u+1)
    c = a * b
      if y pari
         return c
      else
         return c*x

end

procedura Calcola(i,j)
  begin
    if i=j
       return Potenza(k, i)
    else
     begin
      u = parte_intera_inf((i+j)/2)
      a = Calcola(i, u)
      b = Calcola(u+1, j)
      return a + b;
    end
end