Você está aqui: Java ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Como encontrar a soma máxima em uma subsequência de tamanho k em Java - Programação Dinâmica em Java - Lista de Exercícios Resolvidos de Java

Quantidade de visualizações: 424 vezes
Pergunta/Tarefa:

Este desafio, presente em quase todos os livros de programação dinâmica em Java, envolve encontrar a soma máxima em um subarray contíguo, ou seja, de elementos consecutivos, obedecendo a um tamanho k.

O tamanho k determina a quantidade de elementos que a subsequencia pode ter. É possível ter mais de um subarray de tamanho k que contenha a soma máxima, mas o exercício pede para retornar apenas a soma máxima. Em outras abordagens do site eu mostro como retornar a quantidade de subarrays e até mesmo os índices de início e término de cada uma dessas subsequencias.

Assim, dado o vetor v[] de números inteiros [-7, 1, 3, 11, 5, -4, 9, 2], encontre a maior soma que pode ser obtida por uma sequencia contígua de 3 elementos.

Sua saída deverá ser parecida com:

O conteúdo do array é: [-7, 1, 3, 11, 5, -4, 9, 2]
A soma máxima é: 19
Embora o exercício não peça para mostrar a sub-sequência com a maior soma, você pode fazer o teste de mesa no algorítmo e verificar que o sub-array de 3 elementos que contém a soma máxima é [3, 11, 5]

Resposta/Solução:

Veja a resolução comentada deste exercício usando Java:

Atenção: Existem muitos algorítmos refinados para uma solução mais eficiente deste problema. Aqui eu apresento a solução usando força-bruta. Essa é a forma mais ineficiente e que consome mais tempo e recursos da máquina. No entanto, esta é também a forma mais fácil de entender o algorítmo aplicado.

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;

import java.util.Arrays;

public class Estudos{
  public static void main(String args[]){
    // vamos criar um vetor com 8 elementos
    int valores[] = {-7, 1, 3, 11, 5, -4, 9, 2};
    // vamos mostrar os valores do array
    System.out.println("O conteúdo do array é: " +
      Arrays.toString(valores));
    
    // definimos o tamanho da subsequencia
    int k = 3;
    // e o tamanho do vetor
    int n = valores.length;
 
    // e chamamos a função que retorna a soma máxima
    int soma_maxima = soma_maxima_subarray_k(valores, n, k);
    // finalmente mostramos o resultado
    System.out.println("A soma máxima é: " + soma_maxima);
  }
  
  // método que recebe um vetor v e um número inteiro
  // k e retorna a maior soma que pode ser obtida por
  // uma subsequencia contígua de tamanho k
  static int soma_maxima_subarray_k(int arr[], int n, int k){
    // o primeiro passo é declarar a soma
    // máxima como 0
    int soma_maxima = 0;
    
    // agora percorremos os elementos do vetor, começando
    // no primeiro e indo até o elemento indicado pelo
    // tamanho do array menos o k
    for (int i = 0; i <= n - k; i++) {
      // criamos uma variável temporário com valor 0
      int soma_temp = 0;
      
      // fazemos a soma dos elementos começando no
      // índice i atual e percorrendo
      // a quantidade de elementos k
      for (int j = i; j < i + k; j++) {
        // adicionamos o valor do elemento no índice j
        // à soma temporária
        soma_temp += arr[j];
      }
      
      // a soma temporária é maior que a soma
      // que já temos?
      if (soma_temp > soma_maxima) {
        // a nova soma é a soma temporária
        soma_maxima = soma_temp;
      }
    }
 
    // retorna a soma máxima
    return soma_maxima;
  }
}


Link para compartilhar na Internet ou com seus amigos:

Java ::: Dicas & Truques ::: Geometria, Trigonometria e Figuras Geométricas

Como calcular o ponto de interseção de duas retas em Java - Java para Geometria Analítica e Álgebra Linear

Quantidade de visualizações: 998 vezes
Duas retas podem encontrar-se em 0, 1 ou 2 pontos. No primeiro caso, elas são chamadas paralelas; no segundo, elas são chamadas concorrentes e o ponto de encontro entre elas é chamado ponto de interseção; no terceiro caso, se duas retas possuem dois pontos em comum, então elas obrigatoriamente apresentam todos os pontos em comum e são chamadas coincidentes.

Nesta dica mostrarei como podemos encontrar o ponto de interseção (ou intersecção) de duas retas usando Java. Mas, antes de vermos o código, dê uma olhada na seguinte imagem:



Note que temos os pontos A e B correspondentes ao segmento de reta AB e os pontos C e D correspondentes ao segmento de reta CD. Nossa tarefa é encontrar o ponto exato de intersecção entre esses dois segmentos de reta.

Veja o código Java completo que nos auxilia na resolução deste problema:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;

// Classe usada para representar um ponto no
// plano 2d (Plano Cartesiano)
class Ponto{
  double x, y;
  
  // construtor da classe
  public Ponto(double x, double y){
    this.x = x;
    this.y = y;
  }
}

public class Estudos {
  public static void main(String[] args) {
    // vamos construir os quatro pontos
    Ponto A = new Ponto(5, 7);
    Ponto B = new Ponto(9, -4);
    Ponto C = new Ponto(-8, 2);
    Ponto D = new Ponto(11, 6);
    
    // vamos obter a representação do segmento AB    
    double a1 = B.y - A.y;
    double b1 = A.x - B.x;
    double c1 = (a1 * A.x) + (b1 * A.y);
       
    // vamos obter a representação do segmento CD
    double a2 = D.y - C.y;
    double b2 = C.x - D.x;
    double c2 = (a2 * C.x) + (b2 * C.y);
    
    // obtém o determinante
    double determinante = (a1 * b2) - (a2 * b1);
    
    // as duas retas são paralelas?
    if(determinante == 0){
      System.out.println("\nAs duas retas são paralelas.\n");
    }
    else{
      // e construímos o ponto de intersecção
      double x = ((b2 * c1) - (b1 * c2)) / determinante;
      double y = ((a1 * c2) - (a2 * c1)) / determinante;
      Ponto inters = new Ponto(x, y);
    
      System.out.printf("O ponto de interseção é: x = %.2f; y = %.2f",
        inters.x, inters.y);
    }
    
    System.out.println();
  }
} 

Ao executar este código Java nós teremos o seguinte resultado:

O ponto de interseção é: x = 5,76; y = 4,90

De fato, se você olhar a imagem novamente e desenhar este ponto, verá que ele se situa exatamente na intersecção das retas indicadas.


Java ::: Desafios e Lista de Exercícios Resolvidos ::: Programação Orientada a Objetos

Exercício Resolvido de Java - Crie uma classe Agenda que pode armazenar 10 pessoas e que seja capaz de realizar as seguintes operações

Quantidade de visualizações: 5835 vezes
Exercícios Resolvidos de Java - Crie uma classe Agenda que pode armazenar 10 pessoas e que seja capaz de realizar as seguintes operações

Pergunta/Tarefa:

Crie uma classe Agenda que pode armazenar 10 pessoas e que seja capaz de realizar as seguintes operações:

void armazenaPessoa(String nome, int idade, float altura);
void removePessoa(String nome);
int buscaPessoa(String nome); // informa em que posição da agenda está a pessoa
void imprimeAgenda(); // imprime os dados de todas as pessoas da agenda
void imprimePessoa(int index); // imprime os dados da pessoa que está na posição "i" da agenda.

O código deverá ser desenvolvido em Java console (modo texto) e usar um menu switch() para as operações.

Sua saída deverá ser parecida com:



Resposta/Solução:

Veja a resolução comentada deste exercício usando Java console:

Código para a classe Pessoa (Pessoa.java):

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package arquivodecodigos;

public class Pessoa {
  private String nome;
  private int idade;
  private double altura;

  // construtor cheio 
  public Pessoa(String nome, int idade, double altura) {
    this.nome = nome;
    this.idade = idade;
    this.altura = altura;
  }

  // construtor vazio
  public Pessoa() {
  }
  
  
  // método que imprime todos os dados da pessoa
  public void imprimirDados(){
    System.out.println("Nome: " + nome + "\nIdade: " +
      idade + "\nAltura: " + altura);
  }
  
  public String getNome() {
    return nome;
  }

  public void setNome(String nome) {
    this.nome = nome;
  }

  public int getIdade() {
    return idade;
  }

  public void setIdade(int idade) {
    this.idade = idade;
  }

  public double getAltura() {
    return altura;
  }

  public void setAltura(double altura) {
    this.altura = altura;
  }
}     

Código para a classe Agenda (Agenda.java):

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package arquivodecodigos;

public class Agenda {
  // vetor que guardará as pessoas
  private Pessoa pessoas[];

  // construtor da classe Agenda
  public Agenda(int quantidade){
    pessoas = new Pessoa[quantidade];
  }

  public void armazenaPessoa(String nome, int idade, double altura){
    // ainda temos posições disponíveis na agenda?
    boolean cadastrado = false;
    for(int i = 0; i < pessoas.length; i++){
      if(pessoas[i] == null){
        // encontramos uma posição
        Pessoa p = new Pessoa(nome, idade, altura); // criamos uma nova pessoa
        // guardamos ela no vetor
        pessoas[i] = p;
        // e avisamos que o cadastro foi efetuado com sucesso
        cadastrado = true;
        break; // sai do laço
      }
    }
    
    if(cadastrado){
      System.out.println("\nCadastro efetuado com sucesso");
    }
    else{
      System.out.println("\nNão foi possível cadastrar. Agenda cheia");
    }
  }

  // método que permite pesquisar e excluir uma pessoa
  public void removePessoa(String nome){
    // vamos verificar se a exclusão foi efetuada com sucesso
    boolean excluido = false;
    for(int i = 0; i < pessoas.length; i++){
      if(pessoas[i] != null){
        // esta é a pessoa que estamos procurando?
        if(pessoas[i].getNome().equals(nome)){
          pessoas[i] = null; // posição disponível novamente
          excluido = true;
          break; // sai do laço
        }
      }
    }
    
    if(excluido){
      System.out.println("\nPessoa removida com sucesso");
    }
    else{
      System.out.println("\nNão foi possível remover. Pessoa não encontrada.");
    }
  }

  // informa em que posição da agenda está a pessoa 
  public int buscaPessoa(String nome){
    int resultado = -1;
    
    // vamos verificar se a pessoa existe na agenda
    for(int i = 0; i < pessoas.length; i++){
      if(pessoas[i] != null){
        // esta é a pessoa que estamos procurando?
        if(pessoas[i].getNome().equals(nome)){
          resultado = i;
          break; // sai do laço
        }
      }
    }
    
    return resultado;
  }

  // imprime os dados de todas as pessoas da agenda
  public void imprimeAgenda(){
    // vamos percorrer o vetor de pessoas e imprimir cada uma
    for(int i = 0; i < pessoas.length; i++){
      if(pessoas[i] != null){
        Pessoa p = pessoas[i];
        System.out.println("\nNome: " + p.getNome());
        System.out.println("Idade: " + p.getIdade());
        System.out.println("Altura: " + p.getAltura());
      }
    }
  }

  // imprime os dados da pessoa que está na posição "i" da agenda
  public void imprimePessoa(int index){
    // este índice é válido?
    if((index < 0) || (index > (pessoas.length - 1))){
      System.out.println("\nÍndice inválido");
    }
    else{
      Pessoa p = pessoas[index];
      if(p == null){
        System.out.println("\nNão existe pessoa nesse índice ainda.");
      }
      else{
        System.out.println("\nNome: " + p.getNome());
        System.out.println("Idade: " + p.getIdade());
        System.out.println("Altura: " + p.getAltura());
      }
    }
  }  
}

Código para a classe Principal (Principal.java):

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package arquivodecodigos;

import java.util.Scanner;

public class Principal {
  // para fazer a leitura da entrada do usuário
  static Scanner entrada = new Scanner(System.in);
  
  public static void main(String[] args) {
    // cria uma nova Agenda
    Agenda agenda = new Agenda(10);
    String nome; // nome da pessoa
    int idade; // idade da pessoa
    double altura; // altura da pessoa
    
    // cria o menu de opções
    while(true){
      System.out.println("\n1. Nova Pessoa");
      System.out.println("2. Excluir Pessoa");
      System.out.println("3. Buscar Pessoa");
      System.out.println("4. Imprimir Agenda");
      System.out.println("5. Imprimir Pessoa (Índice)");
      System.out.println("6. Sair");
      System.out.print("Sua opção: ");
      int opcao = Integer.parseInt(entrada.nextLine());
      
      switch(opcao){
        case 1:
          System.out.print("\nInforme o nome: ");
          nome = entrada.nextLine();
          System.out.print("Informe a idade: ");
          idade = Integer.parseInt(entrada.nextLine());
          System.out.print("Informe a altura (use ponto em vez de vírgula): ");
          altura = Double.parseDouble(entrada.nextLine());
          agenda.armazenaPessoa(nome, idade, altura);
          break;
          
        case 2:
          System.out.print("\nInforme o nome a ser removido: ");
          nome = entrada.nextLine();
          agenda.removePessoa(nome);
          break;  
        
        case 3:
          System.out.print("\nInforme o nome a ser pesquisado: ");
          nome = entrada.nextLine();
          int indice = agenda.buscaPessoa(nome);
          if(indice < 0){
            System.out.println("\nA pessoa não foi encontrada");
          }
          else{
            System.out.println("\nA pessoa foi encontrada no índice: "
              + indice);
          }
          
          break;  
        
        case 4:
          agenda.imprimeAgenda();
          break;
        
        case 5:
          System.out.print("\nInforme o índice desejado: ");
          int index = Integer.parseInt(entrada.nextLine());
          agenda.imprimePessoa(index);
          break;  
          
        case 6:
          System.exit(0);
          
        default:
          System.out.println("\nOpção inválida\n");
          break;
      }
    }
  }
}



Java ::: Dicas & Truques ::: Trigonometria - Funções Trigonométricas

Como obter o arco-seno de um ângulo em radianos usando o método asin() da classe Math da linguagem Java

Quantidade de visualizações: 13877 vezes
Nesta dica eu mostrarei como podemos obter o arco seno (ou arco-seno) de um determinado ângulo (em radianos, não em graus). De acordo com a seguinte definição:

Se seno(x) = y, então arcoseno(y) = x

O arco-seno (geralmente abreviado como arcsen, ou arcsin) é parte das funções trigonométricas inversas, ou seja, ele é o inverso do seno. Dessa forma, se o seno é a relação entre o cateto oposto ao ângulo e a hipotenusa, o arcoseno parte dessa relação para encontrar o valor do ângulo.

A classe Math, do pacote java.lang, possui o seguinte método:

public static double asin(double a)


Este método recebe um valor double e retorna também um valor double, na faixa (-PI / 2) <= x <= (PI / 2), onde x é o valor forcecido para o método.

Veja o código para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package arquivodecodigos;

public class Estudos{
  public static void main(String[] args){
    double angulo = 0.5;
    System.out.println("O arco seno de " +
      angulo + " é " + Math.asin(angulo));
  }
}

Ao executarmos este código nós teremos o seguinte resultado:

O arco seno de 0.5 é 0.5235987755982989

Não se esqueça de que o resultado será em radianos. Assim, se efetuarmos o cálculo abaixo:

Graus = Radianos * (180 / PI)
Graus = 0.5235987755982989 * (180 / 3.14)

Teremos o valor aproximado de 30.015216435571276 para o ângulo em graus.


Desafios, Exercícios e Algoritmos Resolvidos de Java

Veja mais Dicas e truques de Java

Dicas e truques de outras linguagens

Códigos Fonte

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento
Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesControle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades
Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: Delphi
6º lugar: C
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 24 usuários muito felizes estudando em nosso site.