プログラミングの為の数学と算数 vol.2

1 名前：デフォルトの名無しさん [04/09/05 16:22] プログラムに必要な数学、算数に関する話題について 語りましょう。TIPS/Q&Aスレです。 404 名前：400 mailto:sage [2006/02/09(木) 17:45:26 ] ま、>>391には皮肉も通じないようなんでマジレスに切り替えるけどね。 思うんだが学歴を今後も問題の条件に入れ続ける気なら 学歴板でも行ったらどうかと思う。 ここはプログラム板の数学スレだから学歴は関係ない。 そしてプログラムに関係ないセンター試験の問題について 受験生向け解説依頼を受け付けるスレでもない。 受験生ならオトナシク受験板でも行ってたほうがいいんじゃない？ 大学受験板 etc4.2ch.net/kouri/ 学歴板 tmp6.2ch.net/joke/ 405 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/02/09(木) 18:10:56 ] 答えたくなければいいんですよ。 答えなくなければね;) 406 名前：デフォルトの名無しさん mailto:sage [2006/02/09(木) 18:16:13 ] 実際答えたくねーし。 407 名前：デフォルトの名無しさん mailto:sage [2006/02/09(木) 18:39:45 ] プログラムに関係ない受験数学の質問する厨な荒しは 今後スルーが相応と思うがどうか？ 408 名前：デフォルトの名無しさん mailto:sage [2006/02/09(木) 19:39:20 ] すべて水に流して　心機一転 　ー　　再開　　ー 409 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/02/09(木) 21:36:08 ] >今後スルーが相応と思うがどうか？ 毎度スルースルーと言ってる割には毎度我慢できなくなってレスしちゃうんだね。 子供?;) 410 名前：デフォルトの名無しさん mailto:sage [2006/02/10(金) 00:01:50 ] ここはム板なんだから、やっぱプログラム的に 近似的に解くべきだなｗ 411 名前：デフォルトの名無しさん mailto:sage [2006/02/10(金) 02:34:30 ] >>409 えーと、どこで笑えばいいのかな？ 412 名前：デフォルトの名無しさん mailto:sage [2006/02/10(金) 16:15:10 ] >>410 じゃぁ、両端を探すために二分探索でもするか？ 413 名前：デフォルトの名無しさん mailto:sage [2006/03/01(水) 22:02:54 ] >>411 　m9（^Д^） じゃなくて 　;) を無理して使うとこ 414 名前：デフォルトの名無しさん mailto:sage [2006/03/03(金) 14:58:11 ] 自分の趣味としては;)よりは;-) 415 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 09:58:52 ] 僕的には :-P とかがかわいくて好きでつ 416 名前：デフォルトの名無しさん [2006/03/09(木) 11:39:33 ] ここは顔文字スレになりました。よろしくね ;-P 417 名前：デフォルトの名無しさん [2006/03/09(木) 11:56:57 ] 問題だ 1＋1＝ 418 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 12:14:22 ] 11 419 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 12:24:33 ] 10説も提唱するか。 420 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 12:34:32 ] Error: '=' の左が左辺値ではありません 421 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 13:24:56 ] Error: '=' で式が終わっています 422 名前：デフォルトの名無しさん mailto:sage [2006/03/09(木) 23:36:01 ] Error : 予期せぬ問題が出題されました 423 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 00:06:04 ] 符号付整数除算で四捨五入の処理について質問があります。 a÷b の結果を四捨五入して ret に取得する処理を以下のようにしました。 [バージョンA] // 除数と被除数の符号チェック if ((a ^ b) < 0) { 　　// a, bが異符号 　　// ret = (a / b) - (1 / 2) 　　ret = (2 * a - b) / (2 * b); } else { 　　// a, bが同符号 　　// ret = (a / b) + (1 / 2) 　　ret = (2 * a + b) / (2 * b) } この方法だと正の場合0.5→1、負の場合-0.5→-1となり 数値0に対して正負の結果が対称になります。 (続く・・・) 424 名前：423 mailto:sage [2006/03/10(金) 00:07:03 ] 今、実装したいと考えているのは 除算結果の整数部: n、小数部: s (s >= 0) としたとき 四捨五入後の結果 ・s < 0.5 のとき n ・s >= 0.5 のとき n + 1 [実例] ・-0.6 = -1 + 0.4 = -1 + 0 = -1 ・-0.5 = -1 + 0.5 = -1 + 1 = 0 ・-0.4 = -1 + 0.6 = -1 + 1 = 0 ・0.4 = 0 + 0.4 = 0 + 0 = 0 ・0.5 = 0 + 0.5 = 0 + 1 = 1 としたいのですが、上手い方法が見つかりません。 一応、自分なりに考えて以下のように実装したら上手くいきました。 [バージョンB] if ((a ^ b) < 0) { 　　// 正数にして計算を行う 　　a = abs(a); b = abs(b); 　　// ・整数除算の結果を -1 したもの 　　// ・小数部を割合化したもの(？)である (b - (a % b)) / b + (1 / 2) を四捨五入したもの 　　// を加えて求める。 　　ret = -(a + b) / b + (2 * (b - (a % b)) + b) / (2 * b); } else { 　　ret = (2 * a + b) / (2 * b); } 除数、被除数の符号チェックをしたりしてスマートではないので もっとシンプルにできる整数演算での上手い方法はあるのでしょうか？ よろしくお願いします。 425 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 00:11:33 ] 0.5足して切り捨てしちゃ駄目？ 426 名前：423 mailto:sage [2006/03/10(金) 01:16:10 ] >>425 画像処理で使用するため浮動小数点は、できるだけ使用しないようにしています。 ちなみにバージョンA,Bともに四捨五入をするときは ret = (a / b) + 0.5 　= (a / b) + (1 / 2) 　= (2 * a + b) / (2 * b) ←通分(だったっけ？) のように0.5を足すようにしています。 427 名前：423 mailto:sage [2006/03/10(金) 01:32:01 ] ちょっと言葉足らずだったので補足を・・・ 単純に0.5を足して切り捨てると除算結果が負数の場合に問題があるのです。 (たとえば、結果が-2のときは -2.0+0.5 → -1.5 → -1になってしまう) そのためにバージョンAでは、除算の結果が正負で場合わけをして +0.5か-0.5を切り分けることにしました。 428 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 02:46:54 ] ＞画像処理で使用するため浮動小数点は、できるだけ使用しないように そもそもここに間違いがあると思うだけどな 429 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 11:44:35 ] >424 方法はそれしかない。可搬性を確保したい場合符号チェックは必然。 挙げられた例題は結果の精度として整数値しか必要でない (小数点以下0ビットの精度)場合の固定小数点演算と看做すことができる。 固定小数点演算とは例えば小数点以下に2ビットの精度が必要な場合に 3ビット下駄を履かせて1→8、0.5→4とするなどして整数演算によって 一定精度の実数演算を行う方法だ。 その場合結局四捨五入の処理も必要になる。 最下位ビットが0か1かを決めるために剰余を使うのもまさに例題と同じだ。 （固定小数点演算という枠組みで考える理由は精度が異なる場合も 同じ考え方で統一的に考えられるというだけだ。） そして符号の処理も結局必要になる。 ただ、符号付整数除算のハードウェア仕様としてはAもBもありえて、 ハードウェアの仕様を調べてそれに依存するなら処理を省略できる可能性はある。 通常の整数は2の補数表示をすることで正数に対する処理を転用して 負数を扱っているで0に対して表現が元々対称でない。 だからBバージョンが目当てなら見込みは割とある。 ハードウェアに依存しちゃうけどね。 430 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 11:58:45 ] 訂正 2ビットの精度が必要な場合→3ビットの精度が必要な場合 精度は悪化するけど2bitの精度が必要な場合に3bit取って 剰余は見ないで最下位ビットだけ見て四捨五入って手はあるけどね。 431 名前：423 mailto:sage [2006/03/10(金) 14:08:49 ] 色々とありがとうございます。 やはり、符号チェックは必要なのですね・・・ 浮動小数を使いたくないというのは、参考にしているライブラリの処理速度を計測したところ その結果から浮動少数は使っていないと思われるためです。 ちなみに、そのライブラリは Win32API のウィンドウとビューポート間の座標変換処理で 比較対照としているものは LPtoDP() という関数です。 こいつが結構くせもので、整数部を n 、小数部を s としたとき だいたい s >= 0.47 で四捨五入して n + s → n + 1 としているのです。 （負数の場合も -1.53 = -2.0 + 0.47 = -1 [入]、-1.54 = -2.0 + 0.46 = -2 [捨]） 上記のように、四捨五入の仕様は>>424のバージョンBと同じです。 整数演算で 0.47 くらいで四捨五入なんて特殊なことをしているので 何か整数演算独自の四捨五入の方式があるのかと思い質問させていただきました。 個人的にはバージョンBの除数、被除数の符号が異なる場合に 除算を2回行うというのに満足できないので、もう少し紙とペンで色々と考えてみます。 432 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 15:50:22 ] サンプルを少数表記じゃなくて整数比で示してくれないか？ その方が解析しやすい。 433 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 15:55:04 ] 知ってるかどうか知らないが、 小数点以下の数を10進表記するとそれだけで誤差が含まれる。 だからこの場合、実数に換算しないで考えたほうがよい。 つまり計算させてる事例に関わる整数の比がないと 何が行われているか正確なことはわからない。 LPtoDP()ってことは窓の大きさとディスプレイの解像度が絡むんだろ？ 434 名前：デフォルトの名無しさん [2006/03/10(金) 16:18:42 ] 固定少数点で負数の時だけ処理するのを条件判断を使わずにやりたいなら、 ret = (2 * a + b*sgn) / (2 * b); として sgn を 1か-1にすればいい あるいは ret = (2 * a + b*(sgn+1)-b) / (2 * b); とすれば　sgn+1 は 0か2なので 0か-1の変数fを使い ret = (2 * a-b + 2*b&f) / (2 * b); xor結果の最上位で fを-1か0にすればいい 　・右へのビット幅だけシフト 　・インラインアセンブラを使って符号拡張命令 　して、符号ビットを埋めて ゴチャゴチャやる方法があるけど、そんなの使いたい？ 435 名前：デフォルトの名無しさん [2006/03/10(金) 16:27:53 ] 他に ret = (2 * a + (b^t)) / (2 * b); として tを 0か-1とする方法もある でもたぶん ret = ( a + ((b^t)>>1) ) / b; あたりでやってんじゃないかな 436 名前：423 mailto:sage [2006/03/10(金) 18:01:03 ] みなさん、どうもありがとうございます。 >>432 >>433 座標変換のための設定は以下の通りです。 // マッピングモード設定 ::SetMapMode(hDc, MM_ANISOTROPIC); // ウィンドウ領域 (0, 0) - (1000, 1000) ::SetWindowExtEx(hDc, 1000, 1000, NULL); ::SetWindowOrgEx(hDc, 0, 0, NULL); // ビューポート設定 (0, 0) - (10, 10) ::SetViewportExtEx(hDc, 10, 10, NULL); ::SetViewportOrgEx(hDc, 0, 0, NULL); 単純にウィンドウからビューポートへ(1/100)倍する変換です。 ウィンドウ、ビューポートのx座標をそれぞれ wx, vx として -1000 <= wx <= 1000 の範囲で変換してます。 変換式は憶測ですが vx = wx * (10 / 1000) で求めていると思われます。 四捨五入の「入」、「捨」の境界は以下のとおり 0.46〜0.47 です。 (これ以外の146, 246, ...、-154, -254, ... でも同様の結果です) wx = -54 → vx = -1 (-54/100 → -0.54 → -1 + 0.46 → -1) wx = -53 → vx = 0 (-53/100 → -0.53 → -1 + 0.47 → 0) wx = 46 → vx = 0 (46/100 → 0.46 → 0 + 0.46 → 0) wx = 47 → vx = 1 (47/100 → 0.47 → 0 + 0.47 → 1) >>434 その方法だと>>423のバージョンAと同じになってしまうんです。 今は>>424のバージョンB方式の四捨五入の実装方法で迷ってるんです。 437 名前：423 mailto:sage [2006/03/10(金) 18:03:48 ] 追加情報で、ウィンドウ領域とビュー領域の数値は32bit(int型)で設定可能なのですが MSDNで調べたところウィンドウ領域は32bitを保証してビューポートは27bitしか保証しないと 明記されてます。 残り5bitを小数部とした固定小数点で計算とかをしているんですかね？ 438 名前：434 [2006/03/10(金) 18:21:37 ] >>436 折角書いてやったんだから、ちゃんと読め！ いいか　その>>424のバージョンB　ってのは　a/bの符号によって 符号負　　ret = (2 * a - b) / (2 * b); 符号正　　ret = (2 * a + b) / (2 * b) としたいわけだろ？ 符号を sgn +1/-1 なら 　ret = (2 * a - b*sgn) / (2 * b); だろが！　 439 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 18:57:40 ] >>438 論外 ポイントになるのは、0.1刻みとして(-2.5〜-1.6), (-1.5〜-0.6), (-0.5〜0.4), (0.5〜1.4) をどうやって同じグループにするかということ 440 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 19:21:54 ] 素直に　floor(val + 0.5)　いっとく？ 441 名前：434 [2006/03/10(金) 19:27:10 ] ああ、そりゃ悪かったな。　しかし多少修正すりゃいいことじゃないか　 単に >>435の符号を入替えて int div(int x,int y){ int sgn=x^y; sgn=sgn>>31; return (x-((-y^sgn)>>1))/y; } x/y = div(x,y) -20/10= -2 -19/10= -2 -18/10= -2 -17/10= -2 -16/10= -2 -15/10= -1 -5/10= 0 5/10= 1 15/10= 2 -14/10= -1 -4/10= 0 6/10= 1 16/10= 2 -13/10= -1 -3/10= 0 7/10= 1 17/10= 2 -12/10= -1 -2/10= 0 8/10= 1 18/10= 2 -11/10= -1 -1/10= 0 9/10= 1 19/10= 2 -10/10= -1 0/10= 0 10/10= 1 20/10= 2 -9/10= -1 1/10= 0 11/10= 1 -8/10= -1 2/10= 0 12/10= 1 -7/10= -1 3/10= 0 13/10= 1 -6/10= -1 4/10= 0 14/10= 1 これでいいんだろ？ 442 名前：434 [2006/03/10(金) 19:32:15 ] たぶん、 ホントは四捨五入でret = (2 * a + (b^t)) / (2 * b)　を使いたかったけど2つある2倍が嫌なんで ret = ( a + ((b^t)>>1) ) / b; 　としたら、プラス側が6で変化したんで ret = ( a - ((-b^t)>>1) ) / b;　として、まあマイナス側に-6で変化したっていいやで　計算量優先にしたんだろ 443 名前：434 [2006/03/10(金) 19:59:13 ] いや、もしかして abs(x) の代わりに (x>>31)^x のようなのを使ってて出た誤差かな 444 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 20:05:54 ] (2*a + 2*a*a*b - b) / (2*b) + 1 - a*a 445 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 20:28:42 ] >>423 またおまえか。 446 名前：423 mailto:sage [2006/03/10(金) 21:07:51 ] みなさん、ありがとうございます。 とても参考になりました。 特に>>434さんの方法には脱帽しました。 異符号の場合に -1 と XOR して1の補数を用いるなんて思いもつきませんでした。 と言っても、まだ完全には理解できてはいないのですが 先にお礼を言っておきたかったので。 本当にありがとうございました。 447 名前：434 [2006/03/10(金) 21:28:04 ] ごめん。　変な方法使うより #include <stdlib.h>　に div という関数がある　除算とあまりを出す関数だ div_t d=div(x+y/2,y); if(d.rem<0) d.quot--; で　d.quot　を使えばいい 条件判断を無くしたいなら d.quot+d.rem>>31 でいい たぶんコレが正解だろう 448 名前：434 [2006/03/10(金) 21:30:52 ] ようするに、結果見ると、変な四捨五入じゃなくて 普通の四捨五入をやりたいって事にやっと気付いた。　すまんな。 449 名前：434 [2006/03/10(金) 21:40:25 ] ちなみに試したコード #include <stdlib.h> int divd(int x,int y){ div_t d=div(x+y/2,y); return d.quot+(d.rem>>31); } int divd(int x,int y){ div_t d=div(x*2+y,y*2); return d.quot+(d.rem>>31); } 結果はどっちも >>441　と y=10では同じになる 450 名前：434 [2006/03/10(金) 22:11:31 ] 言い訳すると >>427　で　 ＞単純に0.5を足して切り捨てると除算結果が負数の場合に問題があるのです に騙されてしまった。 単純に0.5を足して切り捨てるのをやりたかったのだろう。 ただ、X86では除算の結果が負数になる場合は余りも負数になる。 a/b＝ n余りsなら a = n*b + s = s+b+(n-1)*b となる修正をすればいい アセンブラで書けば、 　　cdq 　　idiv 　　sqr edx,#31 　　add eax,edx と4命令 451 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 22:13:38 ] >>441は xが正でyが負のときおかしい。 かけ算はいってるけど int func(int a, int b){ int absa = (a >> 31) ^ a; return (a + absa*b + (b>>1)) / b - absa; } 452 名前：434 [2006/03/10(金) 22:18:43 ] >>451 そうだね。他に y=1の時も >>441は変になるだろう >>449なら大丈夫な筈だ 453 名前：434 [2006/03/10(金) 22:21:39 ] アセンブラの　sqr は　sarのタイプミスだ　>>950 アセンブラだと４行なのに 使わないと除算とmodを別に計算するか div 関数を使う必要があるのが面倒な所 div関数だと結果も構造体渡しだからメモリアクセスが入って遅くなる 454 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 22:27:09 ] 今一状況がわかんないんだけど、divの定義見た? あんなの使う気にならないんだけど。 455 名前：434 [2006/03/10(金) 22:34:07 ] >>454 だったらインラインアセンブラでやるといいよ。 cだけで書くなら x+=y/2; int r=x/y; if( (x % y)<0) r--; return r; 456 名前：434 [2006/03/10(金) 22:54:48 ] >>451 原理としては、　余りが負数にならないように巧くオフセットを加えてるわけだよね 巧い方法だけど、 a b が大きい時にオーバフローの問題が起きるね。 abs*a ではなくて aよりも少しだけ大きい　bの倍数　を計算させた方がいいのでは？ この場合 >>436 のように座標計算に使うのだから、　マッピングモード設定 時に予め計算させておけばいい 457 名前：434 [2006/03/10(金) 22:56:56 ] ああボケてるな　マッピングモード設定 時にはaが判らないのだから予め計算出来る筈がない 458 名前：デフォルトの名無しさん [2006/03/10(金) 23:12:33 ] 学校の宿題なのですが、 廊下にたっていて、向かい側の壁にはたくさんの開くドア又は開かないドアA,B,C。。。。が無限にあって、 それを開くかどうか確認したい。 スタートはAとーAの間にいる。 。。。｜D｜C｜B｜A｜−A｜−B｜ーC｜−D｜。。。っとドアが続く 最初に地点から一番近い、開くドアを見つけたいが、動く距離をｘとして、 距離の総和がO(x)ペースになるように探したい。 例えば、A,−A,B,−B,C,ーCの順番で探していくと、 動く距離が、１、２、３、４、５,...nとなり、距離の総和は1/2*(n)*(n-1)となり、 O(X^2)のペースになるから駄目である。 っていう問題なのですが、何か良い探し法、アルゴリズムありますかね？ 459 名前：434 [2006/03/10(金) 23:13:40 ] aよりも少しだけ大きい　bの倍数 だけど ( abs(a/b)+1)*b でどうだろ？ 除算が遅いなら　| b|をシフトしていって |a| を超えた所でもいいか 460 名前：434 [2006/03/10(金) 23:21:43 ] >>458 で、開いてるか開いていないかの確率はどの程度なの？ というか確率を仮定して 右方に N1内で調べてみてなければ右側にN2個調べて　見つかる確率を求めてみたら？ 右側で M番目に開けば左側でM番目まで調べ調べればいいでしょ 461 名前：デフォルトの名無しさん [2006/03/10(金) 23:29:11 ] 確率は問題には確定されてないです。 それも考えたのですが、例えば、3つずつの固まりで調べていくとして、 C,B,A,-C,-B,-A, F,E,D,−F,−E,−D 距離を考えていくと、 （３＋１＋１）＋（３＋１＋１）＋ （６＋１＋１）＋（９＋１＋１）＋、、、 となって、総和はどうなるのでしょう。。。 462 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 23:40:17 ] 初期位置より右側を線形探索形に (-A,-B,-C,...) するようにして 初期位置より左側を A , C , E と２個おきに移動 して末端 n で（奇数個偶数個で微調整か？） .... F D B と戻ってくれば O(x) っぽくならない？ 463 名前：434 [2006/03/10(金) 23:47:52 ] だいたいこういうのは2倍づつ調べるのを増やすんだろうけどなあ 464 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 23:51:11 ] >>458 左の方を一つ探す「A」 右の方を二つ探す「-A, -B」 左の方を四つ探す「B, C, D, E」 右の方を八つ探す「-C, -D, -E, -F, -G, -H, -I, -J」 この要領でいけないかな。 465 名前：デフォルトの名無しさん mailto:sage [2006/03/10(金) 23:55:52 ] >>458 ＞A,−A,B,−B,C,ーCの順番で探していくと、 ＞動く距離が、１、２、３、４、５,...nとなり、距離の総和は1/2*(n)*(n-1)となり、 ＞O(X^2)のペースになるから駄目である。 「調べないけど移動してる」に　オーダーのコストかかってる？ 466 名前：デフォルトの名無しさん [2006/03/11(土) 00:06:37 ] ＞＞４６４ そうすると、kブロックに区切って、 (1)+(1+1)+(3+1+1+1)+(7+1+1+1+1+1+1+1)+(15+1+1+1+1+1+...)+ = 1+1*2+3*2+7*2+15*2+....+? 467 名前：デフォルトの名無しさん [2006/03/11(土) 00:08:01 ] 立ち止まる＝調べる、 動く距離＝そこで調べるの意味だと思います。 468 名前：デフォルトの名無しさん mailto:sage [2006/03/11(土) 00:31:55 ] >>464で、x番目に調べるまでの距離の総和をf(x)とすると、 f(2^n-1) = 2*Σ{i=1..(n-1)}(2^i-1) = 2*((2^n-2)-(n-1)) <= 2*2^n 2^(n-1) <= x <= 2^n-1のとき、 f(x) <= f(2^n-1) <= 2*2^n = 4*2^(n-1) <= 4*x よってO(x) 469 名前：デフォルトの名無しさん [2006/03/11(土) 01:10:36 ] ＞＞４６８ なるほど。 助かりました。 ありがとうございました。 470 名前：デフォルトの名無しさん mailto:sage [2006/03/14(火) 22:27:00 ] (0,1)における実数の集合が、可算無限集合ではないことを背理法と対角線論法を使って証明するやつだけど、 いまいち何やってるか分からないんだよね。 分かった気にはなるけど、どうもしっくりこないっつうかなんつうか。 他に証明方法とかあるのかね？ 471 名前：デフォルトの名無しさん mailto:sage [2006/03/14(火) 22:38:27 ] >>470 有理数列と実数の部分集合に1対1の対応が作れる 有理数列は自然数→有理数の写像とみなせる 自然数→有理数の写像の濃度は アレフ0^アレフ0 ＝ 2^アレフ0 アレフ0 ＜ 2^アレフ0 （ある集合の濃度が N のとき、その冪集合の濃度は 2^N、 　ある集合とその冪集合の間にはどうやっても全単写が作れない） なので、可算濃度＜実数の濃度 472 名前：デフォルトの名無しさん [2006/03/16(木) 13:32:51 ] 冪集合がわからんヒトがいると見た。 473 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 08:50:19 ] 数学板から誘導されて来ました。 QRを解析するプログラムを作ろうと思っているのですが、 誤り訂正複合のリード・ソロモン符号の複合の仕方が分かりません。 R=(r0,r1,r2,r3...,r25) R(x)=(r0+r1x+r2x^2+...+r25x^25) ここにri(i=0〜25)は、GF(2^8)の元とする。 とあり、r0-r25に間違っていないデータ（0-255）を代入しているのですが、次のシンドロームを求める式でシンドロームが0になってくれません。 シンドロームSiを求める式 S0=R(1)=r0+r1+r2....+r25 S1=R(a)=r0+r1a+r2a^2....+r25a^25 データをr0-r25に代入して、それらをGF(2^8)の法100011101（a^8+a^4+a^3+a^2+1）で割っているのですが0になりません。 もう数日煮詰まっています。お願いします。何方かご教授して下さい。 474 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 09:42:13 ] >>473 誰かのコードを参考にするといいよ 例： isw3.kankyo-u.ac.jp/project/2004/project/1013063.pdf 475 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 11:04:44 ] >>474さん、ありがとうございます。 ありがたく拝見させてもらいましたが、残念ながら書き込みの処理しか載っていませんでした。 （書き忘れて申し訳ございませんが、473で書いた部分はQRを読み取る部分の処理です） 他にもあるかもと思って「誤り訂正　QR」などで検索を掛けてみましたが、書き込みに関する部分ばかりで、 読み取り解析に関するサイトは見つかりませんでした。 JISの企画書もシンドロームを求めるとしか書いてありませんし、もう、完全に行き詰っています。 どんな些細な事でも結構ですので、アドバイスを頂けないでしょうか。 お願いします。 476 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 11:27:53 ] >>475 その部分のコード晒してみて、 + は　XORの事とか　　掛算は足算の事とか、そこらへんは判ってるんだよね？ 477 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 11:37:40 ] >>475 じゃあココのは見たの？　オレは中身はみてないけど sourceforge.jp/projects/qrcode/ 478 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 12:37:08 ] >>476さん、ありがとうございます。 ＋は足し算で、掛け算は掛け算で計算していたので、直してみましたが、やはり０になってくれません。 コードはこのようになっています。 //求められたデータ語 int[]Data={ 32, 65, 205, 69, 41, 220, 46, 128, 236, 42, 159, 74, 221, 244 ,169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61 }; //a指数→整数 int[] a_int={1,2,4…（以下続いています）}; public void Syndrome(){ //求めるシンドロームの数を決定 int[]S=new int[8]; for(int i=0;i<S.length;i++){ for(int d=0;d<Data.length;d++){ S[i]=S[i]^(Data[d]+a_int[(d*i)%255]); } } } >>477さん、 このプログラムは知りませんでした。早速今から落として見て見たいと思います。 ありがとうございます。 479 名前：デフォルトの名無しさん mailto:sage [2006/03/18(土) 13:24:07 ] >>478 やっぱり計算式が違うよ >>474のcalculate.javaをよく見てみて 480 名前：http://www.vector.co.jp/soft/win95/util/se072729.html mailto:http://www.microsoft.com/japan/windowsxp/64bit/default.mspx [2006/03/18(土) 19:44:49 ] TextSS　のWindowsXP(Professional)64bit化おながいします もしくは64bitにネイティブ対応したテキスト置換ソフトありますか？ 481 名前：デフォルトの名無しさん mailto:sage [2006/03/19(日) 23:37:58 ] ラジアンをぶつかった壁に対して面対称で XだけYだけ90°ひっくり返すにはどうすればいいの？ 482 名前：デフォルトの名無しさん mailto:sage [2006/03/19(日) 23:56:28 ] いや言ってる意味が良くわかりませんから 483 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 00:24:24 ] ビリヤードか 484 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 00:45:38 ] vy = -vy; vx = vx + 90/180*PI 485 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 11:03:21 ] >>483 ビリヤードなら90度というのがどこから来るのか・・・・ 486 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 16:05:35 ] 必ず90度で跳ね返るPONGでも作ってみるか 487 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 16:42:10 ] その場合、速度はどうなるのん？ 488 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 17:22:36 ] 必ず180で反射するコーナーリフレクターは実在するけど 必ず90度ってどうやるんだ？ 489 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 17:24:03 ] 三角関数？簡単なブロック崩しだったらそんなの使わんぞ つーか、玉の軌道をＸ軸かY軸で反転すれば問題なし。 490 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 18:44:58 ] さて、ここで唐突に「三角関数」とか出てきたわけだが 491 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 18:52:43 ] 「プログラマが今まで「これはすげえ」と思ったｹﾞｰﾑ」 の149からの流れがここに？ pc8.2ch.net/test/read.cgi/prog/1134791216/149- 492 名前：デフォルトの名無しさん mailto:sage [2006/03/20(月) 19:24:06 ] ttp://www.dango-itimi.com/blog/archives/2005/11/1.html 斜面への衝突判定と反射1 493 名前：デフォルトの名無しさん [2006/03/23(木) 07:46:12 ] 学校の宿題なのですが・・・。 HはHASH関数で、p は(p-1)/2も素数であるような素数。 aは、1<a<p-1も満たす整数。 g=a^2(mod p) H(x,y,z,t)=g^(xy+zt) (mod p) このとき、Hはone-way関数であるが、collision-free関数ではないことを示せ。 なのですが、どなたか分かる方、助けてください。 494 名前：デフォルトの名無しさん mailto:sage [2006/03/23(木) 12:28:39 ] 定義は知らんがアバウトに考えて、 剰余が絡んでる段階で多対一関数だから1方向だろうし collision-freeではなさそうだわな。 証明は2つの値が実際に1個の値になる例を計算すればいいんじゃね？ 495 名前：494 mailto:sage [2006/03/24(金) 16:59:01 ] エエカゲンに書いたのに誰も突っ込まない…。 ほ、放置プレイ？ 496 名前：デフォルトの名無しさん mailto:sage [2006/03/24(金) 18:30:11 ] 定義がないのでなんともはや 497 名前：デフォルトの名無しさん [2006/03/28(火) 08:18:12 ] sin(x)/x Ｑ１　 って関数に名前を付けたいけど適切な名前は？ Ｑ２　　浮動小数点なので計算方法は単純に 　　　　 abs（x)<0.0001 の時は1-x*x/6 でなければ そのまま計算でいいよね？ 498 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 08:53:02 ] キャラの座標は 左上と真ん中 どちらのポイントを保持して使うべきですか 499 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 08:55:22 ] >>497 sine_x_per_x() 500 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 09:01:48 ] >>498 いまどきどこでもいい。 処理によって必要な座標は違う。例えばサイドビューのジャンプアクションなら足元座標も使う。 必要な座標を計算するメソッドがあればそれでよい。 数学関係ない。 501 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 12:19:04 ] >>497 それは一般的にsinc関数と呼ばれている。 502 名前：497 mailto:sage [2006/03/28(火) 12:41:21 ] >>501 ありがとう 503 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 17:19:04 ] >>498 RPGの座標には、マップ上の座標と表示する座標があるが、 マップ上の座標で保存する。 表示する時には、表示する座標に変換して表示する。 504 名前：デフォルトの名無しさん mailto:sage [2006/03/28(火) 17:58:28 ] >>503 キャラといえばRPGしか連想できないゲーマーですか?

---

---

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

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