質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

1631閲覧

yukicoder.No47 : ビスケットが2の指数で増える問題

退会済みユーザー

退会済みユーザー

総合スコア0

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2015/07/13 05:16

[質問文]
こんにちは,今回はyukicoderというサイトの問題で質問させていただきに来ました.
こちらにNo.47の問題,
http://yukicoder.me/problems/89
があります.前提として,自分はこの問題を人づてに聞いておりまして,
最初2進数であらわす問題だと思って以下に示すコードを作りました.
ですが,実際に問題サイトへいってみると,ビスケット1000枚 --> 10回 が答えになっており
,疑問に思い,他の方のコードを拝見させていただくと,どうも 2^k ≧ Nとなるkを求めているようでした.

そこで質問なのですが,

  1. この問題は,「N = ビスケット数,となるように2の指数で増えるポケットをだけをつかってビスケットを増やす.そのためにポケットにいれるビスケットの数を調整する」という問題なのでしょうか?

つまり,2^k ≧ Nとなるkをもとめる問題では無いという解釈でいいのでしょうか?
2. 自分の問題解釈があっているなら,1000 --> 10にできるような組み合わせが存在するということでしょうか?
3. 解釈が間違っているのなら,いかに示すコードは,自分の解釈通りなら正解のコードといえるでしょうか?

[ソースコード]

#include <iostream>
#include <string>

int sumTataku( int n )
{
int ans = 0;

int on_bit_num = 0, dist = 0; int temp = n, dist_calc = 0; do{ if( temp % 2 ){ ++on_bit_num; dist += dist_calc; } ++dist_calc; } while( ( temp = temp >> 1 ) > 0 ); std::cout << "on_bit_num = " << on_bit_num << "\n"; std::cout << "dist = " << dist << "\n"; ans += dist; temp = on_bit_num; if( temp % 2 && temp > 1){ ++ans; } on_bit_num = 0; dist = 0; dist_calc = 0; do{ if( temp % 2 ){ ++on_bit_num; dist += dist_calc; } ++dist_calc; } while( ( temp = temp >> 1 ) > 0 ); std::cout << "on_bit_num2 = " << on_bit_num << "\n"; std::cout << "dist2 = " << dist << "\n"; ans += dist; return ans;

}

void mysource()
{
while( true ){
try{
std::cout << "number : ";
std::string strn;
std::cin >> strn;
int n = std::stoi( strn );
std::cout << " ans = " << sumTataku( n ) << "\n\n";
}
catch( ... ){
break;
}
}
}

int main()
{

mysource(); return 0;

}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

問題のサンプルにあるとおりに1000枚のビスケットを目指すとすると、

1回目 1枚をポケットに入れ 叩く → 2枚
2回目 2枚をポケットに入れ 叩く → 4枚
3回目 4枚をポケットに入れ 叩く → 8枚
4回目 8枚をポケットに入れ 叩く → 16枚
5回目 16枚をポケットに入れ 叩く → 32枚
6回目 32枚をポケットに入れ 叩く → 64枚
7回目 64枚をポケットに入れ 叩く → 128枚
8回目 128枚をポケットに入れ 叩く → 256枚
9回目 256枚をポケットに入れ 叩く → 512枚
10回目 488枚をポケットに入れ 叩く → 1000枚

もし目指す枚数が500枚だとしたら、
1回目 1枚をポケットに入れ 叩く → 2枚
2回目 2枚をポケットに入れ 叩く → 4枚
3回目 4枚をポケットに入れ 叩く → 8枚
4回目 8枚をポケットに入れ 叩く → 16枚
5回目 16枚をポケットに入れ 叩く → 32枚
6回目 32枚をポケットに入れ 叩く → 64枚
7回目 64枚をポケットに入れ 叩く → 128枚
8回目 128枚をポケットに入れ 叩く → 256枚
9回目 244枚をポケットに入れ 叩く → 500枚

途中までは持っているビスケットの全てをポケットに入れて増やす、
最後の1回だけ、ポケットに入れるビスケットの枚数を減らして、
数値の調整をすればいいのです。

つまり、
2枚 1回
34枚 2回
5
8枚 3回
916枚 4回
17
32枚 5回
3364枚 6回
65
128枚 7回
129256枚 8回
257
512枚 9回
513~1024枚 10回

よって、2^k ≧ Nとなるkを求めれば良いということになります。

投稿2015/07/13 05:45

編集2015/07/13 05:47
moriyama

総合スコア259

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2015/07/13 05:55

なるほど,任意にポケットから取り出せるということを失念していました. つまり,この問題のキモは,2^k ≧ N となるkをもとめればよい,というのを, 証明することだったわけですね(コード上には載りませんが).
guest

0

2倍になるて書いてあるので、
N = 2 * x ですね。
最初にポケットに入る数は1固定ぽいので、
1回目のタッチで2枚
2回目のタッチで4枚
3回目のタッチで8枚と増えるようですね。
でN枚得るには何回タッチするかて問題ですね。

投稿2015/07/13 05:25

MasaakiIrie

総合スコア1021

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2015/07/13 05:38

キモは,Nちょうどなのか,N≧なのかということです. Nちょうどならこれは2進数への変換問題と考えられる,と考えた次第です.
退会済みユーザー

退会済みユーザー

2015/07/13 05:40

あ,Nちょうどっておっしゃられてますね.失礼しました. であれば,1000 --> 10となるようなタッチが存在するということでしょうか?
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問