//*******************************************************************
// Dear CompileJava users,
//
// CompileJava has been operating since 2013 completely free. If you
// find this site useful, or would otherwise like to contribute, then
// please consider a donation (link in 'More Info' tab) to support
// development of the new CompileJava website (stay tuned!).
//
// Most sincerely, Z.
//*******************************************************************

import java.lang.Math; // headers MUST be above the first class

// one class needs to have a main() method
public class HelloWorld
{
  static char[] C={'a', 'b', 'c'};
  static char[] R= {' ', ' ', ' '};
 
  static void combina (int m) {
    if (m==0) {
      System.out.println (R);
      return;
    }
    int i=0;
    while (i<C.length) {
      // tem combina
      //System.out.print (C[i]);
      R[m-1]=C[i];
      combina(m-1);
      i++;
    }
  }
 
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    combina (3);
  }
}

Código para atividade 2

public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    Comparador.inicio();
    for (int i=0;Comparador.menor (i,10);i++) {
      System.out.println (i);
    }
    if (Comparador.igual(0,33)) System.exit (0);
    Comparador.fim();
    Comparador.imprimeResultado();  }
}

public class Comparador
{
  static long tI, tF;
  static int nComp;
 
  Comparador () {
    tI=0;tF=0;nComp=0;
  }

  public static void reIniciaTempo() {
    tI=0;tF=0;
  }
  public static void reIniciaComp() {
    nComp=0;
  }
  public static boolean igual (int a, int b) {
    nComp++;
    return a==b;
  }
  public static boolean menor (int a, int b) {
    nComp++;
    return a<b;
  }

  public static void inicio () {
    tI=System.nanoTime();
  }
  public static void fim () {
    tF=System.nanoTime();
  }
  public static void imprimeResultado () {
    System.out.println ("Tempo transcorrido = " + (tF-tI));
    System.out.println ("Comparações efetuadas = " + nComp);
  }
}

Interface para Atividade 1

O próximo passo é testar esta estrutura: medir tempos de inserção, remoção e busca, contar comparações, em conjuntos de dados pequenos e grandes, graficar, ajustar as escalas e verificar se o que se sabe na teoria é confirmado.

01 /** A classe que implementar esta interface deve ocultar sua estrutura interna. 02     A estrutura interna pode ser qualquer, assim como o funcionamento dos  03     métodos. Assim, precisamos diferenciar elementos internos, que são os que  04     você define para armazenar a informação e elementos externos, que são os 05     usados para passar informação, e que estão nos parâmetros e valores de 06     retorno dos métodos. 07     Para fins deste exercício, a estrutura interna deve ser uma tabela de  08     hashing com solução de colisão por encadeamento. A função de hashing deve 09     ser encapsulada em método privado. 10 */ 11  12 interface Dicionario { 13 /** Cria um elemento interno, copia o que for necessário de 'o' que é 14     elemento externo para o elemento interno, insere o elemento interno na 15     estrutura interna. 16     */ 17    public void insere (Object o); 18 /** Busca um elemento interno com base no elemento externo, caso encontre, 19     preenche o objeto externo com a informação e o retorna. Caso não 20     encontre, retorna null. 21     */ 22    public Object busca (Object o); 23 /** Busca um elemento interno com base no elemento externo, caso encontre, 24     remove-o. 25     */ 26    public void remove (Object o); 27 }

Java2html

MergeSort

