7

Estou resolvendo uma solução baseado na história envolvendo o tabuleiro de xadrez. Veja um pedaço da história:

"Então Sessa pediu seu pagamento em grão de trigo da seguinte maneira: Um grão de trigo pela primeira casa do tabuleiro, dois pela segunda, quatro pela terceira, e assim dobrando até a sexagésima quarta e última casa do tabuleiro.

Qual o total de grãos?"

Comecei o código assim:

import java.math.BigInteger;

public class Graos {

    // Só consegui até este método 
    public static BigInteger numeroGraos(BigInteger totalGraos) {

        //nao sei o que por aqui e retornar.

    }

     public static void main(String[] args) {

       int i=1;
       int grao=1;

       for (i=1; i<=64; i++) {

           totalGraos+=grao;

           grao=(grao*2); //o quadro seguinte é duas vezes o anterior (PG).
       }

       System.out.println ("O total de grãos é " + totalGraos);
    }
 }

Se usar inteiro para o total de grãos, ultrapassará o tamanho do tipo int.

Já testei i com limite menor e funcionou. O detalhe é só no BigInt.

Como procedo daqui em diante?

0

3 Respostas 3

10

Aquele método não é 100% necessário, você pode usar o tipo BigInteger no lugar do int, a diferença é que o BigInteger é uma classe e seus objetos são imutáveis, e os seus métodos retornam um valor, sem alterar o objeto que chamou o método, isso torna um pouco chatinho de trabalhar com ele, mas resolve o seu problema.

import java.math.BigInteger;

public class Graos {
    public static void main(String[] args) {
        BigInteger grao = BigInteger.valueOf(1);
        BigInteger totalGraos = BigInteger.valueOf(0);

        for (int i=1; i<=64; i++) { 
            totalGraos = totalGraos.add(grao);
            grao = grao.multiply(BigInteger.valueOf(2));
        }   
        System.out.println ("O total de grãos é " + totalGraos);    
    }
}

Resultado:

O total de grãos é 18446744073709551615

5

Não sei se entendi corretamente a sua dúvida,

Segue o que entendi o que você quer fazer:

import java.math.BigInteger;

public class Graos {
    
     public static BigInteger numeroGraos(int casasDoTabuleiro) {    
         // Inciamos com zero 
         BigInteger numerosDeGrao = BigInteger.valueOf(0L);
         // Inciamos com 1 grão ...
         BigInteger quantidadeDeGrao = BigInteger.valueOf(1L);
         
         int ponteiro = 0;
         
         for (ponteiro=1; ponteiro<=casasDoTabuleiro; ponteiro++) {
             
             // somamos o numeroDeGrao com a quantidadeDeGrao, passando a soma para a variável!
             numerosDeGrao =  numerosDeGrao.add( quantidadeDeGrao  );
             // Multiplicamos a quantidadeDeGrao por 2!
             quantidadeDeGrao =  quantidadeDeGrao.multiply(BigInteger.valueOf(2L) )  ;
             
         }
            
         return numerosDeGrao;

    }

    public static void main(String[] args) {

        
        BigInteger total = numeroGraos(64);
        System.out.println("Total: "+total);
        
        
    }

}
1
  • OK, as duas respostas parecidas, mas que ajudaram bastante. Commented 18/09/2015 às 14:24
2

Não precisa fazer um loop

Dá para resolver com um cálculo simples, sem precisar de loop.

No fundo estamos trabalhando com potências de 2, o que facilita bastante o cálculo.

Primeiro vamos ver quantos grãos estão em cada casa do tabuleiro:

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

Então para saber o total de grãos para N casas, basta somar as potências de 2, com o expoente indo de zero até N - 1. E já tem uma fórmula que faz isso:

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

Ou seja, para as 64 casas do tabuleiro, temos que N=64, e portanto o total de grãos é 264 - 1. Usando BigInteger ficaria assim:

// para 64 casas, total de grãos é 2⁶⁴ - 1
BigInteger totalGraos = BigInteger.valueOf(2).pow(64).subtract(BigInteger.ONE);
System.out.println("O total de grãos é " + totalGraos);
1
  • 1
    Essa reposta deveria ser marcada como a correta,pois é a mais eficiente.
    – Jony Lima
    Commented 1/10/2022 às 22:24

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .