Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I
1a. lista de exercícios

  1. Escreva um método que recebe como parâmetro uma matriz quadrada n x n representanda por um arranjo de arranjos de elementos do tipo double.  Este método calcula a e retorna a média aritmética dos elementos abaixo da diagonal principal. A diagonal principal não deve ser incluida.

    2. static double media(double[][] mat)
     
  2. Define-se como elemento minimax de uma matriz o menor elemento de uma linha onde se encontra o maior elemento da matriz. Escreva uma função que escreve (System.out.println) qual é o elemento minimax e a posição em que o mesmo se encontra em uma matriz n x n.

    3. static void escreve_minmax(double[][] mat)
     
  3. Complete a função abaixo que recebe dois arranjos de inteiros representando dois vetores e um inteiro como parâmetros. A função devolve um valor booleano indicando se um dos vetores corresponde à multiplicação do outro pelo parâmetro inteiro, ou seja se um dos vetores é uma combinação linear do outro.

    4. static boolean combinacaoLinear(int[] a1, int[] a2, int p){
      if(a1==null && a2== null) return true;
      if(a1==null || a2==null) return false;
      if(a1.length != a2.length) return false;
      int i=0;
      while(i<a1.length & a1[i]==p*a2[i]) i++;
      if(i==a1.length) ...
  4. O modo usual de se expressar a magnitude de um vetor ou de uma matriz é por meio de um escalar denominado norma. Uma das normas conhecidas é a Euclidiana que é definida pela raiz quadrada do somatório do quadrado dos componentes.

    5. Exemplo: Dado o vetor x = [3  -5  1], a norma do vetor x é a raiz quadrada de (9+25+1) = 5.9161
    Escreva uma função que calcula a norma euclidiana de um vetor cujos valores das dimensões encontram-se em um arranjo.
    static double norma(double[] vetor)
  5. Escreva uma função que, dados dois números inteiros, calcula os divisores de ambos e, a partir desses dados, determina o Máximo Divisor Comum (MDC) entre esses números.

    6. static int maximo_divisor_comum(int num1, int num2)
     
  6. Escreva uma função que implementa um método alternativo, diferente do apresentado anteriormente, para calcular o MDC entre dois números inteiros.

    7. static int maximo_divisor_comum_alt(int num1, int num2)
     
  7. Escreva uma função que, dado um arranjo representando uma matriz quadrada, realize as seguintes trocas (assuma que n é dado por mat.length >=10):

    8. (a) a linha 2 com a linha 8;
    static void trocaValoresLinha2Com8(int[][] mat)
    (b) a coluna 4 com a coluna 10;
    static void trocaValoresColuna4Com10(int[][] mat)
    (c) a diagonal principal com a secundária;
    static void trocaDiagonalPrincipalComSecundaria(int[][] mat)
    (d) a linha 5 com a coluna 10;
    static void trocaLinha5ComColuna10(int[][] mat)
     
  8. Escreva uma função que recebe como parâmetro uma matriz representada por um arranjo de arranjo de inteiros cujos elementos contêm apenas os valores 1 ou 0. A função deve trocar os valores da matriz de acordo com o seguinte critério:

    9. (1) Se um elemento tem um número ímpar de vizinhos 1, este elemento deve mudar seu valor se for 1 para 0;
    (2) Se um elemento tem um número par (não zero) de vizinhos 1, este elemento deve mudar seu valor se for 0 para 1;
    (3) Se todos os vizinhos de um elemento forem 0, mudar o valor desse elemento de 1 para 0, ou de 0 para 1;
    (4) Se todos os vizinhos forem 1, o elemento permanece com o mesmo valor.
    static void troca(int[][] mat)

  9. Um matemático propôs a geração de uma seqüência de números a partir de qualquer número inteiro positivo n (n > 1) da seguinte maneira:

    10. Se o valor de n é 1, pare.
    Se n é par, substitua-o por n/2.
    Se n é ímpar, substitua-o por 3*n +1.
    Continue com esse processo até que o valor 1 seja alcançado.
    Por exemplo, quando n=3, a seqüência é a seguinte: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
    Entretanto, nunca se sabe se, realmente a seqüência convergirá para o valor 1. Assim, pode haver seqüências que caiam em loop ou até cresçam indefinidamente.
    (a)Escreva uma função que dado um n inteiro positivo retorna:
    true caso a seqüência convirja para o valor 1 dentro de um número especificado de iterações e false caso contrário;
    static boolean SequenciaConverge(int n, int num_iteracoes)
    (b)Escreva uma função que retorna o k-ésimo termo dessa seqüência;
    static int sequencia(int n, int k)

  10. A seqüência de Ulam {ai} = (u,v) é definida por a1 = u, a2 = v, com o termo geral an, para n>2 dado pelo menor inteiro que pode ser expresso unicamente como a soma de dois termos distintos já determinados dessa seqüência. Os números produzidos são chamados de Números de Ulam.

    11. Ex.: Os primeiros números na seqüência de Ulam (1,2) são 1, 2, 3, 4, 6, 8, 11, 13, 16 ... Aqui, a1 e a2 já são definidos e são, respectivamente, 1 e 2. O terceiro termo dessa seqüência é, obviamente 3 (3 = 1+2). O próximo termo é 4 =1+3. (Não deve-se preocupar com a possibilidade de 4=2+2 desde que trata-se de uma soma de dois termos distintos já pertencentes à essa seqüência). 5 não é um membro dessa seqüência já que, ele pode ser representado de duas formas, 5 = 1+4 = 2+3, mas 6 = 2+4 é membro.
    Procedendo da mesma maneira, podemos gerar uma seqüência de Ulam para qualquer (u,v) dado. Exemplos são dados na tabela abaixo:
    (u,v) Sequência
    (1,2) 1, 2, 3, 4, 6, 8 ...
    (1,3) 1, 3, 4, 5, 6, 8 ...
    (2,5) 2, 5, 7, 9, 11, 12, ...
    Escreva uma função que, dados u (termo1) e v (termo2), calcula os n>=2 primeiros termos da seqüência de Ulam. A função deve devolver um arranjo com n+1 elementos e o elemento de índice 0 do arranjo deve ser iniciado com 0, o elemento de índice 1 com termo1, o elemento de índice 2 com termo2 e os n-2 elementos restantes devem ser calculados
    static int[] SequenciaUlam(int termo1, int termo2, int n)