//*******************************************************************
// 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);

Pseudo-código de algoritmo guloso - slide do livro do Ziviani baixado da Web - Aula de 04.08.2017

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

Desafio 1: Use o algoritmo guloso para tentar resolver um problema que conhece, por exemplo o problema da mochila. 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 2: Escreva o programa, meça os tempos de execução 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?

Parada4 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 4 (Este já é bom!): 09 */ 10  11 public class Parada4 { 12     //int i=10; 13     public void soma (int i) { 14         //int i=10; 15         if (i<=0) return; 16         //i--; 17         soma(i-1);  /* A diferença com Parada3 é que este 18                        não modifica o valor de i no método 19                        chamador (o que pode ter consequências 20                        dependendo do que codificarmos depois. */ 21         System.out.println ("somei - " + i); 22     } 23     public static void main(String args[]) { 24         Parada4 m = new Parada4(); 25         m.soma(10); 26     } 27 }

Java2html

Parada3 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 3 (Este já é bom!): 09 */ 10  11 public class Parada3 { 12     //int i=10; 13     public void soma (int i) { 14         //int i=10; 15         if (i<=0) return; 16         System.out.println ("somei"); 17         i--;        /*Assim é mais seguro que soma(--i),  18                       que deve ter o mesmo efeito. */ 19         soma(i);    /* soma(i--) tem efeito diferente,  20                        de acordo com a norma pois 21                        --i e i-- tem precedências diferentes.*/ 22     } 23     public static void main(String args[]) { 24         Parada3 m = new Parada3(); 25         m.soma(10); 26     } 27 }

Java2html

Parada2 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 2 (Para, em determinadas condições 09     até faz o que gostaríamos, em outras condições 10     não faz... a questão é o escopo de i: a variável 11     i não foi declarada no escopo usual para métodos 12     recursivos): 13 */ 14  15 public class Parada2 { 16     int i=10; 17     public void soma () { 18         //int i=10; 19         if (i<=0) return; 20         i--; 21         System.out.println ("somei"); 22         soma(); 23     } 24     public static void main(String args[]) { 25         Parada2 m = new Parada2(); 26         m.soma(); 27     } 28 }

Java2html

Parada1 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 1 (não para): 09 */ 10  11 public class Parada1 { 12     public void soma () { 13         int i=10; 14         if (i<=0) return; 15         i--; 16         System.out.println ("somei"); 17         soma(); 18     } 19     public static void main(String args[]) { 20         Parada1 m = new Parada1(); 21         m.soma(); 22     } 23 }

Java2html

Métodos e pilha de execução - Aula de 01.08.2017

01 /** A construção de um método recursivo em partes. 02     Parte 1: um método que "invoca a si mesmo". 03     O que acontece quando o programa abaixo é 04     executado? 05      06     A invocação e o retorno de métodos é implementada 07     na máquina virtual Java (JVM) com a ajuda da pilha de 08     execução. Nela são armazenados o endereço de retorno 09     e os parâmetros (cabe refletir sobre o tipo dos  10     parâmetros e conectar os conceitos). 11     Note que em java, quando executamos a JVM esta, sem  12     nossa intervenção direta, invoca o método main do 13     arquivo .class que passamos como argumento de linha de 14     comando.  15      16     Na execução de qualquer método (no exemplo usaremos 17     main), quando INVOCAMOS um método (que pode ser outro 18     ou pode ser o mesmo), antes de executar o código que 19     você escreveu, são escritos na pilha o endereço de memória 20     do próximo comando no método "invocador" (main), a que  21     chamamos endereço de retorno, e copiados  22     os valores que devem ser armazenados nos parâmetros. Então 23     passa-se a executar o método invocado. 24      25     Ainda antes de executar o código que você escreveu,  26     os parâmetros (mais precisamente as  27     variáveis locais ao método que têm os identificadores 28     que correspondem aos parâmetros no código-fonte)  29     são alocados e os 30     valores desempilhados e armazenados nessas variáveis. 31      32     Note que na pilha restou somente o endereço de retorno. 33     O código que você escreveu passa a ser executado e  34     quando atingir um return ou o fim do método, o endereço 35     de retorno é desempilhado e usado para voltar a executar 36     o método "invocador".  37      38     O que também é importante observar é que se invocamos 39     métodos que não "retornam", os endereços de retorno 40     acumulam na pilha de execução e esta tem tamanho  41     limitado. Quando ultrapassa-se esse limite ocorre um 42     "transbordamento de pilha" (chamado também estouro de 43     pilha), em inglês: stack overflow. Que é a exceção  44     informada na execução do programa abaixo. 45      46 */ 47  48 public class MyClass { 49     public void soma () { 50         System.out.println ("somei"); 51         soma(); 52     } 53     public static void main(String args[]) { 54         MyClass m = new MyClass(); 55         m.soma(); 56     } 57 }

Java2html

Parâmetros - Aula de 01.08.2017

01 /** passagem de parâmetros 02     Em Java, o que é armazenado em  03     variáveis de tipo primitivo? 04     O que é armazenado em variáveis  05     de tipo abstrato (objetos)? 06     Como isso influencia a passagem de 07     parâmetros e a modificação de 08     variáveis dentro e fora do escopo 09     do método?  10     O exemplo abaixo ilustra esses 11     processos. Atenção especial sobre 12     que variáveis são modificadas pelo 13     método soma e como isso repercute 14     no método main. 15  16 */ 17  18 public class MyClass { 19     static int[] a = {1,2,3,4,5,6}; 20     public int soma (int[] a, int b) { 21         b=33; 22         a[0]=a[0]+b; 23         System.out.println (a[0]); 24         System.out.println (b); 25         return a[0]; 26     } 27     public static void main(String args[]) { 28         int x=10; 29         int y=25; 30         MyClass m = new MyClass(); 31         System.out.println("Sum of x+y = " + m.soma (a,y)); 32         System.out.println (a[0]); 33         System.out.println (y); 34     } 35 }

Java2html