Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor

Recentemente colocámos neste blog um post com um dos problemas que usamos em muitas das entrevistas de 2009 no SAPO. O problema consistia em desenhar (escrever) um algoritmo para resolver o seguinte problema, em pseudo-código:     "Vais receber uma lista de números. Encontra a maior diferença entre quaisquer dois números nessa lista." Hoje vamos analisar algumas das soluções com que nos deparámos nas entrevistas.

Estranhamente, uma solução que é apresentada com frequência é a seguinte:

maior_diferenca = 0; for ( i = 1 ; i < length lista ; i++ ) { if ( lista[i] - lista[i-1] > maior_diferenca ) { maior_diferenca = lista[i] - lista[i-1]; } } return maior_diferenca;

Esta é uma solução que não apresenta o resultado correcto e que demonstra uma série de problemas no raciocínio do candidato (problemas esses que não iremos abordar aqui, mas é de facto uma situação comum).

Eis a solução mais básica que poderia ser apresentada (seguindo-se a lista de problemas que a mesma apresenta):

maior_diferenca = 0; for ( i = 0 ; i < length lista ; i++ ) { for ( j = 0 ; j < length lista ; j++ ) { if ( abs( lista[i] - lista[j] > maior_diferenca ) ) { maior_diferenca = abs( lista[i] - lista[j] ); } } } return maior_diferenca;

Problemas de eficiência:

  • Para cada dois números na lista, a diferença é calculada duas vezes
  • Em cada um dos ciclos, o resultado de "length lista" é calculado n vezes


Erros e corner-cases:

  • O valor 0 é retornado caso a lista seja vazia ou tenha apenas um elemento.


Vejamos agora a mesma solução já com alguns destes problemas resolvidos:

maior_diferenca = 0; tamanho = length lista; for ( i = 0 ; i < tamanho ; i++ ) { for ( j = i+1 ; j < tamanho ; j++ ) { diferenca = abs( lista[i] - lista[j] ); if ( diferenca_actual > maior_diferenca ) ) { maior_diferenca = diferenca_actual; } } } return maior_diferenca;

Apesar de esta solução ainda não estar a prever os casos da lista vazia ou da lista com um único elemento, esta já é uma solução mais eficiente que a anterior. Ainda assim, um bom candidato consegue, desde o início, compreender que não necessita realizar tantas operações, já que lhe basta encontrar o maior e o menor elemento da lista e calcular a diferença entre dois.

Infelizmente, isto faz com que alguns candidatos apresentem uma solução semelhante à seguinte:

lista = sort lista; max = last lista; min = first lista; return max - min;

Apesar da solução estar correcta, não é de todo eficaz, dada a complexidade de um sort numa lista com, por exemplo, 20,000 valores.

Eis uma outra solução seguindo esta ideia, ainda com alguns problemas:

min = 0; max = 0; for ( i = 0; i < tamanho; i++ ) { if ( lista[i] < min ) { min = lista[i]; } if ( lista[i] > max ) { max = lista[i]; } } return max - min;

Esta é uma solução que não funciona, uma vez que basta que todos os números sejam positivos ou negativos para retornar o valor errado.

Uma melhor solução seria algo no seguinte sentido:

min = null; max = null; for ( i = 0; i < tamanho; i++ ) { if ( min == null or lista[i] < min ) { min = lista[i]; } if ( max == null or lista[i] > max ) { max = lista[i]; } } if ( min != null and max != null ) { return max - min; } else { # ... }

Entre todas estas versões, há ainda mais uma série de variantes que outros candidatos apresentam. Há também questões específicas de cada linguagem que podem fazer com que pequenas partes devam ser alteradas por uma questão de eficiência.

Ao ser confrontado com este problema, o candidato ideal:

  • sabe que a lista pode ser vazia ou ter apenas um elemento
  • sabe que a lista pode ser enorme (e não tenta fazer um sort)
  • sabe que a lista recebida pode ter elementos que não sejam números
  • percebe quase imediatamente que basta encontrar o máximo e o mínimo da lista
  • consegue sugerir uma ou mais soluções para quando não é possível encontrar uma diferença
  • resolve o problema rápida e eficazmente, e sabe explicar porque fez o que fez

Convém ainda deixar claro que este é apenas um problema que fez parte de um grande conjunto de desafios colocados aos candidatos e que não é apenas a resolução de um simples problema que dita o recrutamento ou não da pessoa.

Programação Java

Escreva um programa em Java que leia uma sequência N de números inteiros (negativos, positivos e o zero) para um vetor. No início do programa é solicitado ao usuário (pelo teclado) qual é a quantidade de elementos que serão lidos para o vetor e depois disso os números são lidos para o vetor. Em seguida você deve implementar para cada um dos itens abaixo uma função: a) Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor. b) Verifica se o vetor está em ordem crescente, e retorna true caso esteja e false

