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

1 名前：デフォルトの名無しさん [04/09/05 16:22] プログラムに必要な数学、算数に関する話題について 語りましょう。TIPS/Q&Aスレです。 371 名前：デフォルトの名無しさん [2006/01/09(月) 00:38:04 ] 答えが来るかわからんけど マージソートについて勉強してます マージソートの配列の分割についてなんですけど 例えば8だけの場合は 4 4 2 2 2 2 1 1 1 1 1 1 1 1 とだけ分割できると思います。 ですが例えば要素が34の場合 17 17 と一回だけ分割すると素数になってしまいます。 更に極端にしますと 7や23などの要素の個数の場合はどう分割するのでしょうか・・ まだ勉強初めて1日だけなんでアレですが参考のページでもあると嬉しいです 372 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 00:49:45 ] >>371 そりゃ、8と9に割ればいいじゃん。 373 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 00:54:24 ] >>372 しかしその場合併合(マージ)しようとするとどんな風になるのでしょうか グーグル先生のイメージ検索はエレメントの個数が偶数ばかりのもので・・ 勉強してきます(´･ω･`) 374 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 00:56:37 ] どんな感じってソートするだけだろ。 375 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 03:02:59 ] >>373 べつに偶数のときとかわらん。 違う数に分割されたからといって コードの何処も変える必要なんかない。 そんな必要があったら そもそもマージソートじゃない 376 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 10:30:58 ] >371 例えば9の場合、 4, 5 (2, 2), (2, 3) ((1, 1), (1, 1)), ((1, 1), (1, 2)) ((1, 1), (1, 1)), ((1, 1), (1, (1, 1))) と分割すればいい。 てか図解すると並列に見えるけど、実際の処理は再帰的に行われるから、 部分的に階層が深くなっても問題ない。 ttp://oku.edu.mie-u.ac.jp/~okumura/algo/archive/algo.lzh の mergsort.c 読めば解るよ。 377 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 13:56:17 ] >>373 つーか、聞く前に一度自分で実際にやってみ。 マージって全然個数の違う2つの列相手にもできるから。 例えば極端な話 1, 16 とかで分けてもマージできる。 378 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/01/23(月) 00:20:53 ] シュレーディンガーの猫というのは簡単に言うとあれだろ 堀江由衣の処女 379 名前：デフォルトの名無しさん mailto:sage [2006/01/23(月) 04:26:20 ] 　　　　　　　　 ,,-‐----‐､　, -'"`￣￣"`''-,__, --‐‐-.., 　　　　　　　 /　 、ﾞヽ､ ‐-'´ 　　　　　　　　　ヽ‐- / /　 　ヽ 　　　　　　,/´　..,　ヽ,,l_),'　　　　　　 　 　　　 　'､,ﾄ/ /　　　 ヽ 　　　　　/　　　　ヽ,r' l　　　　　 .,､z:ｭ､,_.　　,､=,ﾞ.-〈__r,'､　　　ヽ_ 　　　　_.l　　　 ヽ」 　 , l.　　　　　´ ,r'ャ､`'　i'rｬ;|　 　 ﾞ‐ヽ､＿,,　 /l 　　　 ,l l|　　−'´ll　　,ll ヽ. 　 　 　''｀¨¨´ 　 ヽ　|　　 　.,//ﾞl　　 //＼ 　　　 l｀l|　　　　 l|ヽ　 ヽ 入　　 　　 　 ,ィ _. 　', l　　　 |l 　　　// 　　} 　　　ｌ　 ＼　　　 l| ,l　　ヽ_.　　　　　 '　`'ﾞ`'‐'iﾞ ,'　　　　|,l　 　//　　　 l 　　ﾊﾞｶｼﾞｬﾈｰﾉ 　　 /　　　'＼ 　 l|｀l　　　l ヽ`'.　　　 ,∠.ニﾌ /　　　　l ヽ　//　　 　　| 　　,l　　　　　'＼ l|　.lヽ＿l　` ､ ､ 　　い.... ,' /＿__／　|　 ∨/　　 　　 ,} 　　|　　　　　　　ヽl　| 　　　,| .ヽ',　.ヽ`二ﾌ.,' ヽ　　　　 ,|　　　　　 　 　 ,l 　　|　　　　　　　　　 l 　　　,l　 　' .､,＿｀,.ィ　　l ＼　　　　　　　　　　　/ 　　ヽ　　　　　　　　 　|　　　＼.　　 　ヽ/　 　 l　 ヽ　　 　　　　　　／j 　　　 ＼　　　　　　　 /　　　　 ヽ　　　　ヽ　　|　　 l　　　　　 　　 　/ 　　　　 ﾞl＼..　　　　 /　　　　　　ヽ　　　　　ヽj　　　|　　　　,　　　 / 　　　　　ヽﾞ　　　　　 　　　　　　　 ヽ　　　　　ヽ 　　ヽ　　/　 　　,l 　　　　　　ヽ、　　　　　　　　　　　　 ヽ　　　　　l　　　}　/　　　 ,r 　　　　　　　 ヽ　　　　　　　　　　　　　ヽ　　　　 |　　/′　,,...'' 　　　　　　　　｀'':..､　　___　＿__,.．-..　　 |,　　　 ,l　,　 :..-‐'"´ 　　　　　　　　　　　￣ /lr‐‐‐'--､_.....　　ｌ_,.．-'''""'- " 380 名前：デフォルトの名無しさん mailto:sage [2006/01/30(月) 23:54:04 ] 原点(0,0)を中心とした半径Rの円がある 中心点から角度θの軸を考え、横2W縦2Hの長方形の中心がこの軸を移動するとして 長方形の頂点が円周上にくる点の座標は？ 381 名前：380 mailto:sage [2006/01/30(月) 23:55:32 ] >>380書き忘れ 長方形は円の内側にあるものとする 382 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 00:41:23 ] >380-381 人にモノ聞く態度じゃねぇな。 出直して来い。 383 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 09:44:41 ] それになんか問の内容も何がいいたいかよーわからん。 もしかして日本語が不自由な方なんでわ？ 384 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 10:41:19 ] ここは宿題スレじゃないんじゃね？ 385 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 18:07:46 ] 正方形じゃねーのかな・・・ 386 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 18:42:49 ] プログラムじゃなくて普通に算数（三角比を使うにしても数学ってほどじゃない）だなぁ。とりあえず解いたんで書く。 r=-(Wcosθ+Hsinθ)+√(R^2-(Wsinθ-Hcosθ)^2) として (rcosθ+W, rsinθ+H) …(1) θの範囲は0≦θ<π/2だけどね。他の範囲は(1)式にある符号が変化するだけのはず。 387 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 08:22:33 ] >>386 それだと、 W = H = 0 の時にしか、長方形の頂点が円周上にこないんじゃない？ 「点の座標」ってのが長方形の中心だとしても頂点だとしても。 多分やつは問題を理解できてないんだろうなあ。 2Dゲーム作ってて、円形フィールドからはみ出さないようにしたい、と推測したがどうか。 388 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 17:20:04 ] >>387 それだと浮動小数点でやってる場合、 点の座標を求めて＝で判別したらイタイ目見そうだ。 （丁度等しくならなかった時に判定をスリ抜ける。） 不等式で「内側」の度合い評価できる基準を見つけないと。 389 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 17:29:09 ] 2Dゲームの判定に使う程度なら たぶん長方形の外接円で判定してごまかすのが楽なんじゃないかなぁ。 中心点同士の距離と半径だけで判定できる。 2乗ノルムでやれば平方根もいらないし。 もし精密にやりたければ上記の方法で簡易判定して明らかに接触しない事例を除いた上で 拙速するかもしれないケースだけ長方形を構成する線分が交差するかどうかを判定すれば いいのかな。 390 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 17:31:22 ] で、この場合長方形の軌道は無視して一般化できて 軌道は具体的に長方形の位置を計算する以外は無関係だね。 391 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/02/04(土) 00:33:27 ] log(2)(x-1) + log(1/2)(3-x) <= 0 //logの真ん中の()は底 を満たすxの値の範囲は a < x <= b このaとbと導かれる過程がわからん。 包茎じゃなくて東京六大学に在学中か卒業した人だけ答えてくださーい。 392 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 11:10:14 ] ヒント： a<x の部分は真数条件から 393 名前：デフォルトの名無しさん [2006/02/05(日) 13:36:53 ] 　　　　　　　　　　　　　　　　　　　　　　　　　　　＿＿＿　　　　＿ 　　 |￣|　 ／>　　＿　　　　　　　　　　 ＿　　　/　　 ＿|　　　｜　| 　／> 　　 | 　|／／　　 ＼ ＼　　　__　　　／ ／　　　＼　＼.　　 　　|　 |／／ 　　 | 　　 ＼　　　　 ＼ ＼／　＼／ ／　　　 　 　〉　ヽ.　　　　|　　　＼ 　　 | 　|＼　＼　　　　 ＼　／＼　／　　　 |￣￣　 　ﾉ　　　　 |　 |＼　＼ 　／::::/'" 　￣ヾi 　　　／　￣￣　＼　　／::::/'"￣￣ヾi　　 ／　　￣　　 ヽ 　|:::::::|　,,,,,_　 ,,,,,,|　　　| 　^　　　^　 |　　|:::::::|　,,,,,_　 ,,,,,,|　　| 　^　　 　^　 | 　|r-==（　｡);（　｡)　　　|　>ﾉ(､_, )ヽ､.| 　 |r-==（　｡);（　｡) 　 |　>ﾉ(､_, )ヽ､.｜ 　(　ヽ　　:::__)..:: } 　　　!　! -=ﾆ=- ﾉ !　　(　ヽ　　:::__)..:: }　　 !　! -=ﾆ=- ﾉ ! 　 ヽ　　ー==　;　　　 　 ＼ ｀ﾆﾆ´ ／　　　ヽ　　ー==　;　　　 ＼　｀ﾆﾆ´ ／ 　　　＼＿＿_ !　　　　　　　￣￣　　　　　　 ＼＿＿_ !　　 　 　 ￣￣￣ 394 名前：デフォルトの名無しさん [2006/02/06(月) 04:30:36 ] 東京六大学ってスポーツリーグだろ？ あんなかでまともな偏差値誇ってんのは 東京 慶應 早稲田 だけだろ あとの三つは……やめた。 395 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 11:34:15 ] >391 名大出のしがない漏れは 頑張って答えようとしたりせずにニヤニヤしてれば好いわけね？ 396 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 19:59:06 ] 包茎云々は法政のことかいのう・・・ 397 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 22:59:21 ] 法経学部？ しかし>391ってまるっきり高校レベルじゃないか 398 名前：デフォルトの名無しさん mailto:sage [2006/02/08(水) 12:53:00 ] >>397 シッ！　皆わかっててニヤ(・∀・)ニヤしてるんだから！ 399 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/02/08(水) 18:49:12 ] 高卒･大卒なのにセンター試験の問題すら答えられないんだね;) 400 名前：デフォルトの名無しさん mailto:sage [2006/02/09(木) 10:40:54 ] >>399 イヤー、オヂサン参ったな。ナント院卒だが答えられないぞ。 >391が出した問題の最後に示された条件： > 包茎じゃなくて東京六大学に在学中か卒業した人 を満たすことができないからなー。何せ漏れは重度の冠頭包茎だし、 名古屋生まれの名古屋育ちで大学も院も名古屋大学だからな。 漏れがこの問題に答えるためには 東京6大学（慶応、上智、東京、明治、立教、早稲田）のどっかに入らないと イカンわけだろ？ いやー回答者の資格に制限がある問題は難しいわ、ホント難しい、 全然答えられそうにないよｗｗｗ 最近のセンター試験ってこんな答えるのが難しい問題出すの？（・∀・） 401 名前：デフォルトの名無しさん mailto:sage [2006/02/09(木) 10:43:17 ] 解らないっつってた本人が捨て台詞。 相変わらず莫迦なコテだな。 402 名前：400 mailto:sage [2006/02/09(木) 11:08:11 ] あ、書き忘れてたけど漏れが問題に答えるためには My包皮も切らないとイカンのかー。やっぱ難しいわ。 漏れ包皮ついてるほうが好きだし、 臆病者だから体の一部切るなんてコワいしなー。 403 名前：マイク ◆yrBrqfF1Ew mailto:sage [2006/02/09(木) 17:15:47 ] >>401 エセ学歴な上にノータリンですか?(▽ >>400 名古屋はもういいよ。 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、 　ある集合とその冪集合の間にはどうやっても全単写が作れない） なので、可算濃度＜実数の濃度

---

---

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

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