*どんな問題でも解けるコード！？ [#ld7dad7b]

今回は，

> ''どんな問題も，いくらでも大きい数値が使用可能ならば，14バイト以下で解ける''

ということを紹介したいと思います．テクニックとしては数値手法，12バイト構文の周辺ですね．

例えば次のコードを見てみましょう：
 a(T):ra(T-64)sa(T+T), a(N)

これは大体N/64の2進法展開の計算に対応しています．~
64で割った余りを2倍し，さらに64で割った余りを2倍し…という計算がおこなわれますね．~
「大体対応」という半端な表現をしたのは，正確な2進法展開とはずれがあるからで，~
「割った余り」といっても0のときは64が生き残るという影響で，2進法展開とは異なります．~
また，商が0のときはrが1回，商が1のときはrが2回実行されますね．~
何はともあれ，この構文にN=1からN=64を代入した結果を考えると，~
最初の6回の計算結果は全て異なるものになります（←深く考えず書いたので要確認ｗ）．~
「rを(1回または2回)+s」を6セット並べるパターンは64通りあり，それが全部実現されます．

----
これを，64よりも大きな数でやるとどうなるでしょうか？？~
''いくらでも大きな数値を使用可能という前提''に立つならば，
> 「rを(1回または2回)+s」を10000セット並べる

みたいなものも，Nの値を変化させるだけで全て12バイトで作り出せる計算になります！

しかし残念ながら，これでは任意の問題が解けるわけではありません．~
細長い道を直進しようとすると，「rを(1回または2回)+s」だけでは不可能です．~
そこで，必ずrが「1回または2回」で出てくるというのを修正する必要があります．~
簡単な実装方法を2つ紹介しましょう（他にもあるかもしれないけど）．

まずは，「rを(1回または4回)+s」を並べるというもので，~
これを実装するには2進法の代わりに4進法を使うだけです：

 a(T):ra(T-A)sa(T+T)
 a(N)

AやNのところを大きな数にすると，「rを(1回または4回)+s」を自在に並べられます．~
直進したければrを4回やればいいですね．~
別の方針は，「sを(0回または1回)+r」を並べるというものです．~
普通に書くと1回または2回になるので，1回目は実行されないというような処理をつけます．

 a(X,T):Xa(s,T-A)ra(,T+T)
 a(,N)

AやNのところを大きな数にすると，「sを(0回または1回)+r」を自在に並べられます．~
実行ステップ的にはこちらの方法の方がスマートでしょうか？？？

----

任意の問題が14Bで解ける!!!!!と思いきや，現実は厳しいですｗ~
数値が256までしかないので, この方法だけで問題が短く解けることはまずありません. 

しかし, このような考え方から[[数値関数による長文圧縮]]の手法が生まれました.
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS