05/11/15 15:43:57
>>157
ありがとうございます！m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ
再帰の途中で覚えさせる方法が分からなくて困っていました。
なるほど、ああやって割り込むんですね。本当に勉強になります。
solve(i, start, adj, visited)を二回呼んでるのは後でなんとかします。
ああ、もっと賢くなりたい。←自分
160:フローチャート
05/11/23 20:25:34
価格Ａ，Ｂの商品をそれぞれＸ，Ｙ個、購入する場合の
支払い金額を計算するフローチャートを示せ。ただし、値引き率８％と
消費税５％を考慮すること
161:デフォルトの名無しさん
05/11/23 20:28:11
>>160
そりは難しい課題だねえ。
まずはフローチャートを描くルーチンを作成しないと。
環境は何？ まさか、線を引くルーチンから作らなくちゃいけない？
162:デフォルトの名無しさん
05/11/26 17:42:03
その前に有理数体での加減乗除を定義しないと。
また、有理数の円未満の端数処理をどうするか検討しないとな。
切捨て？切りage？四捨五入？設定で選択できるようにしないと
実用に耐えないかもよ。
163:デフォルトの名無しさん
05/11/26 20:15:28
意地悪なやつらめ。そんなおまえらが好きではあるけど。
164:デフォルトの名無しさん
05/11/26 21:21:57
まあ 137 あたりの経緯があるからな
165:デフォルトの名無しさん
05/11/27 18:06:06
>>162
有理数体上の加減乗除は自明じゃねーの？
166:デフォルトの名無しさん
05/11/27 21:26:38
ていうかコンピュータ上では有理数全てを表現できないし
167:デフォルトの名無しさん
05/11/27 21:35:56
ディジタルコンピュータ上ではできないね。
168:デフォルトの名無しさん
05/11/27 21:45:26
全ては表現できなくても適当な位相さえ入れば十分でしょ
169:デフォルトの名無しさん
05/12/01 12:06:34
てか、実数から見たら表現できる数値なんて穴だらけだよな。
170:デフォルトの名無しさん
05/12/01 18:13:16
つ 区間演算
171:デフォルトの名無しさん
05/12/04 01:41:03
配列nに対してn-1個の値があり、残りひとつはNULLでも0でもいいのでデータとしては何も入ってない状態。
その配列nの中のn-1個の数列を配列nの中だけでソートしたいのですが何かいいアイデアないでしょうか？
つまりデータ構造やポインタは勿論、
二分木や多分木を使ってヒープも駄目ということです。
172:デフォルトの名無しさん
05/12/04 02:00:23
バブルソートなりクイックソートなり
173:デフォルトの名無しさん
05/12/04 03:54:54
>171
状況がよくわからん。
具体的に。
174:デフォルトの名無しさん
05/12/05 16:33:28
カタカナの「ノ」の形の離散データの極率を求める数値計算法ってありますか？
書物で調べたりググったりしていますが、見つかりません。
175:174
05/12/05 16:35:59
極率 ではなく 曲率 でした。
176:デフォルトの名無しさん
05/12/05 16:40:06
二次回帰分析とかって話?
177:174
05/12/05 16:58:41
>>176
レスありがとうございます。
二次回帰分析ですと、y=a(x^2)+bx+c のa,b,cを決定するとこになると思われます。
今やりたいことは、例えば y = exp(-3*p)+q^2 に対応する離散データから
(p, q)を求めるというものです。
exp(x)は２次関数ではありませんが、例えばテイラー展開等で近似をすれば、
適応出来る物なのでしょうか？
178:デフォルトの名無しさん
05/12/05 19:46:30
最小二乗フィッティングだね．
理論的には，s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を
データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和
φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2
を最小化する s_1, ..., s_n を求めてやればいい．
で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い．
ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず．
179:デフォルトの名無しさん
05/12/05 19:50:09
画像調整のガンマをスクロールバーで実装したいのですが、
イマイチ正確な定義が分かりません。
それか、組み込めるライブラリどこかに落ちてないでしょうか？
180:174
05/12/05 20:15:07
>>178
詳しいレスありがとうございます。
今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が
最小になる(p, q)の組を解としています。
勾配法、アニーリングを調べてみて、検討してみます。
181:デフォルトの名無しさん
05/12/05 20:17:32
>>179
質問の意味がわからないけど多分スレ違い。
・言語と開発ツールは何を使ってるのか
・具体的にやりたいことは何か
・今自分は何がわからないのか
この三点をはっきりさせて、適切なスレに行って聞いてください。
182:デフォルトの名無しさん
05/12/05 21:10:48
あるデータ列に
Y = (A(X^3)+B(X^2))/(CX+D)
の最小自乗法を適応するばあい、
残差の２乗和 S に対して
A, B, C, Dそれぞれで偏微分したもの = 0
の連立方程式を解いて、
A = Σを含む式
B = ...
C = ...
D = ...
とすれば良いのでしょうか？
簡単な式の最小自乗法しか使っていなかったので、
そのまま適応して良いものかどうかが分かりません。
お願いします。
183:デフォルトの名無しさん
05/12/05 21:18:39
>>182
OK．
ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので
出した解が本当に良いフィッティングになってるかは十分議論する必要がある．
184:182
05/12/05 21:30:11
>>183
ありがとうございます。勉強になります。
185:アルゴリズム
05/12/06 10:20:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する
186:デフォルトの名無しさん
05/12/06 10:59:37
select average(weight), average(height) from DATA where (age <= 30);
187:デフォルトの名無しさん
05/12/06 12:50:40
>185
スレタイくらい嫁。
くだ質スレか宿題スレ池や。
188:デフォルトの名無しさん
05/12/06 20:36:58
>177
エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。
ところでexp（）の形になると判ってるなら、logを取ったらどうなる？
189:デフォルトの名無しさん
05/12/06 21:51:46
プチ統計学講座だなｗ
190:デフォルトの名無しさん
05/12/06 22:09:54
>>188
ヒント：Windowsとは限らない
191:デフォルトの名無しさん
05/12/06 22:28:03
ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。
192:デフォルトの名無しさん
05/12/06 22:34:45
>>190-191
ヒント：そもそも汎用機とも限らない 例：宇宙計算用スパコン
だからこそのアルゴリズムスレだろ？
193:デフォルトの名無しさん
05/12/06 23:14:51
だからlogとったらどうなるかと聞いてみたんだけど
194:デフォルトの名無しさん
05/12/06 23:30:44
だから前半にだけ突っこんだんだけど
195:デフォルトの名無しさん
05/12/07 19:22:24
まぁまぁ、次のネタを待ちましょう
196:デフォルトの名無しさん
05/12/07 19:55:37
上にも最小自乗法の話題が出ていますが･･･
y=(A(x^3)+B(x))/(C(x^2)+D)
の関数に最小自乗法を適応することは出来ますか？
残差の２乗和が最小になる(A,B,C,D)を見つけるわけですが、
例えばCで偏微分して=0となるCは、単なる極地のCであり、
それが極小かつ最小となるわけではありませんよね？
197:196
05/12/07 19:57:51
あれ！？
よく見たら>>182とまったく同じ式でした･･･。
当方、学生ではないので課題とかでもないのですが。
同じ書物を読んでいるのかしら。
>>183を参考にします。
無視してください。
198:デフォルトの名無しさん
05/12/07 20:29:05
フローチャートしか知らない
199:デフォルトの名無しさん
05/12/08 10:14:07
二次元配列と、
その中の３つの点で定義される三角形があって、
ある点がその中か外か判定するアルゴリズム教えて下さい。
200:デフォルトの名無しさん
05/12/08 11:58:18
>>199
(0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、
(1,1) という点がその三角形の中にあるかどうかということだよな？
1)与えられた3点が三角形を構成するかどうかを吟味。
2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。
3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。
4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。
201:デフォルトの名無しさん
05/12/08 12:26:41
そのまんまじゃん
202:デフォルトの名無しさん
05/12/08 13:04:30
ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、
できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、
どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが
最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ
*リュックサックに全ての荷物を入れて旅行する人のこと。
問1
0/1 ナップザック問題とは何か？
問2
全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん
な問題となるのだろうか？
問3
アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの
か？
問4
ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考
書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか
記述せよ．
203:デフォルトの名無しさん
05/12/08 15:35:02
>>202
ここは君が来るべきスレでは無いよ。
204:デフォルトの名無しさん
05/12/08 15:59:27
>>203
いいじゃんべつに。
お前の個人的な感情は出さなくてもいいよ。
そんなもの読んでいる人間には全く価値がないから。
文句があるならどのスレにいけ、ぐらいは言えよ。
あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。
205:デフォルトの名無しさん
05/12/08 18:15:33
>>204
つまんないﾈﾀ書くのも自由だし
それを批判するのも自由。
206:デフォルトの名無しさん
05/12/08 18:37:18
座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？
207:デフォルトの名無しさん
05/12/08 18:40:49
>>205
自重しろよ。
自由ではないんだよ？あまりひどいとアク禁だ。
208:デフォルトの名無しさん
05/12/08 19:52:21
>>206
3点から辺の長さ求めてHeronの公式、とか。
209:デフォルトの名無しさん
05/12/08 20:01:43
三点のベクトルが v1, v2, v3 のとき
[v1-v2, v3-v2]/2 の絶対値が面積になるね。
[x,y] は x と y の外積ね。
210:デフォルトの名無しさん
05/12/08 20:02:07
>>206
ある点を原点に移動させるように全体を並行移動させて、
(0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを
使った方が簡単かも。
３点が三角形が作られない位置に無いことを確かめてからね。
211:デフォルトの名無しさん
05/12/08 20:03:50
実は
（>>182の式）≠（>>196の式）
である件について
212:デフォルトの名無しさん
05/12/08 20:55:54
>>206
URLﾘﾝｸ(www.tensyo.com)
の多角形の面積でやれば？
213:デフォルトの名無しさん
05/12/08 23:07:36
>>199
>>99,>>107-108
>>204
>>187
てか、質問する前にスレ内くらいは読もうぜ？
214:デフォルトの名無しさん
05/12/13 18:24:45
>>206
でも、3点とも座標がわかってて位置不明ってどゆこと？
215:デフォルトの名無しさん
05/12/13 19:24:25
>214
「固定座標じゃない」って意味だろ。
確かに意味は解らないが、気持ちは伝わってきた。
216:デフォルトの名無しさん
05/12/13 20:30:04
ヘロンの公式のことをたずねているの？
217:デフォルトの名無しさん
05/12/13 20:39:02
辺の長さが与えられてるわけじゃなく、頂点座標だから
ヘロンの公式をわざわざ使うより
素直に台形公式による閉曲線積分
218:デフォルトの名無しさん
05/12/13 20:56:04
>>217
頂点座標？閉曲線積分？言葉はちゃんと使おうぜ
219:デフォルトの名無しさん
05/12/14 01:18:24
>>214
任意の三点ってことだろ。
220:デフォルトの名無しさん
05/12/14 11:53:04
三角形なんだから、3点を P, Q, R として、
2つのベクトル a ＝ PQ、b ＝ PR を定義。
(1/2) |a × b|
ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。
っつーか、ぐぐれ。
URLﾘﾝｸ(homepage2.nifty.com)
221:BASIC
05/12/14 15:57:56
次のプログラムをＢＡＳＩＣで作成しなさい
データを１件ずつ、ユーザ定義関数を利用して
「公共料金」を計算させることにします
＜水道料金の計算＞
基本料金：1250円 定量制料金単価は
・使用量が10立方米以下であれば80円／立方米
・ 〃 10立方米超20立方米以下であれば185円／立方米
・ 〃 20立方米超50立方米以下であれば205円／立方米
・ 〃 50立方米超100立方米以下であれば240円／立方米
・ 〃 100立方米超200立方米以下であれば275円／立方米
・ 〃 200立方米超であれば310円／立方米
（計算例）
使用量が8立方米であれば、1250＋8×80
使用量が15立方米であれば、1250＋10×80＋(15－10)×185
＝2050＋(15－10)×185
使用量が40立方米であれば、1250＋10×80＋10×185＋(40－20)×205
＝3900＋(40－20)×205
使用量が75立方米であれば、1250＋10×80＋10×185＋30×205＋
(75－50)×240＝10050＋(75－50)×240
使用量が120立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240＋(120－100)×275＝22050＋(120－100)×275
使用量が230立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240 ＋100×275＋(230－200)×310 ＝49550＋(230－200)×310
222:デフォルトの名無しさん
05/12/14 15:58:42
作成しなさい、だってさ↓
223:デフォルトの名無しさん
05/12/14 16:01:00
｜ ∧＿∧
｜. (･ω･` )ｽﾙｰ
｜ｽｽ… /J J
↓ ,,, し―-J
224:デフォルトの名無しさん
05/12/14 16:51:10
アルゴリズムじゃねえな
225:デフォルトの名無しさん
05/12/14 19:15:46
アゴリズムだな
226:デフォルトの名無しさん
05/12/15 00:36:36
アルゴリズムじゃねえって！
227:デフォルトの名無しさん
05/12/15 04:40:03
アルゴリズム体操！アルゴリズム体操！
228:デフォルトの名無しさん
05/12/16 15:42:28
立方米って一般的なのか。
m^3と書かないの。
229:デフォルトの名無しさん
05/12/16 15:51:32
>>228
メートル=米、だからね。
他にも糎とか粍とか。
でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。
#平米は割と一般的でしょ。
230:デフォルトの名無しさん
05/12/17 12:32:02
口頭ではよく「へーべー」と言うな。
俺の父親が。
231:デフォルトの名無しさん
05/12/17 12:34:10
なんでメートルが米なの？？その由来は？
232:デフォルトの名無しさん
05/12/17 12:58:32
亜米利加 と同じじゃないの？ メの元の漢字だと思ってたけど
URLﾘﾝｸ(www.fudemojiya.com)
によると 女 らしい
233:デフォルトの名無しさん
05/12/17 13:05:23
明治時代か江戸末期に「メートル(或いはメーター)」という音に似ているから当てたんじゃないの?
他にもグラムやインチなどにも当てられた漢字があることだし。
234:デフォルトの名無しさん
05/12/17 19:27:50
URLﾘﾝｸ(freett.com)
発案した人も途中からヤケクソになっていったのだと推測
235:デフォルトの名無しさん
05/12/17 22:42:29
>>234
そこまでして漢字にせんでもええやん…とおもた。
236:デフォルトの名無しさん
05/12/18 03:23:45
当時ハ送リ仮名ガ片仮名デアッタタメ
外来語ヲ片仮名ニ割リ当テルトイウ
発想ハ無カッタンダロウナ
237:デフォルトの名無しさん
05/12/18 04:08:19
質問なのですが、例えば、
1、２、３、４、５、４０、５０、６０、７０ といった代表値である数字があるとします。
で、例えばXがその代表値のどれに一番近いかを求めるとき
すべてを探索すれば答えはわかると思いますが、できるだけ高速に
求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、
例えばXが6だとするとまず、5が一番近いことがわかります
これをどうやって木にしたらいいのかがわかりません。
また１，２、３・・・・といっていましたが
（X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？
一致するのを探すのではなく一番近いものを探すので苦労しています。
近さの判定としてはユークリッド距離を用います。
どうぞよろしくお願いいたします
238:デフォルトの名無しさん
05/12/18 04:13:08
代表値の数列が整列されている前提ならバイナリサーチでいいのでは？
239:デフォルトの名無しさん
05/12/18 04:32:56
>>238
ありがとうございます。
バイナリサーチですと完全に一致する場合は問題ありませんが
完全に一致せず一番近いものを選択するときに問題がおきます
237の例で6に一番近いものをバイナリサーチで探そうとすると
40になると思われます
240:デフォルトの名無しさん
05/12/18 04:46:58
バイナリサーチで最終的に 40 がヒットするわけだけど、
この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。
あとはどちらに近いかを計算するだけじゃないのかな。
241:デフォルトの名無しさん
05/12/18 04:54:28
>239
最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。
n次の場合は、a=f(X,Y,...)で、aの値でソート。
242:デフォルトの名無しさん
05/12/18 05:01:13
>>240
>>241
ありがとうございます。
ｎ次の場合はうまくいかないように感じるのですが
できれば具体例を出していただけないでしょうか？
241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか
しらべて次はY、Z・・・というふうなことだと感じているのですが
例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで
Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので
あまりうまくいかなようなきがします。
間違っていたらすみません
243:241
05/12/18 05:37:33
>242
スマソ、完全に寝ぼけてた。
1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？
244:デフォルトの名無しさん
05/12/18 05:40:16
>>243
ありがとうございます。
総当りですか・・・それですと時間がかかるので
何かいい方法がないかなと思いまして
245:デフォルトの名無しさん
05/12/18 07:16:28
>>241
２次元（平面）ならボロノイ図・近傍で似たような問題がある
３次元以上だとできるかどうか知らない
総当りにしたら
246:245
05/12/18 07:17:31
>>245 の >>241 は >>237 の間違いです ｽﾏｿ
247:デフォルトの名無しさん
05/12/18 07:55:24
>>245
ありがとうございます。
ボロノイ図については知っていまして、三次元でも可能のようです。
ですが、これをどう木にすればいいのかよくわからなかったもので
何かいい方法があればと思って相談してみました、。
248:デフォルトの名無しさん
05/12/18 09:03:12
>>237
空間データベースって分野のお話だね．
望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．
ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
URLﾘﾝｸ(www.kecl.ntt.co.jp)
URLﾘﾝｸ(vision.unige.ch)
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley
249:デフォルトの名無しさん
05/12/18 10:00:28
>>248
ありがとうございます
望んだ形でデータを持っていても大丈夫です。
K－ｄ tree についてなのですが、これでは一番近い代表値に近似することはできないと
考えられます。
例えば
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のｋ－ｄ ｔｒｅｅ のところの図で説明しますと
代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に
一番近い点（一番近い代表地に近似したい点）があったとすると
これはＰ４かＰ５に近似されることになります。
実際はＰ９に一番近いのにこれには近似されないとおいうことです
木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます
しかしＲ－ｔｒｅｅというのは使えそうな気がします
ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが
なんとかがんばってみます
ありがとうございました
250:デフォルトの名無しさん
05/12/18 10:04:36
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のＲ－ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に
近似されないように感じます。
うーんどうしよう
251:デフォルトの名無しさん
05/12/18 10:05:18
一番近い点は一回では求まらないだろう。
求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。
たとえば2次元なら x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで
矩形で絞り込めばいいでしょ
252:デフォルトの名無しさん
05/12/18 10:07:59
あと、この問題は、最悪の場合は、全数検索が必要になる。
たとえば円周上に点が並んでいて、中心に近似しようとした場合など
253:デフォルトの名無しさん
05/12/18 10:17:52
>>251
>>252
ありがとうございます。
自分の中で何か新しいアイデアが浮かんできそうな気がします
が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです
どうかおねがいします
254:デフォルトの名無しさん
05/12/18 10:25:28
データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある
母点までのリンクを距離順に並べて持たせておいて
最初に検索した母点までの距離内にあるリンクだけ全検索する
検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする
255:デフォルトの名無しさん
05/12/18 10:35:34
>>254
ありがとうございます
私の理解力不足のためわからなかったです すいませんが
もう少し簡単な説明をしていただけないでしょうか どうかお願いします
256:248
05/12/18 10:53:05
>>249
二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について
コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう．
257:デフォルトの名無しさん
05/12/19 09:08:38
長いですが、NP完全について質問です。
アルゴリズムの本に
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？
"=Which of the diagrams do not contradict the current state of our knowledge
about the complexity classes P, NP, and NPC (NP-complete problems)"」
という質問があってヒントに
「これらのうちの二つのみが現在の私たちの知識と矛盾している
"=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。
「私たちの知識」とはその本に載っている
「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ
"=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」
っぽいです。
図は五つあって、そのうち
aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、
これらは明らかに矛盾しているので除外です。
eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。
URLﾘﾝｸ(www.jyi.org)
で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが
NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？)
これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。
そうだとしたらこの本の間違いなんですが…。
ここの賢い人、どうか答えてください。せめてヒントだけでも…。
258:257
05/12/19 09:19:37
あまりの必死さに図を描いてしまいます。m(__)m
c. ＮＰ
┌───┬───┐
│ │ │
│ Ｐ │ ＮＰＣ │
│ │ │
└───┴───┘
てな感じです。
259:257
05/12/19 09:23:48
度々すみません。訳し間違えました。正しくは
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」
と
「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」
です。もう後で逝ってくるつもりです。m(__)m
260:デフォルトの名無しさん
05/12/19 10:19:49
>>188
すみません
261:デフォルトの名無しさん
05/12/19 13:34:18
>>257
「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」
であって、「P≠NP」とは限らない。
262:257
05/12/20 12:17:51
>>261
ありがとうございます。
なるほど、「P≠NP」とは限りませんよね。
もしそうだとすれば選択肢は「P＝NP」しかない訳で
その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」
と解釈してよいのでしょうか？
友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？
図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。
cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。
すみません、自分、人より脳が少し足りないようです。
また説明お願いします。m(__)m
263:デフォルトの名無しさん
05/12/20 14:31:12
>>262
現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。
P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で
とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、
多項式時間で解くことの出来ない問題があることを証明できていない現在、
P=NPは矛盾しているとはいえない。
264:257
05/12/21 12:01:14
>>263
なるほど、ようやく分かりました。
すべてのNP問題が(近似解とかではなく)
多項式時間で解けるようになったら面白いでしょうね。
天寿を全うするまでに見たいものです。
ありがとうございました！
265:デフォルトの名無しさん
06/01/09 00:12:14
age
266:BASIC
06/01/09 16:12:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する
267:デフォルトの名無しさん
06/01/09 17:34:00
宿題は自分でやれ
268:デフォルトの名無しさん
06/01/09 17:54:08
BASICなんて記憶の彼方だな
269:デフォルトの名無しさん
06/01/09 18:15:01
何ベーシックかは指定していないな。
VBとかでもいいとすれば随分アレだ
270:デフォルトの名無しさん
06/01/09 19:08:23
>>266
URLﾘﾝｸ(www.sagami.ne.jp)
271:デフォルトの名無しさん
06/01/11 03:29:11
ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？
(n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです
もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！
272:デフォルトの名無しさん
06/01/11 06:49:10
Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない．
定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし．
O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？
273:デフォルトの名無しさん
06/01/11 10:57:45
>271
LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、
次回以降は演算を省くってのはどうだろう？
辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。
274:271
06/01/12 12:31:26
>>272-273
早いレスどうもです！
>>272
やはりO(nm)回は「本質的に」避けられないわけですよねー・・・
微分の差分近似をループでnm回やるつまらない実装なんで、
工夫できないかなと思った次第だったのですが。
ちなみに問題は非線形関数の最小値探査みたいな感じです
>>273
んー、いいアイディアなんですが今回は
適用できないような気がします、ゴメンナサイ
ただ、そのうち他の問題で使えそうな気がするんで、
そのネタはもらって覚えておきます！ ありがとう！
275:デフォルトの名無しさん
06/01/14 00:48:34
>>274
最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような
276:デフォルトの名無しさん
06/01/31 17:55:55
最小二乗法のライブラリきぼんゅ。
277:デフォルトの名無しさん
06/02/01 03:14:47
>>276
ライブラリも何も、大した計算じゃないじゃん。
278:デフォルトの名無しさん
06/02/01 12:32:21
>>277
世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？
279:276
06/02/01 12:44:24
最小二乗法おしえて欲しいぉ。
280:デフォルトの名無しさん
06/02/01 13:38:16
残差平方和が最小になるようにパラメータを決定するのです
このスレでも簡単な例がいくつか
>>178
>>182
>>196
非線形になってくるとちょっとめんどい
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(en.wikipedia.org)
ここら辺を参考に
281:デフォルトの名無しさん
06/02/02 02:20:31
>>278
FFTになると、ライブラリが欲しい程度には複雑だと思う。
282:デフォルトの名無しさん
06/02/02 08:51:05
>>281
どれだけある？という問いにＦＦＴ１個かよ。
283:デフォルトの名無しさん
06/02/02 09:25:21
>>282
世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。
284:デフォルトの名無しさん
06/02/02 13:43:21
行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい．
285:デフォルトの名無しさん
06/02/02 14:58:57
あとは圧縮＆展開と多倍長演算あたりかね？ 汎用的なのは。
各分野毎にはいろいろとあるだろうけど。
画像エフェクト、サウンドエフェクト、3D系演算とか。
286:デフォルトの名無しさん
06/02/02 15:52:22
>>281
難しくはないが複雑ではあるよな。
287:デフォルトの名無しさん
06/02/02 22:26:58
各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。
288:デフォルトの名無しさん
06/02/05 09:27:32
最小二乗法は
円に適用するだけでも、厄介だし、
直線に適用しようとしたって、実はけっこう難しいよ。
たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。
残差って何って所から取り掛からないとね。
そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。
数値解で求める事になるだろうな
289:デフォルトの名無しさん
06/02/06 07:09:38
>>288
ただの偏微分でしか説明しないのって，相当ひどい学校だと思う
290:276
06/02/06 10:04:37
>>288
じゃ、何を使うのさ？？？？？
>>289
詳しく！！！！！
291:デフォルトの名無しさん
06/02/06 14:14:46
>>288
最小二乗法はロバストでないのでそのあたりは考慮しないと。
例えば、y=x上に完全に点が並んでいる状態で、
たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。
292:276
06/02/06 14:22:51
今回の開発では点の数に関しては、決めウチできます。
293:288
06/02/07 06:30:36
>>290
だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ
直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う
数表上なら結果の誤差を最小にしたいし
2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある
294:デフォルトの名無しさん
06/02/09 11:57:07
最小2乗法ｱｹﾞ
295:sage
06/02/09 21:45:42
sage
296:デフォルトの名無しさん
06/02/11 17:31:27
n個の要素の2番目に小さい要素は最悪n+logn－2回の比較で求められることを証明しなさい。
順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。
どなかか説明してもらえないでしょうか？よろしくお願いします。
高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。
297:デフォルトの名無しさん
06/02/11 18:07:41
／￣￣￣￣＼
／ ● ●
|Y Y ＼
| | | ▼ | ﾊﾟｸｯ
| ＼／ ＿＿＿＿人__|
| |∨∨∨∨∨ ←296
＼ ＼∧∧ ）
｜ ｜ |＼ ￣￣＼＼＼
｜ ｜ | ￣￣￣ し し/
（_＿）＿）
298:デフォルトの名無しさん
06/02/11 18:33:39
最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。
今適当に考えただけだから間違ってるかもしれないけど。
299:デフォルトの名無しさん
06/02/11 18:40:59
違った、最悪 n回か。
300:デフォルトの名無しさん
06/02/11 18:45:05
>>298
いや、漏れが覚えている限りでは違うと思われ。
MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず
院試にでてたかも。
301:デフォルトの名無しさん
06/02/11 18:57:23
>>300
やっぱり違ってた。考え直したら、
nが偶数なら (3/2)*n - 2,
奇数なら (3/2)*n - 3/2 回だった。
302:デフォルトの名無しさん
06/02/11 20:58:20
>>296
ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。
あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。
303:デフォルトの名無しさん
06/02/12 00:24:16
証明になってないｗ
304:デフォルトの名無しさん
06/02/12 03:01:20
>>296
完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのにn-1回の比較が必要。
二番目に小さい要素は一番小さい要素の対戦相手のどれか。
木の高さはceil(log n)で木の一番上には対戦相手はいないから、
二番目に小さい要素の候補たりえるものはceil(log n)-1個
この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。
したがって比較回数は、
(n-1)+ceil(log n)-2<n+logn-2
ただし、ceil(x)はxの小数点以下切り上げの関数
305:デフォルトの名無しさん
06/02/13 00:39:26
>>304
なるほど。
それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど
どうなんだろう。
306:デフォルトの名無しさん
06/02/13 06:11:40
２分木にする必要性が感じられないってかなってないｗ
307:デフォルトの名無しさん
06/02/14 10:30:15
>>305
実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは
結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。
308:デフォルトの名無しさん
06/02/27 09:33:06
３２ビットの符号無整数型で３２個のビットのうち
N個をランダムに選んで１にするアルゴリズム。
（残りの３２－N個は０）
賢い人教えて。
309:デフォルトの名無しさん
06/02/27 11:33:45
>>308
そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。
それとも乱数生成のアルゴリズム自体を聞いてるの？
310:デフォルトの名無しさん
06/02/27 12:12:40
たぶん
１）組み合わせの数の計算方法が判らない
２）乱数と、その全部の組み合わせを対応させる方法が判らない
のだろうと思うんだけどね
311:デフォルトの名無しさん
06/02/27 12:28:33
1U << (rand() & 31)
とか、そういうことではないの？
312:デフォルトの名無しさん
06/02/27 12:35:07
>>311
rand って完全にランダムじゃなくて、
下位ビットほど短い周期性持ってるから、
rand() & 31 はあんまりよくない。
(rand() >> 16) & 31 とか、何ビットかシフトするの推奨。
313:デフォルトの名無しさん
06/02/27 12:38:20
分かってて書いてたつもりだけど…アルゴリズムの質問だし。
random()でもMTでも好きなの使えばいいんじゃない？
314:デフォルトの名無しさん
06/02/27 12:41:56
>>313
まあそうだけどね。
>>308 がそんな判断できると思えなかったんで、一応補足のつもり。
315:308
06/02/27 13:09:41
MTとかで生成された乱数の立っているビットの数は
１６本を中心にした正規分布になってると思うんだけど、
必ずN本になるようにしたい。
３本とか３０本とかってのはたまにしか発生しないし。
N回ループで一度使った数は記憶させとくとかっていう
愚直なのは思いついたんだけど遅そうなので聞いてみた。
316:デフォルトの名無しさん
06/02/27 15:31:21
32個の数字から N個取り出して順不同というのと 問題は同じでしょ
317:デフォルトの名無しさん
06/02/27 20:50:08
>>316
ですね。
1～32の間で離散一様乱数発生させたものをa_0、
1～31の間の乱数をa_1、1～30の間をa_2として、
初期値は0で左からa_0番目のビットを1にする。
以降左からa_k番目の0のビットを1にする。
~~
318:308
06/02/28 09:54:13
>>317
今はそれでやってます。
みなさん聞いてくれてありがとう。
319:308
06/02/28 09:58:33
あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。
連投ごめん。
320:308
06/03/01 16:40:57
やっぱりもっと速いのないかな。
321:デフォルトの名無しさん
06/03/01 17:19:36
>>320
これ以上議論するなら，「速い」をきっちり定義してもらわないと．
特に乱数生成のコスト，各ビットを参照するコストなどが無いと，
どっちが速いかなんて比較できんよ．
322:デフォルトの名無しさん
06/03/02 11:59:32
もっと早い方法は、全部の組み合わせのテーブルを作っておいて
それの配列番号を乱数で選ぶ事だね
323:デフォルトの名無しさん
06/03/02 12:53:16
>>322
2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB
何を使って動かすつもり？
324:デフォルトの名無しさん
06/03/02 16:39:38
>>317
それは、順番を考慮した場合のアルゴリズムだから違うようだけど
結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか
>>323
Nを固定すれば 最大の組合せ数は N=16の時で その1/4程度の容量だから最近のPCなら入るんじゃないの？
組み合わせの数ってどの程度だろ？
32!/N!/2^N では大きすぎるな
325:デフォルトの名無しさん
06/03/02 16:43:14
たとえば32個中3個が１の組み合わせを F(32,3) のように書くと
先頭ビットが0 なら 残りは F(31,3)
先頭ビットが1 なら 残りは F(31,2)
という事で
F(N,M)=F(N-1,M)+F(N-1,M-1)
326:デフォルトの名無しさん
06/03/02 17:23:15
>>324,325 高校数学の教科書読み直したら？
URLﾘﾝｸ(ja.wikibooks.org)
327:デフォルトの名無しさん
06/03/02 18:34:31
という事は 32 C 16
URLﾘﾝｸ(www.google.co.jp)(16!*16!)
601 080 390
って事か
Σ M C n =2^M って事になるんだな
328:デフォルトの名無しさん
06/03/02 18:39:51
で 32個中16個の組み合わせ は 32!/(16!*16!)
なのに >>317の方法は 順列 で 32!/16! という事で、16! の重複があるから、なんか重そうに見えるという事？
329:デフォルトの名無しさん
06/03/03 07:29:43
配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜
330:デフォルトの名無しさん
06/03/03 07:50:10
var max1,max2 min1,min2;
max1:=data[0];
max2:=data[1];
if max2> max1 then swap(max1,max2);
min2:=max1;
min1:=max2;
for i:=low(data)+2 to High(data) do begin
if data[i] > max2 then begin
if data[i] > max1 then max1:=data[i] else max2:=data[i];
end;
if data[i] < min2 then begin
if data[i] < min1 then min1:=data[i] else min2:=data[i];
end;
end;
こんな感じでは？
331:デフォルトの名無しさん
06/04/18 07:42:35
いわゆる○×。ただし、ちょっと特殊。
ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面 位置関係はこんな感じ
turn //ターン数 最初は1
プレイヤーＡのターン開始
↓
Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号
（Ａは１、Ｂは２とする。）を代入。
↓
turn>6ならば、次のことを行う。
banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに１を足し、Ａのターンを終了、Ｂのターンになる。
で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。
332:デフォルトの名無しさん
06/04/18 13:54:18
あぶらあげ
333:デフォルトの名無しさん
06/04/22 16:23:12
>>331
ゲーム木使って実際に解いてみたら。
EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。
終盤6個そろってからの場合の数は
9*8*7*6*5*4 = 60480
回転と対称で重なるものを除くと
60480/8 = 7560
リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。
自分の手番でダブルリーチをかけられる状態であれば勝ち。
双方最善を尽くしたとき、ループに陥れば引き分け。
334:デフォルトの名無しさん
06/04/22 17:08:22
消してから勝利判定だとダブルリーチにならないんじゃない？
335:デフォルトの名無しさん
06/05/22 17:26:54
楕円近似ライブラリなんてありまつか？
336:デフォルトの名無しさん
06/05/22 17:37:12
楕円近似というのは
１、点列を楕円の一部として近似する事
２、楕円の周長を近似計算する事
どっち？１はとても難しい 円ならまだ方法があるが
337:デフォルトの名無しさん
06/05/22 17:56:27
＞１、点列を楕円の一部として近似する事
これをやりたいです。
338:デフォルトの名無しさん
06/05/22 18:20:03
円なら
URLﾘﾝｸ(www.tensyo.com)
ここの円弧推定が良い方法だと思える。
普通は、円との誤差を ｓ＝√｛（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2｝－ｒ と置くが
これだと非線形で解かなければならない。
（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2－r^2 とすれば数値解が簡単に求まるというものだ。
楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ
339:AVL木
06/05/22 20:52:10
18,7,35,13,16,10,40,21,22,50,46,3,5 を
からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。
340:デフォルトの名無しさん
06/05/22 21:41:44
教科書読め
341:デフォルトの名無しさん
06/05/25 18:54:44
繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？
342:デフォルトの名無しさん
06/05/25 20:20:09
デジタル回路の閾値関数を考えたのですが、既知ですか？
f:=x->cos(PI/2*x)^2
f(f(f(x))), x=-0.5..1.5
343:デフォルトの名無しさん
06/05/31 01:36:13
>>335
Direct least-squares fitting of ellipses
Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher
IEEE Transactions on Pattern Analysis and Machine Intelligence,
21(5), 476--480, May 1999
URLﾘﾝｸ(research.microsoft.com)
URLﾘﾝｸ(research.microsoft.com)
一応 Java 実装もあるけどコードがちょっと汚いかも。
344:デフォルトの名無しさん
06/07/28 23:01:36
fla板から来ました以下の解答お願いします。
プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？
(x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが
具体的にどういった計算をすればいいかご教授願います
ちなみに最小二乗法だと、
＼
／
＼
／
このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・
345:デフォルトの名無しさん
06/07/28 23:26:48
>>344
軌跡が直線に近いってのは、どういうこと?
346:デフォルトの名無しさん
06/07/28 23:37:46
>>344
最小二乗法で相関係数みりゃいいだろ。
347:デフォルトの名無しさん
06/07/29 00:13:17
>344
数値を求めたいんだろう？
最後の行が意味不明だぞ
348:344
06/07/29 00:16:20
>>345
URLﾘﾝｸ(www.uploda.org)
この画像のように、どれだけ直線に近い動きをしたか、ということを
直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。
>>346
相関係数ですか、調べてみます
ありがとうございます
349:デフォルトの名無しさん
06/07/29 15:15:39
もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。
「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？
350:デフォルトの名無しさん
06/08/10 08:08:24
あらかじめ引いてある直線が X 軸に合うように回転させて
Σ(Yi^2)/N とか
軌跡の2次モーメントとか
351:デフォルトの名無しさん
06/09/15 13:37:19
軌跡に沿って所与の直線との距離を積分すればいいじゃないの。
352:デフォルトの名無しさん
06/09/16 00:36:41
随分とまた遅い進行だな
353:デフォルトの名無しさん
06/10/18 22:34:05
ベクトルを正規化する式は
float x, y, z;//元のベクトル
float vx, vy, vz;//正規化したベクトル
float s;
s=sqrt(x*x+y*y+z*z);
vx=x/s;
vy=y/s;
vz=z/s;
で求まると思いますが、sqrtを使わずに正規化するにはどうすればいいのでしょうか？
どうしても速度が気になります。
自分でも考えてみましたが分かりませんでした。よろしく御願いします。
354:age
06/10/18 22:38:49
age
355:デフォルトの名無しさん
06/10/18 23:04:16
f(u0,v0)=
ΣΣf(uk,vl)C(uk-u0)C(vl-v0)
k l
ここで
C(x)= 1-2|x|^2+|x|^3 (0<|x|<1)
4-8|x|+5|x|^2-|x|^3 (1<|x|<2)
0 (2<|x|)
3次補間法の計算式なのですが，どのようにプログラムで書いたら良いのでしょうか?
356:デフォルトの名無しさん
06/10/19 00:02:01
>>353
>どうしても速度が気になります。
本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。
sqrtを使わなければできないと思いますけど。
本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。
ただし、精度を犠牲にしてのことですけど。
Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で）
まずは実測です。
357:デフォルトの名無しさん
06/10/19 00:08:31
脳味噌ぶら～んにでも行って速そうなの探してこいよ。
358:デフォルトの名無しさん
06/10/19 01:37:21
>353
まず環境晒そうや。
CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。
359:デフォルトの名無しさん
06/10/19 10:20:45
>>356
精度にもよるけどせいぜい３－５回ぐらいじゃなかったか？
20回もまわすか。
360:デフォルトの名無しさん
06/10/19 10:52:10
double sqrt(double x) {
double a = 1.0;
double eps = 1.0E-10; /* 精度 */
while (abs(a * a - x) > 1.0E-10) {
a = 0.5 * (a + x / a);
}
return a;
}
361:デフォルトの名無しさん
06/10/19 10:56:57
>>353
URLﾘﾝｸ(www.google.co.jp)
362:デフォルトの名無しさん
06/10/19 12:32:48
>>360
そのコードで３－５回
1.0E-15で9回ってところ
確かに20回もありえるけど、極端な言いぐさは信用されないな。
363:デフォルトの名無しさん
06/10/19 13:16:19
>>360
Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。
SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。
364:デフォルトの名無しさん
06/10/19 13:44:45
>>355
その計算式のままだと思うけど…
アルゴリズムの入力と出力は理解できてる?
(入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値)
365:デフォルトの名無しさん
06/10/19 16:36:19
式は分かってるんですがプログラムにできないんです・・・
366:デフォルトの名無しさん
06/10/19 17:01:18
>>365
具体的なコードが欲しいなら
具体的な入力形式を指定した方がいいと思うよ。
(これは大学の宿題か何かですか?)
367:デフォルトの名無しさん
06/10/19 17:19:03
初心者なもですいません．大学のC言語の画像処理の宿題です．
#include <stdio.h>
#include <rasterfile.h>
#include <math.h>
#include "bitshift.h"
void Disp_Ras(struct rasterfile ras);
void cercle(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void tri(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void sq(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void satr(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
int height;
int width;
int main(int argc,char *argv[]){
/*変数宣言*/
int i=0;
int j=0;
int point[2];
struct rasterfile ras;
unsigned char **R,**G,**B;
unsigned char **r,**g,**b;
FILE *fp1,*fp2;
int nt,nn;
double p,q;
double bai;
int tmp_nt,tump_nn;
368:デフォルトの名無しさん
06/10/19 17:22:41
続き
printf("倍率を入力");
scanf("%lf",&bai);
/* 入力画像 */
if((fp1 = fopen("hane256.ras","rb")) == NULL){
fprintf(stderr,"can't open file!!\none more check it!!\n");
exit(1);}
/* ヘッダ読み込み */
ras.ras_magic = readtoInt(fp1);
ras.ras_width = readtoInt(fp1);
ras.ras_height = readtoInt(fp1);
ras.ras_depth = readtoInt(fp1);
ras.ras_length = readtoInt(fp1);
ras.ras_type = readtoInt(fp1);
ras.ras_maptype = readtoInt(fp1);
ras.ras_maplength = readtoInt(fp1);
369:デフォルトの名無しさん
06/10/19 17:23:35
続き
height =bai*ras.ras_height;
width = bai*ras.ras_width;
height = height - height%4;
width = width - width%4;
/* 出力画像 */
fp2 = fopen("out.ras","wb");
/* ヘッダ書き込み */
writetoInt(fp2,ras.ras_magic);
writetoInt(fp2,width);
writetoInt(fp2,height);
writetoInt(fp2,ras.ras_depth);
writetoInt(fp2,ras.ras_length);
writetoInt(fp2,ras.ras_type);
writetoInt(fp2,ras.ras_maptype);
writetoInt(fp2,ras.ras_maplength);
370:デフォルトの名無しさん
06/10/19 17:24:06
続き
/* メモリ確保 */
R = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
G = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
B = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
r = (unsigned char**)calloc(height,sizeof(unsigned char *));
g = (unsigned char**)calloc(height,sizeof(unsigned char *));
b = (unsigned char**)calloc(height,sizeof(unsigned char *));
for(i=0;i<ras.ras_height;i++){
R[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
G[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
B[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
}
for(i=0;i<height;i++){
r[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
g[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
b[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
}
371:デフォルトの名無しさん
06/10/19 17:24:59
/* 画素データ取り込み */
for(i=0;i<ras.ras_height;i++){
for(j=0;j<ras.ras_width;j++){
/* B → G → R(24bit) */
fread(&B[i][j],sizeof(unsigned char),1,fp1);
fread(&G[i][j],sizeof(unsigned char),1,fp1);
fread(&R[i][j],sizeof(unsigned char),1,fp1);
}
}
/*線形補間法*/
for(i=0;i<height;i++){
for(j=0;j<width;j++){
nt = floor(i/bai);
nn = floor(j/bai);
p = i/bai - nt;
q = j/bai - nn;
r[i][j] = R[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+R[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+R[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+R[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
g[i][j] = G[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+G[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+G[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+G[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
b[i][j] = B[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+B[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+B[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+B[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
}
}
372:デフォルトの名無しさん
06/10/19 17:27:39
この線形ほかんの部分を3次補間にしないといけないのですが・・・
373:デフォルトの名無しさん
06/10/19 17:50:33
宿題スレ池
374:デフォルトの名無しさん
06/10/19 21:39:46
>367-371
・宿題の趣旨を理解していないバカ
・「初心者」と書けばなにをしても許されると思ってるバカ
・構造化出来ないバカ
・ざっと見ただけでもコンパイルが通らないのが解るコードを晒すバカ
久々に悪寒が走るほど汚ぇコード見たわ。
375:デフォルトの名無しさん
06/10/19 22:12:12
初心者をバカにするやつに上級者はいない(^.^)
376:デフォルトの名無しさん
06/10/19 23:37:57
>>374
これ、たぶん宿題出した先生が書いたコードだと思うんだけど、
大学の先生 (特に年配の人) って結構こういうコード書くのよ。
漏れが習った人も FORTRAN が最初だったらしくてこんな感じだった。
理論とかに関してはすごく頭切れるんだけどね…。
377:デフォルトの名無しさん
06/10/20 01:36:50
・糞レスでageるやつは2ch初心者
・携帯のノリで顔文字使ってるやつは2ch初心者
378:デフォルトの名無しさん
06/10/20 10:59:23
>>371
＞nt = floor(i/bai);
キャストしる。
＞R[(unsigned char)nt][(unsigned char)nn]
このキャストは意味あるの？
元画像が縦横どちらか256pixel超えると破綻すると思うけど。
それとも、charが16bitか32bitの処理系？
マジで講師の書いたコードだとしたらヤバイな。
こんなの習った奴が卒業して、新人として入社してくるんか・・・orz
379:デフォルトの名無しさん
06/10/21 13:02:51
>>376
結構いるよね
原理が分かるんだからいいじゃん，
コード読みやすくするのは各自勝手にやってくれとか思ってそう
380:デフォルトの名無しさん
06/10/21 14:37:21
まあ、歳食うと新しいこと覚えられないからねぇ。
FORTRAN のパラダイムのままで C とか Java 書くのなんて当たり前。
381:デフォルトの名無しさん
06/10/21 15:04:24
つまり、年寄りってゴミっていうこと？
382:デフォルトの名無しさん
06/10/21 15:28:34
そこまでは言わんが･･･
383:デフォルトの名無しさん
06/10/21 15:58:18
でも実際この業界では、年寄りは廃棄処分にされるんだよね？
384:デフォルトの名無しさん
06/10/21 16:11:20
>>383
その当時、専門でなかった人材を無理矢理ソフトウェア開発に回した、という背景があるからじゃない？
そういう年寄り連中は基礎的な事を学ばずに、現場たたき上げで今までやってきたけど、そのツケが今に回ってきてる。
385:デフォルトの名無しさん
06/10/21 16:31:02
んじゃ、年寄りが新しいことを覚えられないというのは、基礎的なことを知らないから、新しいことに対処する能力が低いということ？
386:デフォルトの名無しさん
06/10/21 17:07:54
歳食うと新しいこと覚えられないってのは、人間なら誰でも。
普通は、新しいこと出来ないってのを今までの経験からくる勘とかで補うんだけど、
>>384 みたいな背景があるんじゃ、この業界じゃほんとにゴミになりかねんな、年寄り。
387:デフォルトの名無しさん
06/10/21 19:36:38
どの業界でも年取れば、現場から一歩引いて管理職になるが普通じゃないのか？
ただし、ITドカタじゃそれが特別速く押し寄せるってこと。
388:デフォルトの名無しさん
06/10/21 20:05:52
>>387
アメリカでは職種は変わらない。
389:デフォルトの名無しさん
06/10/21 20:48:27
お前はどこで仕事してる？
390:デフォルトの名無しさん
06/10/22 00:03:00
>>387
まあ、だってさ、管理職って多人数は必要ないわけじゃん。
全員が管理職にはなれないだろ。
って、話題がなんかマ板臭いな。
391:デフォルトの名無しさん
06/10/22 00:13:51
【】この業界では何故、年寄りは廃棄されるのか？【】
392:デフォルトの名無しさん
06/10/22 13:56:19
>>390
その話の最後は、「国が必要もない公共工事をいつまでも続けるのはなぜなのか」に落ち着くぞ。
393:デフォルトの名無しさん
06/10/22 22:12:32
ｵﾏｲﾗ赤黒木ってしってる？
394:デフォルトの名無しさん
06/10/22 22:13:44
常識では
395:デフォルトの名無しさん
06/10/22 23:30:04
実装を知ってるのと聴いたことあるのとではまったく違う
396:デフォルトの名無しさん
06/10/22 23:53:11
どのくらい効率いいの？＞red-black tree
小規模のDBなら偏っても問題無いし、大規模DBならいまどきツリー使ってないだろうし。
ターゲットはどこらなん？
397:デフォルトの名無しさん
06/10/23 00:33:08
FEMプログラムで使われてるのは見たことある。
398:デフォルトの名無しさん
06/10/23 00:43:13
>>国が必要も無い公共工事を続ける理由
三下土方に職を与える為
に落ち着くぞ
399:デフォルトの名無しさん
06/10/23 00:45:39
>>人口減ってるから、住宅作らなくてもいいんだよ。
どうせ大半は地震でぶっ壊れるし。
いやいやゼネコンの小遣い稼ぎでしょう。
400:デフォルトの名無しさん
06/10/23 02:05:37
>>393
日本語だと、2色木って言われることの方が多いような、red-black tree。
>>396
要素の挿入・削除時にちょっと処理が増えるけど、
要素の探索時にはペナルティなしで、
木の高さが必ず log n オーダーに抑えられる。
数百～数万程度のデータ扱うときにはすごい効率いいと思うよ。
C++ の map とか C# の SortedDictionary は2色木使ってる。
Java の Hashtable も、名前に反して実装は2色木じゃなかったっけ？
401:デフォルトの名無しさん
06/10/23 16:39:56
2色木は初めて聞いた。俺は赤黒木派。
402:デフォルトの名無しさん
06/10/23 18:36:23
実測結果キボンヌ
403:デフォルトの名無しさん
06/11/17 17:26:34
平面上の凸とは限らないポリゴンを三角形分割したいのですが、どういったアルゴリズムがあるでしょうか？
また、そのポリゴンに穴が開いている場合も対処できるアルゴリズムはありますか？
1週間ほど調べているのですが埒があかなくて。。。
404:デフォルトの名無しさん
06/11/17 18:51:11
穴空きなら、外側とつなぐ。切れ込みを入れる感じで。
凹なら凹部と別の頂点で分割して凸にする。
405:デフォルトの名無しさん
06/11/18 03:15:54
どんな多角形だろうと、単調多角形への分割をした後に
単調多角形の三角形分割をして O(n) で解けることが知られている。
まともな計算幾何の本ならだいたい書いてあるとおもうが。
406:デフォルトの名無しさん
06/11/18 03:21:41
その単調って凸と同じ意味？
407:デフォルトの名無しさん
06/11/18 12:45:18
違う。端点のリストを一番下にある点から巡回したとき
y_1 < y_2 < ... < y_k, y_k > y_{k+1} > y_{k+2} ... > y_n となること。
つーか本嫁。
408:デフォルトの名無しさん
06/11/18 21:06:08
ここにでてくるShare Sortってなに？
ぐぐっても日本語の解説が見つからなかったよ。
とりあえず並列処理用のアルゴリズムらしいのは
わかったけど。
URLﾘﾝｸ(www.cs.rit.edu)
409:403
06/11/19 15:10:28
>>404-407
ありがとうございます。
なんとなくわかりました。
ただ、本屋に行ってみて計算幾何の本をいくつか見てみたのですが、どの本がよいかよくわからなくて...
もしお勧めがあれば教えていただけないでしょうか。すみません。
410:デフォルトの名無しさん
06/11/19 15:57:59
>>408
URLﾘﾝｸ(www.cs.mu.oz.au)
これじゃだめ？
・row columnにわける(row数,column数はプロセッサ数の定数倍に近いほうがよいだろう)
・奇数rowで昇順ソート偶数rowで降順ソートをする
・columnで昇順ソートをする
何回かやってるとできるはずなのでできたら取り出す
なんでrowのソートで逆にする必要があるのかな...
411:デフォルトの名無しさん
06/11/19 19:39:16
>>409
URLﾘﾝｸ(www.amazon.co.jp)
URLﾘﾝｸ(www.amazon.co.jp)
412:デフォルトの名無しさん
06/11/19 20:20:48
>>411
ありがとうございます！
早速買ってこようとおもいます。本当にありがとうございました。
413:デフォルトの名無しさん
06/11/19 20:44:17
shear sort実装してテストしてみたんだが、std::sortに比べて遅い・・・
int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、
2^32程度だと１回のテストで1000倍程度遅かった。
coreが1個だとオーダも悪いね。n個もcoreがあるなら、
quick sortでも順次分けていけるようなきがするし、
メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。
414:デフォルトの名無しさん
06/11/19 21:06:23
O(n log n) を切れるソートって、かなり特殊な前提がないと使えないんじゃないの？
データの数と同じだけプロセッサがあるなら、
バブルソートでも O(n) でしょ、確か。
その Shear ソートも、そういう前提の下で O(√n) とかではないの？
415:デフォルトの名無しさん
06/12/13 12:06:49
「ｍ個の数字集合からｎ(0～ｍ)個の組み合わせを比較し、指定値Ｘ以上かつ最小の組み合わせを求める。」
こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。
どなたかお願いします。
例
インプット
数字集合：5,7,10,12,15
指定値：18
↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。
アウトプット
最小合計値の組み合わせ：7+12=19
416:デフォルトの名無しさん
06/12/13 12:34:57
>>415
アルゴリズムを説明すれば自分でプログラム書けるの？
プログラム書いてほしいとか言うのは宿題スレいってくれ
417:デフォルトの名無しさん
06/12/13 12:50:26
ナップサック問題のバリエーション？
418:415
06/12/13 12:50:50
>>416
アルゴリズムによってはプログラムで書けるか分からないので、宿題スレに行きます。
419:429
06/12/13 13:26:11
415ではないが移動先はっとく
ｽﾚﾘﾝｸ(tech板:22番)
420:デフォルトの名無しさん
06/12/13 14:16:15
>>417
Subset Sum Problem という有名 NP （の、最適化問題版）。
まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。
421:デフォルトの名無しさん
06/12/13 14:37:22
問題から推測すると集合の最大値は指定値をより小さいのかな
422:415
06/12/13 15:15:11
>>419
お手数おかけしました。
>>417>>420
有名な問題なのですね。
名前自体しらなかったです。
>>421
集合の全合計値より、指定値が小さいという意味ならそうです。
423:デフォルトの名無しさん
07/01/23 17:46:53
sqrt(O(N^2)の処理)の計算量が知りたいのですが
sqrtの計算量わかる人いますか
424:デフォルトの名無しさん
07/01/23 19:59:02
>>423
sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。
具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。
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 残りの分を求める
↓
（データ）・・分を出力
↓
（終了）