おちゃめくらぶ掲示板 - 1659321896

866：御茶目菜子：2012/02/11(土) 21:32:10: 最短の2進数変換プログラムは・・・？
最初に2進数ではなく汎用性の高いN進数に変換する場合を考えてみるにょ。
10進数をN進数に変換する場合にはNのP乗の和の形にすればいいにょ。
123を3進数に変換するためには3のP乗で表記する必要があり下記のようになるにょ。

　123　＝　3^5x1 ＋ 3^4x1 ＋ 3^3x1 ＋ 3^2x2 ＋ 3^1x0

それぞれの項の係数だけを抜き出すと1、1、1、2、0となりこれが10進数で123を3進数に
変換した値になるにょ。
ただし、この方法は手動による計算だとかなり大変にょ。
簡単に計算するにはN進数ならばNで割り続けその剰余を順に抜き出してそれを逆に並べれば
良いにょ。

　3) 123　・・・0　　←本当は除算の記号を上下逆にしたものを書きたかったけど
　3)??41　・・・2　　　横棒は表記し辛いため省略している
　3)??13　・・・1
　3)?? 4　・・・1
　3)?? 1

これを下から逆に読んでいけば11120となり上記の結果と同じになることが分かるにょ。

では、これをポケコンBASICで表記する場合に必要なものは下記のようなものにょ。

　入力処理
　演算処理
　出力処理

入力はINPUTを使えば簡単にできるし、出力はPRINTでいいにょ。
問題は演算部分だけとなるけどこれは変数Aに入力された数字をN進数に変換する場合には
AをNでどんどん割っていきAの値がNを下回った時にループを抜ければ問題ないにょ。
ここで厄介なのはポケコン（PC-E500シリーズ）には剰余を返す演算子がないという
ことにょ。
そのためINT (A/N)で商を求めてそれを使って剰余を求めるしかないにょ。

というわけでN進数変換プログラム（2≦N≦9）を作ってみたにょ。

リスト1
10 N=3:Z$="":INPUT A
20 B=INT (A/N):Z$=STR$ (A-B*N)+Z$:A=B
30 IF A>0 THEN 20
40 PRINT Z$

次にこのプログラムを2進数限定でさらに短くする方法がないか考えてみるにょ。
2進数だと10行目のN=3を省略し、20行目のNを2に変えるだけで完成にょ。

リスト2
10 Z$="":INPUT A
20 B=INT(A/2):Z$=STR$(A-B*2)+Z$:A=B
30 IF A>0 THEN 20
40 PRINT Z$

ただし、これは2進数に特化したものとは言い難いにょ。
剰余の演算子がないポケコンでも2進数限定であればANDを使うことで剰余を求めることが
可能になるにょ。

リスト3
10 Z$="":INPUT A
20 A$=STR$(1AND A)+A$:A=A/2
30 IF A>=1THEN 20
40 PRINT Z$

これで問題はないのだけどPC-E500シリーズの場合はANDの引数が-32768≦A＜32768に
なっている点に注意が必要にょ。
もしも、65535まで求めたいならばこの方法は使えないにょ。
32768単位で切ってから演算すれば問題ないけどかえって長くなるからね。

では、さらに1文字分短くすることは可能とはいえそれより縮めるためには発想の逆転を
することになるにょ。
Z$に値を入れるという方法をなぜとっているかというとそうしないと逆に並べる場合に
リストが長くなるからにょ。
逆にせずにストレートに出た順番に値を表示した場合には下記のようになるにょ。

リスト4
1 INPUT A
2 B=INT(A/2):PRINTA-B*2;:A=B:IF A THEN 2

