Exercícios CANA

[Glauber]

Alguém já começou fazer os exercícios? Daqui a pouco posto o rascunho
que fiz de uma questão para que possamos chegar a uma resposta correta.

[Thiago Macedo]

  Eu já andei resolvendo as questões, no que puder auxiliar...

-------------------------

Att.

Thiago Crystyan

[Glauber]

2.1-3
Considere o problema de pesquisa :
Entrada: Uma sequência de n números A = (al, a2, ..., an) e um valor
v.
Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não
aparecer em A.
Escreva o pseudocódigo para pesquisa linear, que faça a varredura da
sequência, procurando
por v. Usando um loop invariante, prove que seu algoritmo é correto.
Certifique-se de que seu
loop invariante satisfaz às três propriedades necessárias.


Algoritmo

i ← 1
v
saida ← 0
for i←1 to comprimento[A] do
if A[i] = v
then
saida ← A[i]
i ← i + 1
else
i ← i + 1
if saida = 0
then
saida ← null


Se o algoritmo estiver correto, como faço invariante de loop?

On 25 fev, 15:32, Thiago Macedo <crystyan...@gmail.com> wrote:
>   Eu já andei resolvendo as questões, no que puder auxiliar...
> -------------------------
> Att.
> Thiago Crystyan
>

[Thiago Macedo]

Cara eu fiz assim

 

for i  1 to n do

  if A[i] = v then

    return i
  end if
end for
return nil

 

 Pra ivariante de loop garantimos que nenhum dos elementos de indice A[1...i-1] estão no array.

[Glauber Bezerra]

Desse jeito ele retorna nil, mesmo depois de retornar o i?

[Thiago Macedo]

Não cara, tem de abstrair que seja um programa estrutura, imagine isso como uma função que retorna ou uma coisa ou outra.

[Glauber]

blz então.

Com relação a questão 2.1-4 - Somar dois inteiros binários de n bits.
Nesse caso criei dois arranjos A e B com o tamanho do comprimento de A
e B e depois tem que vir somando da direita para esquerda e sempre
atentando para o "sobra 1". Tenho que ir até o final do array de A e
somar com o último elemento de B e assim por diante, mas como sei o
tamanho final (C) para criar o array C?

valeu

On 25 fev, 17:57, Thiago Macedo <crystyan...@gmail.com> wrote:
> Não cara, tem de abstrair que seja um programa estrutura, imagine isso como
> uma função que retorna ou uma coisa ou outra.
> -------------------------
> Att.
> Thiago Crystyan
>

> Em 25 de fevereiro de 2011 17:30, Glauber Bezerra <gtbeze...@gmail.com>escreveu:
>
> > Desse jeito ele retorna nil, mesmo depois de retornar o i?
>

> > Em 25 de fevereiro de 2011 16:57, Thiago Macedo <crystyan...@gmail.com>escreveu:
>
> >  Cara eu fiz assim
>
> >> for i  1 to n do
>
> >>   if A[i] = v then
> >>     return i
> >>   end if
> >> end for
> >> return nil
>
> >>  Pra ivariante de loop garantimos que nenhum dos elementos de indice
> >> A[1...i-1] estão no array.
> >> -------------------------
> >> Att.
> >> Thiago Crystyan
>

[Thiago Macedo]

Cara essa eu não fiz, mas tu uma coisa é certa o C ele pode vir a ter o tamanho do maior, se for A ou B, mais um, justamente por causa do resta 1.

 

 Valeu.

[Thiago Barcelos]

Pessoa, ainda estou sem acesso ao unifor online.O professor já
disponibilizou a lista de exercícios??

On 28 fev, 09:32, Thiago Macedo <crystyan...@gmail.com> wrote:
> Cara essa eu não fiz, mas tu uma coisa é certa o C ele pode vir a ter o
> tamanho do maior, se for A ou B, mais um, justamente por causa do resta 1.
>
>  Valeu.
> -------------------------
> Att.
> Thiago Crystyan
>

> > > >>> correta.- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

[Glauber Bezerra]

Segue a lista


Gláuber Bezerra

[Leonardo Silveira]

questão 2.3-5

Como chegar na recorrencia? e demonstrar que é teta(lg n)

??? Se alguem souber vai ajudar bastante

[Glauber Bezerra]

Segue o algoritmo que peguei no gabarito, acho que é (lg n) porque na pior situação ele entra no if e depois chama a recursão..



Input: A sorted array A and a value v.
Output: An index i such that v = A[i] or nil.
if p >= r and v<> A[p] then
  return nil
  end if
j<--- A[(r - p)/2]
if v = A[j] then
  return j
  else
    if v < A[j] then
      return BINARY-SEARCH(A, v, p, j)
    else
      return BINARY-SEARCH(A, v, j, r)
    end if
end if

--
Atenciosamente,
Gláuber Bezerra
tel.: 85 9177-9604
tel.: 85 9901-4301
"Não faça da sua falta de planejamento a minha urgência."

[Brunow]

Encontrei esse aqui, que parece mais simples

int busca_b(int a[], int x, int baixo, int alto)

}

int meio;

if (baixo > alto)

   return(-1);

meio = (baixo + alto)/2;

return(x == a[meio]) ? meio : x < a[meio] ? busca_b(a, x, baixo, meio-1) : busca_b(a, x, meio+1, alto);

Acredito que 

T(n) = 1 se n=1

          T(n/2)+c se n>1

é isso mesmo? Não existe outro N por não existir laços dentro do algoritmo, não é?

Alguém conseguiu resolver a 4.3-2? Alguém tem anotado como que ele chega no log, a partir do somatório no caso da Arvore de recursão?

Essa prova vai ser loucura... =P

2011/4/3 Glauber Bezerra <gtbe...@gmail.com>

--
Bruno Muniz

SoftSite Tecnologia
www.softsite.com.br
Fortaleza: +55 (85) 3278 1698

[Glauber Bezerra]

A questão 4.3-2 é sobre método mestre, acho que seria a 4.2-3, não? Se for essa eu cheguei em teta(n2) tranquilo, mas não consegui provar usando o método da substituição.

--
Atenciosamente,
Gláuber Bezerra
tel.: 85 9177-9604
tel.: 85 9901-4301
"Não faça da sua falta de planejamento a minha urgência."

[Glauber Bezerra]

Achei esse outro algoritmo para busca binária

V: vetor com elementos
e: o elemento que se deseja encontrar

BUSCA-BINÁRIA (V[], início, fim, e)
     i recebe o índice do meio entre início e fim
     se (v[i] = e) entao
         devolva o índice i   # elemento e encontrado
     senão (inicio = fim) entao
         não encontrou o elemento procurado
     senão
        se (V[i] vem antes de e) então
           faça a BUSCA-BINÁRIA(V, i+1, fim, e)
        senão
           faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
        fimse
     fimse

--
Atenciosamente,
Gláuber Bezerra
tel.: 85 9177-9604
tel.: 85 9901-4301
"Não faça da sua falta de planejamento a minha urgência."