Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP

Aula Prática #01 - Introdução ao Java
(17/02 a 21/02)

Nesta e noutras aulas, quando for indicado um comando para correr na shell, verá algo como o seguinte (onde $ é apenas o símbolo da prompt e não deverá ser introduzido):

$ ls -l

Um pedaço de código no meio de uma alínea de um exercício vem indicado do seguinte modo:

int i = 0;

Para apoiar as aulas práticas disponibilizamos outros recursos online que podem também servir de referência, nomeadamente:

Para as aulas práticas é fortemente recomendado que use apenas um editor simples (algo como o Emacs) e não um IDE complexo com auto-complete (algo como o Eclipse) para que realmente tenha perceba tudo o que está a acontecer e não dependa de ajuda externa (é possível que nas avaliações apenas possa usar um editor simples).

Note também que o horário das aulas práticas deve ser interpretado como horas de contacto, onde pode tirar dúvidas com o seu docente. É no entanto muito importante e expectável que trabalhem fora da hora das aulas práticas. Iremos sempre divulgar o guião da aula antecipadamente, para que possam ir trabalhando nele antes da aula. Para tirar dúvidas iremos usar o Piazza de EDados 19/20, onde qualquer um dos 5 docentes (ou até mesmo outros alunos) lhe poderá responder.

Exercício 1) O meu primeiro programa em Java

// Uma classe muito simples que usa um ciclo para imprimir numeros entre 1 e n

// O ficheiro tem de ter o mesmo nome da classe + a extensão '.java'
public class Numbers {
    public static void main(String[] args) {
	int n = 10; // limite dos numeros
	
	System.out.println("Numeros de 1 a " + n + ":"); // + é o operador de concatenação de strings
	for (int i=1; i<=n; i++)
	    System.out.println(i);
    }
}

  1. A minha primeira execução de código Java.
    Copie este pedaço de código para um ficheiro, compile-o e execute o programa (ver secção de compilação e execução da introdução).
    1. Como se deve chamar o ficheiro? O que diz o compilador se o ficheiro tiver outro nome?
    2. Com que nome fica o ficheiro resultante da compilação?
    3. Qual o resultado da sua execução? Experimente mesmo executar o programa
  2. Case Sensitive?
    Experimente mudar logo na primeira linha a palavra class, alterando-a para Class. O que acontece se voltar a compilar? Porquê?
  3. Erros de compilação
    Experimente retirar o ';' na declaração da variável n e compile. O que acontece?
  4. Escrevendo código.
    Modifique o programa para que passe a escrever os números todos na mesma linha, separados por vírgulas (sem nenhuma vírgula a mais no final, mas com mudança de linha) Exemplo de execução pretendida:
    $ java Numbers
Numeros de 1 a 10: 1,2,3,4,5,6,7,8,9,10
$
  5. Somando números.
    Acrescente ao programa código para somar todos os números entre 1 e n e no final imprimir a soma.

Exercício 2) Procedimentos

public class Square {
    // Desenha uma linha de n caracteres onde:
    // - o primeiro e o último caracteres são o caracter da variável 'a'
    // - todos os outros caracteres são o caracter da variável 'b'
    static void line(char a, char b, int n) {
	System.out.print(a);
	for (int i=1; i<=n-2; i++)
	    System.out.print(b);
	System.out.println(a);
    }

    // O procedimento executado inicialmente é sempre o main
    public static void main(String[] args) {	
	line('*','-',5);	    
    }
}

  1. Um procedimento simples.
    Copie este pedaço de código para um ficheiro, compile-o e execute o programa.
  2. Criando um novo procedimento.
    O objectivo deste exercício é criar um novo procedimento square(int n) que quando chamado desenha um quadrado de tamanho n. Por exemplo, uma chamada a square(6) deve resultar na escrita de: 
    +----+
|....|
|....|
|....|
|....|
+----+

Exercício 3) Funções e instruções condicionais

public class Primes {
    // Verifica se o número n é primo (apenas divisível por 1 e por si próprio)
    // [função ainda por completar]
    static boolean isPrime(int n) {
	return true;
    }
    
    public static void main(String[] args) {
	
	int n=1000; // Limite dos números
	
	for (int i=2; i<=n; i++)
	    if (isPrime(i))
		System.out.println(i);
    }
}

  1. Testando o código base.
    Compile e execute este código. Qual o resultado?
    • Se quisesse saber o número de linhas escrito poderia por exemplo usar o comando wc de Linux. Por exemplo, a seguinte linha de comandos envia o output do seu programa (usando um pipe) para o wc no modo -l (contagem de linhas). 
      $ java Primes | wc -l
