課題解き。
ソートについては忘れてください(ぉ
いや、書いてみたら予想以上にカオスになったので教科書眺めてください。多分ここ見るよかカクジツです。
例のごとく課題はこちら→課題
#毎度のことですがこんなエントリだれもよんでへん!ってツッコミはなしで
狙い目はやはり課題72
再起を書くだけです。
ちゃんと授業出てノートとってたなら課題71も楽勝
課題71
順列を求める問題。
perm [1,2,3]
なら
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
を出せばおっけー。
とりあえず一番根本となるアルゴリズムはこちら
void perm( int* a, int n ) { for( i = 0; i < n; i++ ) { swap( a[i], a[0] ); perm( &a[1], n - 1 ); swap( a[i], a[0] ); } }
#swapは適宜、適当なもんに置き換えてください。
授業でてれば完璧なはず。
流れとしては与えられた配列のうち0番目,1番目,2番目...をそれぞれ先頭と入れ替える。
で、先頭以外をもいっかい再起で変えていく、と。
実際に紙に書いて、脳内逐次実行していけば完璧。
ただこれだけだと何も表示しないのでひとひねり。
具体的にはn==0のとき、順列の生成が最後までできた、ということでなので、このタイミングで出力してやればいい。
いいのだが、その時にa::int*は配列の一番最後、というか最後の次を指しているのでaはそのままでは使えない。
引数増やしてやったり、あるいはグローバル変数を使うなりすればおっけーです。
多分簡単なのは後者。オリジナルのaとnをグローバルに保存しておけば、そいつを使って表示できます。
ソース書くとそのまま答えになっちゃうので割愛。
あ、haskellのソースは書いておきます(w
pickup :: Int -> [a] -> (a, [a]) pickup n xs = let (ys,(z:zs)) = splitAt n xs in (z, ys ++ zs) perm :: [a] -> [[a]] perm [] = [[]] perm xs = concat $ map (\n -> let (y,ys) = pickup n xs in map (y:) (perm ys)) [0..length xs - 1]
んー、もっと綺麗になりそうなものだが...
課題72
べき乗を求める問題。
考え方はすでに問題に書いてあるので、ここでは乗算回数のカウントのしかた。
友人*1が悩んでいたので(w
一番簡単なのはグローバル変数を使うこと。
グローバルに
int count;
とかしておいて掛け算が出る度に"count++"してやればいいだけ。
最後にprintするのを忘れぬように。
ちなみに
printf( "答え:%d\n回数:%d回\n", power( x, n ), count );
とか書くと、うまく行かないので注意。
result = power( x, n ); printf( "答え:%d\n回数:%d回\n", result, count );
と言う風に結果を一回変数にいれるか
printf( "答え:%d\n", power( x, n ) ); printf( "回数:%d回\n", count );
の用に分けてやってください。
なぜ最初のではいけないのかは次のコードを試してみて、考えてみてください。(なんか物言いが偉そうですいません...(д
int count = 0; int foo() { count++; printf( "This is foo.\n" ); printf( "count is %d.\n", count ); return 100; } int main( int argc, char* argv[] ) { printf( "count=%d, foo=%d, count=%d\n", count, foo(), count ); return 0; }
引数がどういう順番で処理されるかは確か規格があったと記憶してますが...
実際問題としては、実装依存、つまり「どうなるか分からない」と考えておいた方が身のためです。
結構やらかします。これ。
乗算回数は10乗で6回、20乗で7回、30乗なら9回、ぐらいの回数が出ればokがでると思います。
黒板には書かれませんでしたが、もうちょい工夫をすると、10乗,20乗,30乗でそれぞれ4回,5回,7回ぐらいまで減ります。
「もうちょい工夫」とか言って実はたったの二行増えただけなんですがね。
中学生レベルの工夫なので少し考えてみるといいカモ。
あと多分多いだろうなというミスは
return power( x, n/2 ) * power( x, n/2 )
とかしてしまうこと。
これはpowerが二回呼ばれちゃうので乗算回数が増えちゃいます。
これもまた
int powX = power( x, n/2 ); return powX * powX;
とかして一回変数にいれてやりましょう。*2
これまた、ソース書くとそのまま答えになっちゃうので割愛。
問題73
アッカーマン関数を求める問題。
定義は問題の方に書いておきましたが、定義のシンプルさに反してかなり凶悪な関数です。
単純に実装するとA(3,12)で0.05秒切るのは不可能だと思われます。
うちのパソコンではCPU使用率99%で、9秒程度かかりました。
ちなみに値は32765で、再起で呼ばれた回数は715,664,091回。
手計算で求める、なんてことはできなさそうです。どう考えても。
これで0.05秒切りたければ一回の再起が.00000000007秒ほどで終わらないとできないらしいです。
...多分、無理。
ちなみに英語版のwikipediaみれば分かりますが、「タワー記号」やら「チェーン記号」やらが出てきます。
たしか、タワー記号は"m↑↑n"と書いて、値は「mをm乗したものを、さらにm乗して、m乗して、m乗して...」をn回繰り替えしたもの。
例えば"3↑↑2"なら「3の3乗」で27、"3↑↑3"なら「3の3乗の3乗」=「3の27乗」で7625597484987、"3↑↑4"なら...あれ、計算できねぇや。
で、さらに"m↑↑↑n"と矢印を三つ書くと"m↑↑m↑↑m...↑↑m"(mがn個)という凄まじいものになって、"m↑↑↑↑n"なら"m↑↑↑m↑↑↑m...↑↑↑m"(mがn個)...
というものです。
チェーン記号はそのさらに発展版。
「何それ?」的なイかした記号が出てくるアッカーマン関数。
本文を読まなくても異常さがヒシヒシと伝わってきます。
そんなアッカーマン関数を求めろだってさ。
ま、色々チートるとずいぶん速くなります。(m<4の時限定
$ time ./73 3 12 32765 0.00user 0.00system 0:00.00elapsed 300%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+123minor)pagefaults 0swaps
と、まぁ、実質0秒で値が出てます。("300%CPU"?*3
再起で呼ばれた回数は14回。色々アレしてます。
#実はもうちと速くできるのですが...。
一応m=4で試してみると、
$ time ./73 4 1 65533 0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+122minor)pagefaults 0swaps $ time ./73 4 2 4294967293 0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+122minor)pagefaults 0swaps $ time ./73 4 3 4294967293 44.14user 0.25system 0:44.51elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+123minor)pagefaults 0swaps $ time ./73 4 4 4294967293 86.76user 0.12system 1:27.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+123minor)pagefaults 0swaps
これ以上は怖くてきでません。(というか終わりません。
あと、出力を見るとバグってるのが分かります。
値が大きすぎたようです。*4
m=1,2,3 n=1,2..10の時のアッカーマン関数の値を書いておきます
ack(1,1) = 3 ack(1,2) = 4 ack(1,3) = 5 ack(1,4) = 6 ack(1,5) = 7 ack(1,6) = 8 ack(1,7) = 9 ack(1,8) = 10 ack(1,9) = 11 ack(1,10) = 12 ack(2,1) = 5 ack(2,2) = 7 ack(2,3) = 9 ack(2,4) = 11 ack(2,5) = 13 ack(2,6) = 15 ack(2,7) = 17 ack(2,8) = 19 ack(2,9) = 21 ack(2,10) = 23 ack(3,1) = 13 ack(3,2) = 29 ack(3,3) = 61 ack(3,4) = 125 ack(3,5) = 253 ack(3,6) = 509 ack(3,7) = 1021 ack(3,8) = 2045 ack(3,9) = 4093 ack(3,10) = 8189
これを眺めていると回答の糸口が見えると思います。
ということでこれまで。Good Luck!
