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

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

新規登録して質問してみよう
ただいま回答率
85.50%
基本情報技術者

基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

Q&A

解決済

3回答

2533閲覧

2個の文字AとBを使って、長さ1以上7以下の文字列は何通りできるか。

teityura

総合スコア84

基本情報技術者

基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

0グッド

0クリップ

投稿2018/10/19 15:14

2個の文字AとBを使って、長さ1以上7以下の文字列は何通りできるか。
平成20年度 春 FE 問7らしいです。

解説では、

2進数ではn桁では2^n通りの表現できるため、
2^1+2^2+2^3*2^4+2^5+2^6+2^7で254通りになる。

とのことです。

2進数で8ビットだと、
10進数で0~255の256通りの数値が表せますよね。

256-254=2
の2個分はどこへ消えてしまったのでしょうか。
計算では
2^1+2^2+2^3*2^4+2^5+2^6+2^7=254は納得できますが、
いまいち腑に落ちないようで、気持ちが悪いです。

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

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

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

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

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

guest

回答3

0

2進数で8ビットに相当するのは「文字2つでちょうど8文字の文字列は何種類あるか?」です。「7文字以下の文字列」とは別の話。

等比級数の公式から
1+2+4+・・・128=2^8-1=255になります。長さゼロの文字列(1種類)を除外しているのでさらに1つ引いて254

投稿2018/10/19 15:36

a_saitoh

総合スコア702

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

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

swordone

2018/10/19 15:44 編集

すみません、私が間違えていたようです。
teityura

2018/10/19 15:59

私が勘違いしてたのは、 8文字丁度の文字列の個数を考えていたからなんですね。 1-7文字の文字列の個数が 2^1~2^7になるのはそういうことだったのですね。 ありがとうございました。
guest

0

解説に

.. 2進数ではn桁では2^n通りの表現できるため ..

とあります。
つまり
長さの1の文字列なら 2通り (A, B)
長さの2の文字列なら 4通り (AA, AB, BA, BB)
...
です。そして解説にある 次の式が出てきます。

2^1+2^2+2^3*2^4+2^5+2^6+2^7

これを律儀に計算すれば 254 に あります。

解説とはすこし違う考え方をしてみます。
この問題は
A, B (2通り -> 2進数だと 10 通り)
AA, AB, BA, BB (4通リ -> 2進数だと 100通り)
AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB (8通り -> 2 進数だと 1000通り)
...
の合計を数えることです。
つまり、2進数で考えれば、 1111110 (1が6個, 最後が0) が答えです。
これに +1 すれば、 1111111 (1が7個), さらに +1 すれば 1000000 (1の後に 0 が7つ)になります。
10000000 (2^8 = 256) なので 1111110 は 256 - 2 = 254 です。

投稿2018/10/19 22:13

katoy

総合スコア22324

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

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

0

ベストアンサー

根本的な勘違いとして、問題は最大で7文字なので、7ビットで考える必要があります。
つまり7ビットと考えたとき、2^7=128なので、254は多いのです。

なぜか?

7ビット整数を単純にAを0,Bを1と対応付けて考えようとすると、7文字しか表せないのです。
6文字、5文字…の分を別途考えなければならないのです。

投稿2018/10/19 15:39

swordone

総合スコア20649

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

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

teityura

2018/10/19 15:57

なるほど、大前提として、 問題は1以上7以下の文字列であり、 私の勘違いしていた、8ビットはいわば、 8(1-7を含まない)の文字列であったわけですね。 8ビットだと、00000000~11111111の範囲以内で、 2^8個であるわけですが、 1-7ビットだと、0~1111111の範囲以内である訳で、 2^7個だけでなく、2^6~2^1までも対象になるので、 全部足して、254個なんですね。 納得、スッキリできました。ありがとうございました!
swordone

2018/10/19 16:02

「0000000」と「0」を区別しないと題意は得られませんからね。 8ビットでうまく説明できるかと考えた(8ビット目が0の時は先頭0を無視した文字列、8ビット目が1の時は先頭0を文字に置き換えた文字列…)けど、先頭0を無視した文字列がB始まりの文字列しか作れないので無理だった
teityura

2018/10/19 16:12

確かに、 2進数7ビットの0000000 と 2進数1ビットの0 は 10進数では同じ0 ですが、 文字列のA と 文字列のAAAAAAA は 別のものとして扱う必要があるのがポイントですね。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問