Recursão: Divisão e Conquista

[BlackHeartX 0]

Oi gente,

 

Estou precisando de uma ajudinha na solução de dois problemas. São os seguintes:

 

 

1) Sejam X e Y dois vetores ordenados de tamanho n e m, respectivamente. Desenvolva um algoritmo para encontrar o k-ésimo elemento de XUY (xis unido à ipsolon). O algoritmo deve executar em O(log(m) + log(n)) unidades de tempo (complexidade). Note que intercalar X e Y para identificar o elemento na k-ésima posição leva a um algoritmo O(k), o que pode ser menos eficiente que O(log(m) + log(n)).

 

2) Suponha uma pesquisa de opinião pública onde os entrevistados respondem à seguinte pergunta: qual a marca de produto mais popular dentre todas que você conhece? as respostas de n entrevistados são armazenadas num vetor V. Elabore um algoritmo de tempo de execução linear para identificar se existe uma marca citada por mais da metade dos entrevistados. O algoritmo não deve alocar memoria extra além da necessária para armazenar V.

 

 

A primeira eu ainda tenho dúvidas quanto a resolução, mas eu pensei em fazer a segunda usando a estratégia de Ordenação por Contagem que está no Cormen (só não sei exatamente como). As soluções devem apresentar as técnicas de Divisão e Conquista em ordem a obter a complexidade especificada no problema (dá para verificar a complexidade do algoritmo usando arvore de recursão, por exemplo). O real problema esta em atingir a complexidade especificada (por isso não adianta QUALQUER algoritmo, recursão é quase uma exigência). O algoritmo pode ser escrito em pseudo-código também, além de C/C++ (dá pra converter sem problemas, não acho que eles sejam algoritmos muito grandes).

 

Alguem pode me dar uma luz?

[BlackHeartX 0]

Bom, eu respondi o bagulho ai. Virei a noite (mas não tinha muita escolha mesmo, pois era pra nota). Vou compartilhar com vocês:

 

int Localiza(int A[], int B[], double c1, double n1, double c2, double n2, int k) {

        int x = (int) Math.ceil( (c1+n1)/2);
        int y = (int) Math.ceil( (c2+n2)/2);
        int p = A[x];
        int q = B[y];
        int w = x + y;

        int n1int = (int) n1, c1int = (int) c1, n2int = (int) n2, c2int = (int) c2;

        if(k == 1) {
            return (Math.min(A[1], B[1]));
        }
        if(k == ( n1int + n2int )) {
            return(Math.max(A[n1int], B[n2int]));
        }
        if(B[c2int] >= A[n1int] || A[c1int] >= B[n2int]) {
            if(B[c2int] >= A[n1int]) {
                if(k <= n1int) {
                    return A[k];
                }
                else {
                    return B[k - n1int];
                }
            }
            if(A[c1int] >= B[n2int]) {
                if(k <= n2int) {
                    return B[k];
                }
                else {
                    return A[k - n2int];
                }
            }
        }
        if(w > k) {
            if( n1int == c1int || n2int == c2int )  {
                return Math.min(p, q);
            }
            if(p > q) {
                return Localiza(A, B, c1, Math.floor((c1 + n1)/2), c2, n2, k);
            }
            else {
                return Localiza(A, B, c1, n1, c2, Math.floor((c2 + n2)/2), k);
            }
        }
        if(w <= k) {
            if(n1int == c1int || n2int == c2int) {
                return Math.max(p, q);
            }
            if(p > q) {
                return Localiza(A, B, c1, n1, Math.ceil((c2 + n2)/2), n2, k);
            }
            else {
                return Localiza(A, B, Math.ceil((c1 + n1)/2), n1, c2, n2, k);
            }
        }

        return 0;
    }

int Encontra(int A[], int n) {

        int k, c;

        k = A[1];
        c = 1;

        for(int i = 2; i<=n; i++) {
            if(k == A[i]) {
                c++;
            }
            else {
                c--;
                if(c == 0) {
                    k = A[i];
                    c = 1;
                }
            }
        }

        int z = n-1, cant = c, kant = k;
        k = A[n];
        c = 1;

        while(z >= 1) {
            if(k == A[z]) {
                c++;
            }
            else {
                c--;
                if(c == 0) {
                    k = A[z];
                    c = 1;
                }
            }
            z--;
        }

        if(kant == k) {
            if(c >= ((n/2)+1) - (n-(n/2)-1)) {
                return k;
            }
        }
        return 0;
    }

 

Terminou ficando em Java (o professor liberou java, mas como eu não uso nenhuma função unica da linguágem, a conversão para C/C++ não deve ser problema). Fica como um bom exemplo de recursividade.

 

A primeira ainda NÃO está completa. Ela falha para algumas certas entradas, ainda vou checar isso. Se alguem quiser, posta ai.

[_Isis_ 202]

Só um detalhe: o que são x,y,p,q,w,k,c,kant e cant?

Os nomes das variáveis não estão nada explicativos. No primeiro enunciado, X e Y são os vetores, mas no primeiro código, são doubles quaisquer obtidos com uma equação que não me diz nada sobre ela (por que o ceil? de onde veio o ceil?).

Lembro de ter lido um fonte onde cada linha do código era comentada, informando o que estava sendo feito (pra quem conhece as construções da linguagem é óbvio que um for itera sobre alguma coisa, que int a; é uma declaração de variáveis e que #include{/b] inclui um header -- não é necessário escrever isso). No entanto, você não sabia o que o código fazia de cara porque tinha que adivinhar que era o cálculo de raiz quadrada pelo método da aproximação de Newton.

 

http://www.infoq.com/br/news/2010/03/To-Comment-or-Not-to-Comment

[BlackHeartX 0]

Só um detalhe: o que são x,y,p,q,w,k,c,kant e cant?

Os nomes das variáveis não estão nada explicativos. No primeiro enunciado, X e Y são os vetores, mas no primeiro código, são doubles quaisquer obtidos com uma equação que não me diz nada sobre ela (por que o ceil? de onde veio o ceil?).

Lembro de ter lido um fonte onde cada linha do código era comentada, informando o que estava sendo feito (pra quem conhece as construções da linguagem é óbvio que um for itera sobre alguma coisa, que int a; é uma declaração de variáveis e que #include{/b] inclui um header -- não é necessário escrever isso). No entanto, você não sabia o que o código fazia de cara porque tinha que adivinhar que era o cálculo de raiz quadrada pelo método da aproximação de Newton.

 

http://www.infoq.com/br/news/2010/03/To-Comment-or-Not-to-Comment

 

Heh, não é uma boa prática, sei disso. De fato, postei o código sem comentários pois também precisei escrever um relatório com o cálculo da complexidade, e nele está contido todas as devidas explicações passo a passo, com todas as variáveis bem definidas e devidamente comentadas. Posso postar o relatório assim que conclui-lo, daí ficará intuitivo compreender o código.

 

Em nota, o ceil representa o teto de um valor real. Ele arredonda para o inteiro mais próximo de um número, sempre para cima. Precisei utiliza-lo, pois recursivamente dividia o vetor em 2, pegando o elemento médio (somando c1 + n1 e dividindo por 2) mas nem sempre o valor obtido era inteiro e, portanto, não determinava uma posição válida do vetor. O primeiro algoritmo funciona assim (direto do meu relatório):

 

O algoritmo utiliza-se do principio da Busca Binária, porém dotado de certas peculiaridades. Dados dois vetores, toma-se as posições dos elementos médios de cada vetor e armazena sua soma em uma variável w. Sabe-se que a soma dessas posições representará a menor posição possível que o maior dos dois elementos médios poderá ocupar. Com base nesse fato, elimina-se a segunda metade do vetor que contém o maior dos dois elementos médios se a posição k buscada for menor que o valor de w (pois nesse caso seria irrelevante procurar nessa metade eliminada, já que se sabe que ela apenas possuirá elementos em posições superiores ao k buscado no vetor união). Elimina-se a primeira metade do vetor que contém o menor elemento, quando o k buscado for maior ou igual ao w em análise (por razões similares as dadas anteriormente). O algoritmo retorna um valor quando um dos vetores for restringido o suficiente para se retornar com segurança o valor da posição que representa a posição k no vetor união.

 

Um resumo básico dele. Depois eu posto algo mais detalhado.

[_Isis_ 202]

Eu sei o que a função ceil faz. O que não se sabe de imediato quando se lê o programa é a função dela no procedimento, que também é desconhecido. Entendeu? Não poste códigos sem dizer o que você está tentando fazer com ele (isso vale pras outras pessoas que aparecerem por aqui e lerem isso)