caso contrário.

Isso é fácil de fazer.

Mas me diz aí… como você nunca usou Java e agora precisa resolver esse problema?

faculdade ue, primeiro semestre foi inteiro em python… agora segundo semestre querem em java

Ai eh brabo, pq são linguagens bem diferentes.

Com java, vc pode fazer a leitura da entrada de dados pelo teclado usando a classe Scanner:

try (Scanner teclado = new Scanner(System.in)) { String valor = teclado.nextLine(); }

Para declarar um vetor, vc faz assim:

int[] numeros = new int[10]; // vetor com 10 posições

Vc vai precisar percorrer o vetor, com isso, vc pode usar um FOR:

for (int i = 0; i < numeros.length; i++) { System.out.println(numeros[i]); }

Boa sorte.

1 curtida

import java.util.Scanner;

public class MeuPrograma {

private static Scanner scanner;

public static void main(String[] args) {

scanner = new Scanner(System.in); int N = scanner.nextInt(); if (N > 0) { int[] vetor = new int[N]; for (int i = 0; i < N; i++) { vetor[i] = scanner.nextInt(); } System.out.println(); System.out.println(maiorDiferenca(vetor)); System.out.println(ordemCrescente(vetor)); }

}

public static int maiorDiferenca(int vetor[]) {

int maior, segundoMaior; maior = vetor[0]; segundoMaior = maior; for (int i = 1; i < vetor.length; i++) { if (vetor[i] > maior) { segundoMaior = maior; maior = vetor[i]; } else if (vetor[i] > segundoMaior && vetor[i] != maior) { segundoMaior = vetor[i]; } } if (maior == segundoMaior) { return 0; } return maior - segundoMaior;

}

public static boolean ordemCrescente(int vetor[]) {

for (int i = 1; i < vetor.length; i++) { if (vetor[i] < vetor[i - 1]) { return false; } } return true;

}

}

assim?

Alguém pode me ajudar a fazer esse exercicio? Não sou bom em Java.

Segue:

Escreva um programa em Java que leia uma sequência N de números inteiros

(negativos, positivos e o zero) para um vetor. No início do programa é solicitado ao

usuário (pelo teclado) qual é a quantidade de elementos que serão lidos para o vetor

e depois disso os números são lidos para o vetor.

a) Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor.

b) Verifica se o vetor está em ordem crescente, e retorna true caso esteja e false caso contrário.

Isso foi o que consegui fazer até agora, o que seria a “primeira parte”:

public class Main {

public class static void main(String[] args) {

Scanner s = new Scanner( System.in);

int tamanho = Integer.parseInt( s.nextLine() );

int[] array = new int[tamanho];

}

}

Agora você faz um for de 0 até o tamanho do array.
Dentro dele vc vai pedindo que o usuário digite os números e vá guardando no array.

Fiz dessa forma, será que está correto?

private static Boolean verificaOrdenacao(int[] tamanho) { int i = 0; if (tamanho[i] <= tamanho[i + 1]) { i++; return true; } return false;

Mas não tem nenhum FOR nesse método verificaOrdenacao. Tenta seguir a sugestao do @RoinujNosde.

1 curtida

Fala galera! fiz um for como vocês falaram, alguém pode me dar um help e dizer onde estou errando? segue:

public class Main { public class static void main(String[] args) { Scanner s = new Scanner( System.in); int tamanho = Integer.parseInt(s.nextLine()); int[] array = new int[tamanho]; } Public class static void main(String[] args) { int verifica (int array[], int tamanho) { if (tamanho > 1) for (i = 1; i < tamanho; i++) { if (array[i - 1] > array[i]) return 0; return 1; } } }

Bom dia pessoal sou novato em Java tou a fazer um tarefa e preciso de ajuda! o professor me passou isso.

Construa um programa que calcule a multiplicação de dois números apenas utilizando a operação soma

import java.util.Scanner;

public class Exercicio2 {

public static void main(String[] args) { Scanner entrada = new Scanner(System.in); int num1; int num2; System.out.print("Digite o primeiro número: "); num1 = entrada.nextInt(); System.out.print("Digite o segundo número: "); num2 = entrada.nextInt(); System.out.println(num1 + " * " + num2 + " = " + (num1 * num2) ); }

}

@Joao_Filipe1 não está correto, vc deve utilizar apenas soma (+), não multiplicação (*).
E crie outro tópico, o seu problema não tem relação com este.

2 curtidas

No meu caso acredito que precisaria colocar como Boolean na parte do for?
help…

@JacksonT você tá colocando o carro na frente dos bois. Já fez a parte de pedir os números ao usuário e guardar num array?

Depois vc faz a verificação da ordem.

2 curtidas

Fala mano, decidi refazer do 0, utilizei o for e o while, coloquei a parte de pedir numeros ao usuario e guardar num array.
Não tenho certeza se está correto ainda pois acredito que fiz de uma maneira bem “bagunçada”.

Segue:

Class Main { public static void main(String[] args) { Scanner leitor = new Scanner(System.in); System.out.println("Digite a quantidade de elementos que serão lidos:"); int tp = leitor.nextInt(); int vet[] = new int[tp]; criaVet(tp, vet); diferença = valorMaior(vet); System.out.println("A diferença é " + diferença); } public static void criaVet(int tamanho,int [] vet) { for(int i = 0; i < tamanho; i++) { Scanner leia = new Scanner(System.in); System.out.println("Digite um valor: "); vet[i] = leia.nextInt(); } } public static void main(String[] args) { while(i < tp) { if(vet.get(i) == vet.get(tp - 1)) { return true; } else { if (vet.get(i) > vet.get(i + 1)) { return false; } } i++; } return true; }

Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor
JacksonT:

public static void criaVet(int tamanho,int [] vet) {

Essa variável tamanho não é necessária. A partir do vetor vc pode pegar o tamanho dele: vet.length

Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor
JacksonT:

public static void main(String[] args) { while(i < tp) { if(vet.get(i) == vet.get(tp - 1)) { return true; } else { if (vet.get(i) > vet.get(i + 1)) { return false; } } i++; } return true; }

Já esse método não faz sentido.

Declara um método public static int diferenca(int[] vetor) {} para fazer o cálculo da diferença.

Já consegui fazer quase todo exercício, falta apenas a parte B, que estou com dificuldade ainda.

O que eu teria que fazer para ver se o vetor está em ordem crescente e retornar true se sim e false se não? um for?

Segue as partes que já fiz e testei:

import java.util.Scanner;

public class Main { public static void main(String[] args) { Scanner leitor = new Scanner(System.in); System.out.println("Digite a quantidade de elementos que serão lidos:"); int num = leitor.nextInt(); int v[] = new int[num]; diferenca = vmaior(v); for(int i=0; i < v.length; i++){ System.out.print("v["+i+"] "); v[i] = leitor.nextInt(); } for (int i = 0; i < v.length; i++) { System.out.print(v[i]+ " "); } System.out.println(); int vmaior = v[0]; int vmenor = v[0]; for(int i = 0; i < v.length; i++) { if(v[i] > vmaior) { vmaior= v[i]; } if(v[i] < vmenor){ vmenor=v[i]; } } System.out.println("O maior valor do vetor é: " +vmaior); {

Calcule e retorna o valor da maior diferença entre dois elementos distintos no vetor
JacksonT:

O que eu teria que fazer para ver se o vetor está em ordem crescente e retornar true se sim e false se não? um for?

Utilize um for, percorra todo o vetor e cada vez que percorrer você deve salvar uma variável (fora do laço de repetição) com o nome de ultimoValor. Dentro do for() você irá por um if que irá verificar se valorAtual > UltimoValor, caso passe pelo IF é porque está crescente, caso durante as repetições não passe pelo if já pode retornar false.

Boa tarde galera to precisando de ajuda em uma questão de java sou novo em programação

Criar um algoritmo que solicite ao usuário algumas opções e efetue as operações conforme detalhado abaixo:

"Favor informar uma operação que deseja executar: "

i - Preencher o vetor p - Pesquisar um valor no vetor

a - Alterar um determinado valor no vetor

OBS1.: Caso seja escolhida a opção “p” , solicitar o valor que deseja procurar. Informar ao usuário se localizou ou não;
OBS2.: Caso seja escolhida a opção “a” , solicitar a posição a ser alterada;

OBS3: A opção “i”, é para caso se deseje alterar todo o vetor, porém ele já deve ser criado com valores.
OBS4: O vetor precisa ser de duas dimensões.

@WolfWhiter

No seu caso, é melhor cirar um tópico a parte para tirar sua dúvida. Não esqueça de dizer qual é a dúvida. Vc colocou apenas o que precisa ser feito.