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 JavaQuantidade 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 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 LinearQuantidade 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çõesQuantidade 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 JavaQuantidade 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 |
Software 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 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 |