999
$
  2. Função isPrime.
    Preencha agora o conteúdo da função isPrimepara o código ficar correcto.
    • Um número é primo se apenas for divisível por 1 e por si próprio
    • A função deve retornar true se o número for primo e false caso contrário.
    • Faça um ciclo entre 2 o número e se algum outro número dividir n, então indique que ele não é primo, saindo logo da função.
      (sim, é possivel fazer melhor que testar todos os números, e nos próximos exercícios vamos fazer evoluir o código para algo mais eficiente).
    • Como saber se um número divide outro? Que tipo de operador é necessário? (ver secção de operadores da introdução)
    • Se o programa estiver correcto, para n=1000 deverá encontrar 168 números primos (use o comando wc como atrás descrito para verificar).
  3. Medindo o tempo.
    Neste exercício vamos querer ver quanto tempo o seu programa demora. Para isso vamos usar o comando time de Linux.
    1. Comece por usar time com o seu programa para verificar quanto tempo demora. Deverá ver algo como: 
      $ time java Primes | wc -l
168

real	0m0.079s
user	0m0.076s
sys	0m0.008s
$
    2. Experimente agora mudar n para cem mil e veja quanto tempo demora (nao se esqueça de de recompilar antes de voltar a executar).
    3. Se n for um milhão quanto tempo demora?
      (se ficar cansado de esperar pode parar a execução fazendo Control+C)
  4. Melhorando a eficiência. Vamos agora melhorar a eficiência da função isPrime para melhorar o tempo de execução.
    Em vez de testar como divisores todos números entre 2 e n, basta testar entre 2 e √n. (Porquê?) Modifique o seu programa para fazer isso (não precisa de saber como calcular raízes quadradas em Java, pois não?) e meça o tempo de execução para verificar se melhorou.
     
    (Existiam ainda outras melhorias possíveis à função, mas vamos fazer algo completamente diferente no próximo exercício para calcular números primos).

Exercício 4) Arrays e Crivo de Eratóstenes.

public class Sieve {

    // Procedimento para usar o algoritmo do Crivo de Eratóstenes
    // [procedimento ainda por completar]
    public static void sieve(int n, boolean prime[]) {
    }
    
    public static void main(String[] args) {
	
	int n=100000; // Limite dos números

	// Cria um array de inteiros com tamanho n+1
	// (arrays começam na posição 0)
	boolean[] prime = new boolean[n+1];

	// Chama o procedimento sieve para números até 'n' no array 'prime'
	sieve(n, prime);

	// Escreve todos os números marcados a 'true' no array 'prime'
	for (int i=2; i<=n; i++)
	    if (prime[i])
		System.out.println(i);
    }
}

  1. Testando o código base.
    Compile e execute este código. Qual o resultado?
    (ao contrário do C, o Java inicializa sempre as variáveis com o valor padrão, que no caso de um boolean é false)
  2. Crivo de Eratóstenes
    Modifique o procedimento sieve para implementar o algoritmo do Crivo de Eratóstenes para descobrir números primos.
    • A ideia é que no array prime[] fique guardada a "primalidade" do número correspondente:
      • prime[i] deve ser true se i for primo
      • prime[i] deve ser false se i não for primo
    • O algoritmo funciona do seguinte modo:
      • Inicialmente todos os números são candidatos a primos (marcar tudo como true)
      • Encontrar o primeiro número ainda marcado como primo e marcar todos os seus múltiplos como "não primos". Repetir isto até todos os números primos serem marcados, ou seja:
        • 2 é número primo. Marcar 4, 6, 8, 10, 12, ... como sendo não primo (marcar essas posições a false)
        • Próximo número ainda true é o 3. Marcar 6, 9, 12, 15, 16, ... como sendo não primo
        • Próximo número ainda true é o 5. Marcar 10, 15, 20, 25, 36, ... como sendo não primo
        • ...
        • Continuar até ter processado todos os números. Os que ficam marcados a true são os números primos.
      Se desejar pode comparar o tempo com o programa do exercício anterior. Que vantagens e/ou desvantagens vê num processo como este e em guardar os resultados num array por comparação com uma função que verifica se o número é primo?

Exercício 5) Strings, e alguns erros de execução e compilação

// Exemplos de uso de Strings
public class Strings {

    public static void main(String[] args) {

	String a = 1007;     // A tentar atribuir um número inteiro a uma String
	String b = "1007";   // Colocar "1007" na variável b
	String c = "CC";     // Colocar "CC" na variável c
	String d = c + b;    // Concatenar "CC" com "1007" e colocar resultado na variável d
	String e = c + 1007; // Concatenar "CC" com número 1007 e colocar resultado na variável e

	// Escrever conteúdo das duas strings criadas
	System.out.println("d = " + d);
	System.out.println("e = " + e);

	// Como comparar duas strings
	System.out.println("d==e? " + (d==e));             // Não está correcto (compara referências)
	System.out.println("d.equals(e)? " + d.equals(e)); // Maneira correcta de comparar o conteúdo de duas strings

	// Como calcular o tamanho de uma string
	int size = d.length();
	System.out.println("tamanho de d = " + size);

	// Como ir buscar o caracter numa dada posição da string
	System.out.println("d.charAt(0) = " + d.charAt(0));
	System.out.println("d.charAt(2) = " + d.charAt(2));
	//System.out.println("d.charAt(10) = " + d.charAt(10));

	// Como ir buscar parte de uma string entre duas dadas posições
	String sub = d.substring(1,4);
	System.out.println("d.substring(1,4) = " + sub);

	// Procurando a primeira ocorrência de um dado caracter
	char ch  = '7';
	int pos = d.indexOf(ch);
	System.out.println("d.indexOf(" + ch +") = " + pos);	
    }
}

  1. Um erro de compilação.
    Compile o programa. Que tipo de erro dá? Consegue "ler" e interpretar o que o compilador de Java escreve?
  2. Verificando o programa.
    Comente a linha que deu erro, compile e execute, procurando perceber todas as suas linhas e o output obtido.
    • Ao contrário do C, em Java uma String é um tipo específico (uma classe) e não um mero array de caracteres.
    • Note como o operador concatenação funciona conforme os operandos: se tiver dois números, soma, se tiver pelo menos uma string, interpreta ambos como strings e concatena;
    • Uma simples comparação com == compara as referências e não o conteúdo dos objectos string e por isso devolve que são diferentes (vamos falar sobre objectos e referências noutras aulas)
    • Para podermos operar sobre objectos do tipo String, o Java disponibiliza toda uma biblioteca. Espreite a documentação oficial da classe String para ver quais os métodos existentes (as funções que operam sobre objectos do tipo String). Lá pode encontrar uma explicação detalhada do funcionamento dos vários métodos aqui usados.
  3. Erro durante a execução.
    Descomente a linha que tenta escrever d.charAt(10). Que erro é dado? O Java comunica os erros de execução através de excepções com nomes que indicam o tipo de erro.
  4. Procurando um método.
    Use a documentação para descobrir um método para converter uma String em minúsculas. Teste o método no código, compilando e executando para ver o resultado obtido.
  5. Criando uma função.
    Crie um método que recebe uma String e devolve se esta é ou não um palíndromo (ou seja, se a string é igual à sua versão invertida). Por exemplo:
    • isPalindrome("hello") deve devolver false porque "hello" não é igual a "olleh"
    • isPalindrome("bob") deve devolver true
    Qual deve ser o tipo do argumento da função? E do seu valor de retorno?

Exercícios Extra para consolidação de conhecimentos

  1. Mais ciclos e procedimentos.
    Crie um procedimento que, dado um n ímpar, escreva um losango de tamanho n no ecrã. Por exemplo, se n=5, o output deve ser: 
      #
 ###
#####
 ###
  #
  2. Mais sobre números primos.
    Crie um procedimento que, dado um inteiro n, escreva a sua decomposição em factores primos. Por exemplo, se n=20, o output deve ser: 
    20 = 2 * 2 * 5
  3. Mais sobre arrays e argumentos de funções.
    Crie uma função que, dado um array de n inteiros e um dado inteiro i, devolve o número de ocorrências de i no array. Por exemplo, o número de ocorrências de 2 no array [1,2,4,5,2,4,1,2] é de três.
  4. Mais sobre strings.
    Crie um procedimento que receba um inteiro n e escreva as primeiras n linhas do L-system original de Lindenmayer, que usa as seguintes regras:
    • A primeira linha é "A"
    • Para se obter uma nova linha pega-se na linha anterior e substitui-se todos os "A" por "AB" e todos os "B" por "A".
    Por exemplo, se o procedimento for chamado com n=7 o output deverá ser: 
    A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA

Exercício de Desafio

Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.

Para esta semana, como é apenas a primeira aula e ainda introdutória, o desafio é de organização e estruturação de código. A ideia é resolver o seguinte problema:

Se o conseguirem resolver enviem-me a solução por email () para vos dizer se vai de encontro ao pedido.

Para além da correção (escrever o que é pedido), o que queremos aqui é algo estruturado e generalizável, com o código bem compartimentado em várias funções. Por exemplo, até que ponto seria fácil mudar o tamanho ou usar um "tipo de fonte" diferente?

Ficamos à espera de ver os vossos programas :)

Pedro Ribeiro (DCC/FCUP) / Última actualização: