- 1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18]
- どこにもない強固なスレにしたい
- 820 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 07:55:25.52 ]
- いい案があるわけではないんだけど、確認。
> 障子のあちこちに大きさ形まちまちの穴があいていて、
穴の位置が {(3.8, 2.6), (1.4, 1.4), (2.1, 3.5)} みたいにして与えられると思えばいい？
> その穴をふさぐために使える障子の形を長方形に限定して
辺は x, y 軸と平行？ どんな向きでもあり？
- 821 名前：810 mailto:sage [2011/05/10(火) 09:53:10.32 ]
- 領域分割それっぽいですね。googleとと相談してみます。
ありがとうございます。
>>818
評価関数もふくめ方向性を考えてます
開いている穴のうちふさがれている割合 1.0
を必要条件として
長方形領域の集合のうち、穴を塞いでいる部分の割合をP
用いる長方形の個数をnとすると、
Pとnの多項式で定式化出来ると思いますが、具体的にどうとは考えてないです
>>820
今回私が解こうとしている問題に関しては
BOOL area[][];のようなかたちで入力は与えられますが、
おおむねそういう感じです。
長方形の辺は軸に平行で考えています。
- 822 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 14:22:27.31 ]
- TかFかが与えられる点は格子点で、斜めに置いたりはしないと。
>>817 にあるように、うまく部分問題に分割できないのが難しいねぇ。
理屈の上では組合わせは有限なので順番に評価関数に食わせて一番評価の高いのを
選べばいいわけだけど、現実には組み合わせ爆発で無理だから、よさげなのを探索
するしかないかな。
戦略としてはトップダウンとボトムアップの2通りがあると思うんだけど、トップダウンのほうは、
まず1個の矩形からはじめて、矩形の数が増えてもいいから、塞いでる割合が増えるパターンを、
探索していく。この時最初の矩形より外に広がることはない。（>>817のように途中のプロセス
ではそうでない場合もあるのが難しいところ）
逆にボトムアップは、穴の1個1個をそれぞれ小さな矩形でふさいで、それをだんだん大きい
矩形の集まりにしてゆくというもの。これもやっぱり一本道というわけにいかないのが難しい。
- 823 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 22:59:01.22 ]
- 使えねぇやつらだな。アルゴリズムスレなんだからそれらしいレスしろよ。
Graham走査だろ？ あとはググれ。
- 824 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:12:57.91 ]
- 多角形の凸包が作れて、この問題的にどこがうれしいわけ？
おまえは使える奴なんだから、凸包の多角形から、どういうアルゴリズムで、
いい感じの長方形の集合を作るのか、ちゃんと説明しろよな。
- 825 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:51:27.60 ]
- Graham走査ググったら関係ないふいた
- 826 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:58:02.30 ]
- bitonic sortでクグれよ
- 827 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 10:02:48.66 ]
- 一種のマージソート？
- 828 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:00:00.47 ]
- >>823
が言いたいことはGraham捜査で全ての点を包含する凸包の点を取得し、
その集合からXYそれぞれについての最上、最下の座標を探せば言いよってことなんじゃねえかと。
まあ全ピクセルを捜査してXYの各座標について最小、最大を
見つけるたびに書き換えてあげれば目的の長方形の見つかると思う。
ただし重いｗ
もしデータを書き込むところから制御できるなら、書き込むたびに
XYについて最小値、最大値を書き換えてあげば簡単に見つかると思う。
- 829 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:35:11.13 ]
- >>828
もし >>823の意図がそれなら、彼は必ず一つの長方形で覆うものと勘違いしてないか？
点群が１ヶ所に固まっていれば長方形一つが最も無駄が無いだろうが、
まばらに分散していれば複数の長方形で覆った方が無駄が無い場合の方が多い
- 830 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 13:18:57.72 ]
- >>810の問題だと一つ以上の長方形の集合を求めるだっけか。
前提として点を2つ以上含めた物を長方形とするって決まりが暗黙的に適用されるのかな。
長方形同士ってかさなってはいけないとかもあるのかな？？
- 831 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:06:17.79 ]
- 微妙に問題が曖昧なんだな。
とりあえず、ある程度の塊に点群を分類してからやりたいなら、空間(ここでは平面か)分割してクラスタリング。
クラスタ重心を計算しながら分割領域を調整。調整が終わったらグラハムさんの出番。
…で、できそうな気がするけど、適当思考なので上手く分割できるかちょっと自信ない。
これだと、矩形の重なりは発生する可能性が残ってるし。
- 832 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:17:43.65 ]
- 危険点をカバーするように検査エリアを設定したいのかな。
だとすると、水平方向はある程度無駄が在ってもいいけど垂直方向はできるだけ無駄がない方がいいとか、
矩形同士が重ならないだけでなく水平方向に違う高さを持つ矩形が存在したら拙いとかw
- 833 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:25:36.60 ]
- >>810応答せよｗ
- 834 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:47:16.41 ]
- 何を求めるのか、それが曖昧だ。
面積を最小にするのか、矩形の数を最小にするのか。
n個の点に対して、面積の最小値はnだし、矩形の最小値は1。
なので、求めるモノを定義しないと、「だいたいこんな感じ」の解しかでてこない。
- 835 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 18:06:34.87 ]
- >>834
だから >>818 で評価関数はどうすんのと訊いたら、
>>821 でまだ考えていないと
- 836 名前：デフォルトの名無しさん mailto:sage [2011/05/12(木) 00:17:47.50 ]
- 求めたものを結局何に使うのかがわかればもっと適した方法が絞れるんだろうけどな
- 837 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 19:43:52.24 ]
- ループと動的確保なしで数値範囲の和と積を扱う手法は有りますか？
- 838 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:05.61 ]
- >>837
悪いが意味が分からん
具体的に、何か例を示してくれ
こういう入力に対して、こんな計算をして、こういう出力を得たい、とか
- 839 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:53.56 ]
- >>837
なぜにそんな限定を？
- 840 名前：837 mailto:sage [2011/05/16(月) 22:13:20.11 ]
- YesNoで答えられる質問一つで数値の範囲が決まる
Yesなら[a,b)、Noなら[-inf,a)or[b,+inf)
で可変個の質問にユーザーに答えさせて範囲をand結合して絞りこむ
で、最後に絞り込んだ範囲を表示
という課題がでたんです
でもその講義でまだ入出力とifとgotoしかやってないんです配列もやってません
どうも周りに聞いたところによるとその教授は講義範囲外のことをあまり使うといい顔をしないらしいんです
ですので講義範囲内で処理したいんですが…という感じです
- 841 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 22:58:41.22 ]
- goto と if 使えるならループ作れるじゃん
- 842 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 23:32:25.49 ]
- >>840
宿題は自分でやれよ屑。
あと、おまえみたいなゴミは社会に出てくるな。
氏ね。
- 843 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 01:34:33.75 ]
- いずれにしろこのスレで聞く事じゃないな
- 844 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 03:16:59.99 ]
- >>840
講義範囲外のこと使っていい顔しない教授とかクソだから無視で。
- 845 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 07:32:31.58 ]
- ざっとみて講義が目標とする力量に達していたら
「できるんだったら来週からこなくていいよ。単位だしとくから」
ってのが大学的
- 846 名前：デフォルトの名無しさん [2011/05/31(火) 21:25:56.80 ]
- 相異なる３１個んもデータがある。この中に含まれる数をキーとして逐次探索
を行うデータが見つかるまで、それぞれ何回の判定が必要か、期待値を求めよ
これの逐次ってどうやって求めるんですか？？
1/31+2*1/30+・・・・
みたいな感じでしょうか・
またキーが含まれない場合もおしえてくださいｍｍ
- 847 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 21:39:11.09 ]
- 期待値は31/2回
キーが含まれない場合は31回
- 848 名前：デフォルトの名無しさん [2011/05/31(火) 21:53:04.17 ]
- ありがとうございます
含まれる場合の期待値の求め方をおしえてください
キーが含まれない場合の２分木探索はどうやるんでしょうか？？
- 849 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 23:00:07.25 ]
- どっから二分木でてきたんだ
- 850 名前：デフォルトの名無しさん mailto:sage [2011/06/04(土) 19:20:16.63 ]
- Write-Ahead Loggingのアルゴリズムって
何があるのですか？
- 851 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:23:27.24 ]
- Nこ（N<=256）の重さ付き要素から最小の2こを取り出して合計して1つにして戻す（N-1こになる)という操作をするときに
①昇順ソート→index1,2を取り出して合計して戻す
②一回操作して最小の2つのインデックスを記録→取り出して合計して戻す
どっちが速いかな？オーダーだけ見ると①のような気がするけどswapコストとか考えると②の方がいい？
- 852 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:29:12.79 ]
- それこそ直ぐにプログラムかいてベンチとれってかんじじゃね？ｗ
- 853 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 16:00:31.18 ]
- 256個なら誤算の範囲。
N=100万とかなら、迷わず2じゃね？
なんで、1のオーダーの方が小さいと思うの？
- 854 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:40:48.70 ]
- 各ピクセルが得られるビットマップ画像があります
これをjpgエンコードしたほうがいいのかpnhエンコードしたほうがいいのか判別するにはどのような方法が考えられるでしょうか
- 855 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:42:51.03 ]
- 何を指標にして判断したいのかかけよな、エスパーでもさがしてんのかよ。
- 856 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 16:12:56.69 ]
- 俺はピクセルの取得できないビットマップ画像を教えて欲しい。
- 857 名前： 忍法帖【Lv=3,xxxP】 mailto:sage [2011/06/10(金) 16:31:42.49 ]
- そんなことよりも、私はpnhエンコードとやらを知りたい。
- 858 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 19:09:13.91 ]
- ピンフ形式だよ。言わせるな恥ずかしい。
- 859 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 20:40:53.31 ]
- アンコの方が好みです
- 860 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 21:44:37.61 ]
- 平和、すなわちパチンコ業界の手先だな
- 861 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 22:29:46.37 ]
- 麻雀の役を辞書にして圧縮するとかどうだろう。
グラデは順子が多いとか。
- 862 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 23:47:52.31 ]
- >>851
(3) 最初にヒープを作る→ヒープから最小値2個取り出し合計してヒープに戻す
オーダー的にはこれがいいと思うよ
- 863 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 18:55:05.37 ]
- アルゴリズム考える時ってキャッシュ効率とかアクセス効率とか最初から含めて作業始める？
それとも論理的な計算量だけで考える？
- 864 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 19:16:10.15 ]
- 私は数学屋じゃないから、先ずはシンプルかつ汎用性を考えるね。
- 865 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 21:48:47.05 ]
- 非負の整数a, b（a <=b)があったときに
a <= x <= bになる、「いい感じの整数x」を求める方法はないかね？
クイックソートのピボット選択や、パーリンノイズやGAで使いたい。
一番簡単なのはx=(a+b)/2なのだが、面白味に欠ける。
x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
できればaとbが一意ならxも一意で決まって欲しい。
フィボナッチ分割はどーかなー。
- 866 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:00:02.99 ]
- 黄金分割しろ。
- 867 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:27:59.93 ]
- >>865
> x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
アルゴリズムスレなんだから、「気がする」で放っておくんじゃなくて、
本当に求めているパフォーマンスを達成できないほどのオーバーヘッドか確認しようよ
あとアルゴリズムスレなんだから、何が「いい感じ」なのか
できる限りハッキリさせようよ
とりあえず、a と b の中間値が「いい感じではない」ことは分かった
擬似乱数はシードを決めれば入力値に対して一意に決まるが、
もしオーバーヘッドが気にならないほどであれば、擬似乱数でいいのか？
擬似乱数が「いい感じ」なのか？
そして、アルゴリズムスレなんだから、「フィボナッチ分割はどーかなー」ではなく、
実際にフィボナッチ分割したらどんな a b に対してどんな値が出力されたのか示してくれ
- 868 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:44:09.90 ]
- ゆとり乙
- 869 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 10:53:51.44 ]
- 比率を一定にしたいなら、積の平方根とか。0が入ったら知らんが。
でも、ピボットに使うっていっても、分布しだいじゃね？
- 870 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:07:33.88 ]
- たとえば
func shikaku(left, top, right, bottom){
if (十分小さければ){
塗りつぶす(left, top, right, bottom);
} else {
x = bunkatsu(left, right);
y = bunkatsu(top, bottom);
shikaku(left, top, x, y);
shikaku(x, top, right, y);
shikaku(left, y, x, bottom);
shikaku(x, y, right, bottom);
}
}
で、モヤモヤした感じが出したい。
ピボットはまあ、乱択っぽくて任意の分布でもいいかなと。
- 871 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:15:47.19 ]
- どう見ても全部塗りつぶしてるようにしかみえないのだが。
- 872 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 18:27:45.99 ]
- ああっ、色を指定するの忘れていた
- 873 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 00:42:57.61 ]
- 株に関するプログラムをしたいのですが、
ここで質問して良いですか？
株の専門用語の話とかじゃなくてグラフに関する事なんですが。
- 874 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 09:06:44.12 ]
- ロケット工学投資法を読破した俺が答えてしんぜよう
- 875 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:11:15.41 ]
- >>874
では、それで御願いします。
株のサイトでチャートの形によって、売買銘柄を
選択するサイトがあるのですが、その仕組みというか
考え方を教えて下さい。
一例として、上昇トレンドかどうか判断するには移動平均を
1日ずつ計算して前日より上がっているかどうかを比較して
いけばいいかなと思ったのですが、実際には上がったり下がったりして、
単純な比較だと、実際は上昇トレンドなのに途中に下がった日があるので、
上昇トレンドと判定できない場合が出てきます。
期間を決めて、その期間内の最高値と最安値が何月何日か、
もしくは、本日が期間内の最安値より高いかで決めるにも、
それじゃ、期間を何日間にするのかと言った条件によって
変わってくるだろうし、どう判断条件を作ればいいか分からないのです。
チャートの形にも色々あるので、簡単には説明できないと思いますが、
上昇トレンドの判断の仕方だけでも教えてもらえれば、他にも応用できるかも
しれないと思いますのでよろしくお願いします。
長文失礼しました。
- 876 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:52:34.06 ]
- そりゃスレチだな。
- 877 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 12:13:47.96 ]
- スレチですか。
失礼しました。
- 878 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:12:58.78 ]
- >>875
ロケット工学投資法にはトレンドラインの作り方が載ってる
まああれを馬鹿正直に実装するより楽な方法もあるんだが……
タダでは教えられんｗ
- 879 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:14:23.21 ]
- >>875
追記。単に作画したパターンにマッチする銘柄を選択するだけなら、
それは「パターン認識」技術の世界だ。ぐぐれ。
- 880 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 15:01:28.43 ]
- >>878
∧∧ ｺｲﾔｧｧｧｧ！！
(д´* )
（⊃⌒*⌒⊂)
/__ノωヽ__）
>>879
パターン認識、オソロシス
- 881 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:17:06.36 ]
- この株のネタだと微分の話になるんじゃないのか？
- 882 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:19:46.59 ]
- >>875
チャートだけ見て判断とか馬鹿だろ。
帰納的に、現実に起こった事実と、チャートの微分を比較できなきゃ
予測がかすりさえしないだろ。
- 883 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:47:34.80 ]
- >>882
お前は質問スレで何言ってんだ？
だったら、微分を調べろで良いだろ
馬鹿なのか？氏にやがれなのか？
- 884 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:10:40.43 ]
- ここ質問スレじゃないだろ・・・スレタイなんて書いてあ
- 885 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:15:05.39 ]
- あ、ホントだ
ごめんよ
- 886 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 05:50:28.01 ]
- 木に一本だけ辺をつけ加えて最長となる閉路を探すアルゴリズムか
グラフの中から最長となる閉路を探す方法を教えて下さい
- 887 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 14:11:58.10 ]
- >>886
前者の場合
元の木Tの最も深いノードをルートにした木T'において、
木T'のルートと最も深いノードの間に
一本だけ辺をつけ加えたのが最長閉路になるのでは？
- 888 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 11:34:06.03 ]
- 勉強で木構造とそれを巡回するイテレータをC++で作ってるんですが(STLのようなインターフェイスで)
イテレータの内部にスタックorキューor到達済みノードのリストを動的に確保して保持することなく
すべてのノードを巡回する方法はありますか？
イテレーターなので再帰関数を使って一気にという事ができないので
どうしても内部に状態を保持しないとダメかなとは思うんですがアロケートを駆使返すのは効率が気になって…
- 889 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 13:32:29.72 ]
- vectorかlistを包含したnodeクラス作って再帰で巡回させるのはだめなのかい？
- 890 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 20:48:32.37 ]
- 巡回する順番はどうでもいいんだったら
すべてのノードを共通の動的配列上に確保しておけば?
- 891 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 21:27:39.01 ]
- Addしたら必ず1本の共通なリストにノードを追加するのはありだね！
- 892 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:06:08.91 ]
- オブジェクトプーリングするのもいいかも
- 893 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:27:53.42 ]
- 配列もリストも使わずに、状態保持もしないで全ノードを巡回するアルゴリズム
ただし、木を破壊する
[1]. ルートノードを巡回する
[2]. ルートノードの子ノードから１つノードxを選び、
他の子ノードを全てxの子ノードにする
[3]. xをルートノードと見なして [1] へ
- 894 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:32:36.91 ]
- 親へのポインタ持ってたら普通にできますた
- 895 名前：デフォルトの名無しさん mailto:sage [2011/10/13(木) 14:44:27.48 ]
- バーローｗ
- 896 名前：デフォルトの名無しさん [2011/10/25(火) 21:39:34.27 ]
- 誰か教えてください。
アルゴリズム入門の授業なんですが
・性の小数部分を求めるサブルーチンＤＥＣのフローチャートを書け
・サブルーチンＤＥＣとサブルーチンＩＮＴを使って入力した正の実数の小数点以下を切り上げた
整数を表示するフローチャートを書け
お願いします
- 897 名前：デフォルトの名無しさん mailto:sage [2011/10/25(火) 22:24:50.90 ]
- まず浮動小数点数の規格を調べます
- 898 名前：デフォルトの名無しさん [2011/10/26(水) 02:34:55.29 ]
- 言語の持っている暗黙のキャスト機能が使ってよいなら簡単なんだが
アルゴリズムの授業なんだから多分ダメなんだろうね。
- 899 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 04:55:27.33 ]
- まずは、整数値を求めればいい。元の値 - 整数値が小数部分だ。
切り上げは、小数部分が0かどうかで整数値か整数値+1かを返せばいい。
整数値は
1より小さくなるまで10で割るのを繰り返す。
その回数分10を掛けながら1～9までの値と比較することで一桁づつ数字を確定していく…
なかんじかな。ループ中に10を掛けている値から確定した数字を引いていくのと、
0に初期化してある変数に10を掛けながら足していくのを忘れずに。この変数が元の値の整数値になる。
浮動小数点数でやると、誤差が出るだろうけれど…
- 900 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 08:11:17.89 ]
- アルゴリズムをフローチャートで書かせるって、まだ一般的なんか？
- 901 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 09:02:43.69 ]
- いまどき信じられん教育のレベルだ
- 902 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:02:05.33 ]
- 高校の情報なんちゃらとかって科目じゃね?
- 903 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:14:01.81 ]
- てことは、日本の高校が信じられん教育レベルだって事実になってしまうわけだけども
- 904 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:13.30 ]
- www.johoka.net/flowchart.htm
- 905 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:20.20 ]
- 実際、「使える！Microsoft Office」って改名したらどうだ？ って言いたくなるような
教科書が、高校の情報の教科書の中で一番人気だという話だ。
- 906 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:30:03.53 ]
- 大半の人にとって、Office の使い方が将来一番役立つ可能性が高いのは確かだけども。
日本のソフトウェア開発は育たないわね。
- 907 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:36:20.78 ]
- 小学校から徹底してopen officeを使うように指導すれば
日本全体でオフィスソフトに使われている莫大な金を節約できる
- 908 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 16:20:09.01 ]
- その考え方はまずい…
使う側からしたら無料なのはありがたいけど、作る側それこそ育たない。
- 909 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:41:00.78 ]
- その論理ではOpenOfficeはともかく、GCCとかはこの世に存在しないことになるね。
- 910 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:58:05.44 ]
- >>907
有料だと金が国外に流出してるだけだし
かといって無料だと国内でも回らないし
- 911 名前：デフォルトの名無しさん [2011/11/07(月) 18:03:02.90 ]
- （ExcelVBAのスレから誘導されてきました）
末尾再帰の最適化について質問です。
FunctionA(n As Long)
If n=0 then
FunctionA=1
Else
FunctionA=FunctionA(n-1)+FunctionB(n-1)
End if
End Function
FunctionB(n As Long)
If n=0 then
FunctionB=2
Else
FunctionB=FunctionA(n-1)+FunctionB(n-1)
End if
End Function
このように末尾で2つの関数が再帰呼び出しされている場合、どのように最適化すればよいでしょうか。
nが大きいと2の累乗でスタックに詰まれていくから重くなるのだと思います。
- 912 名前：デフォルトの名無しさん [2011/11/07(月) 18:19:50.43 ]
- forをつかって普通にループをかいてください。
これで理解できなければあなたには無理です。
- 913 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 18:56:27.71 ]
- っていうか、FunctionA や FunctionB の演算って末尾なの？
- 914 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 19:25:14.40 ]
- どちらも、最後に自分に戻ってきて、2つの値を足して、それを戻す、という形になってるから、
末尾呼び出しになってない。
- 915 名前：デフォルトの名無しさん [2011/11/08(火) 00:20:34.51 ]
- うるさいな
- 916 名前：デフォルトの名無しさん [2011/11/08(火) 09:56:31.88 ]
- 足し算じゃなく1個ならforなりn--なりで終息させられるが2個なのが厄介だな
- 917 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 12:52:21.06 ]
- 例が悪いよ
2つの関数が再帰呼び出ししてるのは関数の末尾じゃないし、
FunctionA と FunctionB で異なるのは引数がゼロの場合の返値だけ
おまけに、FunctionA(n-1)+FunctionB(n-1) は共に同じ n-1 に関数を適用してる
だったらアルゴリズムのスレとしては、
相互再帰呼び出しの形自体を止めて一つの関数にまとめた方が効率が良い、
としか言いようがない
そもそも、ここはアルゴリズム大辞典のスレなんだから、
何を実現したくてこのアルゴリズムを選択したのか言わないと議論にならん
（何を入力して何を得るのか）
これなら、ここじゃなくてExcelVBAの住人が答えるべきだと思うが
- 918 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:09:42.38 ]
- www.cc.kyoto-su.ac.jp/~yamada/ap/array_rep2sol.html
このサイトの後半で紹介されている
最大公約数を使って配列を回転させるアルゴリズム
何か名称がついていたら教えてください。
- 919 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:38:54.10 ]
- >>918
もしかして、
p2.2ch.net/p2/read.php?host=hibari.2ch.net&bbs=tech&key=1086272325&rc=918#r917
ここの METHOD 3 と同じかな
>>918 のページの方は配列の要素が遷移する様子が解説されていないから、
処理を追うのが面倒でざっとしか見てないが
「珠玉のプログラミング」という本にも
METHOD 3 と同じ [お手玉の方法] として紹介されているらしいね
- 920 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:42:11.71 ]
- 開発者の
ecommons.cornell.edu/handle/1813/6292
の中では Dolphin algorithm って書いてあるけど、
そんな名前で呼ばれてもだれもわからんだろうな
|
 |
