2014/1: PA: Árvore digital em Java

package pa.arvore.digital01;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author aluno
 */
public class NoArvoreDigital {
    
    char caractere;
    List<NoArvoreDigital> nos;
    
    // construtor
    public NoArvoreDigital(char a)
    {
        this.caractere = a;
        nos = new ArrayList<NoArvoreDigital>();
    }
    
    // inserir palavra
    public boolean inserirPalavra(String palavra)
    {    // 1) obter a primeira letra
        if (palavra.length() == 0)
            return true;
        char letra = palavra.charAt(0);        
        if (palavra.length() > 1)
            palavra = palavra.substring(1);
        else
            palavra = "";
        // 2) verificar se a letra existe na arvore
        NoArvoreDigital no = obterNo(letra);
        if (no != null){// 3) Se ela existir
        // 3.1) obter o no correspondente                
        // 3.2) inserir o resto da palavra neste no
            return no.inserirPalavra(palavra);
        } else {  // 4) Se ela nao existir
        // 4.1) criar um novo nó com o caractere corrente                
            no = new NoArvoreDigital(letra);
            nos.add(no); // 4.2) Adicionar o no na lista de nos
        // 4.3) inserir o resto da palavra neste no
            return no.inserirPalavra(palavra);
        }       
    }
    
    public NoArvoreDigital obterNo(char letra)
    {
        for (NoArvoreDigital no: nos)
        {
            if (no.caractere == letra)
                return no;
        }
        return null;
    }

    @Override
    public String toString() {
        
        return "[" + caractere +"] -> " + 
                nos.toString();
    }
    
    // metodo que verifica se a palavra existe dentro da
    // arvore digital
    public boolean existe(String palavra)
    {
        // 1) obter o primeiro caractere
        if (palavra.length() == 0)
            return true;
        char letra = palavra.charAt(0);
        // 2) obter o restante da palavra
        if (palavra.length() > 1)
            palavra = palavra.substring(1);
        else
            palavra = "";
        // 3) Se o caractere existir no nó
        NoArvoreDigital no = obterNo(letra);
        if (no != null){
        // 3.1) buscar no nó que contem o caractere
            return no.existe(palavra);
        } else {// 4) Senao
        // 4.1) informar que a palavra não existe      
            return false;
        }
    }
    
    public void imprimir()
    {
        for (NoArvoreDigital no:nos)
        {
            System.out.print ("["+no.caractere+"] -> ");
            no.imprimir();
            System.out.println();
        }
    }
    
}

---

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package pa.arvore.digital01;

/**
 *
 * @author aluno
 */
public class PaArvoreDigital01 {

    /**
     * @param args the command line arguments
     */
    public static void main(String [] args)
    {
        NoArvoreDigital no = new NoArvoreDigital('*');
        no.inserirPalavra("texto");
        no.inserirPalavra("teste");
        no.inserirPalavra("casa");
        no.inserirPalavra("tomate");
        System.out.println(no);     
        no.imprimir();
        
        String palavra = "teste";
        System.out.println(palavra + "-> " + no.existe(palavra));
        palavra = "cas";
        System.out.println(palavra + "-> " + no.existe(palavra));
        palavra = "teto";
        System.out.println(palavra + "-> " + no.existe(palavra));
        
    }
    
}

2014-1: Algoritmos e Programação: Busca sequencial e ordenação

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

void ordenarPorSelecao(unsigned short a[], int tam)
{
    int i, j, menor, aux;
    for (i = 0; i < tam; i++){
        menor = i;
        for (j = i + 1; j < tam; j++){
           if (a[j] < a[menor]) 
              menor = j;
        }
        if (menor != i){
          aux = a[menor];
          a[menor] = a[i];
          a[i] = aux;
        }
    }
cout << "Depois de ordenado: " << endl;
    for (int i = 0; i < tam; i++){
        cout << a[i] << "\t";
    }     
}

// funcao que realiza a busca sequencial
// a[]: tabela de dados
// tam: tamanho da tabela de dados
// v  : valor a ser buscado na tabela
// retorno int: posicao de v em a[] caso ele exista, 
//              -1 caso contrario
int buscaSequencial(unsigned short a[], int tam, 
unsigned short v)
{
  int pos = -1; // assumir que o elemento nao existe
  for (int c = 0; c < tam; c++){
      if (a[c] == v){
          pos = c;
          break;
      }
  }
  return pos;
}

int main(int argc, char *argv[])
{
    // Problema
    // Entrada: Um numero digitado pelo usuário e um 
    // vetor/tabela com 1M de números aleatórios
    // Saída: Informar se o número existe na tabela ou não

    // Descrição textual
    // 1) Ler do usuario um numero inteiro
    int tam = 10;
    unsigned short t[tam]; // tabela de dados
    unsigned short n; // entrada do usuario
    int c; // contador
    cout << "Digite um numero inteiro: "<< endl;
    cin >> n;
    // 2) Gerar os numeros aleatorios e armazena-los
    //    no vetor
    srand(time(NULL)); // inicializa o gerador
    for (int i = 0; i < tam; i++){
        t[i] = rand() % 65454;
    }
    // 3) Executar a busca sequencial sobre o vetor
    int r = buscaSequencial(t, tam, n);
    if (r == -1){
       cout << "Resultado não encontrado." << endl;
    } else {
      cout << "Valor encontrado na posicao " << r << endl;
    }
    
    // 4) Exibir o vetor na tela
    for (int i = 0; i < tam; i++){
        cout << t[i] << "\t";
    }
    // 5) ordenar o vetor
    ordenarPorSelecao(t, tam);
    // 6) exibir o vetor ordenado
    cout << "Depois de ordenado: " << endl;
    for (int i = 0; i < tam; i++){
        cout << t[i] << "\t";
    }    
    system("PAUSE");
    return EXIT_SUCCESS;
}