01 class Teste { 02   static void imprime (int[] a) { 03     for (int i=0;i<a.length;i++) { 04       System.out.print (a[i] + ","); 05     } 06     System.out.println (); 07   } 08   int[] metadeInicio (int[] a) { 09     /*Metade do inicio do array - estah correto,  10     tem que considerar a quantidade de operacoes. */ 11     int[] r = new int[a.length/2]; 12     for (int i=0;i<a.length/2;i++) { 13       r[i]=a[i]; 14     } 15     return r; 16   } 17    18   int[] metadeFim (int[] a) { 19     /*Metade do fim do array - estah correto, para o  20     exemplo tem que considerar a quantidade de operacoes. */ 21     int mais=(a.length % 2); 22     int[] r = new int[a.length/2+mais]; 23     for (int i=0;i<a.length/2+mais;i++) { 24       r[i]=a[i+mais+a.length/2]; 25     } 26     return r; 27   } 28    29   int[] fazAlgo (int[] a) { 30     imprime (a);  // AQUI IMPRIME! 31     if (a.length<=1) return a; 32     int[] ini=metadeInicio(a); 33     int[] fim=metadeFim(a); 34     fazAlgo (ini); 35     fazAlgo (fim); 36     int i=0, iIni=0, iFim=0; 37      38     while (i<a.length) { 39       if (iIni>=ini.length) { 40         a[i]=fim[iFim]; 41         iFim++; 42       } else if (iFim>=fim.length) { 43         a[i]=ini[iIni]; 44         iIni++; 45       } else if (ini[iIni]<fim[iFim]) { 46         a[i]=ini[iIni]; 47         iIni++; 48       } else { 49         a[i]=fim[iFim]; 50         iFim++; 51       } 52       i++; 53     }   54     imprime (a);  // AQUI IMPRIME! 55     return a; 56   } 57    58   Teste (int[] a) { 59     fazAlgo (a); 60   } 61    62   public static void main (String[] args) { 63     int[] a={5,3,9,7,2,1,4,8}; 64     Teste t = new Teste (a); 65     imprime(a); 66   } 67 }

Java2html

Algoritmo tentativa e erro (incompleto) escrito na aula de 11.08.2017

/** INCOMPLETO: completar! */ public class MyClass {     static int[] valor={6,5,4,3,2,1};//Maior valor primeiro     static int[] peso={3,7,8,9,12,1};     static int pesoMax=20;//kg     static boolean[] solucao = new boolean[valor.length];     static int p=0; // massa na bolsa     static int value=0; // valor na bolsa     static int i =0;     public static void guloso(int i){              //Enquanto cabe itens na mochila e houver elementos a serem testados         while (p<pesoMax && i<valor.length){             if(p + peso[i]<=pesoMax){                 p+=peso[i];                 solucao[i]= true;                 value+= valor[i];                 if(p != pesoMax){                     guloso(i+1);                     p-=peso[i];                     solucao[i] = false;                     value-=valor[i];                 }                              }             i++;         }         for (int j=0; j<solucao.length; j++){             System.out.print(peso[j] + "\t ");             System.out.print(valor[j] + "\t ");             System.out.print(solucao[j]+ "\t \n");         }         System.out.println("Peso na Mochila: " + p);         System.out.println("Valor na Mochila: " + value);     }          public static void main(String args[]) {        guloso(0);     } }

Java2html

Algoritmo guloso escrito na aula de 11.08.2017

public class MyClass {     static int[] valor={6,5,4,3,2,1};//Maior valor primeiro     static int[] peso={3,7,8,9,12,1};     static int pesoMax=20;//kg     static boolean[] solucao = new boolean[valor.length];     public static void guloso(){         int p=0; // massa na bolsa         int value=0; // valor na bolsa         int i=0;         //Enquanto cabe itens na mochila e houver elementos a serem testados         while (p<pesoMax && i<valor.length){             if(p + peso[i]<pesoMax){                 p+=peso[i];                 solucao[i]= true;                 value+= valor[i];             }             i++;         }         for (int j=0; j<solucao.length; j++){             System.out.print(peso[j] + "\t ");             System.out.print(valor[j] + "\t ");             System.out.print(solucao[j]+ "\t \n");         }         System.out.println("Peso na Mochila: " + p);         System.out.println("Valor na Mochila: " + value);     }          public static void main(String args[]) {        guloso();     } }

Java2html

Pseudo-código de algoritmo de tentativa e erro (backtracking) - slide do livro do Ziviani baixado da Web - Aula de 08.08.2017

Em linhas gerais um método guloso tem os passos descritos no slide abaixo:

Desafio 1: Compare os pseudo-códigos do algoritmo guloso e do tentativa e erro. Aponte semelhanças e diferenças.


Desafio 2: Use o algoritmo de tentativa e erro para tentar resolver um problema que conhece, por exemplo o problema da mochila. Procure saber o que é árvore de execução. Simule a execução (ou: faça o teste de mesa) do algoritmo de tentativa e erro representando a simulação em uma árvore de execução.

Desafio 3: Analise o código que escreveu a fim de saber que variável ṕode ser usada como "tamanho do problema" e como o tempo de execução (ou quantidade de operações executadas, ou quantidade de comparações executadas) evolui em função do tamanho do problema.

Desafio 4: Escreva o programa, meça os tempos de execução de diferentes conjuntos de dados para o problema da mochila e construa o gráfico do tempo de execução em função do tamanho do problema. O resultado coincide com o que intuiu no desafio 1?

Problemas muito usados para exemplificar tentativa e erro:

• Passeio do cavalo;
• 8 rainhas;
• n rainhas;
• Problema da mochila;
• Problema do circuito Hamiltoniano.

Próximos assuntos em ordem cronológica (previsto em 06.08.2017):

• combinatória;
• crescimento de funções;
• divisão e conquista (exemplos: busca binária e MergeSort);
• sequências e séries, fórmulas de recorrência e fórmulas fechadas;
• demonstração por indução;
• indução fraca/forte;
• Notação Assintótica;
• Teorema Mestre;
• HeapSort;
• QuickSort;
• Cota Inferior para algoritmos de ordenação, aproximação de Stirling;
• Ordenação em tempo linear;
• Espalhamento (hashing);