リストを短くするため行番号を1桁にしてIF文においてA>0の「>0」は省略可能なので
それを省略したにょ。
試しに1234と入力すると01001011001と表示されるけどこれは2^9+2^6+2^4+2^3+2^0=601と
なるため正しくないにょ。
しかし、ポケコンを上下逆転すると10011010010となり正しい結果が表示されるにょ。
かなりインチキ臭いけど正しく結果が求められているため問題ないにょ。
もちろんこれがテスト問題だと上下逆に並べ替えるというアルゴリズムも要求されている
ため不正解になるけどこれはテスト問題ではないからね。
例えばゲーム制作において上下にジャンプするゲームを作る場合にできるだけ上下の
幅を長くしたい時にポケコンを縦長に持ってプレイすればいいという発想と同じような
ものであり、決して間違いとは言い難いにょ。
要するに自分が望む結果が求められれば良いわけなので「1から1000までの整数の合計値」を
求める場合に素直に1から順番に加算していくのではなく(1+1000)*1000/2で求めるという
方法も問題ないというのと同じことにょ。

「出力した結果を活用することはない」というのならばさらに短くできるにょ。

リスト5
1 INPUT A:CLS:LINE(15,0)-(0,0),A

これはPC-E500のLINE文が縦横16ピクセルの範囲であれば好きな自由な形が出力できるため
可能なことにょ。
左上を起点にドットがある＝1、ドットがない＝0として16ドット分見ていけば結果が
分かるにょ。
結果が数字ではなく視認性も悪いもののこれでも2進数というのは伝わるためできるだけ
短いものを希望というのならばこれもありにょ。

結局のところ、どこまでありか無しかという個人ごとの条件設定によってによって
どこまで短くできるか変わってくるにょ。
「Aの値は32768未満」「1つの変数に入れて出力しなくてはならない」「ポケコンの画面を
物理的に動かすのが認められない」という条件をすべて満たす場合にはリスト3が最も
短くなるにょ。（ただし、リスト3の行番号を1桁にする）
「32768以上でも計算可能」「結果を数値で出力する」という条件ならばリスト4が最も
短くなるにょ。（ただし、結果確認はポケコンの画面を上下逆にすること）

あと、2進数変換したものをプログラム内で活用するためには出力した結果をどのように
使うかということまで考えなくてはならないけどまとめて出力するよりも1桁ごと出力
した方が圧倒的に使える場面が多くなるにょ。（まとめて文字変数に入れても使用時には
二度手間になって使い勝手が悪いだけだと思う）
そのため「ポケコンをひっくり返すのはインチキ」と考える人であっても実際に自分の
プログラム内で使用する場合にはわざわざ文字変数に逆順に入れることはほとんど無い
と思われるにょ。
実際のプログラム内で処理を短くする場合にはその部分ではなく全体を見る必要がある
ということにょ。
それが本当に最短になるかどうかは実際にプログラム内に組み込んで使用するなど他の
条件がないと分からないからね。

みっぴゅさんへ
＞2chのポケコンスレにて、、、
＞ちょっと自分風に作り変えて投稿してみたら、もっと短いものを！っていうｶｷｺがありました。
＞御茶目さんならばどう作りますか？

レスついでにN進数変換についても書いたので上記を参考にしてにょ。
ちなみに>>972のものが上記のリスト2よりも1文字分短くなっており（バイト数で考えると
面倒なので省略）「32768以上でも計算可能」「ポケコンの画面を（以下略）」という条件
ならば最も短くなっていると思うにょ。
ただし、「32768以上の計算が可能」という条件のみならば10数年前に作ったリスト4
（ただし、結果は画面を上下逆にして確認）が個人的には最短に感じるにょ。

＞割と最近、2Chデビュー！しました！！！

私は10年ちょい前から2chは使用していてポケコンスレにも御茶目菜子で書き込んだことも
あるけれど当時ポケコンスレが荒れてしまいそれは他の板にも影響し、ここ（おちゃめ
くらぶ掲示板）の方まで飛び火してしまったにょ。
それ以降は御茶目菜子で書き込むことをやめてポケコンスレはROMに徹することにしたにょ。
したがって、あの騒動以降に2chで書き込まれた「御茶目菜子」のレスは私ではなく
ただの騙りにょ。