No.47 ポケットを叩くとビスケットが２倍 - ヤマカサのプログラミング勉強日記

ポケットを叩くと・・・？

今回もアルゴリズムの問題を解いていきたいと思います。

f:id:yamakasa3:20180327002353p:plain

問題文

Saraは、「ふしぎなポケット」を手に入れた。

「ふしぎなポケット」は、いくつかビスケットを入れて叩くと、入れたビスケットの数が２倍になる。 Saraは最初1枚のビスケットを持っていて、「ふしぎなポケット」を使ってちょうど N 枚のビスケットにして、全部食べたいと思っている。（食べきれないので枚数をオーバーしてはいけない）

この時、ちょうどN枚にするには、Saraは最低何回ポケットを叩く必要があるか求めてください。 (引用) https://yukicoder.me/problems/no/47

解説

ポケットを叩く回数をnとすると、

$2^{n-1} \lt N \leq 2^{n}$ を満たすnが求める値となります。 $N = 2^{n}$ のときは、ポケットにビスケット入れたまま叩き続ければ良いことが分かります。 $N \leq 2^{n}$ のときは、 $n-1$ 回までポケットにビスケット入れたまま叩き、 $N-2^{n-1}$ 枚のビスケットをポケット入れて1回たたくと、ビスケットの合計は $N$ 枚となります。

コード

public class Biscuit {
    public static void main(String[] args) {
        System.out.println("数字");
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();
        int n = 0;
        int y;
        boolean flag = true;
        // while文の繰り返し回数を20未満とした
        while(flag) {
            y = N - (int) Math.pow(2, n);
            if(y <= 0) {
                break;
            }
            if(n > 20) {
                flag = false;
            }
            n++;
        }
        System.out.println(n);
    }
}