GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

O que está errado no meu código (desafio do trigo)

Enunciando:

Uma rainha requisitou os serviços de um monge e disse-lhe que pagaria qualquer preço. O monge, necessitando de alimentos, perguntou a rainha se o pagamento poderia ser feito em grãos de trigo dispostos em um tabuleiro de damas, de forma que o primeiro quadrado tivesse apenas um grão, e os quadrados subseqüentes, o dobro do quadrado anterior. A rainha considerou o pagamento barato e pediu que o serviço fosse executado, porém, um dos cavaleiros que estava presente e entendia um pouco de matemática alertou-a que seria impossível executar o pagamento, pois a quantidade de grão seria muito alta. Curiosa, a rainha solicitou então a este cavaleiro que era bom em cálculo, que fizesse um programa que recebesse como entrada o número de quadrados a serem usados em um tabuleiro de damas e apresentasse a quantidade de kg de trigo correspondente, sabendo que cada 12 grãos do cereal correspondem a uma grama. Finalmente, o cálculo da quantidade deverá caber em um valor inteiro de 64 bits sem sinal

Exemplo de entradas:

3
7
19
14

Exemplo de saídas:

0 kg
43 kg
1 kg

O meu código:

package principal;
import java.util.Scanner;

public class Programa {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int entrada = scan.nextInt();
		
		int[] graos = new int[entrada];
		int aux;
		
		int[] entradas = new int[entrada];
		
		for(int i = 0; i < entrada; i++) {
			entradas[i] = scan.nextInt();
			
			aux = 1;
			
			for(int j = 1; j < entradas[i]; j ++) {
				aux *= 2;
				graos[i] += aux;
			}
			
		}
		
		for(int i = 0; i < graos.length; i++) {
			graos[i] += 1;
			System.out.println(graos[i] + " kg");
		}
		
		scan.close();
	}
}

Você está calculando a quantidade de grãos. Mas o enunciado diz que “cada 12 grãos do cereal correspondem a um grama” (sim, o correto é “um grama” e não “uma grama”) e o resultado deve ser a quantidade de kg.

Ou seja, a quantidade de grãos tem que ser dividida por 12 (para ter a quantidade de gramas), e depois ainda tem que dividir por 1000 para ter a quantidade de quilos.

Só que ainda tem outro problema. Mas antes vamos ver como simplificar o cálculo, pois dá pra tirar uma fórmula que elimina a necessidade de todos esses loops.

Primeiro vamos ver quantos grãos cabem em cada casa:

Nº da casa Quantidade de grãos desta casa
1 1 = 20
2 2 = 21
3 4 = 22
4 8 = 23
n 2n - 1

Ou seja, se quisermos saber o total de grãos para N casas, basta somar as potências de 2 até N - 1. E tem uma fórmula pra isso:

20 + 21 + 22 + … + 2n - 1 = 2n - 1

Ou seja, total de grãos seria:

Nº de casas Quantidade total de grãos
1 1 = 21 - 1
2 3 = 22 - 1
3 7 = 23 - 1
4 15 = 24 - 1
n 2n - 1

Portanto, para cada entrada n, basta fazer 2n - 1 para ter o total de grãos.

Mas como eu disse antes, ainda tem outro problema. O enunciado disse que “o cálculo da quantidade deverá caber em um valor inteiro de 64 bits sem sinal”. Só que um int em Java tem apenas 32 bits. No caso, dá a entender que precisaria de um long, que tem 64 bits.

Só que na verdade está meio confuso, porque nem mesmo um long se encaixaria no caso, pois apesar de ser um tipo de 64 bits, ele tem sinal (ou seja, o maior valor possível é 263 - 1).

De qualquer forma, daria para fazer para valores de n até 64 se consideramos que o cálculo pode ser simplificado.

Como cada 12 grãos são um grama, então eu posso dividir por 12. Ou seja, para n grãos, a quantidade de gramas é (2n - 1) / 12.

Só que 12 é o mesmo que 3 x 22, e portanto a expressão pode ser simplificada para (2n - 2 / 3) - 1/12 - essa é a quantidade de gramas, ou seja, eu ainda tenho que dividir por 1000 para ter o total de quilos.

E como o valor será arredondado, eu posso até desprezar o 1/12, pois dividido por 1000 dará 0,00008333… - e arredondado dará zero, então essa parte não faz diferença e posso desprezar no cálculo.

Ou seja, no fundo tudo se resume a fazer 2n - 2 / 3000, que é a quantidade de quilos equivalente a n casas. Algo assim:

Scanner scan = new Scanner(System.in);
int quantidadeEntradas = scan.nextInt();

int[] entradas = new int[quantidadeEntradas];
long[] graos = new long[quantidadeEntradas];
for (int i = 0; i < quantidadeEntradas; i++) {
    entradas[i] = scan.nextInt();
    graos[i] = ((long) Math.pow(2, entradas[i] - 2)) / 3000;
}

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

Outro ponto é que não precisaria de um array para guardar os dados (o exercício só diz para imprimir a quantidade de quilos, e se não for usá-los para mais nada, daria para só imprimir depois de ler a entrada):

Scanner scan = new Scanner(System.in);
int quantidadeEntradas = scan.nextInt();
for (int i = 0; i < quantidadeEntradas; i++) {
    int n = scan.nextInt();
    System.out.println(((long) Math.pow(2, n - 2)) / 3000 + " kg");
}

Mais ainda, se eu tiver menos que 14 casas, então 2n - 2 será menor que 3000, então eu já sei que não dá 1 quilo. Ou seja, poderia retorna zero direto nesses casos:

for (int i = 0; i < quantidadeEntradas; i++) {
    int n = scan.nextInt();
    long kg;
    if (n < 14) {
        kg = 0;
    } else {
        kg = ((long) Math.pow(2, n - 2)) / 3000;
    }
    System.out.println(kg + " kg");
}

Isso funciona para valores de n até 65. Acima disso você pode mudar para BigInteger, que suporta valores maiores porém é um pouco mais chato de se trabalhar:

BigInteger dois = new BigInteger("2");
BigInteger conversaoKg = new BigInteger("3000");
for (int i = 0; i < quantidadeEntradas; i++) {
    int n = scan.nextInt();
    BigInteger kg;
    if (n < 14) {
        kg = BigInteger.ZERO;
    } else {
        kg = dois.pow(n - 2).divide(conversaoKg);
    }
    System.out.println(kg + " kg");
}
1 curtida

VLWWWWWWWW mano! Muito obrigado

//