関数の分割
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
〜関数の分割,統一〜
皆様初めまして,今回講座を書こうと思い立ったKtyaでありま...
さて今回はタイトルの通り"関数の分割"について圧縮テクを紹...
*関数の分割 [#v39cec1c]
高校数学でも習う有名な不等式で,"相加相乗の不等式"という...
二数の積が一定のとき,二数の和を小さくするのは二数の差が...
これは三数,四数となっても似たような事実が成り立ちます.
この事実はHOJでも応用(というか皆さん直感的に利用している...
例1 4 を(一つだけ)作るには 4*1 とするより 2*2としたほ...
a(X):XXXX
a(ssrssl)
よりも
a(X):XX
a(a(ssrssl))
の方が短く済みます.この例は非常に些細でどうでも良く,さ...
さて,これに続き"関数の分割"と言うのを考えてみましょう.
例えば諸事情あって次のような関数を使いたくなったとしまし...
a(X):XXXXXXrXXXXXX
(15B)
この関数を"分割"(と言うより、別の関数を用いて再現)して...
繰り返し等の補助として用いた関数にさらに補助としての関数...
例えば次が考えられるでしょう
b(X):XXXXXX
a(X):b(X)rb(X)
(15B)
新しい関数b(X)を定義しつつ,全く同じ15Bを得ました.先ほど...
ただこれだけだとa(X)飲み使いたい時は意味が無いです.そこ...
b(X):XX
a(X):b(XXX)rb(XXX)
(15B)
b(X):XXX
a(X):b(XX)rb(XX)
(14B)
後半はお分かりの通り,byte数を減らせる手法,前半は二倍関...
ここではもう一つ別の見方を紹介してこの例は終わりにします
b(X):XrX
a(X):b(XXXXXX)
(14B)
上の例でa(X)内でb(X)を二度用いている所にムダを感じたとこ...
これを行うとHOJではよくあるギザギザパーツsrslをb(s)lと言...
同様に相加相乗を施すと
b(X):XXrXX
a(X):b(XXX)
(13B)
b(X):XXXrXXX
a(X):b(XX)
(14B)
などが得られます.お分かりの通り一つ目は13Bというとても短...
もちろんどれかが常に一番いい,と言う訳ではないのでこのよ...
作るパーツに応じて変えるるのが良いでしょう
----
*再帰への応用 [#p82c9b99]
(具体例は追々追加する可能性があります)
今まではそのうち止まるコード(=再帰を利用しない)について...
ちなみに使用される事はあまりないので特殊な状況でしか使わ...
-成長速度や向きの調整
分割を上手く行う事で成長速度や向きの調整に力を発揮する事...
ここでは例を使って述べさせてください(現在例が非常に煩雑...
次のような物を書く事を考えます.
[[Problem 1728]]
#get_img(1728)
これは2歩進んだ後右に2*(n-1)歩分の十字,左に2*n歩分の十字...
さて実装方法ですが,まずは愚直に四倍関数を用いて
b(X):XXXX
a(X):ssa(rXX)rra(rsXsX)a(sX)
b(s)a(r)(31B)
もちろんこれを縮めていってもいいですがここでは成長速度の...
b(X):XXXXrr
a(X,Y):ssb(rYY)b(rXX)a(sX,X)
ssa(r,)
(Yに1個前のXを保存する事で上のような書き方を回避しました)
さらに成長速度を1個分遅くする事で最初の二歩も消せてお得です
b(X):XXXXrr
a(X,Y,Z):ssb(rZZ)b(rYY)a(sX,X,Y)
a(r,,)
(29B)
これはrXXと言う関数を次のように組み込むと縮みます
a(X,Y,Z):ssZZZZrrYYYYrra(sX,rXX,Y)
a(r,,)
(27B)
これを関数の分割(1*4を2*2にする)を行う事で最終的には次...
a(X,Y,Z):ssZZrrYYYYrra(sX,rXX,YY)
a(r,,)
(26B)
この問題については少し経路を変更する事(というかそっちが...
-フラクタル
フラクタルを作る際,よく"前のパーツを四倍する"という行為...
さらにその新しく出来たパーツを四倍する(パーツが四方に広...
まずこの状況を上手く再現する事が出来る場合があります,そ...
かなり限られた場合ですので問題を書いておきます..
-[[Problem 0330]]
[[HOJ講座]]
終了行:
〜関数の分割,統一〜
皆様初めまして,今回講座を書こうと思い立ったKtyaでありま...
さて今回はタイトルの通り"関数の分割"について圧縮テクを紹...
*関数の分割 [#v39cec1c]
高校数学でも習う有名な不等式で,"相加相乗の不等式"という...
二数の積が一定のとき,二数の和を小さくするのは二数の差が...
これは三数,四数となっても似たような事実が成り立ちます.
この事実はHOJでも応用(というか皆さん直感的に利用している...
例1 4 を(一つだけ)作るには 4*1 とするより 2*2としたほ...
a(X):XXXX
a(ssrssl)
よりも
a(X):XX
a(a(ssrssl))
の方が短く済みます.この例は非常に些細でどうでも良く,さ...
さて,これに続き"関数の分割"と言うのを考えてみましょう.
例えば諸事情あって次のような関数を使いたくなったとしまし...
a(X):XXXXXXrXXXXXX
(15B)
この関数を"分割"(と言うより、別の関数を用いて再現)して...
繰り返し等の補助として用いた関数にさらに補助としての関数...
例えば次が考えられるでしょう
b(X):XXXXXX
a(X):b(X)rb(X)
(15B)
新しい関数b(X)を定義しつつ,全く同じ15Bを得ました.先ほど...
ただこれだけだとa(X)飲み使いたい時は意味が無いです.そこ...
b(X):XX
a(X):b(XXX)rb(XXX)
(15B)
b(X):XXX
a(X):b(XX)rb(XX)
(14B)
後半はお分かりの通り,byte数を減らせる手法,前半は二倍関...
ここではもう一つ別の見方を紹介してこの例は終わりにします
b(X):XrX
a(X):b(XXXXXX)
(14B)
上の例でa(X)内でb(X)を二度用いている所にムダを感じたとこ...
これを行うとHOJではよくあるギザギザパーツsrslをb(s)lと言...
同様に相加相乗を施すと
b(X):XXrXX
a(X):b(XXX)
(13B)
b(X):XXXrXXX
a(X):b(XX)
(14B)
などが得られます.お分かりの通り一つ目は13Bというとても短...
もちろんどれかが常に一番いい,と言う訳ではないのでこのよ...
作るパーツに応じて変えるるのが良いでしょう
----
*再帰への応用 [#p82c9b99]
(具体例は追々追加する可能性があります)
今まではそのうち止まるコード(=再帰を利用しない)について...
ちなみに使用される事はあまりないので特殊な状況でしか使わ...
-成長速度や向きの調整
分割を上手く行う事で成長速度や向きの調整に力を発揮する事...
ここでは例を使って述べさせてください(現在例が非常に煩雑...
次のような物を書く事を考えます.
[[Problem 1728]]
#get_img(1728)
これは2歩進んだ後右に2*(n-1)歩分の十字,左に2*n歩分の十字...
さて実装方法ですが,まずは愚直に四倍関数を用いて
b(X):XXXX
a(X):ssa(rXX)rra(rsXsX)a(sX)
b(s)a(r)(31B)
もちろんこれを縮めていってもいいですがここでは成長速度の...
b(X):XXXXrr
a(X,Y):ssb(rYY)b(rXX)a(sX,X)
ssa(r,)
(Yに1個前のXを保存する事で上のような書き方を回避しました)
さらに成長速度を1個分遅くする事で最初の二歩も消せてお得です
b(X):XXXXrr
a(X,Y,Z):ssb(rZZ)b(rYY)a(sX,X,Y)
a(r,,)
(29B)
これはrXXと言う関数を次のように組み込むと縮みます
a(X,Y,Z):ssZZZZrrYYYYrra(sX,rXX,Y)
a(r,,)
(27B)
これを関数の分割(1*4を2*2にする)を行う事で最終的には次...
a(X,Y,Z):ssZZrrYYYYrra(sX,rXX,YY)
a(r,,)
(26B)
この問題については少し経路を変更する事(というかそっちが...
-フラクタル
フラクタルを作る際,よく"前のパーツを四倍する"という行為...
さらにその新しく出来たパーツを四倍する(パーツが四方に広...
まずこの状況を上手く再現する事が出来る場合があります,そ...
かなり限られた場合ですので問題を書いておきます..
-[[Problem 0330]]
[[HOJ講座]]
ページ名: