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

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 552 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:22:57 ] >三角関数はマクローリン展開して計算しますよね。 ここで間違ってる 関数近似の教科書読むべし 553 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:30:11 ] >>552 すみません、悠長に教科書読んでる暇がないので結論をお願いします 554 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:36:55 ] CPUのアーキテクチャ等やライブラリ作った奴の腕に依存して色々な可能性がある ただ，どれもθを0〜π/2の範囲に正規化してるだろうから その範囲なら少し速いはず これ以上は本嫁 555 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 01:07:36 ] ぶっちゃけ、今時の単精度演算アクセラレータはテーブル参照プラスリニア補間で済ませている希ガス。 556 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 07:24:15 ] >>554 絶対的な速度が問題なのではなく、速度のむらを気にしているのです。 たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか？ということです >>555 ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。 ターゲットはSH7145 ルネサスのコンパイラを使ってます。 ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので VCやgccだったらどうなのかという意見でもいいのでお願いします。 557 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 09:28:07 ] 後出し多いな 558 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 10:04:11 ] 5倍の差はないだろうけど，1〜2割位なら充分あり得る 実測するのが手っ取り早いかと 559 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 17:45:37 ] >>556 マイコンの方がむしろテーブル変換使用すると思うが 560 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 17:47:40 ] >>554 いっそπ/8に正規化するとか 561 名前：デフォルトの名無しさん mailto:sage [2007/09/09(日) 14:05:26 ] >>553 ＞悠長に教科書読んでる暇がないので そうか。残念だったな。 562 名前：デフォルトの名無しさん [2007/09/12(水) 02:03:16 ] 差異のアルゴリズムでレーベンシュタイン距離を求めていますが、 結局これ求めてどうなるんですか？ 馬鹿でも分かるようにく教えてください。 563 名前：デフォルトの名無しさん mailto:sage [2007/09/12(水) 08:42:09 ] >>562 そんな限られた分野でしか使わないようなものを さも誰もが知ってるかのように聞かなくても。 自然言語処理とかで使う。 Google 先生とかがよくやってる もしかして: ○○ を出したりとかに使える。 564 名前：デフォルトの名無しさん mailto:sage [2007/09/13(木) 00:02:29 ] >563 レスどうも。 2つの文字列を比較して"n文字違います"とかは想像できるんだけど、 diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、 565 名前：デフォルトの名無しさん mailto:sage [2007/09/13(木) 00:05:36 ] >>564 ja.wikipedia.org/wiki/Diff 566 名前：デフォルトの名無しさん mailto:sage [2007/09/15(土) 23:51:51 ] 今、ロバスト解について勉強しています。 ロバスト解発見手法にはシックスシグマ法のDesign For Six Sigma[Brue 03]やDesign For Multi-Objective Six Sigma[Shimoyama 06]、またはガウスノイズがあるということが分かりました。 しかし、上に述べた手法の利点・欠点がほとんど分かりません。 どなたか他の手法と比べた場合の利点・欠点を教えてはいただけないでしょうか? 下に今分かっていることを書きます。 ---------------------------------------------------------------------- Design For Six Sigma[Brue 03] ロバスト解を1つ発見する場合に有効。 Design For Multi-Objective Six Sigma[Shimoyama 06] Design For Six Sigma[Brue 03]を拡張したもの。複数のロバスト解を同時に発見する場合に有効。 ガウスノイズ アルゴリズムは簡単。 ガウスノイズは上に述べたシックスシグマ法を使ったときよりもすばやく収束できる。 吸収現象などのせいでロバスト解からずれた位置に収束するかもしれない。 567 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 03:20:29 ] 質問させてください． y=Ax （x,y:ベクトル， A:マトリックス，大きさ数百〜数万） に対し， x = inv(A) * y を解く問題を考えています． ここで，逆行列演算inv(A)がO(N^3)のコストが掛かり，ネックになっています． いま，Aは疎な帯行列（しかも対称）という条件があるので， 大幅な計算削減ができるのではないか？と考えております． 例えば，計算コストをO(N^2)にするといったことは可能でしょうか？ キーワードだけでも良いので，知恵を貸していただけると幸いです． 568 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 03:49:22 ] つ[特異値分解] 569 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 07:22:57 ] >>567 LU使っているのか？ 対称行列だと、LDL分解でOK 帯行列だとさらに、0要素を見ないことで、さらにスピードアップ 570 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 17:36:11 ] そんな話，数値計算の本見ればいくらでも載ってるだろ 571 名前：567 mailto:sage [2007/09/20(木) 01:53:07 ] >>568 キーワードありがとうございます！ 調べてみます． >>569 LU分解→直接法で逆行列としていました． LDL分解というものがあるのですね． 解法は反復法に持って行くのですかね・・・調べてみようと思います． 反復法は精度の面が少し気になりますが，勉強含めて試してみます． 多謝！ >>570 数値計算の門外漢なもので・・・勉強してきます． 572 名前：デフォルトの名無しさん mailto:sage [2007/09/24(月) 22:11:26 ] kd木で、近い領域を何度も連続して調べたい時、毎回根から辿らないようにショートカットするような技法ってありますか？ 573 名前：デフォルトの名無しさん mailto:sage [2007/09/28(金) 09:44:52 ] 二つの整列済みリストのマージで 要素数が一方がk個,もう一方が2個の場合, n回の比較でマージできる最大のkをanとすると a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号 で与えられるらしいのですが これがどういうアルゴリズムでマージしたときの物なのか, またこれが最良値なのか知りたいのですが, 誰か知りません? 574 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 14:28:02 ] >>573 a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号 この式を見るとnが1増えると√2倍でa[n]は指数的な増加。 ソート済みk個と2個のマージは 2分探索を2回使えば2logk回。 詳しくは見てないが、2logkの係数の2が√2になりそうだし、 kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。 575 名前：573 [2007/09/30(日) 13:03:48 ] >>574 考えてくれてありがとう. 2分探索だけだと最良値にはならないみたい. 573の式だと最初の10個位までは最良値になってるのは 確認できた(虱潰しで) さらに知らべて,もう一方のリストが3個の場合みっけた. Optimal Merging of 3 Elements with n Elements っていう論文のAbstructで f3(1)=0, f3(2)=1, f3(3)=1, f3(4)=2, f3(5)=3, f3(6)=4, f3(7)=6, f3(8)=8 r >= 3 f3(3r) = [(43/7)*2**(r-2)]-2 f3(3r+1) = [(107/7)*2**(r-3)]-2 f3(3r+2) = [17*(2**(r-3)-6)/7]-1 との事. 576 名前：デフォルトの名無しさん mailto:sage [2007/10/30(火) 01:16:41 ] 各データの値がかなり近い時に ハッシュのみだとデータの衝突回数 多い場合ってどうやってみんななら解決する？ あとね、kd木で何の本に詳しく載ってますか？ 577 名前：デフォルトの名無しさん mailto:sage [2007/10/30(火) 01:55:31 ] 値近くてハッシュが衝突するって、どんなアルゴリズムだよ 578 名前：デフォルトの名無しさん mailto:sage [2007/10/31(水) 02:27:51 ] 8byteの16進データを 完全ハッシュ化するソースコード置いてある とこないですか？ 579 名前：デフォルトの名無しさん mailto:sage [2007/10/31(水) 21:09:37 ] 区分サンプリング法やラテン超方格法のアルゴリズムを教えてください。 580 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 05:05:51 ] 二点で定義されてる直線上に、ある点があるかどうかを判定するにはどうすればいいですか、教えてください。 581 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 06:17:51 ] 要は３点が一直線に並んでいるかを知りたい、と解釈し直してみた。 １点を基準に他２点へ直線を引くときの傾きが一緒だったらOK。 x軸と垂直だった場合なんかも考慮すると、 (x1-x0)*(y2-y0)==(x2-x0)*(y1-y0) 582 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 13:05:52 ] あ、なるほど、ありがとうございます 583 名前：デフォルトの名無しさん mailto:sage [2007/12/07(金) 21:54:02 ] [N][N]の2次元配列を３つ [N]の配列を2つ使ってる場合の使用領域のオーダーってＯ(n^2)におさまります？ 584 名前：デフォルトの名無しさん mailto:sage [2007/12/07(金) 22:02:42 ] うん 585 名前：デフォルトの名無しさん mailto:sage [2007/12/09(日) 21:31:14 ] 3N^2+2N = O(N^2) が分かってないのか？ 586 名前：デフォルトの名無しさん [2007/12/14(金) 13:42:55 ] グレブナ基底を求めるプログラム、誰か持っていませんか？ C言語でおねがいしたいです。 587 名前：デフォルトの名無しさん mailto:sage [2007/12/15(土) 02:12:22 ] >>586 23457円になります。 588 名前：デフォルトの名無しさん [2007/12/29(土) 03:46:49 ] 均一なセル上に分割した空間で、円（または球）を配置して、円と交差する セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう？ 589 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 06:33:27 ] セルってのはよくわからないのだが、格子なの？ 格子が座標と平行になるように回転変換して　格子間隔が1になるように伸縮して 円の中心座標の小数点以下座標を見ればいいだけでは？ 590 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 07:51:56 ] あ、格子です。あ、最初から座標軸並行を仮定してます。 さらに辺の長さを1で仮定してしまいましょか。 えーと意味がいまいちつかめないんですが、 ＞格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮 これは元々が単位格子であるなら何もしないでOK? ＞円の中心座標の小数点以下座標 これで、なぜ全ての格子が求まるかがわかりません。 整数部をみれば、中心を含む格子は求まると思いますが。 591 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 13:33:11 ] 欲しいのは「円周」と交わるセルだろ？ そこがちゃんと書いてないから勘違いされたと思われ 592 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 17:06:31 ] あ、そうです。申し訳ない。 593 名前：デフォルトの名無しさん mailto:sage [2007/12/30(日) 12:13:13 ] DDA(digital diffrential analyzer)というのがあるが使えないかな？ ３次元は分からんが 594 名前：デフォルトの名無しさん mailto:sage [2007/12/30(日) 12:39:28 ] 3次元も、半径が違う円で切り出したものと考えればイケルんじゃないの？ 595 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 01:56:42 ] ある年月日が与えられ、そのn日後の日付を求めたいのですが、 1,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める 2,days+nを西暦年月日に変換する という方法を考えました。 2は1の式を変形して解けるだろうと見当を付けていましたが、 小数点以下を切り捨てたりしているためうまく式を求められません。 素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか？ 日付は最近のものに限定して考えています。 ユリウス暦とグレゴリオ暦の判断が面倒になるので… 596 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 08:25:44 ] >>595 日付を1日進めるプログラムは書けるかい？ おｋ。ならば、1日進める部分をn回実行するんだ。 597 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 08:49:10 ] つーか、なんで既存ライブラリを使わないのだろう。 大抵の言語に日付け処理系の関数があると言うのに。 598 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 11:47:35 ] >>595 ttp://ufcpp.net/study/algorithm/o_days.html 599 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:25:41 ] >>595 ちょっと検索してみたらこんなのがあった delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい ttp://kwikwi.cocolog-nifty.com/blog/2005/12/delphi_266f.html ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの？ 日本のサイトしか引っかからないんだよね 600 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:29:16 ] >>596 なるほど。 ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので 上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと･･･ >>597 Cなのでそういった関数はもちろんあるのですが、若干不便なので 勉強も兼ねて自前で実装してみようというわけです。 601 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:51:11 ] >>598 おおお÷4を右シフト演算できるのは考えが及んでませんでした >>599 (mjd - 15078.2) / 365.25　　…?　もはや何がなんだか。 ttp://cl.is.kyushu-u.ac.jp/Literacy/PP/H14/adp/program/date.html こんなの見つけたので読んできます。 602 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 13:18:34 ] >>600 ttp://www.tensyo.com/urame/date/day_c.shm ここの int YMD_AddD(int *Y,char *M,char *D,long d）　って関数を見ると 負数を渡した場合は　400年循環を使って正に直せばいいみたい。 603 名前：デフォルトの名無しさん mailto:sage [2008/01/01(火) 10:28:35 ] つまり、-3日なら 400年前から(146097-3)日後と計算するわけか 604 名前：デフォルトの名無しさん [2008/01/02(水) 02:09:27 ] 除算のシフト演算化はコンパイラの最適化段階で 自動でやってくれるものだと思ってたんだが、そうでもない？ 605 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 08:29:27 ] コンパイラの性能がソレなりならって事でしょう。 固定値の除算ならさらに、掛け算で代用してくれるのも多いね。 606 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 10:22:11 ] >>604 2のべきの定数ならね。 607 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 12:18:44 ] という事で １、カレンダを1日進める関数関数を作る ２、+N日は１の関数をN回呼ぶ ３、-N日は、年数を400日戻してから、146097-N回 １の関数を呼ぶ 608 名前：595 mailto:sage [2008/01/02(水) 20:05:17 ] これでいいのかな？ struct Date{ 　int year,month,day; }; /* 1日進める */ void tomorrow(Date& x) { 　int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 　if((x.year%4==0 && x.year%100!=0) || x.year%400==0){ 　　days[2]++; 　} 　x.day++; 　if(x.day>days[x.month]){ 　　x.day=1; 　　x.month++; 　} 　if(x.month>12){ 　　x.month=1; 　　x.year++; 　} } 609 名前：595 mailto:sage [2008/01/02(水) 20:06:50 ] /* n日後の日付 */ Date after(Date x,int n) { 　for(int i=0;i<n;i++){ 　　tomorrow(x); 　} 　return x; } /* n日前の日付 */ Date before(Date x,int n) { 　n=146097-n; 　for(int i=0;i<n;i++){ 　　tomorrow(x); 　} 　x.year-=400; 　return x; } 610 名前：595 mailto:sage [2008/01/02(水) 20:39:23 ] 「1にちずつ遡りながら日付を表示」とかやるとbefore()の処理量が馬鹿にならないので、 >>601に載ってるのを参考に書き換えてみました /* 西暦1年1月0日からの経過日数から、日付を求める */ Date make_date(int n) { 　int y=(n+305)/146097*400 　　　　+(n+305)%146097/36524*100 　　　　+(n+305)%146097%36524/1461*4 　　　　+(n+305)%146097%36524%1461/365; 　int diff=n-(365*(y-1)+y/4-y/100+y/400+31+28);　// 3月0日からの経過日数 　if(diff==0){　　　　//2月29日 　　diff=366; 　　y--; 　} 　int m; 　for(m=3;;m++){ 　　//3月0日からm月0日までの経過日数, 30*(m-3)+3*(m+1)/5-2 の変形 　　if(153*(m+1)/5-122<diff && diff<=153*(m+2)/5-122){　 　　　break; 　　} 　} 　int d=diff-(153*(m+1)/5-122); 　if(m>12){ 　　m-=12; 　　y++; 　} 　Date x={y,m,d}; 　return x; } 611 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:16:56 ] 漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ 612 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:17:24 ] 誤爆です。 ごめんなさい 613 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 13:01:23 ] >>611 そのまんまの意味じゃなーの。 f(x)=sin xで1,-1は明らかに漸近的ではないが g(x)=1/x(x≥0)で0は漸近的。 614 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:18:07 ] 質問させてください。 「ハッカーのたのしみ」p137 で多倍長のかけ算のサンプルがあったのですが、 わからない部分があります。 void mulmns( unsigned short w[], unsigned short u[], unsigned short v[], int m, int n ) { unsigned int k, t, b; int i, j; for( i = 0; i < m; i++ ) { w[ i ] = 0; } for( j = 0; j < n; j++ ) { k = 0; for( i = 0; i < m; i++ ) { t = u[i] * v[j] + w[ i + j ] + k; w[ i + j ] = t; k = t >> 16; } w[ j + m ] = k; } } u と v がかける数、かけられる数、w に結果が入ることはわかるのですが、k は何に使われているんでしょうか？ 615 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:31:46 ] 繰り上がり 616 名前：614 mailto:sage [2008/02/09(土) 20:41:09 ] >>615 すばやい回答ありがとうございます。 くりあがりですね。 このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、 この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？ 617 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:44:43 ] >>616 そのとおり。 10進数で画面に表示する回数が、普通の計算を行う回数よりも 圧倒的に少ないと考えると、そういう数の表現になる。 618 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 16:13:21 ] w[ i + j ] = t; k = t >> 16; この部分を 　k = t/10; 　t -=k*10; w[ i + j ] = t; とすれば、１０進法になるんじゃない？ 8bitなら１００進数 16bitなら10000進数なんてのがオススメだよ 619 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 23:37:33 ] HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた 620 名前：デフォルトの名無しさん [2008/02/18(月) 17:15:48 ] 行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、 調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。 なぜ誤差が大きくなるのでしょうか？ 621 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:15:28 ] 誤差についてはほとんど知識がないので調べてみました。 たまたま今やっていることに関係あるので。 さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。 なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を しなければいけないこと。まぁ大体こんな感じです。 ではなぜ掃き出し法が誤差が大きいかというと、予測ですが 単純に計算量が他に比べて多いからではないでしょうか。 誤差を含む演算はやればやるほど誤差が大きくなるというわけです。 ちゃんとした理由ではないかもしれませんが、それよりも どうすれば誤差を小さくできるか考えた法がいいと思います。 まぁ原因が分からなくては始まりませんが。 622 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:42:00 ] >>621 そんなに詳しくないから適当に書くけど、 基本的にはその通り。 収束性が悪いほど誤差は積もりやすい。 あと、除算があると誤差大きくなる。 なので、掃き出し法みたいな手計算的手法のものよりも、 ガウスザイデル法みたいな反復計算の方が誤差少ない。 623 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 02:13:06 ] >>620 一概にそうとは言えない。というか、単純に比べることは不適当。 そもそも掃き出しは（解けるならば）必ず A x = b を解くが、 ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。 したがって、無条件で比較することはできない。 次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。 一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。 反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。 624 名前：デフォルトの名無しさん [2008/02/19(火) 13:21:15 ] >>623 掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか？ 新たな課題ですね(￣□￣;)!! 実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、 エクセルの分析ツールの回帰分析した結果、 後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。 後者はガウスザイデルなのかもしれません。 625 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 16:20:26 ] >>624 マクロでやってるなら、ピボットの選択してる？ 626 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 18:31:45 ] >>624 掃き出しで解けてガウスザイデルで解けない問題なんて いくらでもあるよ．たとえば 　x + 2 y = 1 　2 x + y = 1 をこの順番で連立方程式と考え，ガウスザイデルを 初期値 x = 0, y = 0 で適用すると，発散する． ガウスザイデルが収束する必要十分条件は，未解決のはず． 627 名前：デフォルトの名無しさん [2008/02/21(木) 22:41:32 ] >>625 ＞ マクロでやってるなら、ピボットの選択してる？ いえ、まず中心をすべて1にしてから掃き出しています。 これではダメでしょうか？ 628 名前：デフォルトの名無しさん mailto:sage [2008/02/22(金) 19:59:46 ] >>627 ダメ 629 名前：デフォルトの名無しさん [2008/04/03(木) 03:18:18 ] あげ 630 名前：デフォルトの名無しさん [2008/04/17(木) 12:46:54 ] ユークリッドのアルゴリズム(テキストp.10参照．java版はHP参照)を用いて 1,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、 引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック 1GHzに相当）を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。 「X年Xヶ月」など実感が分かる単位に直して答えよ。 この解き方がわかる人がいましたら是非教えて下さい。 解けなくて困っています。 631 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 13:30:05 ] >>630 宿題は自分で解決しようと努力しないと意味がないぞ どこまでは理解できていて、どこが分からないんだ？ 632 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:05:58 ] というか、奇妙な問題だな 10^N は N>=2 なら25で割り切れる。 つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら って場合か？　それでも実感がわかる単位にはならないわな 633 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:46:19 ] ・>>630が問題を間違えている ・出題者のちょっとした遊び心 どっちかじゃね？ 難しそうに見えて実は簡単な問題を出して 最初から課題をやる気がない奴を調べるためだったりしてｗ 634 名前：デフォルトの名無しさん [2008/04/21(月) 13:16:15 ] int型のデータをN個格納できる配列aを考える．つまり，配列要素は a[0], a[1], ..., a[N-1] でアクセスする．a[0]〜a[k]まではデータが既に格 納されており，a[k+1]〜a[N-1]までは「空き」の状態であるとする(0 <= k < N)． このとき，次に挙げる各操作に必要な手間(時間)を，「最も手間のかから ない場合」と「最も手間のかかる場合」のそれぞれの場合について答えよ． 理由も書くこと．(例を参考にせよ) 例：指定された位置にデータを挿入する操作 答:最も手間のかからない場合：定数時間 最も手間のかかる場合：kに比例する時間 理由：指定された位置が末尾の場合には，データをずらす必要がな いため定数時間で可能．指定された位置が先頭の場合には，既に格 納されているk+1個のデータを順にずらす必要があるため，kに比例 した時間が必要． 1-1 指定した位置のデータを削除する操作 1-2 指定したデータが格納されているか探索する操作 1-3 格納されているデータの中で最小の値を探索する操作 これを現在解こうと思っていますが、よく分かりません。 分かる人は是非教えて下さい、お願いします。 635 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 13:32:09 ] 1-1 最良：定数 最悪：k比例 1-2 最良：定数 最悪：k比例 1-3 最良：k比例 最悪：k比例 636 名前：デフォルトの名無しさん [2008/04/21(月) 15:08:07 ] 配列を用いてリストを実現することを考える．今，配列には以下のように データが格納されているとする．(配列keyと配列nextはint型のデータを格 納するとする) key[0] = 0 ,next[0] = 3 key[1] = 0 ,next[1] = 1 key[2] = 'S' ,next[2] = 6 key[3] = 'L' ,next[3] = 4 key[4] = 'A' ,next[4] = 5 key[5] = 'I' ,next[5] = 2 key[6] = 'T' ,next[6] = 1 位置0はhead, 位置1はzを表す． このとき，次の問に答えよ． (1)リストに格納されている文字を，リストの先頭から順に書け． (2) もしも next[0] の値が4だった場合，リストに格納されている文字を リストの先頭から順に書くとどうなるか述べよ． (3) リストから'A'を格納している節点(key[4]とnext[4]に対応)を削除し た場合，配列keyと配列nextの中身はどのように変化するか述べよ (key[4]とnext[4]の値はそれぞれ0に設定せよ) 637 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 16:28:55 ] ここは宿題すれじゃねーんだよ・・・ 638 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:03:43 ] 行列計算のガウスザイデル法が収束しないことがあるので気になっていたけど 検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。 (残差を最小にするから、たとえ解が無くても最適な値が求まる？収束に向かうのは確実？) ただ、ガウスザイデル法は数行のプログラムなのに対して 見つけたプログラムがかなりでかいサイズになっているのがまた気になる。 ガウスザイデル法で残差を小さくするような改良って無いのかな？誰か知ってる？ 639 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:40:08 ] これが、SOR法である。 ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。 従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。 www.akita-nct.ac.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html 640 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 18:02:14 ] ω=1.9から始めて発散なら値を引き下げていけばいいって事だな ω=1がもともとのやつ　 641 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:29:31 ] ガウスザイデル法には，原理的に収束しないインスタンスが存在するので 収束しないことが気になるような場合には，そもそも使ったらダメ． これはSORでも状況は変わらない． GMResやらBiCGやらIDRやら反復解法は色々あるんだから 解きたい問題にあわせて適切に解法を選ばないとダメよ． 642 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:57:39 ] 原理的に収束しないとは? 解が存在する行列でもできないってこと? 643 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 05:48:37 ] >>641 なるほど、どうもです。 プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。 644 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 09:27:07 ] >>642 そのとおり． ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて 解が存在しても，収束するとは限らない． いつ収束するかの厳密なところ（必要十分条件）は，現在でも未解決問題． 645 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 16:48:12 ] >>644 639のこれは? 。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。 646 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 17:10:06 ] >>644 SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている ωの値によって収束が左右される　0に近づければガウスザイデル法で無理な場合も収束するのでは? 647 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 20:15:14 ] ω=1はガウスザイデル法である 648 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:51:21 ] グレースケール変換。こいつより高速アルゴキボンヌ。 条件：徐々にグレースケール変換できればvolumeの持たせ方は自由 // 【メソッド名】convGrayScale // 【引数説明】 // srcRGB：変換元画像(0xRRGGBBのピクセル配列) // pixel_num：ピクセル数 // volume 0(無変換)〜255(完全変換)の範囲でグレースケールに変換 // dstRGB：変換先(0xRRGGBBのピクセル配列) 649 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:52:02 ] public void convGrayScale(int[] srcRGB, int pixel_num, int volume, int[] dstRGB){ 　　int red, green, blue, Y; 　　for(int i=0; i<pixel_num; i++){ 　　　　red = srcRGB[i] >> 16; 　　　　green = (srcRGB[i] & 0xFF00) >> 8; 　　　　blue = srcRGB[i] & 0xFF; 　　　　Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算 　　　　if(Y > red){　// R成分の調整 　　　　　　red += volume; 　　　　　　if(Y < red) red = Y; 　　　　}else if(Y < red){ 　　　　　　red -= volume; 　　　　　　if(Y > red) red = Y; 　　　　} 　　　　if(Y > green){　// G成分の調整 　　　　　　green += volume; 　　　　　　if(Y < green) green = Y; 　　　　}else if(Y < green){ 　　　　　　green -= volume; 　　　　　　if(Y > green) green = Y; 　　　　} 　　　　if(Y > blue){　// B成分の調整 　　　　　　blue += volume; 　　　　　　if(Y < blue) blue = Y; 　　　　}else if(Y < blue){ 　　　　　　blue -= volume; 　　　　　　if(Y > blue) blue = Y; 　　　　} 　　　　dstRGB[i] = (red << 16) + (green << 8) + blue;　// 変換結果 　　} } 650 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:54:17 ] あ、一応JavaだけどCとかでもおｋ 651 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 02:10:24 ] volumeって要は、グレイ化度合いみたいなものなのね。 処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。 652 名前：648 mailto:sage [2008/04/25(金) 03:08:47 ] volumeって要は、グレイ化度合い⇒そのとおり！ volumeを255まで振る前にグレイになってしまう ⇒それは思ったけど、取り得る範囲がわからんかった。。。 　r=0,g=0,b=255、r=255,g=255,b=0の場合で29.191890〜225.808365の範囲で196.616475がMAXかなぁ 振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。 ⇒ちょっとわからんkwsk 　ちなみに自分の使い方としては元画像srcRGBはずっと変えずにvolumeを増やす感じ 　だから一度変換したdstRGBをsrcRGBに使うことはない

---

---

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

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