データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2

1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net] 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ アルゴリズムとデータ構造 - Kaneko Lab. ttp://www.kkaneko.com/adp/algo/index.html アルゴリズムとデータ構造 - ソースコード探険隊 ttp://www.codereading.com/algo_and_ds/ 各種アルゴリズムの C++ による実装 - Spaghetti Source ttp://www.prefield.com/algorithm/ アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP ttp://vipprog.net/wiki/algo_and_data_const.html 313 名前：デフォルトの名無しさん mailto:sage [2014/04/01(火) 20:07:56.78 ID:m1CmrLTr.net] ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists/ ↑のMITの講義で、スキップリストと呼ばれる1989年に考えられたデータ構造の 計算量を見積もるときに以下の問題を解く必要があります。 講義では明らかみたいなことを言っていますが、そんなに明らかでしょうか？ Aを正の実数とする。 f(x_1, x_2, ..., x_n) = x_1 + x_2/x_1 + ... + x_n/x_(n-1) + A/x_n とする。 fの値を最小にする正の実数x_1, x_2, ..., x_nを求めよ。 314 名前： ◆QZaw55cn4c mailto:sage [2014/04/01(火) 21:02:41.83 ID:Xl1FJm59.net] >>313 各項をかけるとx(n)がいかなる値であろうとも常にA 積が一定のとき、各項がすべて等しければ最小 とかいう問題ですか？英語よめないからよくわかりません 315 名前：デフォルトの名無しさん mailto:sage [2014/04/01(火) 21:31:37.80 ID:wNI+pTPk.net] So, I want to minimize L_1 plus n over L_1. And I get to choose L_1. Now, I could differentiate this, set it to zero, and go crazy. Or, I could realize that, I mean, that's not hard. But, that's a little bit too fancy for me. So, I could say, well, this is clearly best when L_1 is small. And this is clearly best when L_1 is large. So, there's a trade-off there. And, the trade-off will be roughly minimized up to constant factors when these two terms are equal. That's when I have pretty good balance between the two ends of the trade-off. So, this is up to constant factors. I can let L_1 equal n over L_1, OK, because at most I'm losing a factor of two there when they happen to be equal. 316 名前：デフォルトの名無しさん mailto:sage [2014/04/02(水) 00:00:27.81 ID:wKQIA80W.net] >>313 どこが分からないの? >>315 のところ？ 317 名前：デフォルトの名無しさん mailto:sage [2014/04/02(水) 06:26:11.63 ID:ueE6QFcL.net] 相加相乗平均の定理 318 名前：デフォルトの名無しさん [2014/04/06(日) 00:40:03.37 ID:tyVsXbcn.net] アルゴリズムの勉強は本当に疲れる センスのある人はアルゴリズムがスラスラ理解できるらしいが、俺は頭が悪いのでウンウン唸りながらじゃないと理解できん 319 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 01:14:46.49 ID:v5F7vKVc.net] それでいいと思う‥‥ 320 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 01:47:58.09 ID:rc99+CA1.net] 俺ハノイの塔とか未だにわからんわ 追っていると頭が混乱しちゃう 321 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 08:05:50.25 ID:B8PUb7p+.net] センスというものなのかどうかはわからんが、 機械の「機械のように正確な」動作を追うことができるかどうかは、 デバッグの効率には影響すると思う。この仕事に対する向き不向きとして。 322 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 08:33:13.34 ID:uLJ3NzvJ.net] 再帰をわかってる人は、大半のアルゴリズムに強い気がする 323 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 10:39:51.62 ID:tUu4o0lA.net] 再帰は確実に終了する根拠がないと使いにくいんだよな。 324 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 12:54:38.12 ID:rc99+CA1.net] ループは確実に終了する根拠がないと使いにくいんだよな。 チューリング完全は確実に終了する根拠が無いと主張できないよな。 325 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 14:01:26.03 ID:mKLMCJ7D.net] >>323 再帰を使う上でその根拠を決めるのは自分でしょ 326 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 17:47:49.59 ID:v5F7vKVc.net] >>323 再帰の頭に終了条件を書くでしょ、そのときに否が応でも自分で決めざるを得ない 327 名前：デフォルトの名無しさん [2014/04/06(日) 17:55:05.95 ID:/BRp7uTK.net] 再帰の頭に書くのは終了条件じゃないよ 328 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 18:32:11.06 ID:v5F7vKVc.net] >>327 ありえない、お前は再帰をもういちど勉強したほうがいい 329 名前：デフォルトの名無しさん [2014/04/06(日) 18:42:52.70 ID:N5LDc9gS.net] 多額な借金で人生つんでるヤシたちw manta.blog.jp livedeaichat.blog.fc2.com/blog-entry-1.html sisutore.blog.jp/archives/1000786211.html 330 名前：デフォルトの名無しさん mailto:sage [2014/04/06(日) 18:48:53.18 ID:1V1mpQ2/.net] >>327 じゃあ、今日からは、再帰を書くときは真っ先に再帰を終了させる条件を定義するようにしましょうよ。 331 名前：デフォルトの名無しさん [2014/04/07(月) 01:56:22.46 ID:d0TT8Xyg.net] 再帰は、内部的にはどーなってるんだ？ アーキテクチャの本を読んでも理解できなかったわ 332 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 03:42:51.76 ID:X0/QJ0Bz.net] >>331 マシン語勉強すれば？ 333 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 05:20:02.79 ID:EBZlvC1X.net] 再帰とマシン語はあんまり関連性ないだろ。 334 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 05:21:46.96 ID:EBZlvC1X.net] つーか終了条件が成立するまで自分自身を呼び出すだけ。 たったこれだけ。単にループを再帰で置き換えるだけなら 簡単。データ量が不定だったりする場合は一定の量だけを 切り出して、そのブロックに対して再帰にすればいい。 335 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 09:20:18.42 ID:X0/QJ0Bz.net] 内部的にどうなってるか知りたいってことは、引数やローカル変数が上書きされないかとか、どうやって元の場所に戻るんだろうとかが疑問だってことでしょ。 自分は、関数呼び出しがマシン語では引数や戻りアドレスをスタックに積んで関数の先頭アドレスにジャンプするコードになるのを知ってたから理解できたけど、そんなのは老害だって言うなら黙るよ。 336 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 09:25:29.71 ID:2J/E/BiW.net] 実装の話だろ、あってんじゃん 337 名前：デフォルトの名無しさん [2014/04/07(月) 09:29:04.52 ID:5wZ1j6dN.net] この関数が老害ってどういうことなんでしょう 338 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 10:06:25.41 ID:Azn2Ag2H.net] mkdir himitsu cd himitsu ln -s . himitsu 339 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 10:40:46.86 ID:2J/E/BiW.net] chown oh:oh himitu 340 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 19:44:06.53 ID:07lAy1km.net] ・ポインタ ・再帰 ・リンクリスト 辺りがダメな人は本当にわからないらしい。 数学科でもダメな奴がいると聞いた。 341 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 19:54:04.79 ID:WXfYbNCh.net] どう突っ込めばいいんだ？ 342 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 19:54:31.72 ID:jH/0whnp.net] ほんとだよなｗ 343 名前：デフォルトの名無しさん [2014/04/07(月) 20:03:59.61 ID:Yv3nxM4P.net] ねじ込むように突っ込む 344 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 21:57:36.22 ID:cPHU7Y9F.net] そんな奴等はメモリモデルとかアドレス空間から教えないと 345 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 22:44:41.34 ID:aZ3ao3+q.net] 還元的な方法以外でも理解可能です。 346 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 23:03:10.48 ID:R8X8CMOs.net] >>344 チューリングの計算可能の話にまで遡るのか・・・ 大学レベルだけど、講義でもないのに教えるの面倒くさいなあ 347 名前：デフォルトの名無しさん mailto:sage [2014/04/07(月) 23:13:47.29 ID:9xD+wUOX.net] なんでやねん 348 名前：デフォルトの名無しさん mailto:sage [2014/04/08(火) 17:07:35.17 ID:h+V2EGQg.net] 数学科って、cでプログラム書くようなことあるのか? 6年ぐらい入門して、最終的に触る機会なんてなかったぞ 349 名前：デフォルトの名無しさん mailto:sage [2014/04/08(火) 17:21:28.77 ID:mk0uQXXd.net] まず日本語を勉強してだな 350 名前：デフォルトの名無しさん mailto:sage [2014/04/08(火) 17:31:13.57 ID:h+V2EGQg.net] >>349 サクラ鯖に、なでしこでCGIでしょうか? 351 名前：デフォルトの名無しさん mailto:sage [2014/04/08(火) 17:44:56.41 ID:q/1QB78S.net] ↑のレスは天才チンパンジー「アイちゃん」が 言語訓練のために書き込んだものです。 352 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 11:33:00.99 ID:V7HoJaA9.net] 初級アルゴリズムならそうかもな 353 名前：デフォルトの名無しさん [2014/04/24(木) 11:55:31.38 ID:1XlNsioB.net] 中級・上級アルゴリストにはどんなことができるの？ 354 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 12:31:07.16 ID:mnsZs1hI.net] 実際に何か作ってるときに「こういうアルゴリズムがあるはずだ」と察知して 探せるようになればおｋ 355 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 14:05:02.62 ID:E/S2XTBi.net] 中級は学部・院生レベルくらいかな 既存のアルゴリズムの改良をしたり、 目的に沿ったアルゴリズムを開発したり、 その計算量やメモリ量を算出・証明したり、 実装したり、論文で発表したりする 356 名前：デフォルトの名無しさん [2014/04/24(木) 17:22:35.13 ID:CrNHZjbB.net] アルゴリズムはデザインがすべて 357 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 20:31:22.55 ID:RrLorudN.net] >>352 違う。 それを勉強し始めた時に思い描いた未来の自分になれば完成だ。 目標もなくただなんとなく勉強しているのなら、完成なんて永遠にこない。 あと、「一応」なんてものも無い。 358 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 21:05:08.96 ID:29x10p2Y.net] algorithmの問題に関する作業能率を最大まで上げたら、 らいなっくすやれいるずを作れるようなすーぱーはっかーになれますか？ 359 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 21:07:30.43 ID:29x10p2Y.net] >>352 蟻本嫁 360 名前：デフォルトの名無しさん mailto:sage [2014/04/24(木) 21:50:29.46 ID:RrLorudN.net] >>358 なれるわけがない。 ウソだと思うなら、実際に効率最大まで上げてみればいい。 361 名前：デフォルトの名無しさん mailto:sage [2014/04/25(金) 01:31:40.05 ID:J0O0+fbt.net] >>331 末尾再帰最適化、継続あたりで検索。 362 名前：デフォルトの名無しさん mailto:sage [2014/04/25(金) 22:30:20.43 ID:k5QgmFyd.net] >>355 高卒なのか? 363 名前：デフォルトの名無しさん mailto:sage [2014/04/26(土) 00:12:34.02 ID:4Xi6PaOs.net] >>153 >ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。 元のお題がI/Oなんで、この程度の比較命令は全く問題にならない。 わかりやすく書くのがいい。 364 名前：デフォルトの名無しさん mailto:sage [2014/04/26(土) 16:51:03.49 ID:LWRQ8Tqr.net] 最近はCPU速いんでネイティブじゃなくてjavascriptが流行ったり 最適なアルゴリズムより線形検索とかでも充分だったり 365 名前：デフォルトの名無しさん mailto:sage [2014/04/26(土) 17:09:52.91 ID:ztOmzoR+.net] うむ。今個人のPCで使われているDDR3-1600だと 転送速度12.8GB/sだからね。 0.01秒だと人間が知覚できるかどうかの世界だけど その時間があれば100MBのデータを探索できるわけだからね。 366 名前：デフォルトの名無しさん mailto:sage [2014/04/27(日) 18:18:02.68 ID:dkXr/W0v.net] 最近のJavascript JITはネイティブより速いことも多々ある。 367 名前：デフォルトの名無しさん mailto:sage [2014/04/29(火) 16:58:26.39 ID:pvgpWpOe.net] 涙ぐましい努力をするより富豪的プログラミングが流行る時代だしね 368 名前：デフォルトの名無しさん mailto:sage [2014/04/29(火) 19:48:18.31 ID:gkPlm+Vx.net] それでもリソースに限りはあるわけで、大きいのだとどっかで破産するんだよな。 富豪的プログラミングじゃなくて、成金的プログラミングだと思うよ。富豪ってのは 周りが無駄に無計画に使っているように見えても、実際は締めるところは締め、 使うところは使うっていうのだからな。 369 名前：デフォルトの名無しさん mailto:sage [2014/04/29(火) 19:50:52.99 ID:rRRSFl+L.net] リソースがショートしちゃうもんな 370 名前：デフォルトの名無しさん mailto:sage [2014/04/29(火) 20:17:40.02 ID:8B6X7USU.net] どこがどう大きくなるのかを見積もって、必要なとこを必要なだけ節約する、って形が有効。 必要以上の節約は労力の無駄使い。 371 名前：デフォルトの名無しさん mailto:sage [2014/04/30(水) 03:59:01.72 ID:RSryIHGR.net] firefoxで動画再生してると メモリ解放されなくてそのうち死ぬ 成金の糞flushのせい 372 名前：デフォルトの名無しさん [2014/04/30(水) 17:31:12.56 ID:8H1kM5Z6.net] UFC 128 - エリック・コク vs. ハファエル・アスンサオ https://www.youtube.com/watch?v=n2CcU1A1i-0 373 名前：デフォルトの名無しさん mailto:sage [2014/05/01(木) 08:04:28.79 ID:9zM4+Fav.net] >>371 一般的に、I/Oなどは、1MBほどのバッファを確保して、 バッファに読み込んで、再生などの処理をしたら、 処理したデータを捨てて、次のデータを読み込む、 シーケンシャル・アクセスで、バッファのサイズは大きくならない そのブラウザは、もう一度再生するときに、 ネット回線からダウンロードせずに再生するために、 データをローカルのメモリかディスクに保存しているんだな データを捨ててないから、最後にはメモリが確保できなくなるので、 もう一度見ないものは、タブを閉じたらいいのでは？ 374 名前：デフォルトの名無しさん [2014/05/03(土) 00:51:05.80 ID:pJ23Zgdt.net] １．中置記法を入力すると逆ポーランドに変換し出力する ２．逆ポーランド記法で入力するとそのまま逆ポーランドで出力する の両方できるアルゴリズムはありませんか？ １．は操車場アルゴリズムでできるようですが、 操車場アルゴリズムだと２ができません。 375 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 01:02:13.43 ID:nIlg1A2j.net] >>374 中値記法と逆ポーランド記法を識別する方法が知りたいって事？ 376 名前：デフォルトの名無しさん [2014/05/03(土) 08:21:56.99 ID:pJ23Zgdt.net] >>375 はい、そうです 識別方法はありますか？ 377 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 08:39:02.09 ID:ci/X6yFn.net] >>376 末尾だけを最初に見れば良いんじゃね？ 逆ポーランド記法の場合、必ず最後は演算子で終わるから。 但し、一番外側にカッコがある場合は、一度取り除いてから末尾を見ないといけないね。 378 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 08:41:32.32 ID:ci/X6yFn.net] 俺がやるなら、まず末尾から文字を順に見ていくかな。 カッコだったら次の文字に移動。 数字が先に現れれば中値記法。 演算子なら逆ポーランド記法。 379 名前：デフォルトの名無しさん [2014/05/03(土) 10:33:17.49 ID:pJ23Zgdt.net] ありがとうございます 末尾判断でやってみます 380 名前：デフォルトの名無しさん [2014/05/03(土) 10:44:34.36 ID:BYcmF+is.net] f 381 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 11:56:43.41 ID:1SJdCv6F.net] 俺は頭からやりたい 382 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 13:34:57.97 ID:gqLjB/uh.net] 頭で再帰しちゃったら無限再帰で _|_ やぞ 383 名前：デフォルトの名無しさん mailto:sage [2014/05/03(土) 14:00:37.70 ID:SFocP469.net] どして？ いま旅行中だから帰ったらやる 384 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 00:30:58.09 ID:/8HFkyur.net] ttp://www.younganimal.com/se/img/02.jpg ttp://www.younganimal.com/se/img/03.jpg ttp://www.younganimal.com/se/img/04.jpg ttp://www.younganimal.com/se/img/05.jpg ttp://www.younganimal.com/se/img/06.jpg ttp://www.younganimal.com/se/img/07.jpg ttp://www.younganimal.com/se/img/08.jpg ttp://www.younganimal.com/se/img/09.jpg ttp://www.younganimal.com/se/img/10.jpg ttp://www.younganimal.com/se/img/11.jpg 385 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:21:41.85 ID:LoW5JUMG.net] 続きはよ 386 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:23:49.16 ID:tByDu0vN.net] 続き見てきたけど、デザインパターンが分かって書いているとは思えないところがなんとも。 387 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:57:49.42 ID:mBc+6kiF.net] 続き読んでないけど、オカマなんか？ 388 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 10:08:06.94 ID:tByDu0vN.net] いや、オナホのソフトを作っている会社の社長。 ハードの話をすっ飛ばしていきなりオナホ界のジョブズだとかw 389 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 11:55:06.72 ID:2wcEJRw7.net] さて、短い旅から帰ってきた 頭からの再帰、明日にでもやろう その前に 頭からとか、末尾からとか 末尾再帰に関わる意味で言ってるんか？ おれは算術式の頭から見ていく という意味で言っていたが それにしてもなんでこんな簡単な問題が！ 初心者の俺は根本的に問題を誤解してるのか？ ま、いいや、明日には書いておく 390 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 14:05:33.54 ID:n8bRVLF6.net] >>389 少なくとも>>377で言ってる末尾は、再帰の話なんて一切してないよ。 単純に数式文字列の最後の文字と言う意味ね。 391 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:22:58.60 ID:peygn8xB.net] >>374 課題では中置を逆ポーランドにだったけど、アルゴリズムの都合上、 中置もポーランドも逆ポーランドに変換(無論、逆ポーランドはそのまま) また、各種記法の混在を認める ((1 + (* 3 5)) (8 - 2) (2 5 expt) +) でもよし 方針　式の頭からワンパスで変換を終了する 使用言語　Scheme codepad.org/Ogp2Lzwh 392 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:41:37.31 ID:2wcEJRw7.net] >>391 どひゃ！ >>391は変数と演算子を区別していない！ 式の計算ではなく 式の変換だけの課題だった！ もう、変換だけでなく計算してしまう過大なら楽なのに！ （今日は寝る） 393 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:44:47.52 ID:2wcEJRw7.net] (number? x)のところを (number (eval x ()) )にすりゃいいな 394 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 08:05:58.63 ID:wP+UVhzo.net] >>391 式に変数も認めるバージョン 演算子情報はは演算子データベースに保持 codepad.org/c65AyXpd 395 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 09:00:44.75 ID:ZPrSoRKy.net] 気持ち悪い 396 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 09:23:14.89 ID:wP+UVhzo.net] あはは ゲロはいてろ 397 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 17:36:11.48 ID:SXeDLzrE.net] 再帰プログラムを非再帰プログラムに変換する方法が理解できません。 たとえば、フィボナッチ数列を再帰的に計算するプログラムを スタックを使って非再帰的に計算するプログラムが野崎昭弘さんの 本に載っているのですが、何度読んでも理解できません。 どうすれば理解できるようになりますか？ 398 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:03:16.22 ID:lP/gHzU8.net] たまたまそのコードと自分の相性が悪い、といったようなことはあるから、 他の例をさがしてみたら？ 399 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:38:21.93 ID:rkx/vo/u.net] >>397 fibonacchi数列の非再帰表現をするにはごく普通にwhileループを使って実現できる f(n) = f(n-2) + f(n-1) のf(n-2)の値を例えば変数prev2に保存し f(n--1)の値を例えば変数prev1に保存すれば f(n) はprev2 + prev1で求められる それを変数ansに格納すれば while ループごとに 　ans = prev2 + prev1 prev2 = prev1 prev1 = ans と更新していけばよい また、f(1)=f(2)=1なのでそれはwhileループで処理しない。逆に f(3)以上の値をwhileループで求めればよい 具体的には、これを見ろ codepad.org/vdi9qyqK 400 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:41:31.99 ID:lP/gHzU8.net] フィボナッチを再帰的じゃなく求める方法についてじゃなくて、 再帰的なコードのループへの変換がわからない、ということでしょ。 401 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:42:59.47 ID:rkx/vo/u.net] ん？スタックを使いたい？プッシュしてな、いきついたら、ポップするんだよ 402 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:13:51.53 ID:a2G3KqVr.net] >>399 まあ再帰は基本的に遅いけど、メモ化すればずっとマシになるし(震え声) C++で書いてみたサンプル↓ codepad.org/HgtP5slM 403 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:17:07.35 ID:a2G3KqVr.net] >>400 まあフィボナッチは末尾再帰(非再帰型にしやすいもの)の中では定番ですし…… そうでなくてもスタックが使えれば原理的にはなんだって非再帰にできるはずだが ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0 www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node67.html 404 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:34:10.95 ID:6FN1Wxeb.net] >>403 ではAVL木や赤黒木（二色木）を非再帰に書き下ろしてみてくださいな 405 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:38:01.88 ID:a2G3KqVr.net] >>404 「原理的に」つっただろ……なぜお前の代わりにそんな面倒なことする必要がある？ 406 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:39:42.73 ID:6FN1Wxeb.net] >>405 できないのですね 407 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:54:10.14 ID:84RD4hek.net] 煽っても何も得られないと思うぞ 408 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 20:11:01.93 ID:6FN1Wxeb.net] ということにしたいのですね 409 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 20:22:30.15 ID:lP/gHzU8.net] CPS変換すればなんでもGOTO 410 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 23:21:34.01 ID:irORkSf3.net] 関数呼び出すは引数をスタックに積んでｇｏｔｏしてるんだものな。 411 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 13:14:23.25 ID:6fCCnAU/.net] 呼び出した場所の情報もスタックに積まないと戻れないぞ 412 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 13:28:37.03 ID:Ml/OqnCm.net] それも引数だと思えばいい。 ていうかCPS変換てのは、戻らない形にするプログラム変換だから。 413 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 15:05:44.99 ID:r0DUx653.net] 「継続」だな 引数だけ渡しても再開できるとは限らんから

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef