計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

425:デフォルトの名無しさん
07/01/24 00:00:12
ひょっとして多倍長計算？
ニュートン法なら一回の反復で桁数２倍

426:426
07/01/24 15:42:39
URLﾘﾝｸ(www.apple.com)
このようなカラーピッカーを作りたいのだけれど、
中心からの位置によってどのようなRGBに変換されるかの式がわかりません。
どうやって計算しているのでしょう？

427:デフォルトの名無しさん
07/01/24 15:46:57
>>426
URLﾘﾝｸ(image-d.isp.jp)
Hが円角度 Sが円半径 Vが隣の垂直ﾊﾞｰ　じゃねーかな？

428:426
07/01/24 15:54:15
>>427
ありがとう、作ってみます

429:デフォルトの名無しさん
07/01/24 16:01:43
>>428
変な色マップになったら　同サイトの HLS変換も試してみてね

430:426
07/01/24 16:58:12
>>429
おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと
427さんに紹介してもらったページのFの式が間違っていた（正しくはF = H/60 - I）ので
ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。
ありがとうございました。

431:デフォルトの名無しさん
07/01/24 17:14:29
強欲アルゴリズムについて分かる人はいますか？

432:デフォルトの名無しさん
07/01/24 17:32:15
貪欲とかgreedyとかで検索したらどうだろう。

433:デフォルトの名無しさん
07/01/24 17:36:37
それがなくて…

434:デフォルトの名無しさん
07/01/24 19:08:19
俺はだいたいのところは分かっていると思うぜ

435:デフォルトの名無しさん
07/01/24 19:27:16
>>430 atan2使えばいいんじゃね？

436:デフォルトの名無しさん
07/01/26 06:11:36
長さが同じint配列が2個ある。
一つの配列内で重複する数は無い。
同じ数がそれぞれの配列で同じ位置にあるとは限らない。
で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。
こういう場合で配列をそれぞれソートして
先頭から最後まで一致するかを調べる以外に何かいい方法ある？

437:デフォルトの名無しさん
07/01/26 07:12:23
それは set equality problem という問題で，
O(n log n) が計算量下界であることが知られている．
よって，計算量的には 436 のソート比較は最適．

ハッシュとか確率的アルゴリズムとかで実用的な速度は
上がるかもしれんが，ソート比較が簡素で良いと思うよ．

438:デフォルトの名無しさん
07/01/26 09:06:29
>>437
なるほど。
ありがとう。

439:デフォルトの名無しさん
07/01/26 09:26:09
>438
データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能
データに対して有効なハッシュ関数があれば広くても同上

440:デフォルトの名無しさん
07/01/27 00:38:31
データの個数があんまり多くないからソート比較でも十分速くできた。
>>439
>>437でハッシュと聞いてピンと来た。
機会があれば今度その方法も試してみるよ。
ありがとう。

441:デフォルトの名無しさん
07/02/02 14:13:28
有無なら配列じゃなくてビットマップにしろや

442:デフォルトの名無しさん
07/02/04 11:48:52
>441
もしかして：ビットの［配列］

443:デフォルトの名無しさん
07/02/04 14:05:22
>>441
アルゴリズムと実装は区別しような
分からなかったらスレッド名も見てくれ

444:デフォルトの名無しさん
07/02/04 23:26:47
>>443
言葉遊びがしたいのか？
アルゴリズムと実装でいうならどう実装をしようが配列は配列
最適化の話がしたいならアセンブラスレでも逝け

445:デフォルトの名無しさん
07/02/05 00:44:54
>>444
444=441 ?

とりあえず君の配列の定義が知りたい。

アルゴリズム論の文脈では、実装における配列と理論における
配列はまったく対応しない可能性があるけど、それは大丈夫？

446:デフォルトの名無しさん
07/02/05 10:54:45
え～い面倒くせえ
ビットマップ＝ビットの配列
でFAだろ

447:デフォルトの名無しさん
07/02/05 12:10:45
まぁ、普通そんなこと言わんがな。

448:デフォルトの名無しさん
07/02/08 15:47:29
ある会計（０円～９９９円）を行う際に
一回の硬貨のやり取り（渡す枚数+受け取る枚数）を最小にするアルゴリズム

考えているんだけど思いつかない・・・助けてくれ

449:デフォルトの名無しさん
07/02/08 16:32:47
void minimumExchange(int account) {
　　int pay = account;
　　int min = getCount(account);
　　for (int i = account + 1; i < 1000; i++) {
　　　　int c = getCount(i) + getCount(i - account);
　　　　if (c < min) {
　　　　　　pay = i;
　　　　　　min = c;
　　　　}
　　}

　　System.out.println("account=" + account + " pay=" + pay + " min=" + min);
}

int getCount(int n) {
　　int c = n/500;
　　n %= 500;
　　c += n/100;
　　n %= 100;
　　c += n/50;
　　n %= 50;
　　c += n/10;
　　n %= 10;
　　c += n/5;
　　n %= 5;
　　return c + n;
}

450:デフォルトの名無しさん
07/02/08 17:16:55
ちょっと修正

＞　　for (int i = account + 1; i < 1000; i++) {
を
　　for (int i = account + 1; i <= 10000; i++) {

＞int getCount(int n) {
を
int getCount(int n) {
　　n %= 1000;

アルゴリズムを考える時はまず、最も分かりやすい方法（しらみつぶしとか）を考えるといいと思います。
それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。

＃「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。

451:デフォルトの名無しさん
07/02/09 22:24:47
1円札から999円札まで1円単位の紙幣を使ってもいいんですよね
特に条件が指定されてないので

452:デフォルトの名無しさん
07/02/09 22:28:43
999円札なんて無いだろ
常識で考えれ
1円札を999枚使うんだ

453:デフォルトの名無しさん
07/02/10 08:59:48
>>452
>1円札を999枚使うんだ

現在有効なお金
URLﾘﾝｸ(www.boj.or.jp)

一円券は今でも有効だから使用は違法ではないし
常識で考えて不可能というわけではないな。
つまり「現在発行されている」という条件がない限り、
硬貨のやり取りは常に0が最小というわけだ。

一本取られたな。

454:デフォルトの名無しさん
07/02/10 14:08:01
でも一円札とかって１円より価値あるよな

455:デフォルトの名無しさん
07/02/10 14:24:42
貨幣として使う分には１円だ。

456:デフォルトの名無しさん
07/02/10 14:26:34
そこでコイン商やオクだな

457:デフォルトの名無しさん
07/02/10 15:35:02
買いたい人が*いれば*ね。
はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。

458:デフォルトの名無しさん
07/02/12 20:53:26
金融恐慌時の裏面がすってないお札なんかは高かったりするのだろうか

459:デフォルトの名無しさん
07/02/12 22:02:58
刷られた数
使用された期間
現存数
等は少なければ少ないほど良い

どんなにいらなそうな物でもコレクターにとっては価値がある

460:デフォルトの名無しさん
07/02/13 03:28:54
そういえばうちの親父が記念硬貨とか集めてたな。
天皇陛下御在位６０年1万円硬貨とか。

461:デフォルトの名無しさん
07/02/13 10:21:21
売りたい人は山のようにいるから。

462:デフォルトの名無しさん
07/03/03 14:04:36
質問よろしいですか。

２次元空間上に重複して平面が沢山（簡単のため長方形で）ありました。
ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、
どんなアルゴリズムがいいでしょう？

よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも
教えていただけると助かります。

463:デフォルトの名無しさん
07/03/03 15:16:32
ん？

たとえばＡ４用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。
ピンが刺さっている紙を全部調べよう

って問題？

464:デフォルトの名無しさん
07/03/03 17:58:17
>>463
ピンを横に置くんじゃないの？

465:デフォルトの名無しさん
07/03/04 09:59:17
長方形と点のコリジョンだね。元データをグリッドに分割しておくのが
普通かな？２次元だと正方形や可変サイズのグリッドとか
ツリー状（検索を対数的なオーダーに減らす）にしておくとかいろいろ種類はあるよ。

466:デフォルトの名無しさん
07/03/04 10:41:11
重複していない空間の分割なら、もっと簡単なのだから
平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな

467:デフォルトの名無しさん
07/03/04 11:15:36
六十周年金貨はあったけど
五十周年金貨ってなかったよね？

468:462
07/03/04 18:16:51
そうです、紙をピン止めみたいな奴です。

3次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。

実装は難しくてもかまいません。

469:デフォルトの名無しさん
07/03/04 19:08:06
長方形は固定で点がいろいろ与えられるって考えていいのかな
今適当に考えただけだけど
最初に排他的な長方形の集合を探してR1とする
(多い方がいいけど最大独立点集合問題はNP困難なので適当でいい）
R1に含まれてない長方形の中から排他的な集合を探してR2とする。
これを再帰的に繰り返す。
点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。

全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから
結局全部チェックしなきゃいけなくなってしまうのでダメ。
もっといい方法があるのかもしれん。

470:デフォルトの名無しさん
07/03/04 19:10:09
空間を超平面で切って平面集合を2つに分ける。
両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。
探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。
これで全部の平面を総当りよりおよそ1/2の計算量になる。
あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。

471:462
07/03/05 01:18:32
空間を超平面で切るってのは、いわゆるBSP木みたいなもんですよね。

その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。
例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら
なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。

472:デフォルトの名無しさん
07/03/05 03:30:57
閾値より大きな領域は、別段そのツリー内に入れなければいいのでは？
単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。

473:デフォルトの名無しさん
07/03/05 20:42:16
空間を平面で切るときに
・一方の空間に完全に属する領域の集合（２つ）
・断面と交わる領域の集合
の３つに分けてみるのはどうか．こうすれば各領域は必ず一箇所に属する．

探索するときは，断面上の領域と点の落ちる空間内の領域の２つを調べる．

断面と交わる領域の格納は
数が少ないとき（多分，n < (log(n))^d'（d'は断面の次元）のとき）は単純なリスト
数が多いときは１つ次元を落とした同様の構造にする

よくわからないけど最終的には
(log(n))^d （dは次元）←適当
あたりになりそうな気がする．

474:デフォルトの名無しさん
07/03/05 21:19:27
>470-471 >473
なぜ一般次元に拡張を…
応用が利くのは良いっちゃあ良いんだけど微妙

475:462
07/03/06 01:07:58
>>472
大きいというか、重複が多い場合に結構問題になるんです。
今回は空間全ての領域で少なくとも３枚は被さっているのを想定してるんで、
必要な記憶領域がかなり大きくなってしまうという。

>>473
あ、そうか、２つとも探索すればいいんですね。
１次元で紙に書いてみたら、いけそうな感じです。
記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。
よーし、明日の夜にでも組んでみます。

476:デフォルトの名無しさん
07/03/06 20:33:21
こーいうのって全くの別人が同時期に同じ解法を求める事ってないよな。

特定(ry

477:デフォルトの名無しさん
07/03/06 21:20:05
空間を分けるってちゃんと図形の配置を考えてやるの?
そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ
それに重なってるところは分割できないので結局全探索になる

478:462
07/03/07 00:33:13
473氏の方法をちょっと変えた物で、無事実装完了しました。今のところい
い感じに動いています。ありがとうございました。

479:デフォルトの名無しさん
07/03/07 23:42:48

高卒でしかも数II？とか勉強いたことない俺にはまったく理解できないんだが
どうすりゃいい？

480:デフォルトの名無しさん
07/03/07 23:44:26
絵を描いてみる
諦める

481:デフォルトの名無しさん
07/03/08 00:10:43
>>479
余り気付かれていないが、高校生ではなくても高校レベルの数学を
勉強することはできる。

482:デフォルトの名無しさん
07/03/08 07:00:17
>>477
おまえ他人の言ってる事理解してないよ
でしゃばるなカス

483:デフォルトの名無しさん
07/03/09 00:58:56
>>482
理解できてないといって理由を書かない

484:デフォルトの名無しさん
07/03/10 23:39:52
自然科学なんかだと、実測データをグラフにプロットしたあと、なめらかな曲線でつないだりしますが、
そういう曲線を計算するアルゴリズムはありますか？

485:デフォルトの名無しさん
07/03/10 23:47:55
つ[Excel]
一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。

486:484
07/03/10 23:49:18
ググってたらcurve fittingと呼ばれている問題だと分かりました。
すれを汚してすいませんでした。

487:デフォルトの名無しさん
07/03/10 23:50:07
>>485
キーワードありがとうございます。
調べてみます。

488:デフォルトの名無しさん
07/03/11 02:21:41
最小二乗法とかね

489:51
07/04/15 21:22:27
SHA-1のハッシュを求めるプログラムを作ろうと調べていて
URLﾘﾝｸ(homepage2.nifty.com)
のサイトを見ていたのですが、

他に参考になるサイトはありませんか？

490:デフォルトの名無しさん
07/04/15 21:54:51
Wikipedia(EN)

491:デフォルトの名無しさん
07/04/24 04:03:28
計算アルゴリズムには限界があり、結局は全部探索したほうが良いって結論？

492:デフォルトの名無しさん
07/04/26 00:56:22
そーでもないと思う。問題が大規模な場合はアルゴリズム使わないと無理だね。
でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、
問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が
安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち
ゃうし。

493:デフォルトの名無しさん
07/04/26 01:28:59
２４シーズンⅤで解析に、独自のアルゴリズムを使って出す、とか言ってた。

494:デフォルトの名無しさん
07/04/26 05:30:17
OR

495:デフォルトの名無しさん
07/05/01 21:40:37
今日専門の方でアルゴリズムの授業が行われたんですがその際この3問だけどうしてもわかりません
何方かこの3問のフローチャートがかける方が居ましたら教えてください
1問目：成績判定１
アルゴリズムの点数を入力して、80点以上のとき「Ａ」、60点以上80点未満の時「B」、60点未満の時「Ｃ」
と出力するフローを答えなさい

2問目：成績判定２
英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。
なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること

3問目：成績判定3
2-12.成績判定2の選択処理の部分を一つにまとめなさい
選択処理部分
英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する

496:デフォルトの名無しさん
07/05/01 21:50:36
アルゴリズムじゃない。

そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。

497:デフォルトの名無しさん
07/05/01 22:19:41
それが問題集しかもらってなくてわからないんですよ

498:デフォルトの名無しさん
07/05/01 22:34:38
>>495
URLﾘﾝｸ(www.cs.takushoku-u.ac.jp)
これみりゃ大体わかるだろ。
いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。

スレ違いsage

499:デフォルトの名無しさん
07/05/03 14:45:41
問題集しかもらってなくてわからないとか言うんだったら、
2chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で
わからないのであったら講師や友達に聞け。

500:デフォルトの名無しさん
07/05/03 19:47:24
ぐぐれる香具師
友達いる香具師

は

2chで質問しない

501:デフォルトの名無しさん
07/05/04 00:08:57
友達の作り方を教える本でも買った方がいいと思う。

502:デフォルトの名無しさん
07/05/04 18:07:54
おとうさんはネットで調べても作れなかったけど

503:デフォルトの名無しさん
07/05/09 01:56:23
グラフ探索でダイクストラやA*より良いのない？

それはそうとA*探索はぐぐるのが難しい。

504:デフォルトの名無しさん
07/05/09 10:12:59
>>503
「Astar探索」とかでググってみたら？
ちなみにA*の場合、heuristicsがadmissible（各ノードから目的地までの予測コストが実際のコストを決して上回らない）でconsistent（いわゆる三角不等式が成立）なら、必ず最適解を返すよ。
それよりも良いってのは、heuristicsを設計できない場合ってこと？

505:デフォルトの名無しさん
07/05/10 07:32:41
どんな探索かわからんし、「良いの」って意味もわからんなあ。

506:sage
07/05/11 04:14:25
>>504
そうですね、良いヒューリスティックを設計できない時です。
近似解法含め、良いのを探してます。

>>505
たしかに「良い」ってのはアバウトでした＾＾；
主観的にでも、よさげなアルゴリズムがないかなぁと。
検索してもダイクストラばっかり引っかかるもので。

507:デフォルトの名無しさん
07/05/11 04:15:48
すみません、間違えて名前欄に書いてしまいました・・・

508:デフォルトの名無しさん
07/05/13 10:47:07
最短路探索ってことでいいの？

だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、
実用的にはヒューリスティックに頼るってのが現在の理解だと思う。
（現在行われてるコンテストでもそんな調子だよね）

近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに
ヒューリスティックを突っ込んだりするくらいだけど、
グラフが何の性質も持たない場合は性能評価が難しいところ。

509:デフォルトの名無しさん
07/05/13 16:40:43
ヒルス達がやってる６４個のソート問題ってどんな問題？

510:デフォルトの名無しさん
07/05/13 16:44:37
クイックソート問題

511:503
07/05/13 18:40:21
つまりのところ、厳密解を求めるなら、あまり良くないヒューリスティック
を用意した時、A*（と色々な改良版）が最速ってことですか。
というか、授業で習ったダイクストラとA*しか知らない物で＾＾；

近似についても、微妙な改良版くらいしかないって事ですね。

512:デフォルトの名無しさん
07/05/13 19:42:30
>>511
とにかく実行速度をなんとかしたいという実用的な要求なら、
問題にあったヒューリスティックとヒープを設計して A* が
たぶんもっとも現実的だと思う。

近似は、微妙な改良版といっても、たとえば幾何グラフとかなら
普通の Dijkstra と比較して一億倍以上早くなるケースもザラなので、
具体的な問題を見ないとなんともいえないところ。

513:503
07/05/15 01:35:21
ありがとうございます。じゃヒューリスティックに精を出してみることに
します。ちなみに問題は経路探索です。

514:デフォルトの名無しさん
07/05/15 22:13:04
>513
ちなみに、カーナビの経路探索だと、ネットワーク側の方を階層的にいくつか持って切り替えることによって高速化してる。
現在地、目的地近辺では全道路のネットワークで探索、それで見つからなければ国道以上のネットワークに移って探索、
さらに探索する場合は高速道路のみのネットワークに移って探索、みたいな感じ。
もちろん最適解は出ないけど、そもそもカーナビの場合、計算で出てくる最適解が、ドライバーにとって最適になるとも限らないしね。

515:503
07/05/15 23:00:45
あぁ、なるほど、中距離の探索とかで、たまにすごくアホな間違いをするの
はそれが理由なんだ。

516:デフォルトの名無しさん
07/05/16 01:49:50
いや
渋滞回避してるだけだろう

517:デフォルトの名無しさん
07/05/29 07:24:16
ｽﾚﾘﾝｸ(jisaku板)
上記スレで強制NaNの計算でインテル不利にするベンチが論争を呼んでますが
極端にAMD不利にする方法を探しています。
では。

518:デフォルトの名無しさん
07/07/10 16:03:47
多倍長演算の割り算のアルゴリズムで
たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
２桁目を決めよう
↓
答えは10かな？21*10＝210で521より小さい
↓
じゃ20かな？21*20＝420＜521
↓
じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする）
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は１桁目・・・

こんなのを考えたのですが、もっと良い方法はないですか？

519:デフォルトの名無しさん
07/07/10 16:04:24
age

520:デフォルトの名無しさん
07/07/10 17:02:29
何このマルチレス

521:デフォルトの名無しさん
07/07/10 20:02:17
10,20,30...
だったら時間掛かるだろ

522:デフォルトの名無しさん
07/07/10 21:23:37
自分で考える前にまず一般にどういう方法が使われているかを知れ
せっかく苦労して自分で考えついたとしても
それが既にみんなが普通に使ってるものと同じやそれ以下だったら悲しいだろ？

523:デフォルトの名無しさん
07/08/15 23:41:39
URLﾘﾝｸ(ss.nkk.affrc.go.jp)
に記述されている、
図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？

524:デフォルトの名無しさん
07/08/16 00:12:41
マルチうぜえ

525:デフォルトの名無しさん
07/08/18 19:37:21
ウィキペディアでB木の項を参照すると、
B+木やB*木というものが存在するとに書いてありますが、
どういったものですか？

>（厳密にはB木の改良型であるB+木やB*木を使うことが多い)

526:デフォルトの名無しさん
07/08/18 20:07:24
B+ は B であって、キーを葉にのみ格納するもの
B* は B で、子の比が 1/2 だったところを 2/3 にしたもの

wikipedia の情報は不正確だから参考にすんな
ちゃんとした教科書とか論文を参照すれば分かるだろ

527:デフォルトの名無しさん
07/08/18 22:38:43
>>526
ありがとうございました。
ウィキペディアから引用したら怒らせてしまった様で。
たまたま名前が載ってたから出しただけです。
B+木B*木は名前だけは以前から知ってましたが、
ググっても関係しそうなのは引っかからないですね。
本は
アルゴリズム事典
はじめてのアルゴリズム入門
アルゴリズムとデータ構造
など持ってますが、載ってないみたいです。

>教科書とか論文
できればこれのポインタ教えてください。

528:デフォルトの名無しさん
07/08/18 23:24:10
>>527
誰が怒っているの?

529:デフォルトの名無しさん
07/08/19 03:52:13
>教科書とか論文
できればこれのポインタ教えてください。

530:デフォルトの名無しさん
07/08/19 07:29:10
>>527
B-plus-tree とか B-star-tree で検索すればいくらでも出るんだけどね。

教科書については、そんな一般的なアルゴリズムの本には
あまり出てなくて、データベースよりの本を見ないとダメ。
R. Ramakrishnan, J. Gehrke, "Database Management Systems", 3rdEd. McGlaw-Hill, 2002

まあ次のサーベイ論文がよくまとまってるので、これを読んでおけば十分だろうけど。
D. Comer, "Ubiquitous B-Tree", ACM Computing Surveys, 1979
(URLﾘﾝｸ(www.cl.cam.ac.uk))

531:デフォルトの名無しさん
07/08/19 18:25:09
便乗だけど、B木と赤黒木どっちがいいか、
って判断はどこら辺ですればいいですか？
使い分ける時の基準みたいなのが知りたい。

532:デフォルトの名無しさん
07/08/19 19:19:15
>>531
どんな用途に使おうとしてるか分からないので、普通の設定で一般的な話をする。
赤黒木は、本質的にはブロックサイズの小さな B 木なので、
あなたの質問は B 木のブロックサイズをどう選ぶか、という質問と同じ。

普通の実装では、n 個の要素を格納するブロックサイズが b の B 木から
要素を検索には O(log (n/b)) 回の木上の探索（ランダムアクセス）と
O(b) 回のブロック内の探索（シーケンシャルアクセス）が必要となる。

ここで雑な計算をするとブロックサイズは、木上の探索の速度と
ブロック内の探索の速度の比くらいに選ぶのがよいことが分かる。

木が丸ごと全部メモリに乗るような場合は、木のアクセスもブロックの
アクセスも同じくらいなので、ブロックサイズも小さく選ぶのが良い。
一方、ハードディスクやネットワーク上のデータベースのような
木のアクセスが遅く、ブロックのアクセスが早い場合は、
ブロックサイズも大きく選ぶのが良い。

533:デフォルトの名無しさん
07/08/19 19:50:28
>>528 参考にすんな→この人怒ってる怖いよぉ

534:デフォルトの名無しさん
07/08/19 19:54:51
どこぞの園児じゃあるまいし。

535:デフォルトの名無しさん
07/08/19 21:04:07
なんでそんな偉そうなんですか

536:デフォルトの名無しさん
07/08/19 21:04:43
どこが偉そうなの

537:デフォルトの名無しさん
07/08/19 21:37:32
質問を質問で返すな
わかりませんと言え

538:デフォルトの名無しさん
07/08/19 21:40:56
なんでそんな偉そうなの

539:デフォルトの名無しさん
07/08/19 21:41:29
そういうのは質問の体をなしてから言え

540:デフォルトの名無しさん
07/08/19 22:26:02
順序付きコンテナは、どうもトライが最強っぽいんだけど、
メモリが・・
なんとかなりませんか？

541:デフォルトの名無しさん
07/08/19 22:59:51
つパトリシア

542:デフォルトの名無しさん
07/08/28 05:58:02
2Dの多角形ポリゴン2個(n個)を合成して1個(?)の多角形にするアルゴリズム

ネット上にこれを実装したソースコードが公開されてない(見つからない・・・)のでどなたか教えてください。
＿＿
＿|＿ |
| |＿|＿|
|＿＿|

ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
　↓
＿＿
＿| |
| ＿|
|＿＿|

ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)

というような感じです。
中抜き( 合成後のポリゴンの内側に穴が開いている )まで考えると、結構むずかしそうで・・・

これでやりたいことは、国土地理院の市町村別のポリゴンデータを県ごとに合成して、県別のポリゴンデータにすることです。
Excel VBAで精細な都道府県地図を描きたいなーと思って、
都道府県の無料のポリゴンデータを探したけど市町村別しか見つからなかったので
じゃあ合成して作ろうか、と思ってたんですが・・・詰まりました。

Java の awt パッケージでポリゴンの合成をしているクラスのオリジナルのソースコードを見ればアルゴリズムがわかるかも
とも思ってみてみたけどソースコードは入っておらず・・・orz

宿題とか課題とかではなくて、あくまで趣味的なものなので急ぎません。
VBでもcでもc++でも良いので、どなたか、お知恵を拝借させてください。

543:542
07/08/28 06:00:14
>>542
図形ずれちゃった・・・
　　＿＿
＿|＿　 |
|　|＿|＿|
|＿＿|

ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
　↓
　＿＿
＿|　　|
|　　＿|
|＿|

ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)

こうです。

544:デフォルトの名無しさん
07/08/28 09:44:30
>542
悪いこと言わないから別の方法考えたほうがいいと思う。
塗り分けるだけなら市町村別のデータでも構わないわけだし。

で、
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277X
の第 2 章にアルゴリズムは載ってる。でも、ここから実装まで持っていくのもそう単純じゃないと思う。

あと、オープンソースライブラリの CGAL にそういう機能はある。
URLﾘﾝｸ(www.cgal.org)
Reference Manual の VI Polygon and Polyhedron Operations 辺り。

545:542
07/08/28 21:33:57
>>544
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277Xの第2章早速読んできました。
例題に挙げられてるのも地図でよさそうだったけど、
プログラミング言語を限定してないアルゴリズムとしての本なんで、
やろうとしていることを実装するには、どういうプログラムを書けばよいのかまでは踏み込めなそうです。

せめて
i ← S1 と S2 の交点
みたいなのがあればなぁ。

CGALのマニュアルも読んでみました。joinあたりのコードか数式が出ていればVBAでも実装できそうなんですが・・・

>悪いこと言わないから別の方法考えたほうがいいと思う。
そうですねー。
ただ、ポリゴンをくっつけるのはもうちょっと粘ってみます。考えるのも楽しいので。

市町村同士は重ならないので、
・辺と辺が重なっている（隣り合っている）ところを見つけてくっつけていく
・中抜きはこの際無視
というように簡単なものを作る方針で考えてみます。
重なりまで考えて汎用的なアルゴリズムにしようと思ったけど、結構しんどそうですので・・・

どうもありがとうございましたー。

546:デフォルトの名無しさん
07/08/29 01:21:12
今日から専門学校のほうで授業アルゴリズムが始まったんですが
時間計算
分時間を入力して○時○分に変換して出力するフローのaとbに該当する処理を記述しなさい。
なお、計算結果は整数部のみとし、小数部は切捨てとなる。
余り（X%Y)で除数の余りを求めることができる。[例、余り（100%3）は1となる]
例：117分の時　1時間57分
（開　始）　何方かa bに入る答えがわかる方いましたら教えてください
　　↓
（データ）・・分時間を入力
　　↓
（処理）・・a 時を求める
　　↓
（データ）・・時を出力
　　↓
（処理）・・b 残りの分を求める
　　↓
（データ）・・分を出力
　　↓
（終了）

547:デフォルトの名無しさん
07/08/29 01:28:01
aとbに入るのは数字？式？言葉？

548:デフォルトの名無しさん
07/08/29 01:39:28
式です＾＾；

549:デフォルトの名無しさん
07/08/29 01:54:03
a・・・分時間/60
b・・・分時間%60

550:デフォルトの名無しさん
07/08/29 03:31:39
>>546
宿題はスレ違い
しかも回答もらって礼も無しかよ

551:デフォルトの名無しさん
07/08/29 19:38:32
三角関数はマクローリン展開して計算しますよね。
単純に考えればsinθのθが何であれ計算時間は変わりませんが、
速度面でチューニングが施されているであろうライブラリではどうなんでしょう？

552:デフォルトの名無しさん
07/08/29 23:22:57
>三角関数はマクローリン展開して計算しますよね。
ここで間違ってる
関数近似の教科書読むべし

553:デフォルトの名無しさん
07/08/29 23:30:11
>>552
すみません、悠長に教科書読んでる暇がないので結論をお願いします

554:デフォルトの名無しさん
07/08/29 23:36:55
CPUのアーキテクチャ等やライブラリ作った奴の腕に依存して色々な可能性がある
ただ，どれもθを0～π/2の範囲に正規化してるだろうから
その範囲なら少し速いはず
これ以上は本嫁

555:デフォルトの名無しさん
07/08/30 01:07:36
ぶっちゃけ、今時の単精度演算アクセラレータはテーブル参照プラスリニア補間で済ませている希ガス。

556:デフォルトの名無しさん
07/08/30 07:24:15
>>554
絶対的な速度が問題なのではなく、速度のむらを気にしているのです。
たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか？ということです

>>555
ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。

ターゲットはSH7145
ルネサスのコンパイラを使ってます。
ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので
VCやgccだったらどうなのかという意見でもいいのでお願いします。

557:デフォルトの名無しさん
07/08/30 09:28:07
後出し多いな

558:デフォルトの名無しさん
07/08/30 10:04:11
5倍の差はないだろうけど，1～2割位なら充分あり得る
実測するのが手っ取り早いかと

559:デフォルトの名無しさん
07/08/30 17:45:37
>>556
マイコンの方がむしろテーブル変換使用すると思うが

560:デフォルトの名無しさん
07/08/30 17:47:40
>>554
いっそπ/8に正規化するとか

561:デフォルトの名無しさん
07/09/09 14:05:26
>>553
＞悠長に教科書読んでる暇がないので

そうか。残念だったな。

562:デフォルトの名無しさん
07/09/12 02:03:16
差異のアルゴリズムでレーベンシュタイン距離を求めていますが、
結局これ求めてどうなるんですか？
馬鹿でも分かるようにく教えてください。

563:デフォルトの名無しさん
07/09/12 08:42:09
>>562
そんな限られた分野でしか使わないようなものを
さも誰もが知ってるかのように聞かなくても。

自然言語処理とかで使う。
Google 先生とかがよくやってる
もしかして: ○○
を出したりとかに使える。

564:デフォルトの名無しさん
07/09/13 00:02:29
>563
レスどうも。

2つの文字列を比較して"n文字違います"とかは想像できるんだけど、
diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、

565:デフォルトの名無しさん
07/09/13 00:05:36
>>564
Wikipedia項目ﾘﾝｸ

566:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/09/19 03:20:29
質問させてください．
y=Ax （x,y:ベクトル， A:マトリックス，大きさ数百～数万）
に対し，
x = inv(A) * y
を解く問題を考えています．
ここで，逆行列演算inv(A)がO(N^3)のコストが掛かり，ネックになっています．
いま，Aは疎な帯行列（しかも対称）という条件があるので，
大幅な計算削減ができるのではないか？と考えております．
例えば，計算コストをO(N^2)にするといったことは可能でしょうか？
キーワードだけでも良いので，知恵を貸していただけると幸いです．

568:デフォルトの名無しさん
07/09/19 03:49:22
つ[特異値分解]

569:デフォルトの名無しさん
07/09/19 07:22:57
>>567
LU使っているのか？
対称行列だと、LDL分解でOK
帯行列だとさらに、0要素を見ないことで、さらにスピードアップ

570:デフォルトの名無しさん
07/09/19 17:36:11
そんな話，数値計算の本見ればいくらでも載ってるだろ

571:567
07/09/20 01:53:07
>>568
キーワードありがとうございます！
調べてみます．

>>569
LU分解→直接法で逆行列としていました．
LDL分解というものがあるのですね．
解法は反復法に持って行くのですかね・・・調べてみようと思います．
反復法は精度の面が少し気になりますが，勉強含めて試してみます．
多謝！

>>570
数値計算の門外漢なもので・・・勉強してきます．

572:デフォルトの名無しさん
07/09/24 22:11:26
kd木で、近い領域を何度も連続して調べたい時、毎回根から辿らないようにショートカットするような技法ってありますか？

573:デフォルトの名無しさん
07/09/28 09:44:52
二つの整列済みリストのマージで
要素数が一方がk個,もう一方が2個の場合,
n回の比較でマージできる最大のkをanとすると
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
で与えられるらしいのですが
これがどういうアルゴリズムでマージしたときの物なのか,
またこれが最良値なのか知りたいのですが, 誰か知りません?

574:デフォルトの名無しさん
07/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
07/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:デフォルトの名無しさん
07/10/30 01:16:41
各データの値がかなり近い時に
ハッシュのみだとデータの衝突回数
多い場合ってどうやってみんななら解決する？

あとね、kd木で何の本に詳しく載ってますか？

577:デフォルトの名無しさん
07/10/30 01:55:31
値近くてハッシュが衝突するって、どんなアルゴリズムだよ

578:デフォルトの名無しさん
07/10/31 02:27:51
8byteの16進データを
完全ハッシュ化するソースコード置いてある
とこないですか？

579:デフォルトの名無しさん
07/10/31 21:09:37
区分サンプリング法やラテン超方格法のアルゴリズムを教えてください。

580:デフォルトの名無しさん
07/11/28 05:05:51
二点で定義されてる直線上に、ある点があるかどうかを判定するにはどうすればいいですか、教えてください。

581:デフォルトの名無しさん
07/11/28 06:17:51
要は３点が一直線に並んでいるかを知りたい、と解釈し直してみた。
１点を基準に他２点へ直線を引くときの傾きが一緒だったらOK。
x軸と垂直だった場合なんかも考慮すると、
(x1-x0)*(y2-y0)==(x2-x0)*(y1-y0)

582:デフォルトの名無しさん
07/11/28 13:05:52
あ、なるほど、ありがとうございます

583:デフォルトの名無しさん
07/12/07 21:54:02
[N][N]の2次元配列を３つ

[N]の配列を2つ使ってる場合の使用領域のオーダーってＯ(n^2)におさまります？

584:デフォルトの名無しさん
07/12/07 22:02:42
うん

585:デフォルトの名無しさん
07/12/09 21:31:14
3N^2+2N = O(N^2) が分かってないのか？

586:デフォルトの名無しさん
07/12/14 13:42:55
グレブナ基底を求めるプログラム、誰か持っていませんか？
C言語でおねがいしたいです。

587:デフォルトの名無しさん
07/12/15 02:12:22
>>586
23457円になります。

588:デフォルトの名無しさん
07/12/29 03:46:49
均一なセル上に分割した空間で、円（または球）を配置して、円と交差する
セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう？

589:デフォルトの名無しさん
07/12/29 06:33:27
セルってのはよくわからないのだが、格子なの？
格子が座標と平行になるように回転変換して　格子間隔が1になるように伸縮して
円の中心座標の小数点以下座標を見ればいいだけでは？

590:デフォルトの名無しさん
07/12/29 07:51:56
あ、格子です。あ、最初から座標軸並行を仮定してます。
さらに辺の長さを1で仮定してしまいましょか。
えーと意味がいまいちつかめないんですが、

＞格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮
これは元々が単位格子であるなら何もしないでOK?

＞円の中心座標の小数点以下座標
これで、なぜ全ての格子が求まるかがわかりません。
整数部をみれば、中心を含む格子は求まると思いますが。

591:デフォルトの名無しさん
07/12/29 13:33:11
欲しいのは「円周」と交わるセルだろ？
そこがちゃんと書いてないから勘違いされたと思われ

592:デフォルトの名無しさん
07/12/29 17:06:31
あ、そうです。申し訳ない。

593:デフォルトの名無しさん
07/12/30 12:13:13
DDA(digital diffrential analyzer)というのがあるが使えないかな？
３次元は分からんが

594:デフォルトの名無しさん
07/12/30 12:39:28
3次元も、半径が違う円で切り出したものと考えればイケルんじゃないの？

595:デフォルトの名無しさん
07/12/31 01:56:42
ある年月日が与えられ、そのn日後の日付を求めたいのですが、
1,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める
2,days+nを西暦年月日に変換する
という方法を考えました。
2は1の式を変形して解けるだろうと見当を付けていましたが、
小数点以下を切り捨てたりしているためうまく式を求められません。
素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか？
日付は最近のものに限定して考えています。
ユリウス暦とグレゴリオ暦の判断が面倒になるので…

596:デフォルトの名無しさん
07/12/31 08:25:44
>>595
日付を1日進めるプログラムは書けるかい？

おｋ。ならば、1日進める部分をn回実行するんだ。

597:デフォルトの名無しさん
07/12/31 08:49:10
つーか、なんで既存ライブラリを使わないのだろう。
大抵の言語に日付け処理系の関数があると言うのに。

598:デフォルトの名無しさん
07/12/31 11:47:35
>>595
URLﾘﾝｸ(ufcpp.net)

599:デフォルトの名無しさん
07/12/31 12:25:41
>>595
ちょっと検索してみたらこんなのがあった
delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい

URLﾘﾝｸ(kwikwi.cocolog-nifty.com)

ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの？
日本のサイトしか引っかからないんだよね

600:デフォルトの名無しさん
07/12/31 12:29:16
>>596
なるほど。
ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので
上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと･･･
>>597
Cなのでそういった関数はもちろんあるのですが、若干不便なので
勉強も兼ねて自前で実装してみようというわけです。

601:デフォルトの名無しさん
07/12/31 12:51:11
>>598
おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25　　…?　もはや何がなんだか。

URLﾘﾝｸ(cl.is.kyushu-u.ac.jp)
こんなの見つけたので読んできます。

602:デフォルトの名無しさん
07/12/31 13:18:34
>>600
URLﾘﾝｸ(www.tensyo.com)
ここの
int YMD_AddD(int *Y,char *M,char *D,long d）　って関数を見ると
負数を渡した場合は　400年循環を使って正に直せばいいみたい。

603:デフォルトの名無しさん
08/01/01 10:28:35
つまり、-3日なら 400年前から(146097-3)日後と計算するわけか

604:デフォルトの名無しさん
08/01/02 02:09:27
除算のシフト演算化はコンパイラの最適化段階で
自動でやってくれるものだと思ってたんだが、そうでもない？

605:デフォルトの名無しさん
08/01/02 08:29:27
コンパイラの性能がソレなりならって事でしょう。
固定値の除算ならさらに、掛け算で代用してくれるのも多いね。

606:デフォルトの名無しさん
08/01/02 10:22:11
>>604
2のべきの定数ならね。

607:デフォルトの名無しさん
08/01/02 12:18:44
という事で
１、カレンダを1日進める関数関数を作る
２、+N日は１の関数をN回呼ぶ
３、-N日は、年数を400日戻してから、146097-N回１の関数を呼ぶ

608:595
08/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
08/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
08/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:デフォルトの名無しさん
08/01/08 03:16:56
漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ

612:デフォルトの名無しさん
08/01/08 03:17:24
誤爆です。
ごめんなさい

613:デフォルトの名無しさん
08/01/08 13:01:23
>>611
そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。

614:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/02/09 20:31:46
繰り上がり

616:614
08/02/09 20:41:09
>>615 すばやい回答ありがとうございます。
くりあがりですね。

このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、
この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？

617:デフォルトの名無しさん
08/02/09 20:44:43
>>616
そのとおり。

10進数で画面に表示する回数が、普通の計算を行う回数よりも
圧倒的に少ないと考えると、そういう数の表現になる。

618:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/02/11 23:37:33
HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた

620:デフォルトの名無しさん
08/02/18 17:15:48
行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、
調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか？

次ページ