プログラミングの為の数学と算数 vol.2
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG語りましょう。TIPS/Q&Aスレです。
0285デフォルトの名無しさん
2005/10/26(水) 23:53:36嘘つきになる要素が・・・
0286デフォルトの名無しさん
2005/10/27(木) 13:49:130287デフォルトの名無しさん
2005/10/27(木) 14:31:050288デフォルトの名無しさん
2005/10/27(木) 15:00:160289デフォルトの名無しさん
2005/10/27(木) 22:38:310290デフォルトの名無しさん
2005/10/28(金) 00:58:510291デフォルトの名無しさん
2005/10/28(金) 01:04:290292291
2005/10/28(金) 01:05:140293デフォルトの名無しさん
2005/10/28(金) 01:10:03素数を生成するコードを書いて落ち着くんだ…
0294デフォルトの名無しさん
2005/10/28(金) 01:21:5420 N = N + 1
30 K=2
40 IF N = K THEN LPRINT N
50 IF N MOD K = 0 THEN GOTO 20
60 K = K + 1
70 GOTO 40
0295デフォルトの名無しさん
2005/10/28(金) 10:58:220296デフォルトの名無しさん
2005/11/04(金) 02:06:550297デフォルトの名無しさん
2005/11/04(金) 22:23:21「だぜ」に突っ込むか・・・。
「やれやれだぜ」自体が漫画の台詞。
ジョジョ。
0298デフォルトの名無しさん
2005/11/04(金) 23:27:220300& ◆BSGaog1Z0Q
2005/11/08(火) 14:18:52//>>294
std::ostream& dumpPrimes(std::ostream& os, int max) {
for(int n=2; n <= max; ++n){
for(int k=2; ; ++k){
if(n==k) {
os << n << "\n";
}
if(n % k == 0) {
break;
}
}
}
return(os);
}
0301デフォルトの名無しさん
2005/11/08(火) 14:36:01if(n==k){
os << n << "\n";
}
return((n % k == 0)? os: testDiv(os, n, k+1));
}
std::ostream& testNum(std::ostream& os, int max, int n){
return((n > max)? os: testNum(testDiv(os, n, 2), max, n+1));
}
std::ostream& dumpPrimes(std::ostream& os, int max) {
return(testNum(os, max, 2));
}
0302デフォルトの名無しさん
2005/11/16(水) 22:10:39> 素数は無限に存在する。
>
> エウクレイデスによる証明
> 背理法による。
> 素数が有限個しかないと仮定し、それらを次のようにおく。
>
> pi, i <= n
> ただし n は定数。
>
> q = p1p2p3．．．ｐｎ + 1
>
> を考えよう。q は合成数であるか素数であるかのいずれかである。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
> 素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
> Q.E.D.
この証明変だよね。
0303デフォルトの名無しさん
2005/11/16(水) 22:18:18どこで引っかかった？何が変？
0304デフォルトの名無しさん
2005/11/16(水) 22:22:32「qが合成数」も「素数が有限」も否定していいんだよ。
0305302
2005/11/16(水) 22:29:52そうとは限らない
2 + 1 =
3 is a prime.
2 x 3 + 1 =
7 is a prime.
2 x 3 x 5 + 1 =
31 is a prime.
2 x 3 x 5 x 7 + 1 =
211 is a prime.
2 x 3 x 5 x 7 x 11 + 1 =
2311 is a prime.
2 x 3 x 5 x 7 x 11 x 13 + 1 =
30031 is 509 x 59
2 x 3 x 5 x 7 x 11 x 13 x 17 + 1 =
510511 is 97 x 5263
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 =
9699691 is 27953 x 347
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 + 1 =
223092871 is 703763 x 317
0306デフォルトの名無しさん
2005/11/16(水) 22:37:59> 2 + 1 =
>3 is a prime.
2<3
> 2 x 3 + 1 =
>7 is a prime.
3<7
> 2 x 3 x 5 + 1 =
>31 is a prime.
5<31
> 2 x 3 x 5 x 7 + 1 =
>211 is a prime.
7<211
> 2 x 3 x 5 x 7 x 11 + 1 =
>2311 is a prime.
11<2311
> 2 x 3 x 5 x 7 x 11 x 13 + 1 =
>30031 is 509 x 59
13<59
> 2 x 3 x 5 x 7 x 11 x 13 x 17 + 1 =
>510511 is 97 x 5263
17<97
> 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 =
>9699691 is 27953 x 347
19<347
> 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 + 1 =
>223092871 is 703763 x 317
23<317
論外なところから値を引っ張ってきて論じようとしている。
23が「最大」の素数であれば、317は素数でも合成数でもないのでどちらにしても矛盾がしょうじる。
0307デフォルトの名無しさん
2005/11/16(水) 22:41:27この推論は「素数が有限個しかない」という偽の前提があるから、反例を持ち出してもしょうがない。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。
これは、「合成数は有限個の素数の積で表される」という定理と「素数はpiしかない」からの帰結。
0308302
2005/11/16(水) 22:49:50> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである
そうでない場合もあるとは思いませんか?
そして、その場合についても論ずるべきでは?
0309デフォルトの名無しさん
2005/11/16(水) 22:57:11だから、>>307に書いたように、
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである
は「素数がpiしかない」という仮定の下で証明できる。
証明できるからには、これが偽である可能性を検討する必要はない。
0310302
2005/11/16(水) 23:37:43>「合成数は有限個の素数の積で表される」という定理
を前提としているわけですか?
0311デフォルトの名無しさん
2005/11/16(水) 23:45:05群論か環論の本を読んでくださいな、素元、既約元のあたりです。あとできれば背理法についてもね。
0312デフォルトの名無しさん
2005/11/16(水) 23:57:48細かい違いはあるかも知れない（例えば、その定理の代わりに「合成数は素因数を持つ」でも十分）けど、
基本的にはその通りだと思う。
0313302
2005/11/17(木) 00:16:30> を考えよう。q は合成数であるか素数であるかのいずれかである。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
> 素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
こう変えてもいいですか?
を考えよう。q は合成数であるか素数であるかのいずれかである。
q が合成数だとすると q は pi のいずれかを用いて積の形に表されるとき、q は pi のいずれで割っても 1 があまり、矛盾する。
また q は pi のいずれかを用いて積の形に表されないとき、q は pi を超える素数を持ち、矛盾する。
素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
0314デフォルトの名無しさん
2005/11/17(木) 00:19:56128bit暗号を解読できるくらいのを
0315デフォルトの名無しさん
2005/11/17(木) 00:31:12ちょっとおかしいところ(「piを超える素数」じゃなくて「pi以外の素因数」というべき)があるけど、大筋としてはそれでもいい。
でも、そう書き換えたところで推論の構造はほとんど変わっていないし、
「合成数は素因数をもつ」ことに依存しているのも変わらない。
0316302
2005/11/17(木) 00:46:27自分なりに納得できて助かりました。
ありがとうございました。
0317デフォルトの名無しさん
2005/11/17(木) 01:16:310318デフォルトの名無しさん
2005/11/17(木) 11:36:57いや、真っ先に背理法を理解すべきでは？
0319デフォルトの名無しさん
2005/11/17(木) 12:27:310320デフォルトの名無しさん
2005/11/17(木) 13:05:040321302
2005/11/17(木) 16:06:10素数を順番にかけるとint型では、23までしかいけなかったので
double型でやったら、途中からおかしな答えになりました。
下から2番目なんですが、答えが1大きくなりました。
なんでなんでしょう？
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 + 1 =
6469693231 is 331 x 19545901
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 + 1 =
200560490131 is a prime.
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 + 1 =
7420738134811 is 181 x 40998553231
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 + 1 =
304250263527211 is 61 x 4987709238151
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 + 1 =
13082761331670032 is 2 x 6541380665835016
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 x 47 + 1 =
614889782588491390 is 2 x 307444891294245700
0322デフォルトの名無しさん
2005/11/17(木) 16:08:500323デフォルトの名無しさん
2005/11/17(木) 17:01:31浮動小数点表現の仮数部が 52 ビットのとき、精度は 15.6 桁。
…って、計算機の初歩の初歩だろうに。
0324302
2005/11/17(木) 17:11:45レスありがとうございます。
2進数の表し方がわからなかったので、
16進数で見てますが、所々おかしなところがあり、
手直ししています。
>>323
そうでしたか、出直してきます。
0325デフォルトの名無しさん
2005/11/17(木) 21:07:29巡回セールスマン問題解くプログラム作ってるんですけど
このスレでいいっすか？
それとも数学板に行ったほうがいいですかね？
http://www.watanabe.nuie.nagoya-u.ac.jp/member/jien/lectures/tokuron/toku5.pdf
↑でとりあえず理屈はわかったんだけど
摂動行列の決め方がわからん。
ていうか
あるルート候補から次のステップのルート候補作るときに
全部シャッフルしたらさすがに効率悪そうだし
隣同士入れ替えただけだともろ局所解に引っかかりそうだし。
なんか巡回セールスマン向けのうまい方法
（あるルートXnからX(n+1)を作るアルゴリズム）
だれかしらないですか？
0326デフォルトの名無しさん
2005/11/17(木) 22:09:18アニーリング関数が適当なら、その隣同士とかでやったとして
局所的なくぼ地にはまってしまうような場合であっても
少ない確率ではあるけどそのくぼ地を乗りこえることかできるから
結局それなりにうまくいくんじゃないのかな
0327デフォルトの名無しさん
2005/11/18(金) 00:37:31つ[long long]
0328デフォルトの名無しさん
2005/11/19(土) 09:22:25つ[多倍長演算]
0329デフォルトの名無しさん
2005/11/19(土) 10:35:170330デフォルトの名無しさん
2005/11/19(土) 11:18:12OK!
0331デフォルトの名無しさん
2005/11/19(土) 11:26:320332デフォルトの名無しさん
2005/11/19(土) 11:29:020333デフォルトの名無しさん
2005/11/19(土) 13:23:14サンクス。
変換しても出てこないので違うのかなと思っていた。
0334デフォルトの名無しさん
2005/11/19(土) 13:51:31かな漢字変換辞書が全ての技術語を網羅しているわけがないだろう。
それともあれか、藻前は「へんかんできないからそんな字ない」とか言っちゃう小学生か?
0335デフォルトの名無しさん
2005/11/19(土) 19:32:310336デフォルトの名無しさん
2005/11/19(土) 20:10:17そんなにキツく言わんでも・・。
0337デフォルトの名無しさん
2005/11/20(日) 22:49:35そのタプルが大きさ N の全順列中において辞書順で何番目かを返すアルゴリズムを
実装したいんですが，どういうアルゴリズムが考えられますか？
例えば， {1, 2, 0} を与えたら 4 を返すような感じのアルゴリズムです．
0338デフォルトの名無しさん
2005/11/20(日) 22:53:590339デフォルトの名無しさん
2005/11/20(日) 23:01:25tuple
【名】 組、《コ》タプル
0340デフォルトの名無しさん
2005/11/20(日) 23:08:44それの例のまま、 {1, 2, 0} で考えると、
最初が 1 → このタプルより前には {0, *, *} がある → 前に 2! 個 ＝ 2個 ある
次が 2 → でも1は出てる → これより前で、{0, *, *} 以外のものは {1, 0, *} → 1個
だから、{1, 2, 0} より前には3個のタプルがあるから、
{1, 2, 0} は4番目。って感じ？
1つ数字増やして {2, 3, 1, 0} とかでいくと、
最初、{0, *, *, *} と {1, *, *, *} 数えて、 3! ＝ 6個
次、{2, 0, *, *} と {2, 1, * *} で 2×2! ＝ 4個
次、{2, 3, 0, *} があるから 1個
計11個前にあるから {2, 3, 1, 0} は12番目。
0341デフォルトの名無しさん
2005/11/20(日) 23:10:03で、マッチングをとる。
0342デフォルトの名無しさん
2005/11/20(日) 23:17:15最後の結果も18だわ。
>>341
それだと順列生成自体が糞重たいし、コーディング結構難しくない？
0343デフォルトの名無しさん
2005/11/21(月) 00:32:410344デフォルトの名無しさん
2005/11/21(月) 01:58:190345デフォルトの名無しさん
2005/11/21(月) 11:28:06std::vector<int> src, arr;
src.push_back(1);
src.push_back(2);
src.push_back(0);
arr = src;
size_t ct = 0;
do {
#ifdef _DEBUG
std::cout << "{";
for (int i=0; i<arr.size(); i++)
std::cout << (i? ", ": "") << arr[i];
std::cout << "}" << std::endl;
#endif // _DEBUG
} while (ct++, std::prev_permutation(arr.begin(), arr.end()));
std::cout << ct << std::endl;
結果:
{1, 2, 0}
{1, 0, 2}
{0, 2, 1}
{0, 1, 2}
4
0346デフォルトの名無しさん
2005/11/21(月) 15:45:08素直に説明を読むと、
「1からNまでのN個の順列組み合わせを辞書式順序で並べたとき
各組合わせは何番目？」
という問だと思うのだが、いきなり組の要素に0があったりするのはなぜ？
0347337
2005/11/21(月) 18:58:04素直にやるなら，前から順に読んでいって現れた数字を記録しないとならないですよね．
前から順に読んで現れた数字より大きい数字を全てデクリメントしていくやり方も
あるのかな？参考になります．
>>345
これって 340 さんの考え方じゃなくてむしろ 341 さんの考え方ですよね？
>>346
すいません．最初，説明を「0 から N-1」と書いてて後で直したんですが
例を書き直すのを忘れてました．337 の正しい例は {2, 3, 1} です．
0348デフォルトの名無しさん
2005/11/22(火) 04:02:57それでいいんでね？
(1)result=0で初期化
*ここで、1〜Nの整数が、適当に並べ替えられて並んでいたとして、
(2)N=1ならresult+1を返し終了。
(3)左端の数aに対し (a-1)*(N-1)! を計算し、resultに加算。
(4)列の中で、aより大きい要素は全て1だけ減らす(小さい要素はいじらない)。
(5)先頭のaを切り落とし(N=N-1)、残った列に対し*に戻る。
0349340
2005/11/22(火) 12:02:43それ見てて思ったけど、
(3)（階乗計算）とか(4)の計算に掛かる時間を考えると、
>>345 のコードよりも計算量大きくなるかも。
>>345 だと標準ライブラリの機能そのまま使っててコード量的にも少ないし。
順列生成のアルゴリズムって、>>345 の結果見てる感じ、
バブルソートを1ステップずつやるようなものなのね。
0350デフォルトの名無しさん
2005/11/22(火) 16:31:371 から N までの N 個の異なる自然数による順序付タブル をランダムに出力せよ
0351デフォルトの名無しさん
2005/11/22(火) 18:36:000352337
2005/11/23(水) 22:03:52345 さんのコードだと平均・最悪で O(N!) な一方で
348 さんのだと平均・最悪で（階乗計算も含めて） O(N^2) ですから，
特別な事情がなければ 348 さんのを選択するのが良いと思います．
というか 348 さんのアルゴリズムで実装できました．ありがとうございました．
0353デフォルトの名無しさん
2005/11/28(月) 23:10:17フーリエ変換が趣味です。
http://hobby8.2ch.net/test/read.cgi/hobby/1133005088/
0354デフォルトの名無しさん
2005/11/29(火) 19:35:47べての方程式を解くことは困難なので、そのプログラムで解ける範囲を指定し記述せよ。』
この問題のアルゴリズムと、ソースを書いてくれませんか？
ここで悩んでいるので是非とも力を貸してください!!お願いします。
0355デフォルトの名無しさん
2005/11/29(火) 19:36:390356デフォルトの名無しさん
2005/11/29(火) 19:36:55○答え教えろ
0357デフォルトの名無しさん
2005/11/29(火) 20:08:28とりあえずオイラー法を用意して、それで解ける範囲を明示しておけばレポート通るんじゃね？
0358デフォルトの名無しさん
2005/11/30(水) 01:23:230359デフォルトの名無しさん
2005/12/07(水) 23:46:24上記のサイトで、Sinをテイラー展開で求めているようですが、
sin(0.00) = NaN (非数値)
sin(0.01) = NaN (非数値)
sin(0.02) = NaN (非数値)
・
・
となってしまいます。どこが間違っているのでしょうか？
0360デフォルトの名無しさん
2005/12/08(木) 00:11:24double Sin(double x)
{
double xx = -x * x;
double fact = 1;
double sin = x;
for(int i=1; i<100; )
{
fact *= ++i; fact *= ++i;
x *= xx;
sin += x / fact;
}
return sin;
}
0361デフォルトの名無しさん
2005/12/08(木) 00:16:080362359
2005/12/08(木) 00:39:53なるほど！ 数学関連の話で、何が合っていてどこから手をつけていいものか
困り果てているところでした。非常にお早いレス感服いたします。
ありがとうございました。
>>361
すみません。いくつか間違いがみられ、一応メールアドレスを探してみた
のですがわかりやすい位置になかったので、すぐに断念してしまいました。
0363デフォルトの名無しさん
2005/12/08(木) 00:42:210364デフォルトの名無しさん
2005/12/08(木) 01:32:540365340
2005/12/08(木) 11:29:34トップページたどれって。
全ページに連絡先入れといた方がいいのか？
>>363
それいいだすとさ、
π/2 の範囲に収まるように mod 2π とか三角関数の公式使って変換して、
sin と cos のどちらか選んで計算するとか、凝りだすときりない。
餅は餅屋と言う奴で、そういうのは数値計算屋さんにお任せしないと。
0366デフォルトの名無しさん
2005/12/08(木) 22:43:03ウェブページの作り方的な話なら、
全ページにaddress要素は入れるのが基本
address要素内には連絡先として通常メールアドレスが入る
0367デフォルトの名無しさん
2005/12/08(木) 23:13:51それ、確かに推奨はされてるけど、
ボットにアドレス収集されるのが嫌で、実際やってる人いなくない？
0368デフォルトの名無しさん
2005/12/08(木) 23:25:27俺はやってるよ
あるいは自働収集が嫌って言って
画像を使ったり余計な文字をはさんだりしてる人もいる
要は形式上の問題じゃなくて、
>>362みたいな状況にならないようにっていうのが
目的なんだし。
0369 【凶】 【308円】
2006/01/01(日) 07:54:110371デフォルトの名無しさん
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日だけなんでアレですが参考のページでもあると嬉しいです
0372デフォルトの名無しさん
2006/01/09(月) 00:49:45そりゃ、8と9に割ればいいじゃん。
0373デフォルトの名無しさん
2006/01/09(月) 00:54:24しかしその場合併合(マージ)しようとするとどんな風になるのでしょうか
グーグル先生のイメージ検索はエレメントの個数が偶数ばかりのもので・・
勉強してきます(´･ω･`)
0374デフォルトの名無しさん
2006/01/09(月) 00:56:370375デフォルトの名無しさん
2006/01/09(月) 03:02:59べつに偶数のときとかわらん。
違う数に分割されたからといって
コードの何処も変える必要なんかない。
そんな必要があったら
そもそもマージソートじゃない
0376デフォルトの名無しさん
2006/01/09(月) 10:30:58例えば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 読めば解るよ。
0377デフォルトの名無しさん
2006/01/09(月) 13:56:17つーか、聞く前に一度自分で実際にやってみ。
マージって全然個数の違う2つの列相手にもできるから。
例えば極端な話 1, 16 とかで分けてもマージできる。
0378マイク ◆yrBrqfF1Ew
2006/01/23(月) 00:20:53堀江由衣の処女
0379デフォルトの名無しさん
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‐‐‐'--､_..... ｌ_,.．-'''""'- "
0380デフォルトの名無しさん
2006/01/30(月) 23:54:04中心点から角度θの軸を考え、横2W縦2Hの長方形の中心がこの軸を移動するとして
長方形の頂点が円周上にくる点の座標は？
0382デフォルトの名無しさん
2006/01/31(火) 00:41:23人にモノ聞く態度じゃねぇな。
出直して来い。
0383デフォルトの名無しさん
2006/01/31(火) 09:44:41もしかして日本語が不自由な方なんでわ？
0384デフォルトの名無しさん
2006/01/31(火) 10:41:19■ このスレッドは過去ログ倉庫に格納されています