計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 52 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:20:12 ] 円だから未知数は３つだろう　中心と半径 53 名前：デフォルトの名無しさん [2005/10/16(日) 20:33:32 ] >>7 外積のほうが説明楽だろ、θ=tan＾-1(|a x b|/|a ・ b|) 54 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:34:10 ] ごめんなさい r, x, y, z とか数えてました……． 55 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:34:50 ] 数値解も案外厄介だな　 56 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:35:51 ] >>53 元ネタは2次元だから外積持ち出すのは・・・・ 57 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 16:22:40 ] ていうか、3つの円の大きさとか位置関係とかどうなっているの？ 58 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 18:14:48 ] そりゃ色々あるんだろう。　だから厄介みたいだね。 59 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 20:20:52 ] 最悪ケースとして同心円×3 みたいな場合もあるから何も考えずに連立方程式を解くのは危ないかも 60 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 20:39:42 ] 点の包含球だったらドロニー図書くのと似た技法使うんだっけか。 もう覚えてないや 61 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 22:11:56 ] >>60 凸包だね。ドロネー図を求める手法なのは確かだが、凸包の方がはるかに 有名だと思うんだけど。 62 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 22:31:30 ] ベジェでかかれた複合パスを分割するアルゴリズムへのポインタを 教えてください。 63 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 23:33:21 ] >>56 複素数の導入をはじめとして 次元をひとつ上げると関係が急にシンプルになるケースは非常に多いので その突っ込み方はおかしいと思うす 64 名前：デフォルトの名無しさん [2005/10/18(火) 02:06:23 ] >>56 情報科学では、２次元の外積を定義することがありますよ 65 名前：デフォルトの名無しさん [2005/10/18(火) 12:16:54 ] すみません、質問ですが、まず翻訳から。(残り時間12時間…) a. Write a pseudo code for a divide-and-conquer algorithm for the exponentiation problem of computing a^n where a>0 and n is a positive integer. 累乗の問題a^n (aは0よりも大きくnは正の整数)を計算するdivide-and-conquerアルゴリズムの擬似コードを書きなさい。 b. Set up and solve (for n=2^k) a recurrence ralation for the number of multiplications made by algorithm. そのアルゴリズムによって作られた(発生した)掛け算の数のための回帰関係(n=2^k)を設定して解きなさい。 c. How does this algorithm compare with the brute-force algorithm for this problem. このアルゴリズムはこの(同じ)問題のためのブルートフォースアルゴリズムとどう比較しますか？ (比較するとどうですか、ということだと思いますが) a.でもう躓いてます。手のつけようがありません。 divide-and-conquerなんてmergesortとquicksortくらいなら知ってますが、 a^nなんて普通に計算すればいいんじゃないかと…いや、数が大きいと駄目なのかな？ どうか擬似コード教えてください。お願いします。m(__)m 66 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 12:20:44 ] 宿題スレ行きなよ。 67 名前：65 mailto:sage [2005/10/18(火) 12:23:16 ] 質問する前に「divide and conquer "a^n"」でググって "a^n"の部分がうまく引っ掛からずに質問したんですが キーワードをexponentiationにしたら擬似コード見つかりました。あらら。 例えばここ: ttp://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Outlines/outline.22.html#simplerecursiveexponentiation 失礼しました。 でも(b)(c)で分からなかったらまたここに来ますね。 (ということで多分戻ってくることになると思います…) 68 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 14:14:12 ] ていうか、とりあえず代数的に解いて、 出た解を吟味するのがアルゴリズム的には簡単。 69 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 14:17:01 ] 残り時間12時間って、提出期限は夜中？ 真夜中の専門学校？？？ 70 名前：65 mailto:sage [2005/10/18(火) 14:38:38 ] >>68 ありがとうございます。 a.は擬似コード見つけました。 FastPower(a; n): if n = 1 return a else x FastPower(a; bn=2c) if n is even return x * x else return x * x * a The total number of multiplications is given by the recurrence T(n) <= T(L n/2 」) + 2, with the base case T(1) = 0. After a domain transformation, the Master Theorem gives us the solution T(n) = O(log n). Incidentally, this algorithm is asymptotically optimal|any algorithm for computing an must perform (log n) multiplications. b.はT(n) <= T(L n/2 」) + 2, T(1) = 0で設定して最終的にO(log n)になるのは分かるのですが どうやってそれを導きだせばいいのでしょうか？ 自分でやると… T(1) = 0 T(2) = T(L 2/2 」) + 2 = T(1) + 2 = 0 + 2 = 2 (!?) 2^4で掛け算の数が2になるはずですが…(2^2)^2)ですから…あれあれ？ ということで、どうか助けてください。お願いします。m(__)m 71 名前：65 mailto:sage [2005/10/18(火) 14:40:59 ] >>69 海外なものですから。 もう図書館が閉まるので8時間後くらいにまた来ます。 それまでも自分で考えてみますが、よろしくお願いします。 72 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 15:25:55 ] >>70 n is oddのときのは+2、n is evenのときは+1。だからT(N) = T(L n/2 」) + 2 じゃなくてT(n) <= T(L n/2 」) + 2になってるだろ。問(b)の定義でn=2^kに なっているのでT(n) = T(n/2) + 1になる。 73 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 15:45:09 ] >>69 うちの大学は情報系の課題は"日付が変わるまで"の先生が多かったけど。 74 名前：65 mailto:sage [2005/10/18(火) 23:38:06 ] >>72 >>72さんの説明を読んでようやく理解し、今問題を終えました。 "<="になっていたのには気付きませんでした。(^^ゞ b. T(n) = T(n/2)+1 =(T(n/4)+1)+1 =T(n/4)+2 =(T(n/8)+1)+2 =T(n/8)+3 　　　　: =T(n/2^k)+k =1 + log2 (n) ≒O(log n) c.は brute forceでは 2^8=2*2*2*2*2*2*2*2=8つの掛け算≒O(n) それに対してdivide and conquerでは 2^8=(2^4)^2=((2^2)^2)^2=3つの掛け算≒O(log n) O(n) >> O(log n) ですね。 間に合いました。これから授業です。ありがとうございました！ 75 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 10:13:17 ] ３点を通る円すら計算できない俺は終ったな。嗚呼 76 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 11:58:19 ] 3点を通る円なら ttp://www.tensyo.com/urame/prog/linealgo.htm G=( y2*x1-y1*x2 +y3*x2-y2*x3 +y1*x3-y3*x1 ) Xc= (x12+y12)*(y2-y3)+(x22+y22)*(y3-y1)+(x32+y32)*(y1-y2)/(2*G) Yc=-(x12+y12)*(x2-x3)+(x22+y22)*(x3-x1)+(x32+y32)*(x1-x2)/(2*G) にあった。　数値計算なら、３つの円周上の点から半径が最大になる点を求めれば良さそうだが・・・・ 77 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 23:19:46 ] 弦の垂直二等分線の交点だろ 78 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 23:22:46 ] 幾何の話になるとどうしても図が欲しくなるな 79 名前：62 mailto:sage [2005/10/20(木) 00:34:12 ] 一般的にはないんでしょうか？企業機密？ 80 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 01:59:03 ] ちいとは手前で考えろよ。 81 名前：デフォルトの名無しさん [2005/10/20(木) 17:26:42 ] ２点定義されてる直線のある距離の点から垂線を引きたいんですが、 簡単に引く方法はありますか？ 82 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 17:45:14 ] プログラミングの前に数学勉強しろよ 83 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 17:47:37 ] >>81 方向ベクトル求めれば直交する方向ベクトルが自明に定まるのでそれを使う 84 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 22:01:41 ] >>81 >>76のページに　２点の中点を通りそれに直行する直線　というのがある また、 ＞　3)点(X1,Y1)に一番近い点 {c(cX1-sY1)-s*d,-s(cX1-sY1)-c*d} を使えば、その点と結べば垂線だ 85 名前：デフォルトの名無しさん [2005/10/20(木) 23:56:47 ] >>81 3角定規をあてる。 86 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 01:16:51 ] 寧ろコンパスかと。 87 名前：デフォルトの名無しさん [2005/10/21(金) 10:33:10 ] >>85 代数学では、３角定規は平行線を描く以外に使っちゃダメだろ習わなかったか？ そもそもアレは９０ﾟなのか？ 88 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 10:36:15 ] >>87 ﾊｧ? 代数学? 89 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 11:20:04 ] >>62　だと、何を聞きたいのか判らん。 >>79 90 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 15:26:24 ] 三点((x1,y1), (x2, y2), (x3,y3))を通る円の方程式が欲しい場合は、 4行4列の行列 (x**2+y**2,x,y,1) (x1**2+y2**2,x2,y2,1) (x2**2+y2**2,x2,y2,1) (x3**2+y3**2,x3,y3,1) の行列式 = 0 と置けば出るよな。 91 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 10:35:15 ] >>90 証明のヒントを下さい。 92 名前：90 mailto:sage [2005/10/23(日) 13:24:43 ] (x0**2+y0**2,x0,y0,1) (1) (x1**2+y2**2,x1,y1,1) (a) (x2**2+y2**2,x2,y2,1) (b) = 0 (x3**2+y3**2,x3,y3,1) (c) っていう連立方程式が a, b, c について解けるなら x^2 + y^2 + ax + by + c = 0 が求める円の方程式になるよね。 解が存在するためには rank が 3 以下じゃなくちゃいけないので 行列式 = 0 が出てくるという寸法。 三点が同一直線上にないっていうことも別途確認する必要もあるね。 93 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 15:32:04 ] >>92 ありがとうございました。 94 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 18:48:38 ] ゼロと比較する時は要注意だ。 95 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 19:07:39 ] >>90 複素平面上だと Im((z1-z3)/(z2-z3)*(z2-z4)/(z1-z4))=0 96 名前：デフォルトの名無しさん [2005/10/25(火) 22:00:04 ] アルゴリズムC・新版―基礎・データ構造・整列・探索 R. セジウィック (著), Robert Sedgewick (原著), 野下 浩平 (翻訳), 佐藤 創 (翻訳), 星 守 (翻訳), 田口 東 (翻訳) この本って買い？ 内容とか翻訳の質とか教えてください。 97 名前：デフォルトの名無しさん [2005/10/25(火) 23:15:47 ] 買いです。 Cのコーディングスタイルは疑問なんで、丸写ししたい人向けじゃないです。 98 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 00:05:01 ] 新版はコードましになってると聞いたけど不明。 99 名前：デフォルトの名無しさん [2005/10/26(水) 16:52:05 ] 平面座標に座標配列で定義された閉じたポリゴンがあるとして、 そこにある座標がポリゴン内か外か、どういうアルゴリズムになりますか？ 100 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 17:05:56 ] なんで >>76 のリンク先に丁度ある話題ばかりでるのだろう？ どっかの学校があそこみて課題出してる？ 101 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 22:30:36 ] 幾何と代数は複素数によって等価であることが結びつけられた。 102 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 22:53:40 ] >>101 何言ってる不明 103 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 22:55:46 ] >>101 工エｴェｪ(´д｀)ｪェｴエ工 104 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 22:58:41 ] >>101 ちなみに聞くけど複素数が何か知っていってるの？ 105 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 23:04:04 ] i = √(-1) とか言うなよ？ 言ったら笑っちゃうよ？ 106 名前：デフォルトの名無しさん [2005/10/26(水) 23:21:58 ] >>101 えっと、幾何と代数の意味はわかってるよね？ 107 名前：デフォルトの名無しさん mailto:sage [2005/10/27(木) 02:21:08 ] >99 点ABCから成る三角形の内側に、点Pが存在しているか？ いくつか方法あるけど、 内積から以下の角度を求めて、成立していれば内側 ( ∠ABC > ∠ABP ) && ( ∠BCA > ∠BCP ) あとは外積から法線の向きで判別する方法とかもある。 108 名前：デフォルトの名無しさん mailto:sage [2005/10/27(木) 06:23:44 ] 　点 q を指定し 点p配列で指定した多角形の内側かどうか？ 　の次は、　　ttp://www.tensyo.com/urame/prog/linealgo.htm 　・　線分の上にあるか？ 　・　線分が交わるか？ 　・　線分と点の距離 　・　円を水平線で塗り潰す 　・　最小２乗法による直線推定 　・　最小２乗法による円弧推定 　・　面積/重心 　・　スプライン 109 名前：デフォルトの名無しさん mailto:sage [2005/10/27(木) 09:30:20 ] ｦｫ, ｻﾝｸｽ >>107 >>108 結構ムズいんですね。 110 名前：デフォルトの名無しさん mailto:sage [2005/10/27(木) 12:27:06 ] >>109 コードは20行にもならないだろう 111 名前：ハーピィ mailto:sage [2005/10/28(金) 14:05:04 ] E・∇・ﾖﾉｼ　＜111ｹﾞｯﾄ♫ 112 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 16:26:06 ] あるn次元ベクトルxとある対称行列A(nxn)の二次形式 x'Ax を O(n)で計算できる夢のようなアルゴリズムはありますか？ 113 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 17:17:52 ] ありますよ。 でもここでは余白が狭すぎて書けません。ごめんなさい。 114 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 17:33:49 ] >>112 存在しない． x = (x_1, ..., x_n) としたとき，Σ_{i,j} (x_i x_j) という二次形式がありうるが， これは項数が n^2 なので，それより小さなオーダーにはできない． 115 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 17:53:58 ] ご返答ありがとうございます。 では一歩譲ってn^2オーダーだとしても、その中でなんとか 効率よく計算量を減らす方法などはありますでしょうか？ Aが対称行列なので、行列の半分だけを使って2倍しながら計算、 それにxi*a_iiの二乗和を加えるという方法で、なんとか半分程度に 減らすことはできたのですが、もはや削減もここまででしょうか？ 116 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 18:48:19 ] FFTみたいのが使えたらいいのにね・・・・って事？ 117 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 00:53:28 ] てゆうか、最低限やらなあかん計算量ってのがある罠。 それ以下にはできんでしょ。 118 名前：112 mailto:sage [2005/11/03(木) 01:46:51 ] >>116 FFTのアルゴリズムを理解してないんでなんとも言えませんが、 nが2の累乗みたいな特定の条件下のみで最適化可能というものでも もしあればありがたいと思いましたが。。 >>117 ごもっともです。 必要なデータを読み出さずに計算なんて神の所業ですよね。 自分の書いたＣ言語のプログラムが、二次形式を計算する箇所の for文二重ループたったひとつのせいでむやみやたらと遅くなったもので。。 だいたいnが数百〜数千くらいなんで当たり前っちゃ当たり前なんですが。 二次形式をn*100回以上繰り返し計算するわけですが、今回の場合、 Aはいつも定数で、xは要素のどれか一つだけが更新されているという 条件があって、もう少し計算が省けそうなのでがんばってみます。 119 名前：112 mailto:sage [2005/11/03(木) 01:51:08 ] 間違いました。訂正です。 > xは要素のどれか一つだけが更新されているという条件 どれかひとつじゃなくてxの要素はまるごとそっくり 入れ替わっている必要がありました。失礼。 120 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 06:53:34 ] そもそも計算しないで済ませる 121 名前：120 mailto:sage [2005/11/03(木) 07:16:43 ] 途中で書き込んじゃった．で，どんな問題解いてるの？ 行列処理だったら本質的に O(N^2) は避けられないので，それが許せないなら問題に合わせた解法を用意するしかない． 例えば A が問題設定の時点でわかってるならそれを対角化するような座標を選んで O(N) の反復に落とすとか． 122 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 08:08:58 ] >112 １．SIMD命令で最適化する ２．ループを展開する 123 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 10:23:41 ] >>122 >>122 >>122 >>122 >>122 >>122 >>122 >>122 124 名前：デフォルトの名無しさん [2005/11/03(木) 15:59:19 ] 数学板で質問させていただいたのですが、ム板で伺ったらよいアドバイスが聞けるのではとの誘導を受けたので質問させていただきます。 直方体の空間をm*n*n個の直方体にさいの目状に分割したとします。で一個一個の直方体をセルとします。 例えば一つのセルの大きさを1とすると、 セル（i ,j ,k）は八つの点（i, j, k),(i+1, j, k),(i, j+1, k), (i, j+1, k), (i, j, k+1),, (i, j+1, k+1), (i+1, j, k+1), (i+1, j+1, k+1) を頂点とする直方体です。(i, j, k = 0, 1, 2, 3...) この空間内に単位方向ベクトルA(u, v, w)と通る点P(p, q, r)で表される直線を与えたとします。 すると直線は媒介変数表示でP + t*Aとかけると思います。 この直線がどのセルを通過するのか、 またはあるセル(i,　j,　k)とこの直線が交わるか判別するには どのように考えたら宜しいでしょうか？ 実際には、光線が通過するセルとの2つの交点を求めて、そのセル内での光線の通過距離を計算しようとしています。 125 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 16:26:47 ] 数学板で聞いたとの事ですが 最終的に作りたいのはプログラムコードなわけですか？ 126 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 16:42:16 ] そうです。今のとこ考えてるのはセルの6つの面全部で切っちゃう方法 ・x = iの時j < x < j+1かつk < z < k+1かどうか ・x = i　+　1の時j < x < j+1かつk < z < k+1かどうか といった具合にy = j, y =j+1, z = k, z = k + 1についても調べる。 で通る2点を計算、といった力技なのですが、もう少し手順を減らせそうな気がして･･･ 127 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 16:53:50 ] 俺は>>126に書いてあることが理解できていないんだが まず隣接する直方体をまとめて大きい直方体を作ってその直方体と 光線が交わるならその直方体の中の小さい直方体を調べる、という やりかたで計算量を減らせると思うよ（八分木、oct tree）。 128 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:02:22 ] DDAのように始点から追っていったらどう？ 全体の直方体との交点のうち一方を始点に使って。 通過するセルの数は m + n + n よりも小さいし。 129 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:13:24 ] 問題が分からん 1) あるセル(i,　j,　k)と直線が交わるか判別する 判別して通ると分かった場合に 2) その通るセルと直線との交点（２つ）を求めて、 　　そのセル内での光線の通過距離を計算する ということ？ 130 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:31:15 ] ええ。最終的に光線の通るセルが分かる→そのそれぞれのセル内での通過距離が分かる様な感じです。 A)全てのセル（m*n*n個)について光線と交わるか判別する→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算 B）直線の式から通過するセルが分かる夢のような方法→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算 のどちらかでしょうか。実はプログラミング自体限りなく初心者なので オクトリー・DDAなどのアドバイスしていただいたアルゴリズムについて勉強してみようと思います。 131 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:57:31 ] 2次元の正方格子で考えてみると、 光線を原点から方向ベクトル(1,√2)とすると、 最初の交点の候補は、x=1とy=1になる点(1/√2,1)と(1,√2)だが、 xの小さい(1/√2,1)が最初の交点。 その次の候補点はx=2かy=1のときで(√2,2)か(1,√2) だが、xの小さいほうをとって(1,√2) みたいにするとよいのでは。 距離と通ったセルは簡単にわかるだろ。 三次元だと3つから選ぶだけ。 132 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 18:16:16 ] >>131に賛成。あるセルが通るかどうかを全部のセルについてやるより x,y,zにだらーって整数を入れてって交点を求めてから、その交点がどのセルに属すかやったほうがよさげ。 133 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 18:19:11 ] 該当する格子の周囲(距離一)を探索すれば十分？ 134 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 21:14:54 ] >>124 "ray march"のようなことがやりたいのかな？ 135 名前：124 mailto:sage [2005/11/03(木) 23:48:11 ] 沢山のアドバイス有難うございました。色々自分なりに調べてみたところ、>>128さんの仰ってくださったDDAや>>131さんの方法に似た方法で CGの分野では直線描画の基本らしい「ブレゼンハムのアルゴリズム」というものがヒントになりそうです。 農学系の研究にCGの手法が役立つとは・・・本当に有難うございました。 136 名前：デフォルトの名無しさん mailto:sage [2005/11/04(金) 13:11:07 ] >>135 農学って、単位空間あたりの光量の計算とかでもするのかな？ ＣＧでボクセル描画するのだとばっかりおもてたyo 137 名前：フローチャート [2005/11/08(火) 17:16:52 ] 自然数ｍ、ｎに対して、ｍのn乗を計算する効率のよいアルゴリズムを フローチャートで書け。 138 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 17:22:24 ] >>137 フローチャートは勝手に書いてくれ pow m n   | n == 0         = 1   | n `mod` 2 == 1 = m * pow m (n-1)   | otherwise      = t * t where t = pow m (n `div` 2) 139 名前：デフォルトの名無しさん [2005/11/08(火) 17:32:16 ] 日本ＮＯ１プレミアムＭＭＯ CreateGame〜陸海空オンライン〜 ただ今、鋭意開発中！力ある奴だけこい！ 140 名前：フローチャート mailto:fh [2005/11/08(火) 19:32:26 ] >>138 フローチャートを書け、という課題なので、フローチャートを書いてください 141 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 19:46:42 ] >>140 そのぐらいは自分でやりなさい。そもそも掲示板にどうやって フローチャートを描けと。 142 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:29:36 ] こんなもんかな。 ○pow(m, n) │ │n==0 ◇─┐ │　 ○return 1 │ │n%2==1 ◇─┐ │　 ○return m * pow(m, n - 1) │ □t = pow(m, n / 2) │ ○return t * t 143 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:55:31 ] >>142 もっと効率よくできるはずです。やり直しなさい。 144 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:56:13 ] >>142 あと、そのアルゴリズムにはバグが潜んでいます。なおしなさい。 145 名前：デフォルトの名無しさん [2005/11/11(金) 00:09:51 ] 晒しage 146 名前：デフォルトの名無しさん mailto:sage [2005/11/11(金) 01:23:17 ] >>137 ○pow(m, n) │ □　ret　←　1 │ △　ループ(　i=0 ; i<m ; i++) │ □　ret ← ret*n; │ ▽ │ ○　戻り値 ← ret 147 名前：デフォルトの名無しさん mailto:sage [2005/11/12(土) 04:00:38 ] 巡回セールスマン問題をブルートフォースで解くソースコードってないですか？ 擬似コードでもいいです。 148 名前：デフォルトの名無しさん mailto:sage [2005/11/12(土) 07:15:53 ] >>147 枝刈りも何もなしでいいなら15分くらいで書けるでしょ 149 名前：147 mailto:sage [2005/11/13(日) 11:03:59 ] >>148 その枝刈りも何もなしでいい15分くらいで書ける奴をお願いします。m(__)m 150 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 11:38:37 ] >>149 その代わり解くのには数年間〜数十年間(ry 151 名前：147 mailto:sage [2005/11/13(日) 12:02:13 ] >>150 ドサ回りする都市の数は5くらいまででいいです。 152 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 17:16:00 ] >>151 入力データの仕様をください

---

---

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

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