ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

マイナス2進法で数を数えよ!?

マイクロソフトの入社試験の問題らしいです。
ま、マイナス2進法…。

私、中1ながら2進法は知っているのですが
(本読んで覚えたんだぜぇい、すげぇだろ~。)

nがマイナスの進法が存在するとは…

と、言うわけで、
MS電卓でやってみました!(暗算は面倒い!)



前提

・10進数の数をn進数に変換するには以下の方法を使う。

1.変換したい数をnで割る。
このとき、答えを少数にせずに余りを用いる。

2.余りは書き残しておき、商をさらにnで割る。
そのつど余りを書き残し、nで割るのを繰り返す。

3.商が0になったら計算をやめ、
書き残した余りを各1桁として結合させる。
(古い余りから順に桁を大きくしていく、また一番新しい余りがマイナス符号付きなら、全体をマイナスの数とみなす。)

完了


・n進数の数を10進数に変換するには以下の方法を使う。

1.それぞれの桁を確認し、
1桁目ならその桁のみの数×n1を、2桁目ならその桁のみの数×n2をする事にし、
全ての各桁にその計算をして、各答えを保持する。

2.全ての各答えを足したのが10進数に変換された数。

完了


と言うややっこしい前提を元にnをマイナス2にしてやってみました。

例えば「5」はマイナス2進法だと…

5 / (-2) = -2 mod 1
(-2) / (-2) = 1 mod 0
1 / (-2) = 0 mod 1

つまり、「101」となりました。
ちゃんと逆変換しても4+0+1で「5」になりますよ。

ここで面白いのが「5」をプラス2進法にしてみると

5 / 2 = 2 mod 1
2 / 2 = 1 mod 0
1 / 2 = 0 mod 1

「101」となり、マイナス2進法の際と同じなのです。
累乗はプラスとなるからかも知れません。


そこで私は考えました。
「マイナス進法があるなら、少数の進法もあるんじゃね?」

とりあえず「1.4」、1.4進数をやってみました。
変換するのは「5」です。

5 / 1.4 = 3 mod 0.8
3 / 1.4 = 2 mod 0.2
2 / 1.4 = 1 mod 0.6
1 / 1.4 = 0 mod 1

まさか余りが小数になってしまうとは…
強引に(カッコ)で囲むと1桁とみなす事にしましょう。

結果は「1(0.6)(0.2)(0.8)」でした。

ではこれを5に戻してみようと言うことで

(0.8) * 1.40 = 0.8
(0.2) * 1.41 = 0.28
(0.6) * 1.42 = 1.176
1 * 1.43 = 2.744
0.8 + 0.28 + 1.176 + 2.744 = 5

ちゃんと「5」になったじゃありませんかぁぁぁ!

つまりnが少数の進法も存在するのです。

私のまとめはこうなりました。

・マイナス、少数など何でもn進数のnに適用できる。
・何でもといったが、1以下(マイナスでは-1以上)の数はnに適用できない。(そもそも変換できなかった。)


長文になってしまいましたが、それだけ私の興奮は凄かったのです。

私、頭いい~!(笑)

tag:

コメント

とても魅力的な記事でした!!
また遊びに来ます!!
ありがとうございます。。

  • 2012/06/25(月) 17:45:20 |
  • URL |
  • あろえ #-
  • [ 編集 ]

10進数5が2進法と-2進法で同じ表記になるのは単に1桁目と3桁目で基数が同じになるから。
試しに6を-2進数に変換して見ると全く違うことが分かるでしょう。
あなたが思っているほどに単純な話ではないのです。
非常に浅はか。

  • 2014/08/28(木) 22:02:22 |
  • URL |
  • 七十 #-
  • [ 編集 ]

Re: 七十

おそらく記事内容について誤解されています。
10進数の5については、2進法表現でも-2進法表現でも同じになると言いたかったのです。

一般的な数の話では、2進法表現と-2進法表現が同じ数字になるという主張はしておらず、単に10進数とn進数の変換を行うアルゴリズムは「n = -2」においても正しく変換できるという事を主張しています。

まぁ誤解をされるのも無理がない書き方でした。
混乱させてしまい申し訳ございません。

Re: Re: 七十

って、確認してみたらどうやらこのアルゴリズムも n = -2 では正しく変換できないようでした。
このことをおっしゃっていたのなら申し訳ございません。
1より大きい有理数ならいけるんですけどね。

いえ、こちらこそ。
ちなみに、1は基数に適用でき、1進法は存在します。
少数点から数えてN桁目の重みが基数^Nになるということを考えてみるとわかりやすいかと思います。
全ての重みが1になるので、表したい数だけ文字を書くのが1進法です。
非合理的に思えるかもしれませんが基数で割る方法だと変換できません。
通常の発想ではない考え方が必要だと思います。
まれにしか用いない概念ですので、良い記事だったと思います。
経年の浅い小生、至らない点があったと思います。
これからは実数以外を基数に適用する研究をしたいと考えています。
また、これからのサイバー少年様のご活躍も応援しています。
失礼しました。

  • 2014/08/31(日) 17:30:43 |
  • URL |
  • 七十 #-
  • [ 編集 ]

Re: 七十

ああ、なるほど~。
重みをかけて足すという解釈でいけば1進法はありですね。
小数は表現できませんが。

ただ、一般的なN進法の定義では、N = 1としてしまうと色々な法則が無効になってしまいますね。
N進法のN = 1の場合と考えるより、2進法や10進法とは全く別物の記数法と考えたほうが扱いやすいと思います。

当記事の内容でも、前半のマイナス2進法は2進法や10進法と同じように定義できそうですが、後半の実数が基数となる記数法は違う定義にしないといけなさそうです。

実数以外の基数の研究ですか…。よい成果が出ることをお祈りします。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/67-2f576f64
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。