Implementar Algoritmo de pesquisa

11 de fevereiro de 2011 3 respostas

explod1ng 11 de fevereiro de 2011

Input

O input consistirá em sequências de valores inteiros positivos (entre 1 e 1.000).

A primeira linha de cada subsequência terá o tamanho da subsequência e o VALOR a pesquisar.

As linhas seguintes apresentam os elementos da subsequência (um por linha).

Uma linha com o par ?0 0? indica o final do input.

Output

Para cada sequência do input o programa deverá indicar, consoante exista ou não uma
subsequência cuja soma seja igual a VALOR:

SUBSEQUENCIA NAO ENCONTRADA

SUBSEQUENCIA NA POSICAO i (sendo i a posição a partir da qual está a subsequência)

Exemplo de Input
3 8
10
5
1
7 5
1
2
3
4
5
6
7
0 0

Exemplo de Output
SUBSEQUENCIA NAO ENCONTRADA
SUBSEQUENCIA NA POSICAO 2

Na primeira resolução do problema, deverá ser usado um algoritmo baseado na pesquisa directa e
exaustiva de todas as sequências possíveis:

PARA i=1 ATÉ N { 
           PARA j=i ATÉ N
          {
               soma = 0;
           PARA z = i ATÉ j
          {
               soma = soma + sequencia[z]
          }
          SE soma == VALOR ENTÃO
         {
                Subsequencia existe na posição i
                TERMINA
         }
}
}
Subsequência não existe

Já implementei o algoritmo pedido em Java ficando assim:

public class B {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        for (int i = 1;i<len(N);i++){
            for (int j = i;j<len(N);){
                int soma =0;
                for(int z=i;z<j;){
                    soma = soma + sequencia[z];
                }
                if (soma== valor){
                    System.out.println("Subsequencia existe");
                    break;
                }
            }
        }
        System.out.println("Subsequencia nao existe");
    }

}

Agora a minha dúvida é na parte de inputs e outputs uma vez que estes: “Para cada execução o Mooshak lê o input na entrada default (stdin) e produz o output na saída default (stdout).”, ou seja não sei como atribuir os valores de input as variaveis Valor, N e sequencia, uma vez que não sei como usar o stdin e o stdout. Se alguém conseguir ajudar agradeço.

3 Respostas

javer 12 de fev. de 2011

StdIn
StdOut

explod1ng 12 de fev. de 2011

Obrigado pela ajuda. Encontrei o seguinte código que penso que ajuda a resolver o problema que estava a ter:

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String s;

while ((s = in.readLine()) != null && s.length() != 0)

System.out.println(s);

// An empty line or Ctrl-Z terminates the program

}

So que na implementação deste codigo surgiu-me outro problema:

Exemplo de Input
3 8
10
5
1
7 5
1
2
3
4
5
6
7
0 0

O input deve parar ao encontrar a sequencia 0 0, alem disso tenho 3 variaveis no meu algoritmo, N que devia ficar com o tamanho da sequencia no caso deste exemplo 3 e depois 7, Valor que fica com o valor a pesquisar 8 e 5 e por fim sequencia que fica com os valores da sequencia:{10,5,1}; etc. O problema e que não estou a conseguir atribuir os valores as variáveis. Se alguém conseguir dar uma ajuda ou explicação da melhor maneira para fazer isso agradeço.

explod1ng 12 de fev. de 2011

import java.io.*;
import java.util.*;
/**
 *
 * @author pauleta
 */
public class B {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int [] sequencia = null;
        Scanner stdin = new Scanner(System.in);
        while(stdin.hasNext()){
            int N = stdin.nextInt();
            int valor = stdin.nextInt();
            if((N==0)||(valor==0))
                break;
            sequencia = new int[N];
            for(int i=0;i<N;i++){  
                sequencia[i]=stdin.nextInt();
       
            }
            int index = exaustiva(N,valor,sequencia);

            if (index == 0)
                System.out.println("SUBSEQUENCIA NAO ENCONTRADA");
            else
                System.out.println("SUBSEQUENCIA EXISTE NA POSICAO " +index);
            //stdin.nextLine();
        }
    }

    public static int exaustiva(int N, int valor, int[] sequencia){
        for (int i = 1;i<=N;i++){
            for (int j = i;j<=N;j++){
                int soma =0;
                for(int z=i;z<=j;z++){
                    soma = soma + sequencia[z-1];
                }
                if (soma== valor){
                    return i;
                }
            }
        }
        return 0;
    }
}

Já tenho o algoritmo a funcionar e o codigo apenas tem um bug que nao tou a conseguir resolver.

Tendo em conta o input:

3 10
2
3
4
7 5
1
2
3
4
5
6
7
0 0

Quando o programa entra as variaveis N e valor vao ficar com os valores 3 e 10. Depois o programa devia saltar para a linha seguinte para ir buscar o valor 2 e meter no array sequencia, depois o valor 3 e 4 indo sempre buscar a linha seguinte. Depois terminando de preencher o array sequencia o programa corre o algoritmo e depois do algoritmo corrido e de verificado se a subsequencia existe ou nao, devia novamente saltar a linha para as variaveis valor ficarem com os valores 7 e 5 e novamente saltar de linha para começar a preencher o array sequencia. O problema e que não estou a conseguir fazer este salto de linha, ja experimentei o .nextLine() mas nao está a resultar.

Criado 11 de fevereiro de 2011

Ultima resposta 12 de fev. de 2011

Respostas 3

Participantes 2

3 Respostas

Topicos relacionados