17/07/16 16:33:07.01 8ZBD9z9c.net
お題：
自分用多倍長整数演算関数
…って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの
制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。
385:デフォルトの名無しさん
17/07/16 18:30:49.57 8+Akms5T.net
多倍長整数演算がサポートされている言語を使う
終わり
386: ◆QZaw55cn4c
17/07/16 18:54:09.85 eA1jggM5.net
>>375
C++98 URLﾘﾝｸ(codepad.org)
オートボクシング等はなく便利にはできていない．
387:デフォルトの名無しさん
17/07/16 2
388:0:34:05.63 ID:yctBkD01.net
389: ◆QZaw55cn4c
17/07/16 20:36:24.09 eA1jggM5.net
>>378
うん，FFTを使うそうだが‥いまいちよくわからない
390:375
17/07/16 20:41:46.81 8ZBD9z9c.net
>>376
仕事で言語を選べる立場になってみたいものだわ。
この言語でやってってののは多々あるけど…orz
>>377
Karatsuba-Ofman法を目指してごーごー
391:デフォルトの名無しさん
17/07/17 22:48:25.95 5edeqhg+.net
>>296
手計算で計算出来るレベルにまで計算量を減らせた
もちろん数学的な裏付け付きで
ある条件を見たせば一瞬で求まる
"123456789123456789" > 98秒
残念ながら、これだけはその条件を満たしてない
392:デフォルトの名無しさん
17/07/18 06:37:17.84 nFCFlf58.net
>>381
22とか2323もその条件を満たしてない感じ？
393:デフォルトの名無しさん
17/07/18 07:37:05.09 Ew0RSScO.net
22 は微妙
2323 は大丈夫
394:デフォルトの名無しさん
17/07/18 07:41:44.22 Ew0RSScO.net
まだコードになってないんで、
コードになったらアップします
寿司を食べる時間 < レーンの回転周期
という前提をつけちゃおうと思ったけど、
つけない方が良さそうですね
寿司を食べる時間がレーンの回転周期の整数倍の寿司は
ちょっと特別な処理が必要
395:デフォルトの名無しさん
17/07/18 08:01:32.43 Ew0RSScO.net
整数倍の寿司が無いもので
条件に当てはまらない最小は
2222
かな
396:デフォルトの名無しさん
17/07/18 08:49:51.93 YLlwVFMJ.net
>>334 SageMath
URLﾘﾝｸ(sagecell.sagemath.org)
普通に(？)多桁のisqrt()なので何の捻りも無し。
397:386
17/07/18 09:39:56.20 YLlwVFMJ.net
>>339
つ mpz_sqrt()
398:デフォルトの名無しさん
17/07/19 18:12:29.37 Np9hKHT2.net
>>296
>>373
URLﾘﾝｸ(ideone.com)
C++。結局、i7-6700のmem2G使って7分で解けた。
どうしようもない位遅いな。
でも一応題意には添えたと思う。
もう見たくない・・・。Orz
高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。
よくわからんけど、数学で頑張ってる人に期待だ。
399:386
17/07/20 01:57:16.81 Q7XnESC/.net
100のべき乗に変更
URLﾘﾝｸ(sagecell.sagemath.org)
400:デフォルトの名無しさん
17/07/21 15:21:18.13.net
>>296
URLﾘﾝｸ(ideone.com)
C++。試しに再起化してみたら処理速度倍になった。
自分の環境では3分ちょいで解ける。
相変わらずメモリ馬鹿食いするけど。
もう俺には無理。
俺の中では終了でーす。Orz
401:デフォルトの名無しさん
17/07/22 08:54:36.28 OQXA8cUK.net
>>388
数学で頑張ってる人だけど、
もうちょっとまって
>>296の問題だけなら簡単だけど、
まだ全体を解明できてない
というか、忙しくて>>381から進んでない
402:デフォルトの名無しさん
17/07/22 08:55:28.19 OQXA8cUK.net
このスレが無くならないうちに解明します
403:デフォルトの名無しさん
17/07/22 10:43:30.03 apsnR2Z0.net
>>391
wktkデス！
コード見るのが好きなのでぜひ完走していただけたらと思います。
404:デフォルトの名無しさん
17/07/23 11:26:56.94 ipiEUPYV.net
>>375
のほかの実装はでてこないねぇ‥
405:デフォルトの名無しさん
17/07/23 12:53:55.68 7fREas1L.net
>>394
使えるコードにするためには、規模がでかくなりすぎるから
406:デフォルトの名無しさん
17/07/23 14:15:20.13 ipiEUPYV.net
C/C++ で最長1000行ぐらいとみて、2日ぐらいあれば、とりあ�
407:ｦず動く 土日で仕上がってくるんじゃないかと期待してたんだが
408:デフォルトの名無しさん
17/07/23 14:18:11.58 7fREas1L.net
速度が考えられてないコードなんて実用にはならないよ
409:デフォルトの名無しさん
17/07/23 14:21:31.79 7fREas1L.net
ていうか、
コードに対する条件とか
サポートする機能とか
条件が無さすぎる
410:デフォルトの名無しさん
17/07/23 14:24:57.75 ipiEUPYV.net
速度‥か‥
どうしてもローテートとかキャリーフラグとかを使いたいから、これはアセンブラの領域になるね
よくみかけるアセンブラ中毒者が今頃爪を研いでいるのだろうか？
411:デフォルトの名無しさん
17/07/23 14:25:42.29 ipiEUPYV.net
>>398
そこは「自分用」だから自由に決めていいんでないかい？
412:デフォルトの名無しさん
17/07/23 14:49:34.77 TcY6qE9r.net
>>394
当日に >>305 で >>390 より10倍以上早いのがでているだろう。
しかも 計算量まで書いてある
413:デフォルトの名無しさん
17/07/23 14:53:19.94 ipiEUPYV.net
>>401
お題が違うのでは？
414:デフォルトの名無しさん
17/07/23 15:05:28.62 TcY6qE9r.net
>>402 >>394
確かに違った、すいません。
c++多倍長なら、karatsubaにも対応して300行くらいの以下をパクって使うのも一案
URLﾘﾝｸ(sites.google.com)
415:デフォルトの名無しさん
17/07/23 15:09:21.91 ipiEUPYV.net
>>403
base 10進ならば、表示（operator<<) が楽でいいね、なるほど、それは思いつかなかった
416:デフォルトの名無しさん
17/07/23 16:51:44.88 7fREas1L.net
>>399
通常、
処理時間のほとんどが乗算
乗算のほとんどがFFT
アセンブラの出番は当分先
417:デフォルトの名無しさん
17/07/23 16:52:43.21 7fREas1L.net
FFTのライブラリをどこからか持ってくるのでもいいけど、
それなら素直に多倍長ライブラリを持ってくれば
ってことになる
418:デフォルトの名無しさん
17/07/23 16:54:07.19 7fREas1L.net
今は浮動小数点演算が速いので、
カラツバの出番はあまりない
419:デフォルトの名無しさん
17/07/23 18:50:17.74 5CSy1R8t.net
基数を10のべき乗にするとか(printf()的なものが簡単だから)、乗算はunsigned shortやintとの
乗算に限るとか、除算無しとかいうのは…
プログラムの本体に組み込まれてしまって、再利用可能なライブラリの形で括りだされてる事の
方が少ないかｗ
420:デフォルトの名無しさん
17/07/24 00:48:44.80 XgJeE+LA.net
>>6-285 SageMath
URLﾘﾝｸ(sagecell.sagemath.org)
421:デフォルトの名無しさん
17/07/24 18:24:00.06 UuUAOyUA.net
>>408
裁定ラインとしては、乗算は Bigint×Bigint、および除算の実装ですかね、でも足し算の回数での乗算や引き算の回数での除算は嫌ですね
422:デフォルトの名無しさん
17/07/24 18:58:12.05 5ve8i6tz.net
お題：お題スレ3の>>170をファレイ数列を使って解く。
ｽﾚﾘﾝｸ(tech板:170番)
423:デフォルトの名無しさん
17/07/24 19:10:35.21 nJVItCRy.net
>>411 Ruby
def farey_sequence(n)
(1..n-1).map{|i| 1r*i/n}
end
def ans_411(m)
(2..m).map{|i| farey_sequence(i)}.flatten.uniq.sort
end
ans_411 3 #=> [(1/3), (1/2), (2/3)]
ans_411 5 #=> [(1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5)]
424:デフォルトの名無しさん
17/07/24 19:11:05.16 7nQ6Z7f9.net
>>296
超高速版が出来ました！
URLﾘﾝｸ(ideone.com)
一皿9秒が上限であれば、計算オーダーはn
関数自体は何秒でも大丈夫です
コードだけじゃ意味がわからないでしょうけど、とりあえずコードだけ
あまりテストしてないので、バグって�
425:ｽらごめんなさい
426:デフォルトの名無しさん
17/07/24 23:00:47.69 fjGi9Yh0.net
オーダーnは凄いな
427:デフォルトの名無しさん
17/07/25 05:40:32.49 ubbfnjuS.net
>>413
うーんわからん。
俺の思考とは別系統かな。
ホントに0秒で解けてるし、素晴らしい。
素直に賞賛。
428:デフォルトの名無しさん
17/07/25 11:52:16.57 bLUUDw7G.net
回転寿しの問題は、部分的な最短経路が全体の最短経路にならないんだよな
だが最短時間はレーン長の2倍程度の再帰回数で出る
そのあと数十億回再帰して総当たりしてもそれより短くならない
最後の皿から逆方向に探索してもおそらく同じ状況
429:デフォルトの名無しさん
17/07/25 11:56:47.84 bLUUDw7G.net
例えば、”122” は最短時間6だが、1周目で2番目の要素”2”をパスしないとそうならない
430:411
17/07/26 19:54:35.63 6H34MdHA.net
>>412
ファレイ数列の中間数(mediant)を再帰的に生成すると、uniqもsortも要らないのだけど、
mが3や5だと大差無いかｗ
431:デフォルトの名無しさん
17/07/26 20:50:49.45 s8dUUqTb.net
>>411
リンク先が見えません
問題文をもう一回書いてください
432:デフォルトの名無しさん
17/07/26 20:52:34.29 s8dUUqTb.net
と思ったら見れました
ファレイ数列を使って何かを解くわけじゃなくて、
ファレイ数列を求める問題？
433:411
17/07/26 23:20:07.89 6H34MdHA.net
>>420
元の問題はそういうもの(＝ファレイ数列の両端(0/1と1/1)無し版を求める問題)と
解釈してますです。
434:デフォルトの名無しさん
17/07/26 23:26:01.52 lPM9zwS7.net
#include <list>
#include <iostream>
const int N_MAX = 10;
struct RATIONAL {
int num;
int den;
};
int main() {
std::list < RATIONAL > farey;
RATIONAL zero = {0, 1};
RATIONAL one = {1, 1};
farey.push_back(zero);
farey.push_back(one);
for (int n = 1; n <= N_MAX; n++){
for (std::list < RATIONAL > ::iterator i1 = farey.begin(), i0 = i1++; i1 != farey.end(); i0 = i1, i1++) {
if (i0->den + i1->den <= n) {
RATIONAL m = {i0->num + i1->num, i0->den + i1->den};
farey.insert(i1, m);
}
}
std::cout << n << " : ";
for (std::list < RATIONAL > ::iterator i = farey.begin(); i != farey.end(); i++) {
std::cout << i->num << "/" << i->den << " ";
}
std::cout << "\n";
}
return 0;
}
435:デフォルトの名無しさん
17/07/26 23:29:22.49 lPM9zwS7.net
これから0と1を除けば良いって問題であれば、
表示のループに以下を加えれば
if (i->den != 1)
436:デフォルトの名無しさん
17/07/26 23:31:57.11 lPM9zwS7.net
問題の意味も意図も良くわからん
出題者が「そういうものと解釈しています」とか
出題者が >>418 みたいな回答をバカにする発言とか
なんか非常に感じが悪い
437:412
17/07/27 00:12:38.86 qteH6K3e.net
そもそも>>412のfarey_sequenceは定義が間違ってたわ
んでもって再帰にすると>>412より遅くなるという
Ruby
class Farey
def self.[](m)
if m == 1
[0r, 1r]
else
succ(m - 1)
end
end
def self.succ(m)
self[m].each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == m + 1
s << b
}
end
end
Farey[3] # => [(0/1), (1/3), (1/2), (2/3), (1/1)]
Farey[5] # => [(0/1), (1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5), (1/1)]
438:デフォルトの名無しさん
17/07/27 01:59:46.61 GuEy9AL1.net
>>411 Java
URLﾘﾝｸ(ideone.com)
439:デフォルトの名無しさん
17/07/28 18:51:16.80 XBSdfIgC.net
>>375
のほかの実装はでてこないねぇ‥
440:デフォルトの名無しさん
17/07/28 19:19:26.77 mqZJq6H+.net
昔brainf**kで実装したのあるけどちょっとなぁ
441:デフォルトの名無しさん
17/07/28 19:24:55.65 WViVOgsq.net
また懐かしい言語を
442:デフォルトの名無しさん
17/07/28 19:26:36.86 WViVOgsq.net
どうせならチューリングマシンで作ってよ
443:デフォルトの名無しさん
17/07/30 10:59:37.37 A7gIx2b1.net
お題：MathematicaのFareySequence[n,k](引数2つ)に相当するものの実装
URLﾘﾝｸ(reference.wolfram.com)
444:デフォルトの名無しさん
17/07/30 11:53:03.31 EQKnHSgY.net
>>431
URLﾘﾝｸ(ideone.com)
C++。一瞬計算が合わなくてビビったけど、空目だった。
インデックス概念がベーシックなんだな。
445:デフォルトの名無しさん
17/07/30 12:00:36.94 EQKnHSgY.net
っていうか、この関数インデックスに0与えたら何が出力されるんだろう・・・。
早速バグってる気がする。
446:デフォルトの名無しさん
17/07/30 12:15:40.85 EQKnHSgY.net
>>432
バグってた。のでエディトしてFIXした。
所持する数の概念勘違いしてた。
447:デフォルトの名無しさん
17/07/30 12:25:59.30 B3p9Yl5S.net
>>422の微妙な変更でいいよね
448:デフォルトの名無しさん
17/07/30 12:26:41.34 B3p9Yl5S.net
1個だけ求めるなら、もっといい方法がある？
449:デフォルトの名無しさん
17/07/30 12:27:22.69 B3p9Yl5S.net
ていうか、いい加減Fareyはもういいでしょ
他の課題の方が
450:デフォルトの名無しさん
17/07/30 12:30:15.15 EQKnHSgY.net
フィボナッチって素数何だっけ？
451:デフォルトの名無しさん
17/07/30 12:44:33.08 B3p9Yl5S.net
1, 1, 2, 3, 5, 8, ...
違うよね
452:デフォルトの名無しさん
17/07/30 12:47:15.18 EQKnHSgY.net
だよねー。>>422ってフィボナッチ使ってない？
あんまり深く考えてないだけど。Orz
453:デフォルトの名無しさん
17/07/30 12:47:30.85 B3p9Yl5S.net
じゃあ、任意の二個の数からはじまるフィボナッチ数列で、はじめから連続する素数の数が多い物を探す
って課題で
454:デフォルトの名無しさん
17/07/30 12:48:36.68 B3p9Yl5S.net
>>440
フィボナッチではない
wikipediaにのってるレベルの知識で作った
455:デフォルトの名無しさん
17/07/30 12:49:05.29 EQKnHSgY.net
あれ？俺とんちんかんなこと言ってるか？
>>422が数列としてあってるのかよくわからない。Orz
どう考えればいいんだろう。
456:デフォルトの名無しさん
17/07/30 12:53:04.00 EQKnHSgY.net
まぁ、俺のもあってるかどうかはしらんけど。＞＜；
457:デフォルトの名無しさん
17/07/30 12:56:43.60 EQKnHSgY.net
頭悪くてゴメン。爆発しそう。。。
458:デフォルトの名無しさん
17/07/30 13:01:05.96 EQKnHSgY.net
引っ込む。すまんかった。
459:デフォルトの名無しさん
17/07/30 14:17:22.65 t+CfDp82.net
>>431 Java
URLﾘﾝｸ(ideone.com)
460:デフォルトの名無しさん
17/07/30 19:16:10.29 LizATlBz.net
>>431 Ruby
def farey(n, k)
return [0r, 1r][k] if n == 1
farey(n - 1, 0..-1).each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == n
s << b
}[k]
end
461:デフォルトの名無しさん
17/08/03 07:36:01.80 cLWzUq7C.net
お題：ミンコフスキーの疑問符関数の実装
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(reference.wolfram.com)
462:デフォルトの名無しさん
17/08/03 10:39:36.15 ONmyLPuf.net
WIKIぺにコード乗ってますが。
463:デフォルトの名無しさん
17/08/03 10:48:34.50 ONmyLPuf.net
>>449のWIKIより。
/* Minkowski's question mark function */
double minkowski(double x) {
long p=x; if ((double)p>x) --p; /* p=floor(x) */
long q=1, r=p+1, s=1, m, n;
double d=1, y=p;
if (x<(double)p||(p<0)^(r<=0)) return x; /* out of range ?(x) =~ x */
for (;;) /* invariants: q*r-p*s==1 && (double)p/q <= x && x < (double)r/s */
{
d/=2; if (y+d==y) b
464:reak; /* reached max possible precision */ m=p+r; if ((m<0)^(p<0)) break; /* sum overflowed */ n=q+s; if (n<0) break; /* sum overflowed */ if (x<(double)m/n) r=m, s=n; else y+=d, p=m, q=n; } return y+d; /* final round-off */ }
465:デフォルトの名無しさん
17/08/05 17:44:11.83 40G0sflG.net
>>375
のほかの実装はでてこないねぇ‥
466:デフォルトの名無しさん
17/08/12 18:46:00.57 953va2dM.net
寿司のオーダーNのやつを理解しようとしたけどまだやってない。
その仕組みと、ほんとに正解してるのかとか。いたら誰が解説して。
467:デフォルトの名無しさん
17/08/12 19:04:22.18 Bi4KH0eW.net
>>413です
もちろん合っているつもりのコードです
作者が言っても何の説得力もありませんが
468:デフォルトの名無しさん
17/08/12 19:07:04.34 4r/z/Qd5.net
会社に帰ってこない巡回セールスマンだよね
寿司の乗った皿がノード、計算量はO(n!)
469:デフォルトの名無しさん
17/08/12 19:10:18.10 Bi4KH0eW.net
それぞれの寿司を食べている期間をレーン上の線分で表します
この線の重なり具合をpileで表しました
効率良く食べられた場合はレーンがpile_max周するまでの間に食べきることが出来ます
170行目の判定がそれで、trueの場合は効率良く食べられない場合です
470:デフォルトの名無しさん
17/08/12 19:12:06.32 4r/z/Qd5.net
>>456
もしそれで最適解が得られるなら巡回セールスマンも可能じゃないかな？
471:デフォルトの名無しさん
17/08/12 19:17:11.73 6XNTCj+p.net
巡回セールスマン問題とけたら色々応用範囲アルヨ。
マジでどっかに売り込んでもいいくらい。
天才か。
472:デフォルトの名無しさん
17/08/12 19:18:34.85 6XNTCj+p.net
社会的に言うと交通統制とかもそれじゃないかな？
信号の待ち時間問題。よくしらんけど。
473:デフォルトの名無しさん
17/08/12 19:19:17.76 Bi4KH0eW.net
効率良く食べられない方が簡単なのでその場合から
お寿司を以下のグループに分けます
----
各グループのお寿司は、レーンの特定の位置から食べ始めた場合、pile[グループ]周以内で食べ終わることが出来る
このとき、pile_max = Σ pile[グループ]
となる
---
このようなグループの分け方の最小の物が存在します
474:デフォルトの名無しさん
17/08/12 19:22:56.16 Bi4KH0eW.net
同じグループのお寿司は連続して食べます
開始時と、各グループのお寿司を食べ終わった後、最初に来るお寿司から食べはじめ、pile[グループ]以内で食べられる食べ方でそのグループを食べ終える
ということを繰り返せば最小の時間で食べ終えることが出来ます
475:デフォルトの名無しさん
17/08/12 19:26:29.79 Bi4KH0eW.net
グループ分けした時に1個のグループになった場合は、
効率良く食べられることになります
つまり、pile_max周以下で食べ終えることが出来ます
この時は、コード上にあるダミーのお寿司を追加してから最小時間を求め、ダミーのお寿司を食べてる時間を引けば求められます
476:デフォルトの名無しさん
17/08/12 19:28:18.79 4r/z/Qd5.net
うーん、よくわからん
セールスマンの巡回先を一次元にマッピングできれば同じことできそうな
無理か
477:デフォルトの名無しさん
17/08/12 19:30:27.01 Bi4KH0eW.net
グループの分け方は少し難しいです
レーンの各整数位置に対して、
お寿司の線の両端にあたる点同士
線の重なりがpile_max未満である区間の点(両端を含む)
を同じグループの点とし、
これらを続けることで最小のグループ分けが出来ます
線の両端の点のグループが、そのお寿司のグループになります
478:デフォルトの名無しさん
17/08/12 19:31:42.19 Bi4KH0eW.net
それぞれ、証明は出来ているつもりです
479:デフォルトの名無しさん
17/08/12 19:32:49.51 Bi4KH0eW.net
もちろん、一般の巡回問題はこの方法では無理です
480:デフォルトの名無しさん
17/08/12 19:37:29.23 4r/z/Qd5.net
全ノードを巡回する最短時間の問題だから、できそうな気がするけどね
481:デフォルトの名無しさん
17/08/12 19:39:44.61 2Yw2XYfL.net
372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっている
482:フリーランスのサイトはだめだ。 高額に見せているけど実際は50万前後 JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円 平凡な稼働時間の80万円の案件もある。 ユー子も求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト 473非決定性名無しさん2017/08/03(木) 15:21:30.71 JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる 自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の 間でやらしている。 446非決定性名無しさん2017/08/02(水) 22:12:48.95 JIETに毎月5千円払えば３次から入場できるだろ？ 高額をうたうフリーランスのサイトはだいたい５次から４５万円 JIETで閲覧応募できる末端価格からさらに搾取するのが高額をみせつけるフリーランスサイトでした 高額案件をみせつけるフリーランスサイトも案件の取得はJIETでした 自称エージェントはJIETから流れてくる案件を転売してるだけだった。 JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む
483:デフォルトの名無しさん
17/08/12 19:40:20.63 Bi4KH0eW.net
pile_maxとその位置から下限が得られますが、
>>296 の例では98秒の物以外はすべてその下限になっています
一個その下限になるような例を見つければ答えがわかるのですが、
自力で検索してみればわかると思いますがそのような例はあっさり見つかります
98秒の例は効率良く食べられない場合になります
効率良く食べられる側のなかでも、pileから得られる下限値より大きくなる場合もあります
484:デフォルトの名無しさん
17/08/12 19:43:06.99 Bi4KH0eW.net
いずれの場合も、PCを使わなくても手計算で十分可能です
485:デフォルトの名無しさん
17/09/15 10:14:33.05 lRMsxOf0.net
お題:
N次元で１辺のマス目がM個の魔法陣を作る
N>3(任意)、M>=3(任意)の超立方体
486:デフォルトの名無しさん
17/09/15 10:20:33.77 lRMsxOf0.net
参考
URLﾘﾝｸ(magcube.la.coocan.jp)
URLﾘﾝｸ(nadamath2012.web.fc2.com)
487:デフォルトの名無しさん
17/09/17 16:38:38.03 DSKC3zx4.net
魔方陣は1個作ればいいの？
Mが奇数か4の倍数は簡単
4で割って2余るのは検索するしかないのかな？
488:デフォルトの名無しさん
17/09/17 16:55:04.37 fthJj6jv.net
バックトラックで組もうかと思ったけど、重そうだったからやめた。
数独より重そう。
それに一列合計をどの数字にするのかちょっとわからなかった。
489:デフォルトの名無しさん
17/09/17 23:20:36.13 DSKC3zx4.net
一列合計は、M*[数字の平均]
になる
つまり
M*(M^N+1)/2
490:片山博文MZ
17/09/18 21:53:54.06 iMidYxoH.net
お題: URLから適当なサムネイルを生成するWebプログラム。
491:デフォルトの名無しさん
17/09/18 23:06:01.10 FC5+Wne9.net
お題
0以上90未満の整数nを入力として
タンジェントn°の値が有理数ならば真
そうでなければ偽を返す
492:デフォルトの名無しさん
17/09/18 23:29:46.49 45aelXxs.net
bool f(int n){return n==0 || n == 45;}
493:デフォルトの名無しさん
17/09/18 23:33:52.62 ILsR+BHw.net
sed -r -e "s/^(0|45)\$/True/" -e "s/[1-8][0-9]*/False/"
494:デフォルトの名無しさん
17/09/19 01:13:30.78 zMNLdsjY.net
tanの計算しないのはどうかと
495:デフォルトの名無しさん
17/09/19 01:57:23.24 Ten4kOds.net
計算で有理数かどうか確�
496:F？ それは非常に難しいな by 東大数学科卒
497:デフォルトの名無しさん
17/09/19 02:28:36.10 SyuGyzWY.net
>>480
そう思うなら他者を批判するより行動で示せばいいと思うよ
498:デフォルトの名無しさん
17/09/19 03:58:59.82 KVkpgN/c.net
tan1°が無理数であることの証明すら面倒くせえのに一体どんな回答を求めているんだ
499:デフォルトの名無しさん
17/09/19 06:37:25.45 Ten4kOds.net
>>483
面倒くさい？
てことは出来るの？
やってみて
500:デフォルトの名無しさん
17/09/19 07:41:26.64 KVkpgN/c.net
>>484
確か京大の過去問にあったでしょう
説明めんどいからは解法は自分で調べて
501:デフォルトの名無しさん
17/09/19 08:13:59.26 Ten4kOds.net
いや、おれは出来るよ
>>483の実力で出来るのか？と疑問に思っただけ
実力じゃなくてカンニングね
502:デフォルトの名無しさん
17/09/19 08:21:42.19 KVkpgN/c.net
何言ってんだこいつ
503:デフォルトの名無しさん
17/09/19 08:49:35.38 q1kL6yRz.net
問題が悪いな
与えられた有理数rに対し、
tan(πr)が有理数かどうか判別するプログラムを書け
ならテーブルは使えない
504:デフォルトの名無しさん
17/09/19 09:06:24.19 emxMAzY1.net
また、多倍長精度演算のないC++にはきつい問題を・・・。
505:デフォルトの名無しさん
17/09/19 11:09:01.37 q1kL6yRz.net
>>488
すいません
結果を知っていたらこれでも簡単でした
506:デフォルトの名無しさん
17/09/19 11:10:19.22 q1kL6yRz.net
>>489
多倍長を使っても解決しないでしょ
507:デフォルトの名無しさん
17/09/19 12:53:02.28 RSOddfRB.net
そもそも出題者はどういう回答を期待してるんだ？
数学の知識無しでは作れないし、数学の知識を使えば>>478になる
508:デフォルトの名無しさん
17/09/19 14:38:36.12 LvSRuVZD.net
tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数nにより
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数
証明終わり
509:デフォルトの名無しさん
17/09/19 14:54:56.80 RSOddfRB.net
>>476を解くにはあとtan(18度)が無理数であることを証明しないと
510:デフォルトの名無しさん
17/09/19 14:55:28.25 RSOddfRB.net
>>476じゃなくて>>477
511:デフォルトの名無しさん
17/09/19 16:11:41.85 HSXd4/vW.net
>>493
なるほど面白いねw
512:デフォルトの名無しさん
17/09/19 19:41:00.46 Ten4kOds.net
>>493
tan(π/4)は有理数だけど
tan(π/2)は有理数じゃない
513:デフォルトの名無しさん
17/09/19 20:13:34.35 KVkpgN/c.net
tan1(rad)が超越数であることを証明せよ
514:デフォルトの名無しさん
17/09/19 22:25:08.25 FbLYus+p.net
>>492
WolframAlphaが
is tan(pi * 1 / 180) a rational number?
→ not a rational number
と返す仕組みを知りたかった
515:デフォルトの名無しさん
17/09/19 22:57:34.84 Ten4kOds.net
xが有理数、tan(πx)が有理数 ====> xは1/4の倍数
って覚えてるだけかと
516:デフォルトの名無しさん
17/09/20 14:48:00.57 jgmli1ek.net
>>493
は加法定理で（1-tanαtanβ）が０になってはまずいので
０度以上９０未満の範囲内に限定しないといけないな。
tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数で、かつ 0 <= nα < 90なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数 n ( 0 <= n < 90 ) により
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数
517:デフォルトの名無しさん
17/09/20 14:51:06.46 jgmli1ek.net
tan(1)だけじゃなくて
>>477 >>478 も証明できるかな？？？
つまり整数 n ( 0 <= n < 90 ) において
tan(n)が有理数になるのはn=0,45に限ることの証明
tan(90-n) = 1/tan(n) なので
n ( 0 <= n < 45 ) の範囲で証明されればＯＫ
またtan(45)が有理数で加法定理で減算し
tan(45-n):有理数 ⇔ tan(n):有理数 ( 0 <= n < 45 )
も成立
518:デフォルトの名無しさん
17/09/20 14:51:42.84 jgmli1ek.net
60の約数 はtan(n)無理数
1,2,3,4,5,6,10,12,15,20,30
519: これの45-n もtan(n)無理数 44,43,42,41,40,39,35,33,25,15 この約数で、まだ含まれていないもの 11,22,21,8,13,7 45-nにより 34,23,24,37,32,38 この約数で、まだ含まれていないもの 17,16,19 45-nにより 28,29,26 この約数で、まだ含まれていないもの 14 45-nにより 31 ここまでの数を並べると 01,02,03,04,05,06,07,08,**,10, 11,12,13,14,15,16,17,**,19,20, 21,22,23,24,25,26,**,28,29,30, 31,32,33,34,35,**,37,38,39,40, 41,42,43,44 ９度の倍数の証明のみが残された
520:デフォルトの名無しさん
17/09/20 16:48:28.32 UU/UGcdT.net
だから>>494と書いたんだけど
521:デフォルトの名無しさん
17/09/20 21:20:48.49 8kWE0pQL.net
tan(1 rad)が超越数であることは誰も証明できないの
522:デフォルトの名無しさん
17/09/20 21:27:13.08 UU/UGcdT.net
プログラムに証明させる問題？
523:デフォルトの名無しさん
17/09/20 22:23:37.78 vEoThqNS.net
なぜラジアン？
話の流れ的にはtan(1度)だろ
524:デフォルトの名無しさん
17/09/20 22:25:37.42 vEoThqNS.net
と思ったけど、簡単すぎた
525:デフォルトの名無しさん
17/09/21 16:21:06.33 na02B6ss.net
[1] 授業単元名：FizzBuzzクイズ
[2] 問題文(含コード&リンク)：
[3] 環境
[3.1] OS： (Windows/Linux/等々)特に問わない
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)特に問わない
[3.3] 言語： (C/C++/どちらでも可 のいずれか)特に問わない
ｽﾚﾘﾝｸ(prog板:401番)
FizzBuzzクイズ
1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
999.fizz.buzz #=> 999
となるようなメソッドfizz、buzzは定義可能か？
可能である場合、同様にgizzを追加定義し、
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz" と拡張・応用ができるか？
メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。
526:デフォルトの名無しさん
17/09/21 19:58:51.31 +ykHPOb/.net
まともに仕様を書けない出題者
527:デフォルトの名無しさん
17/09/22 07:02:49.79 aD9oWCn2.net
これ普通の発想では無理
528:デフォルトの名無しさん
17/09/22 07:14:29.33 eEMHecr4.net
>>509
修正
×999.fizz.buzz #=> 999
○997.fizz.buzz #=> 997
529:デフォルトの名無しさん
17/09/22 07:55:33.84 FtjqsiSd.net
>>509
C++版
URLﾘﾝｸ(ideone.com)
530:デフォルトの名無しさん
17/09/22 08:00:39.43 pX6TouLp.net
仕様が謎
531:デフォルトの名無しさん
17/09/22 08:13:32.67 FtjqsiSd.net
>>509
C言語
URLﾘﾝｸ(ideone.com)
532:デフォルトの名無しさん
17/09/22 09:43:07.90 eeRMTLx0.net
外部出力を伴う関数（あるいはメソッド）なら簡単
たぶん関数（あるいはメソッド）の返値がそうなるようにって意味かと
（じゃないと普通に書けてクイズにならない）
たしか数理学的にはこういう関数は書けないことになっていたはず
533:デフォルトの名無しさん
17/09/22 12:43:18.77 qmG6L9xB.net
>>509 や >>516 みたいなのとは絶対に一緒に仕事をしたくない
534:デフォルトの名無しさん
17/09/22 12:43:56.86 qmG6L9xB.net
別に戻り値にしても大して変わらんけど
535:デフォルトの名無しさん
17/09/22 12:51:02.25 qmG6L9xB.net
C言語だとトリッキーな技を使わないと出来ない
同じ関数名で複数関数を作れないから
2段や3段重ねて、intを受けて文字列を返すのは普通には無理
C++だと簡単
大きく分けて２つの方法がある
C++でも数値によって戻り値の型を変えるのは無理
数値がconstexprで
536:良いなら出来るだろうけど
537:デフォルトの名無しさん
17/09/22 14:57:30.68 eEMHecr4.net
>>513
＞int l_ = 3
これ、なんとかならないか？
538:デフォルトの名無しさん
17/09/22 16:30:21.56 W1Y66+yK.net
>>520
関数インターフェース的にはその値を与えることが出来ない
別の関数か何かで変えるかインターフェースを変えるしか
539:デフォルトの名無しさん
17/09/22 16:41:43.04 W1Y66+yK.net
>>516
戻り値を文字列にする方法
方法１
段階によって引数と戻り値の型を変える
S1 fizz(int n);
S2 fizz(S1 s);
std::string fizz(S2 s);
※テンプレートを使うと楽
方法２
戻り値をstd::string固定にしてなんとかする
方法２-１
戻り値は常に結果の文字列にし、パラメーター以外で情報を渡す
方法２-２
文字列に情報をエンコードして入れる
最終型段だけ結果を返すようにする
方法３
戻り値を結果文字列そのままではなく、文字列情報を含む情報とする
(これは反則かな？)
540:デフォルトの名無しさん
17/09/22 16:44:03.80 W1Y66+yK.net
方法２-１であれば >>520の問題は解決する
ただし、そのままだとスレッドセーフじゃなくて気持ち悪い
541:デフォルトの名無しさん
17/09/22 16:48:22.63 eEMHecr4.net
>>509
#=>
これって ruby の記法だったかな？評価値を変えたいようだ
542:デフォルトの名無しさん
17/09/22 18:17:47.82 eeRMTLx0.net
例えばRubyだと文字列を含め組み込み型にインスタンス変数を仕込めるので
たぶんそれで次のメソッドに情報を渡せる
543:デフォルトの名無しさん
17/09/22 19:04:29.86 FtjqsiSd.net
>>522 の方法２-１
C++版
URLﾘﾝｸ(ideone.com)
外部情報は「n」のみ
複数スレッドや割り込みハンドラからコールする時はこのnが問題になるんで
なんとかしてstd::stringに埋め込めれば良いんだけど
>>525
問題を変えちゃダメだよね
> [3.3] 言語： (C/C++/どちらでも可 のいずれか)特に問わない
544:デフォルトの名無しさん
17/09/22 19:08:43.22 FtjqsiSd.net
8行目、なんとなく文字列から判別してみたけど、
素直にnと同じように外部にフラグを持てば条件が減る
(文字列の最後が数字にならないとか文字コードが連続してるとか)
545:デフォルトの名無しさん
17/09/22 19:09:11.03 pX6TouLp.net
「(C/C++/どちらでも可 のいずれか)特に問わない」って日本語がまず謎
有限個の具体例しか与えられていないので仕様も謎
546:デフォルトの名無しさん
17/09/22 19:26:24.34 FtjqsiSd.net
出題者の選択枝が [C/C++/どちらでも可] の３個あって、出題者がその「いずれか」を選ぶ
というフォーマットを使った出題
出題者は回答者に対し『その３個のどれでも良いよ』という意味で「特に問わない」と
と私は解釈した
つまり、回答者の選択枝はCかC++のどちらかだと
出力する文字列のルールはリンク先を見れば大体わかる
gizzが7の倍数かどうかは実際には不明で、実は14で割ると7余る数かもしれないが...
リンク先に「プリントする」とあるので
printfなどで標準出力に出せば良いのかと思ったが、
>>516の解釈は違うらしい
数値の場合だけ""でくくってないので、
文字列の場合は""をくっつける必要があるのか、
型を変えろと言っているのかはよくわからん
いずれにしろ、CやC++では値によって戻り値の型を変えるのは不可能
547:デフォルトの名無しさん
17/09/22 19:32:11.08 FtjqsiSd.net
いずれにしろ、
>>510 >>514 >>517
548:デフォルトの名無しさん
17/09/22 19:33:47.07 eEMHecr4.net
>>529
＞回答者の選択枝はCかC++のどちらかだと
いや、そうじゃなくて、本当に「特に問わない」、どういったらいいかな、このテンプレはC宿題スレのものを、そのまま頂戴しただけじゃない？
549:デフォルトの名無しさん
17/09/22 19:36:43.23 FtjqsiSd.net
>>531
君は出題者なのか？違うのか？
立場をはっきりと
550:デフォルトの名無しさん
17/09/22 19:39:18.64 FtjqsiSd.net
出題者なら０点
551:デフォルトの名無しさん
17/09/22 19:43:00.43 pX6TouLp.net
>>529
なるほど
.gizzは、与えられた数字に対してfizzbuzzが数字になるなら"Gizz"、
それ以外の場合は所定の位置(説明省くけど)に"Gizz"を挿入するものなのかと思ってたわ
552:デフォルトの名無しさん
17/09/22 19:51:22.72 FtjqsiSd.net
確かに
7の倍数じゃなくて1の倍数でも良いよな
たまたま >>509 の例がすべて7の倍数になってただけで
この場合、上にあげた３個のコードいずれも
7 を 1 に変えてくださいな
553:デフォルトの名無しさん
17/09/22 19:54:43.95 FtjqsiSd.net
そろそろ
出題者の模範解答
よろしくね
554:デフォルトの名無しさん
17/09/22 20:00:08.36 eEMHecr4.net
え゛
0点の出題だしー模範解答の質も推して知るべし、なんじゃないでしょうか……：－）
555:デフォルトの名無しさん
17/09/22 20:35:12.69 aD9oWCn2.net
>>526
↓この但し書きがあるってことは、問題作成者（≠出題者）としてはC/C++限定とは考えてはいないだろう
> メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
> オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。
そもそもここで出題する時点で [3] の縛りは意味をなさないよ
556:デフォルトの名無しさん
17/09/22 20:43:54.80 W1Y66+yK.net
>>509に書いてある以上は、それに従うのが基本
557:デフォルトの名無しさん
17/09/22 20:47:11.96 W1Y66+yK.net
と思って私は回答しましたが、
他の人が他の解釈で回答することまで否定はしません
558:デフォルトの名無しさん
17/09/22 20:47:48.19 W1Y66+yK.net
ということで、
>>538 よろしく！
559:デフォルトの名無しさん
17/09/23 03:26:09.79 nBwtcNcI.net
>>509 Ruby >>525の方針で
URLﾘﾝｸ(ideone.com)
560:デフォルトの名無しさん
17/09/23 05:00:15.00 FxaWa0db.net
>>509 F#
URLﾘﾝｸ(ideone.com)
561:デフォルトの名無しさん
17/09/23 09:40:19.02 9eQI4Qct.net
>>509
@Mathematica
URLﾘﾝｸ(ideone.com)
入力値（n）をリストにして次の関数に渡さないとﾀﾞﾒﾎﾟ
562:デフォルトの名無しさん
17/09/23 11:10:41.17 koNmB6po.net
PerlやPythonは？
563:デフォルトの名無しさん
17/09/23 11:25:56.13 7PRDVMsP.net
ネタバレになるけど
このクイズはグローバル変数を使えばそれで済んでしまうシンプルな話なんだけど、それをあえて
- 各言語の機能を熟知・駆使して、面白くしたりひと工夫したりする（たとえばスレッドセーフとか）
- 前者のしくみと、7の倍数のgizzの拡張に必要な追加を最小限にすることを両立させる
というポイントが楽しみどころなんじゃないかな
564:デフォルトの名無しさん
17/09/23 11:29:36.36 w6RxEhSu.net
>>509
URLﾘﾝｸ(ideone.com)
C++。題意は満たしてないけど、自分が書くとこんな感じだな。
末尾判定難しい。
565:デフォルトの名無しさん
17/09/23 17:45:33.07 tyQvRaHd.net
>>509
>>536
>>524～>>547 の方法を想定
Java: URLﾘﾝｸ(ideone.com)
566:デフォルトの名無しさん
17/09/23 17:47:47.85 tyQvRaHd.net
× >>524 >>547
○ >>524 >>542
567:デフォルトの名無しさん
17/09/23 18:26:18.44 80k6Tqnu.net
関数の入出力の型が同一である必要がある
Cならintをchar*と解釈するわけにいかないから構造体だろう
568:デフォルトの名無しさん
17/09/23 22:30:47.29 PEiEI8OX.net
スレッドローカル変数で
書いてみている
569:デフォルトの名無しさん
17/09/23 22:51:39.70 PEiEI8OX.net
>>509 Squeak Smalltalk だけどなんとか >>547 っぽい方法で
| FizzBuzzQuiz |
FizzBuzzQuiz := Trait named: #FizzBuzzQuiz uses: #() category: 'FizzBuzz-Quiz'.
FizzBuzzQuiz compile: 'isDivisibleBy: m
^(Processor activeProcess environmentAt: #
570:fbValue) isDivisibleBy: m'. FizzBuzzQuiz compile: ', str Processor activeProcess environmentAt: #fbValue put: self. ^str'. FizzBuzzQuiz compile: 'fizz ^(self isDivisibleBy: 3) ifTrue: [self, ''Fizz''] ifFalse: [self]'. FizzBuzzQuiz compile: 'buzz ^(self isDivisibleBy: 5) ifTrue: [self, ''Buzz''] ifFalse: [self]'. {Number. String} do: [:each | each uses: FizzBuzzQuiz]. 1 fizz buzz. "=> 1 " 3 fizz buzz. "=> 'Fizz' " 5 fizz buzz. "=> 'Buzz' " 15 fizz buzz. "=> 'FizzBuzz' " 14 fizz buzz. "=> 14 " FizzBuzzQuiz compile: 'gizz ^(self isDivisibleBy: 7) ifTrue: [self, ''Gizz''] ifFalse: [self]'. 7 fizz buzz gizz. "=> 'Gizz' " 21 fizz buzz gizz. "=> 'FizzGizz' " 35 fizz buzz gizz. "=> 'BuzzGizz' " 105 fizz buzz gizz. "=> 'FizzBuzzGizz' " 105 fizz gizz buzz. "=> 'FizzGizzBuzz' "
571:デフォルトの名無しさん
17/09/24 08:25:43.37 wOaJDXIV.net
>>552
×>>547 っぽい方法で → ○>>542 っぽい方法で
572:デフォルトの名無しさん
17/09/24 08:49:01.13 wOaJDXIV.net
>>509 Ruby >>542 を >>552 と同様の手法でリファイン
URLﾘﾝｸ(ideone.com)
573:デフォルトの名無しさん
17/09/25 19:17:51.82 WU5gUeBt.net
>>509 c
URLﾘﾝｸ(ideone.com)
・構造体つこうた
・gizzの「追加定義」については簡易解釈
574:デフォルトの名無しさん
17/10/15 20:26:14.16 12RNBD+4.net
過去問を眺めていたが、もっとお気楽な問題が多かったようですね
肩慣らし問題を一つ
問題
循環小数を有理数に直せ。
循環節は括弧をつかって表現する。
例
0.[555] = 5/9
0.3[33] = 1/3
12.[345] = 4111/333
1.2[34] = 611/495
575:デフォルトの名無しさん
17/10/15 21:45:12.25 IPnwHMWa.net
連分数を使うのかね
576:デフォルトの名無しさん
17/10/15 23:12:59.97 Y75uJW9z.net
>>556 Java
URLﾘﾝｸ(ideone.com)
577:デフォルトの名無しさん
17/10/17 15:01:04.33 qd6dTZ1I.net
循環小数は有理数な訳だが
578:デフォルトの名無しさん
17/10/17 16:22:17.58 kN20YVKE.net
0.[555] = 0.[5] = 5/9
0.3[33] = 0.[3] = 3/9
12.[345] = 12+345/999
1.2[34] = 1.2+34/990
579:デフォルトの名無しさん
17/10/17 18:47:49.98 ELG/Hivs.net
てすと
580:デフォルトの名無しさん
17/10/18 11:15:59.21 xwRaz5Kx.net
>>560
おお。そういう法則で行けるのか。
きっと数学では大昔に証明されてるんだろうけど知らなかった。(または忘れたのかなあ？)
581:デフォルトの名無しさん
17/10/18 11:35:57.38 bG8m3FQp.net
ああ。なんとなくわかった。10の桁数乗の値で割るとそっくりそのまま小数点以下になるが
1足りないから循環するのか。ああ、しかし、数学的にどう表現したらいいかわからない。w
582:デフォルトの名無しさん
17/10/18 15:51:59.37 +Osy4cjh.net
お題：顔文字(^o^)があります。この(^o^)を左右に動かしながら出力します。(^o^)は左から右へ一文字ずつ動き、端に到達した瞬間だけ(^o^)から(>_<)に変化し、また(^o^)に戻って左端へ行き、同じように繰り返します。
端から端までは最初80文字分の幅がありますが、(^o^)が端に達した回数だけ1文字ずつ狭くなっていき、最終的に(^o^)の端まで狭くなり、(^o^)が動けなくなります。(^o^)が動けなくなったらプログラムを終了してください。
583:デフォルトの名無しさん
17/10/18 17:36:32.86 jSYDae9q.net
>>564 Bash (builtins)
URLﾘﾝｸ(ideone.com)
幅80文字だと出力が長くなりすぎて途中で切られるので50文字にしました。
584:デフォルトの名無しさん
17/10/18 19:53:42.77 4F2aMcKp.net
ウインドウズでエスケープシーケンス扱うのにおまじないいるからメンドクセー。
585:デフォルトの名無しさん
17/10/18 21:05:28.73 xwRaz5Kx.net
>>564
改行せずにカーソルを先頭に戻すのは CR (13) の出力で良いのか？
それとも curses ライブラリを使うべき�
586:ｩ？
587:デフォルトの名無しさん
17/10/19 01:56:08.11 Lj1i7npR.net
>>567
好きな方をどうぞ
curses使うのはいいですね
こちらからは見れませんが
588:デフォルトの名無しさん
17/10/19 03:35:28.31 CNJYIyj0.net
じゃ、とりあえず CR 出力版。Perl プログラム。
但し、待ち時間入れないと速すぎて見えないので適当に usleep を入れた。
テストした環境は Linux で端末は Windows の TeraTerm。
TERM=xterm の状態。
但し、プログラムを貼り付けたサイト(paiza.io)での出力はおかしくなる。
何故なら端末として動いてないから。
試したい場合はプログラムをコピーして自分の環境のエディタ等にペーストして保存後に実行して。
URLﾘﾝｸ(paiza.io)
589:デフォルトの名無しさん
17/10/19 05:11:39.88 sgSfn4oM.net
>>564
URLﾘﾝｸ(ideone.com)
C++。改行でやってみた。ちょっと汚い。
590:名無しさん＠そうだ選挙に行こう！ Go to vote!
17/10/22 11:49:54.00 /Umsqxkx.net
お題:A～Z、1～9で出来たランダムな文字列がある(文字列はプログラム開始時に自動的に決めてよい)
キーを2つ決めて(←→キーが自然かも)例えば→キーを押すと、文字列のうち2～9があるか
どうかを調べ、あればそのうち一つをランダムに選び、数字を一つ減らし(9なら8へ)、左右ランダムに
1を置く
つまり2以上の数字文字があればそこがゴムのような役目をして文字列が伸びる
全部の数字文字が1になったら何もしない
逆に例えば←キーを押すと、文字列のうち1～8があるかどうかを調べ、そのうちランダムに一つを
選び、その左右どちらかに数字文字がないかを調べ、足した合計が9を超えないようなら足し合わせて
数字文字をその合計値にし、文字列を1つ縮める
足し合わせた合計が9を超えるようなら他の数字文字もランダムに同様に一つ選び、足し合わせて
9を超えない数字文字の部分が見つかったらそれを一つだけ足し合わせて縮める
全部の数字文字が9になるか、9に満たないが足し合わせると9を超えるようになったら何もしない
591:デフォルトの名無しさん
17/10/23 04:21:48.29 sHZ1Pe4U.net
>>571
URLﾘﾝｸ(ideone.com)
C++。デバッグ難しくてやる気がしないのでバグってるかも。
カーソルキー取るの面倒だからASキーにしておいた。
こんな感じでいいのか？
何のシミュレータかしらんけどめんどくせーな。
592:デフォルトの名無しさん
17/10/23 04:35:24.25 sHZ1Pe4U.net
あ、それと、文字列で計算するのめんどくさかったから、数字でやった。
そっち事情なんか知ったこっちゃない。
593:デフォルトの名無しさん
17/10/23 05:46:30.69 iFI38Dlw.net
%%%%1000%%%%
000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end
594:デフォルトの名無しさん
17/10/23 17:28:50.67 f/2PkHQ/.net
>>574
全く読めねぇｗ
595:デフォルトの名無しさん
17/10/23 20:53:32.54 burVCZw1.net
ランダムの分布は指定なし？
596:デフォルトの名無しさん
17/10/23 23:01:59.68 sHZ1Pe4U.net
いろ
597:んなところでたまに見かけるけど、>>547 ってPGなの？
598:デフォルトの名無しさん
17/10/24 06:49:36.20 kt50Dt6N.net
PGとは？
599:デフォルトの名無しさん
17/10/24 07:14:59.91 Ohc+APnW.net
プロパンガス
600:デフォルトの名無しさん
17/10/24 08:55:25.49 TzjXrYm3.net
パーフェクトグレイド
601:デフォルトの名無しさん
17/10/24 11:04:02.33 2qWQgTrR.net
>>575>>577
>>574はvbsウィルスの一部だよ
つまりワクチンソフトに引っかかるとこのログが検疫されるので注意
602:デフォルトの名無しさん
17/10/24 21:14:43.61 6ceRFBNE.net
>>581
さんくす。
603:デフォルトの名無しさん
17/10/25 20:13:14.36 gieh1Z5o.net
お題
())())のように括弧のみからなる文字列が与えられるので
すべての括弧が正しく対応付けされるためには
最低で何箇所の括弧を逆向きに変更すればよいか求めよ
例えば上の例では2文字目か3文字目を変更すればよいので1を出力せよ
何文字変更しても正しく対応付けできない場合は-1を出力せよ
) -> -1
())()) -> 1
)()()( -> 2
)))((( -> 4
(())())((())(()( -> 3
())((())()))()(((()))()((((((((()()(())) -> ?
604:デフォルトの名無しさん
17/10/25 21:21:26.00 /TQ9iqwZ.net
>>583 Java
URLﾘﾝｸ(ideone.com)
605:デフォルトの名無しさん
17/10/26 00:42:38.67 0Gn/TXrF.net
>>583
Ruby
URLﾘﾝｸ(ideone.com)
606:デフォルトの名無しさん
17/10/26 07:09:40.17 vEkFybta.net
>>583
URLﾘﾝｸ(ideone.com)
C++。効率とかショートコーディングとかそういうものをかなぐり捨ててべた書き。
あってるかな？
607:デフォルトの名無しさん
17/10/26 08:33:36.44 8oLfrbud.net
おむ
608:デフォルトの名無しさん
17/10/26 08:35:57.56 8oLfrbud.net
誤爆
>>583 Ruby
def calc str
return -1 if str.size.odd?
ary = optimise str.scan(/(?=.)(\(*)(\)*)/).map{|a, b| a.size - b.size}
(-ary[0] + ary[1].to_i).abs/2 + ary[0]%2
end
def optimise ary
a = ary.reject(&:zero?).chunk(&:positive?).to_a.transpose[1].map(&:sum)
return a if a.size < 3
a.unshift(0) if a[0] < 0
optimise a.each_slice(2).map(&:sum)
end
STR = %w{
)
())())
)()()(
)))(((
(())())((())(()(
())((())()))()(((()))()((((((((()()(()))
}
STR.each{|s| puts "%s -> %d"%[s, calc(s)]} #=>
) -> -1
())()) -> 1
)()()( -> 2
)))((( -> 4
(())())((())(()( -> 3
())((())()))()(((()))()((((((((()()(())) -> 5
609:デフォルトの名無しさん
17/10/26 19:12:02.71 MqWL4ZqL.net
>>583 ruby
URLﾘﾝｸ(ideone.com)
610:デフォルトの名無しさん
17/10/27 22:31:59.57 sfTuRN3o.net
>>583
@Mathematica
URLﾘﾝｸ(ideone.com)
611:デフォルトの名無しさん
17/11/04 00:05:20.36 4+O3ouw4.net
Quineの派生ということで、コードそれ自身を反転させたものを出力せよ
反転とは文字列"abc\ndef"を"fed\ncba"にすること
612:デフォルトの名無しさん
17/11/04 01:52:41.37 P09Vk2Mx.net
数列 6,66,666,6666,66666.....
これをダミアン数列と呼ぶことにしましょう
nを自然数としたときn^n（^はべき乗）の桁数（１０進数で）が
ダミアン数列のどれかになることはあるか？
初歩的な計算で7^7=823543が6桁になることがわかります
問 このような不吉な数は
7のみである
有限個存在する
無限に存在する
ここまで書いてみたけどこの問題だとプログラミングのお題じゃないね
数論で解けるのかなあ？
改めてお題
ダミアン数列の最初の10項につながる不吉な自然数はあるか、あるとすれば
その数はいくつ
613:か 力技では時間が掛かりすぎると思うので工夫してみてください
614:デフォルトの名無しさん
17/11/04 03:18:31.96 RXqoYVvx.net
意味不明
615:デフォルトの名無しさん
17/11/04 03:39:51.41 pxF/c+yt.net
>>591
URLﾘﾝｸ(ideone.com)
C++。VCオンリー。
ウニコード対応しようと思って色々やってたけど、なんかうまくいかねー。
一応VCではうまくいってるっぽいけど、GCCと共通のコードはまだ規格的にきつそうだ。
うへー。大変だったわ。やっぱ、文字列は鬼門。
616:デフォルトの名無しさん
17/11/04 04:34:35.38 tUO6oLmA.net
>>592 Java
URLﾘﾝｸ(ideone.com)
617:デフォルトの名無しさん
17/11/04 08:04:59.76 bqd73Ayh.net
>>591 Squeak/Pharo Smalltalk
thisContext method getSource reversed allButLast: 8
"=> '8 :tsaLtuBlla desrever ecruoSteg dohtem txetnoCsiht' "
618:デフォルトの名無しさん
17/11/04 10:09:48.41 VZ1zDZPp.net
>>591 ruby
URLﾘﾝｸ(ideone.com)
619:デフォルトの名無しさん
17/11/05 14:54:08.02 rWIlHQ+T.net
>>597 ruby
d="]esrever.d,d[%'d=p%;s%' stup";puts '%s;%p=d'%[d,d.reverse]
#=> ]esrever.d,d[%'d=p%;s%' stup;"puts '%s;%p=d'%[d,d.reverse]"=d
620:デフォルトの名無しさん
17/11/05 14:54:35.06 rWIlHQ+T.net
安価ミスったorz
621:デフォルトの名無しさん
17/11/05 22:47:04.05 Pt23fyK7.net
>>595
2で割らずにシフトしてたり芸が細かいですな
622:片山博文MZ
17/11/07 23:38:24.35 BS6pey7a.net
お題。ツイッターのフォロワーを使ってお金を稼ぐ具体的な方法を思い付く限り列挙せよ。
623:デフォルトの名無しさん
17/11/07 23:48:06.18 aP9yM4om.net
やだ。
624:デフォルトの名無しさん
17/11/08 00:39:27.61 z/y1zyUv.net
プログラミングに関係ないお題は却下
625:デフォルトの名無しさん
17/11/08 20:48:53.00 XbOytUUT.net
片山博文MZってコジキなのか？
626:デフォルトの名無しさん
17/11/13 00:48:07.30 PHmyYrtX.net
コジキっていうか、頭の弱い子
627:デフォルトの名無しさん
17/11/14 21:49:31.73 yEmE0LhS.net
コード中でa-zA-Z0-9の文字を一切使わずに
Hello World!!
と出力せよ。
"!"の後ろの改行の有無は問わない。
628:デフォルトの名無しさん
17/11/14 22:13:39.71 1d5ZohBo.net
>>606 whitespace
629:デフォルトの名無しさん
17/11/15 00:12:32.03 ckRbh5hb.net
前にも見たなぁ。
630:デフォルトの名無しさん
17/11/15 00:21:09.60 edbITJRa.net
>>606
それじゃプログラム組めないと思うんだが、記号だけの言語みたいなの使えってこと？
631:デフォルトの名無しさん
17/11/15 00:30:14.08 au/IFdC5.net
>>606 bhnjdsbkjdsb
_
632:デフォルトの名無しさん
17/11/15 00:31:44.60 ckRbh5hb.net
iostreamがすでにアウト。
633:デフォルトの名無しさん
17/11/15 01:21:11.75 f03ykBDy.net
>>606
634:デフォルトの名無しさん
17/11/15 01:21:50.26 f03ykBDy.net
>>606 Ruby
URLﾘﾝｸ(ideone.com)
perlとjavascriptでも殆ど同じことができる
635:デフォルトの名無しさん
17/11/15 01:23:33.97 0AqsUHvD.net
今日は七五三ということで
7,5,3,+,-,×,÷,(),^2を使った式（ただし7,5,3は一個しか使えない）で1から連続でいくつまで数を作れるか
1=3+5-7
2=5-3
3=3
4=(5-3)^2
5=5
6=(7-5)×3
…
636:デフォルトの名無しさん
17/11/15 06:25:11.32 21MTGrxx.net
^2 もありですか
637:デフォルトの名無しさん
17/11/15 11:19:06.80 +wQkBp8E.net
>>613
回答見てもわからない
どういうこと?
638:デフォルトの名無しさん
17/11/15 11:36:08.43 cnBo
639:JhFE.net
640:デフォルトの名無しさん
17/11/15 11:46:46.76 f03ykBDy.net
>>616
特殊変数$$から1を作ってそれをもとに2, 4, 8, 16などを作る
"%c"を繰り返したものをあらかじめ作っておき
そこに上記の数字で作った"Hello World!!"の文字コードをsprintフォーマットする
標準出力を表す特殊変数$>に<<メソッドでできた文字列を出力する
あとは 「"" << 文字コード」で「文字コード.chr」と同様の結果が得られるので適宜利用すると便利
641:デフォルトの名無しさん
17/11/15 12:14:35.50 GYwcr8MQ.net
>>617の間抜けさ加減に草
642:デフォルトの名無しさん
17/11/15 13:25:57.72 YypYHZ3m.net
>>614
^2 は
int sqr(int n){return n*n;}
みたいな関数が使えるって意味だよね
つまり、
x^2^2 とかは (x^2)^2 の意味で使うなら可能ってことだよね
643:デフォルトの名無しさん
17/11/15 13:32:50.33 +wQkBp8E.net
>>618
記号で1を作って、数値、文字コード、文字列としてくのか
いろんな省略記法も知らないとできないな
解説ありがとう
644:デフォルトの名無しさん
17/11/15 19:03:12.96 vzgZy9E8.net
>>614
5と3を繋げて53にするようなこともしていいの？
645:デフォルトの名無しさん
17/11/16 00:18:43.09 /xRbPsNU.net
計算部は書いたけど、元の表記で何算してるか表記するのが面倒だ。
あと、遅い・・・。
646:デフォルトの名無しさん
17/11/16 00:24:47.24 IIofg8Am.net
73/5=14とかは駄目だよね？
647:デフォルトの名無しさん
17/11/16 01:59:04.45 /xRbPsNU.net
>>614
URLﾘﾝｸ(ideone.com)
C++。
それとなく書いてみたけど、誤差でまくり。割り算鬼門すぎる。
多分バグってる。あと、題意理解してない可能性が微レ存。
648:デフォルトの名無しさん
17/11/16 02:00:39.12 /xRbPsNU.net
あ、そうだ。
カッコの処理がバグバグだったからカッコ使わなかった。
649:デフォルトの名無しさん
17/11/16 02:11:42.94 /xRbPsNU.net
うーむ・・・。なんていうか。。。
ギブアップだ。Orz
650:デフォルトの名無しさん
17/11/16 11:38:12.54 clS3oGAP.net
>>625
「題意理解してない可能性が微レ存」どころじゃねえだろこれｗｗ
651:デフォルトの名無しさん
17/11/16 14:11:34.74 9+S8V57k.net
整数の範囲でも有理数の範囲でも答えが変わらないからつまらん
一旦非整数を経由しないと作れないのがないとやっぱり...
652:デフォルトの名無しさん
17/11/16 15:03:27.99 /xRbPsNU.net
>>628
可笑しいところ教えて！
653:デフォルトの名無しさん
17/11/16 15:46:11.61 9+S8V57k.net
(3^2)^2 = 3^4
((3^2)^2)^2 = 3^8
だから、3^(2*3) とかやっちゃダメだろ
あと、
3×5÷7 = 15÷7 ≠ 2
654:デフォルトの名無しさん
17/11/16 15:59:11.96 /xRbPsNU.net
>>631
あー、俺がタコでした。
まぁ、前段は表示系の問題だと思うお。
後者は割り算が全部悪い。
浮動小数で比較したくないんだよなぁ。悩ましい。
655:デフォルトの名無しさん
17/11/16 16:39:35.92 9+S8V57k.net
有理数クラスを作るのだ
656:デフォルトの名無しさん
17/11/16 17:43:36.30 /xRbPsNU.net
有理数の法則がよくわかってないし、デカイ。
ままならんなー。
657:デフォルトの名無しさん
17/11/16 18:03:35.37 9+S8V57k.net
(a/b) + (c/d) = (ad + bc) / bd
(a/b) - (c/d) = (ad - bc) / bd
(a/b) * (c/d) = ac / bd
(a/b) / (c/d) = ad / bc
(a/b) = (c/d) <===> ad = bc
分子 : 整数
分母 : 0以外の整数
658:デフォルトの名無しさん
17/11/16 21:25:39.77 /xRbPsNU.net
数学ムズイ。。。
PGも算数で解いてるからな。
659:デフォルトの名無しさん
17/11/17 00:16:40.63 5DUWZGJy.net
紙とペ
660:ンで考えてみたところ 0以外の任意の整数なら3,5,7で表わせるから問題として不適なのでは？
661:デフォルトの名無しさん
17/11/17 00:20:03.76 M2EFWWXH.net
17
662:デフォルトの名無しさん
17/11/17 10:03:52.61 oe8UBfUe.net
>>637
3,5,7は１回までって回数制限があるから
表せる数は限られるよ。
663:デフォルトの名無しさん
17/11/17 10:44:12.02 a6b9gyRQ.net
17が出来ない
664:デフォルトの名無しさん
17/11/17 19:35:00.15 5DUWZGJy.net
ああ、本当だ。17はどうやっても作れないね
しかしこれをどうやってコードで計算すんだろう
^2があるから全探査はできないし
自分は「+または-」をいくつ使うかで場合分けして一個一個可能性を消していったんだけれども
665:デフォルトの名無しさん
17/11/17 20:04:40.56 M2EFWWXH.net
コードはアップしないけど出来たよ
666:デフォルトの名無しさん
17/11/17 20:07:16.14 M2EFWWXH.net
独自有理数クラス
演算回数を1回ずつ増やしていって、
出来た値に対応するフラグをセット
667:デフォルトの名無しさん
17/11/17 20:09:06.68 M2EFWWXH.net
数値をstd::multisetで保持
演算n回目のmultisetをstd::setで保持
668:デフォルトの名無しさん
17/11/18 17:51:34.79 6foiYhRZ.net
ABC4D
-E3FG
-----
77777
A～G は、1～9 の異なる数字。
ただし、3, 4 ではない
669:デフォルトの名無しさん
17/11/18 17:56:36.72 R4dFDjUs.net
はい、そうですか。
670:デフォルトの名無しさん
17/11/18 19:08:28.21 8fhXEikQ.net
>>645 Java
2年前の問題と俺の回答
ｽﾚﾘﾝｸ(tech板:451番)
を改造したもの (50-54行目と標準入力)
URLﾘﾝｸ(ideone.com)
671:デフォルトの名無しさん
17/11/18 19:44:36.57 oFg54zrO.net
>>645 Ruby
f = ->a, b, c, d, e, f, g{10000*a + 1000*b + 100*c + d - (1000*e + 10*f + g) == 78037}
[1, 2, 5, 6, 7, 8, 9].permutation{|a| puts "%d%d%d4%d - %d3%d%d == 77777" % a if f[*a]}
#=>87142 - 9365 == 77777
672:デフォルトの名無しさん
17/11/18 20:40:01.77 6foiYhRZ.net
>>647
何も、そこまで作り込まなくても良いだろw
色々な覆面算に対応するため、汎用的に書いたのか
673:デフォルトの名無しさん
17/11/19 22:39:02.74 oda4btU4.net
500, 100, 50, 10, 5, 1円のすべての種類の硬貨を、1枚以上使って、
合計15枚で750円にする時、10円硬貨は何枚になるか？
A～E の5人のランナーが走った結果、
完走したのは、1着とべべの2人で、残りの3人は、途中で棄権した
ここで、完走した2人は、必ず真実を言い、
棄権した3人は、必ず嘘をつくものとする
(つまり、事実に対して、真偽値を取る)
A: D は棄権した
B: A は、べべだった
C: E は棄権した
D: C は、べべだった
E: B は完走した
A～Eがこのように答えた時、1着は誰か？
674:デフォルトの名無しさん
17/11/20 01:25:03.39 Z32/GYkn.net
先に答えやそれに至る式がわかっててコードに書き直すだけになっちゃうから
数学的に道筋立てて答えが出せるものはあんまりおもしろくないんだよな
675:デフォルトの名無しさん
17/11/20 03:34:46.27 GkhyFhEh.net
アルゴリズムとは、数式の完全コピー
最初に、数式を考えて、その数式が間違っていれば、
撃墜モードでは、そこを突かれて撃墜される
結局、数式の証明が大事。
証明に、勘違いが無いかどうか
676:デフォルトの名無しさん
17/11/20 11:24:27.08 7i/OQPcC.net
べべってなんぞ？
677:デフォルトの名無しさん
17/11/20 11:38:36.82 OJcNabXy.net
>>653
たぶんこの場合は大阪の方言
678:デフォルトの名無しさん
17/11/20 11:45:30.45 7i/OQPcC.net
俺地方の人間だからわかんない。
679:デフォルトの名無しさん
17/11/20 18:24:16.80 Slkhafwt.net
べべって最下位のことじゃないか
どべ
680:デフォルトの名無しさん
17/11/21 23:50:05.58 zUV8sDjk.net
>>645
こんなのどうかな。Kotlin で作った。
URLﾘﾝｸ(paiza.io)
681:デフォルトの名無しさん
17/11/23 10:05:44.85 zWeuVerg.net
お題
1から99を表示する
お題：1から999を出力する
ただし0を含む数は除く
682:デフォルトの名無しさん
17/11/23 10:11:40.40 TrZHjzbP.net
>>658
1000.times{|i|p i unless i.to_s[?0]}
683:デフォルトの名無しさん
17/11/23 12:15:31.91 6AL/1aep.net
>>658 GNU Smalltalk
1 to: 999 do: [:n | (n asString includes: $0) ifFalse: [n displayNl]]
684:デフォルトの名無しさん
17/11/23 12:38:42.26 KUvGqrz8.net
>>658 F#
let () = seq { 1..999 } |> Seq.iter (printfn "%d")
685:デフォルトの名無しさん
17/11/23 12:40:24.86 KUvGqrz8.net
>>661
すまん、問題よく読んでなかった･･･
686:デフォルトの名無しさん
17/11/23 13:30:23.43 jBvfUrCY.net
>>658
URLﾘﾝｸ(ideone.com)
C++。ほかの言語だと一行で書けるんだけどなぁ。
まぁ過去に比べれば大分短くなったけど。
687:デフォルトの名無しさん
17/11/23 15:45:02.09 ys+VuKpG.net
>>658
文字も数もその場に合わせて適当に解釈してくれる言語だと楽だね。
perl だとこれでできる。
for(1..999){print"$_\n"unless(/0/)}
688:デフォルトの名無しさん
17/11/23 16:16:10.88 JcpJJmmU.net
>>658
@Mathematica
nListWithoutZero[n_]:=n//
Range[1,#]&//
Map[ToString,#]&//
StringCases[#,RegularExpression["^(?!.*0).*$"]]&//
Flatten;
In[1] := nListWithoutZero[999]
Out[1] = (略)
689:デフォルトの名無しさん
17/11/23 16:34:54.15 2sNCCDGP.net
>>658
ダメだお題の意味がわからん
降参
690:デフォルトの名無しさん
17/11/23 16:42:00.54 QTAUjuBR.net
>>658 rust
URLﾘﾝｸ(ideone.com)
fn main() {
println!("{:?}", (1..1000).filter(|i| !i.to_string().contains("0")).collect::<Vec<_>>())
}
691:デフォルトの名無しさん
17/11/23 16:46:25.38 ys+VuKpG.net
>>658
Kotlin で文字列変換してやる場合
fun main(args: Array<String>) {
for (i in 1..999)
if (! i.toString().contains('0', false))
println(i)
}
数値のままやる場合
fun main(args: Array<String>) {
for (i in 1..999)
if (i % 10 != 0
&& (i < 10 || i / 10 % 10 != 0)
&& (i < 100 || i / 100 % 10 != 0))
println(i)
}
692:デフォルトの名無しさん
17/11/23 17:05:13.53 fGVRHt7J.net
>>658
>>668 同じく数値のままやる場合
URLﾘﾝｸ(ideone.com)
693:デフォルトの名無しさん
17/11/23 17:08:37.18 fGVRHt7J.net
ｽﾚﾘﾝｸ(math板:722番)
お題：
n^2-1 = m^5
を満たす自然数 n, m は存在するか？
存在するという人と存在しないという人の両方が存在します
694:デフォルトの名無しさん
17/11/23 17:18:38.32 TrZHjzbP.net
>>670
(n, m) = (1, 0)
揚げ足取りはおいておいて、プログラミングで説く問題じゃないよね
695:デフォルトの名無しさん
17/11/23 18:35:09.23 zveldNvP.net
>>658
python
今回は必要ないかもだけど桁数増えた場合を考え再帰で
URLﾘﾝｸ(ideone.com)
696:デフォルトの名無しさん
17/11/23 19:09:48.15 fGVRHt7J.net
>>671
まあ自明な解はさておき、その他は見つからないのが不思議です
697:
698:デフォルトの名無しさん
17/11/23 20:21:54.46 /mQ4CZGQ.net
>>673
カタラン予想ですでに存在しないことが証明されているのに何が不思議なのかね
699:デフォルトの名無しさん
17/11/23 20:24:10.50 hjkeK8jf.net
>>673
その問題は数学的に解くものではないかな?
まあ、コンピュータなら力業でかなりの値を n, m に入れて計算して確認できるけどさ。
700:デフォルトの名無しさん
17/11/23 20:56:22.87 fGVRHt7J.net
>>674
カタラン予想というのがあるんですね、ありがとうございます！
URLﾘﾝｸ(en.wikipedia.org)
701:デフォルトの名無しさん
17/11/23 21:05:28.66 uF7hi9HH.net
>>658
#!/bin/sh
seq 999|grep -v 0
702:668
17/11/24 06:21:36.98 8wyGH9pr.net
>>658
Kotlin数値判定版。こんな風にも書けるなと後で気づいた。
fun f(n: Int): Boolean {
var m = n;
while (m != 0) {
if (m % 10 == 0)
return false
m = m / 10
}
return true
}
fun main(args: Array<String>) {
(1..999).filter(::f).forEach(::println)
}
703:デフォルトの名無しさん
17/11/24 07:42:25.55 MEHEP0+e.net
存在するしないをプログラミングで証明するのはお題として良くない
704:デフォルトの名無しさん
17/11/24 20:42:02.54 G34PGfZh.net
log 2 を2進数表記した時の小数点第 n 位から n + 9 位までを求めよ． (1 ≦ n ≦ 10^10)
cf. log 2 = 0.10110001...
*Sample input*
1
11
10000
31415926
314159265
*Sample output*
1011000101
1100100001
0010110110
1001010110
0111101001
705:デフォルトの名無しさん
17/11/24 23:31:00.22 r53+zpq0.net
>>680
c++で書いたけど小数第100億位を計算するのに5時間くらいかかりそうorz
706:
17/11/25 00:04:03.20 ROI3Hzdd.net
>>681
もう初手に届くとは劇速ですね
707:デフォルトの名無しさん
17/11/25 06:53:37.62 Uo3oYb2P.net
無条件でlogって書いたら普通自然対数だろ
708:デフォルトの名無しさん
17/11/25 07:01:13.88 Uo3oYb2P.net
ライブラリを使えばほとんど何も書かなくて良いけど
どこから書くことを求められてるの？
709:デフォルトの名無しさん
17/11/25 07:03:54.53 Uo3oYb2P.net
>>679
「良くない」じゃなくて「出来ない」でしょ
710:デフォルトの名無しさん
17/11/25 07:16:55.64 Uo3oYb2P.net
>>684
と思ったけど、普通に全桁計算したら終わらないな
711:デフォルトの名無しさん
17/11/25 07:34:12.57 Uo3oYb2P.net
Σ { 1 / (2^i × i) }
を使って10^10項位までを42bitくらいだけ計算すれば出来るかな？
1/nの周期性を考えないと計算量的に無理？
10^10が微妙に32bitを越えてるのがイヤだねえ
712:デフォルトの名無しさん
17/11/25 08:21:38.07 Uo3oYb2P.net
>>687
ダメだ
ざっと計算量を見積もったらとても5時間じゃ終わらない
713:デフォルトの名無しさん
17/11/25 13:10:34.24 l6j6CjYT.net
>>375
xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl fact.casl
1
1
2
6
24
120
720
5040
40320
362880
途 中 省 略
1405006117752879898543142606244511569936384000000000
60415263063373835637355132068513997507264512000000000
2658271574788448768043625811014615890319638528000000000
119622220865480194561963161495657715064383733760000000000
5502622159812088949850305428800254892961651752960000000000
714:258623241511168180642964355153611979969197632389120000000000 12413915592536072670862289047373375038521486354677760000000000 608281864034267560872252163321295376887552831379210240000000000 30414093201713378043612608166064768844377641568960512000000000000 暇つぶしに書いてみたけど足算掛算割算しかできない 引算は難しすぎるんで諦めた
715:デフォルトの名無しさん
17/11/25 16:35:37.76 J1zvm3XW.net
バイナリ法で最適化した結果なんとか1時間あれば10^10位は計算できるようになったがまだ縮められるかな
716:
17/11/25 16:41:37.19 ROI3Hzdd.net
備忘メモ
ｽﾚﾘﾝｸ(math板:890番)
ちゃんとお題にして出題しなおします
717:
17/11/25 21:49:51.82 ROI3Hzdd.net
>>680
指数関数のマクローリン展開で試してみたのですが、これは収束が遅すぎますね、それに収束半径を超えてるし…
なにか収束の早いよい方法はないものか…
718:
17/11/25 21:54:37.24 ROI3Hzdd.net
>>692
×指数関数
○対数関数
719:デフォルトの名無しさん
17/11/25 22:58:19.91 yyAYDlfh.net
対数関数のマクローリン展開？
そりゃ無理だ
log 0 が定義されてない
720:デフォルトの名無しさん
17/11/25 23:12:41.85 FRsJtlII.net
>>689
CASLで書いたの?
ソースコードは?
721:デフォルトの名無しさん
17/11/25 23:38:41.06 yyAYDlfh.net
>>680
log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) }
冪剰余
でいける気がしてきた
しばらく暇がない
時間が空いたら
アセンブラ & C++ & OpenMP
でやってみる
722:デフォルトの名無しさん
17/11/26 02:33:02.82 T275kIwU.net
>>650
(setq aaa '(1 5 10 50 100 500))
(setq ddd 750)
(setq jjj 15)
(defun bbb (ccc iii)
(if (= iii 0)
ccc
(let (eee)
(dolist (fff ccc)
(dolist (ggg aaa)
(when (<= (+ (apply #'+ fff) ggg) ddd)
(push (cons ggg fff) eee))))
(bbb (remove-duplicates (mapcar (lambda (x) (sort (copy-seq x) #'<)) eee) :test 'equal) (1- iii)))))
(let* ((kkk (bbb '((0)) jjj))
(lll (mapcar (lambda (x) (remove 0 x)) kkk)))
(remove-if-not (lambda (x) (and
(= (apply #'+ x) ddd)
(= (length x) jjj)
(= (length (remove-duplicates x)) (length aaa))
)) lll))
((1 1 1 1 1 5 5 5 10 10 10 50 50 100 500))
723:デフォルトの名無しさん
17/11/26 02:34:12.86 T275kIwU.net
>>650
(setq aaa '(A B C D E))
(defun fff (ddd)
(if (null (cdar ddd))
ddd
(let (eee)
(dolist (jjj ddd)
(let ((bbb (car jjj))
(ccc (cdr jjj)))
(setq eee (append (mapcar (lambda (x) (cons (cons x bbb) (remove x ccc))) ccc) eee))))
(fff eee))))
(defun iii (kkk)
(if (< kkk 2) #'identity #'not))
(let* ((ggg (fff (list (cons nil aaa))))
(hhh (mapcar (lambda (x) (car x)) ggg)))
(remove-if-not (lambda (x) (and (funcall (iii (position 'A x)) (> (position 'D x) 1))
(funcall (iii (position 'B x)) (= (position 'A x) 1))
(funcall (iii (position 'C x)) (> (position 'E x) 1))
(funcall (iii (position 'D x)) (= (position 'C x) 1))
(funcall (iii (position 'E x)) (< (position 'B x) 2)))) hhh))
((D C B E A) (D C E B A) (D C A E B) (D C E A B) (D C A B E) (D C B A E))
724:
17/11/26 11:18:11.00 rNgJnhxq.net
>>694
いやいや
URLﾘﾝｸ(ja.wikipedia.org)
log(1-x) = - Σ((1/n)x^n) に x = -1 を機械的に代入しました、収束半径外ですが、この値は正しいらしい。
725:デフォルトの名無しさん
17/11/26 12:12:20.72 ffy1o2uq.net
お題
ASCIIコード表が載っている�
726:{をあげよ
727:デフォルトの名無しさん
17/11/26 12:35:31.87 tJzac9f2.net
>>695
うんCASL
全部で1200行かあ
ｘｘｘ@ｘｘｘ-VirtualBox:~/casl$ wc -l stdlib.casl bigint.casl fact.casl
274 stdlib.casl
851 bigint.casl
76 fact.casl
1201 合計
ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして
何が何だか分からなくなるよ
ld gr5,0,gr1
ld gr6,1,gr1
lad gr4,4,gr1
addl gr4,gr0
st gr4,0,gr1
st gr6,1,gr1
ld gr4,=1
st gr4,2,gr1
st gr0,3,gr1
ld gr6,gr1
ld gr1,0,gr1
st gr5,0,gr1
st gr6,1,gr1
xor gr4,gr4
st gr4,2,gr1
lad gr2,-4,gr2
subl gr2,gr0
st gr2,3,gr1
ld gr0,gr3
728:デフォルトの名無しさん
17/11/26 12:35:43.37 WgExDItE.net
>>699
他だ単に対数って言えば
log x のこと
これをマクローリン展開は無理
log (1-x) のマクローリン展開ならそう書かないと通じない
収束半径の外じゃなくて、収束半径丁度でしょ
729:デフォルトの名無しさん
17/11/26 12:49:31.90 WgExDItE.net
-log (1-x) のマクローリン展開に、
x = 1/2 を入れると
>>696 になる
730:デフォルトの名無しさん
17/11/26 13:21:30.43 jiBTwXK4.net
理解はしてないが、出てきたので貼っとく。
指数対数関数等の超越関数の多倍精度計算
本論文では、 指数対数関数の高精度計算として Taylor 展開に BSA 法を使って高速化する方法提案する。
約 1000 桁以下の精度の計算では、 Taylor 展開を使った計算が Sasaki and Kanada[5] によって、様々な計算
法を比較して最も高速であることが示されているので、 計算時間が問題となるのは、 1000 桁以上の精度の
計算である。 ここで提案した Taylor 展開に BSA 法を適用して高速化した方法と Sasaki and Kanda によっ
て提案された方法を 1000 桁を超えた精度で比較し、 その高速性を示した。
211 階乗計算例
10000! の計算を行う。 この計算では、 BSA 法を使うだけでなく、 1600 桁以上の数値に対しては FFT を利用して乗算を行っている。
計算方法 計算時間(msec)
BSA 47
従来の方法 3578
このほか、 三角関数、逆三角関数、双曲線関数など簡単な規則で各項の係数が表現でき、 多くの関数がこの
行列の乗算形式に変形できます。Taylor 展開の係数が簡単な規則で表現できない $\tan x$ が例外的に表現できないだけである。
3 まとめ
指数関数や対数関数の Taylor 展開に BSA 法を適用することによって、 BSA を使わない従来の方法に比べ40 %程度の高速化ができた。
対数関数に対しては、 5000 桁程度の精度で最も高速な計算方法として知られた Sasaki and Kanada の方法を超えることを示した。
URLﾘﾝｸ(www.kurims.kyoto-u.ac.jp)
731:
17/11/26 13:37:36.96 rNgJnhxq.net
>>702
たしかに
収束半径は |x < 1| なのでは？
732:デフォルトの名無しさん
17/11/26 13:44:48.59 jiBTwXK4.net
とりあえず理解はできた計算方法として、logxの近似値などをaとおいたとき、
logx = a + log(x/e^a)という変形を用いる方法だ。
aが近似値だと、x≒e^aなので良いらしい。
733:デフォルトの名無しさん
17/11/26 13:58:53.69 WgExDItE.net
>>705
収束半径は1
収束半径は、収束するエリアと収束しないエリアの境目となる円の半径
収束半径丁度の時は収束する場合もあるししない場合もある
734:デフォルトの名無しさん
17/11/26 14:20:52.91 WgExDItE.net
>>706
計算する項が少なければ良いわけではなく、
各項の計算時間も重要
735:デフォルトの名無しさん
17/11/26 15:04:05.33 jiBTwXK4.net
exp(x)は、(exp(x/k))^k (kは2ベキ)、とするといいらしい。
k=2なら、括弧内を計算したやつ同士
736:の掛け算。
737:695
17/11/26 18:33:11.28 XHzckn9a.net
>>701
なるほどありがとう
怖いもの見たさがあった
738:
17/11/26 20:54:13.61 rNgJnhxq.net
>>689
えへへ、調べさせてもらったよｗ
後半は 42! から 50! までの値だね
この範囲なら、多数桁×ワンレジスタの計算で済みますね
多数桁×多数桁を実装すれば思いっきり褒めてあげるよ、えへへ：－）
739:デフォルトの名無しさん
17/11/26 21:11:54.45 tJzac9f2.net
>>711
ほい
xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl bimul.casl
350306543997676425792
153864088327713953064
53899597027434699691252340823058767026688
740:
17/11/26 21:47:36.23 rNgJnhxq.net
>>712
おお、すごい、gmp で確認したがあってるぞ
私はまだ 10進文字列から多数桁型への変換は実装できていない、また仕事ができてしまったなあ
741:デフォルトの名無しさん
17/11/26 23:01:31.48 tJzac9f2.net
>>713
gmpで確かめてるのかあ
俺は確認はclispかrubyでやってるよ
10進文字列からの変換は10倍しながら足しこんでいくだけだから
そんなに難しくないでしょ
掛算なしでも(n<<3)+(n<<1)でできるし
逆の10進文字列への変換は割算が必要だから実装するの大変だったなあ
これができあがるまではメモリを16進ダンプして計算が合ってるか確かめてた
742:デフォルトの名無しさん
17/11/27 06:49:43.60 qqP20rnw.net
>>696がよさげだな
こういうことだろ?
Σ(1/n) >> n
小数にもシフトを適用するとして。
和の誤差がかわかれば、どこまで計算したらいいかわかるがどうやるんだ?
743:デフォルトの名無しさん
17/11/27 07:17:24.36 qqP20rnw.net
誤差しらべたら、テイラー展開は平均値の定理一般化だったか
数値計算とテイラー展開
ある区間において,関数 f(x)がn 回微分可能であるとし,定数aはこの区間に含まれるものとする.x もこの区間内に含まれるとき,
URLﾘﾝｸ(math-lab.main.jp)
をみたすa とx の間の実数c (a <c <x または x <c <a)が存在する
URLﾘﾝｸ(math-lab.main.jp)
744:デフォルトの名無しさん
17/11/27 07:40:30.25 qqP20rnw.net
log(1+x)の誤差項、剰余項は、(-1)^(n-1)/n * (x/(1+c))^n らしいので、
-log(1-x)では、1/n * (x/(1+c))^n か。
x=1/2で考えると、この項をなるべく大きくするならc=0で、誤差は(1/n) >> n以下か。ふたたびシフト使用。
745:デフォルトの名無しさん
17/11/27 07:44:14.48 qqP20rnw.net
まとめると、
log2 - (Σ(1/k) >> k) < (1/n) >> n (級数はn-1までの和)
746:デフォルトの名無しさん
17/11/27 08:54:49.81 qqP20rnw.net
どこか間違えてる 次数か?
747:デフォルトの名無しさん
17/11/27 08:59:59.63 qqP20rnw.net
いやあってるか。
A(k) = (1/k)>>kと置くと、
log2 - ΣA(k) < A(n) (級数はn-1までの和) で
ΣA(k) (n+1以上の和) < A(n) が成立するのか。
748:デフォルトの名無しさん
17/11/27 10:11:23.24 qqP20rnw.net
やはり、どこか間違ってるな。
上のとおりだと、log2 - ΣA(k) (級数はn-1までの和)は、
A(n) を含むので、A(n)より小さいはずがない。
749:
17/11/27 23:07:50.22 b0u4s5jJ.net
>>701
＞ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ
対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、
必要に応じてまた脳みそに搭載できるようにならないものか…
そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね
750:デフォルトの名無しさん
17/11/27 23:36:53.65 bwTh4Bk9.net
>>680
>>696の方法で作ってみました
n=10^10の時に48.3秒くらいです
751:デフォルトの名無しさん
17/11/28 13:09:45.40 IU/PYwM1.net
>>723 はHaswell (4770) 3.4GHz固定での結果で
Skylake (6700K) 定格だと38.4秒でした
ちゃんとCPUも進化してるんですね
752:デフォルトの名無しさん
17/11/28 13:17:18.48 IU/PYwM1.net
>>681
>>690
C++だとどうやって計算してるかが非常に気になります
32bitを越える値同士の乗算(結果が64bitを越える)部分
アセンブラだと
64bit x 64bit ===> 128bit
128bit / 64bit ===> 64bit
等があるのでそれを使っちゃってますが
753:デフォルトの名無しさん
17/11/28 13:20:30.03 IU/PYwM1.net
冪剰余を求めるのに
(a * b) % c
みたいなのがたくさん出てきませんか？
aもbもcも32bitの範囲を微妙に越えてて
754:デフォルトの名無しさん
17/11/28 14:44:32.26 jzUFRHpN.net
誤差部分の間違いが判った。これでよさげだ。
ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。
誤差項ありのマクローリン展開は、0<=c<=xが存在して
f(x) = Σ x^k * f(k)(0)/k! (kは0からn-1まで) + x^n * f(n)(c)/n!
f(x) = -log(1-x)のn次導関数は、(n-1)!/(1-x)^n。
このときマクローリン展開は誤差項は x^n / (n*(1-c)^n)
x=1/2ならば、c=1/2のとき最大で、1/n
755:デフォルトの名無しさん
17/11/28 19:45:30.22 jzUFRHpN.net
これが収束速いようだ。
log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)
log((x+1)/(x-1))
= log((1+1/x)/(1-1/x))
= 2 Σ 1/((2n+1)*x^(2n+1))
756:デフォルトの名無しさん
17/11/28 22:18:22.38 7WoPw74F.net
>>728
1/log(2) ≒ 3.32
1/2log(161)+1/2log(49)+1/2log(31) ≒ 0.85
なので、計算に必要な項数は1/4程度
でも、1つの項の計算には時間がかかる
log(1-x)のマクローリン展開に0.5を入れた物は
分母が i * 2^i だから速く計算できるのだ
757:デフォルトの名無しさん
17/11/28 22:20:46.48 7WoPw74F.net
>>727
残りの項を等比数列と見なせば
簡単に誤差の上限が出ます
758:デフォルトの名無しさん
17/11/28 22:47:09.33 7WoPw74F.net
>>724
Haswellで33.96秒に縮まりました
シングルスレッドだと182.54秒で5.3倍
HTTが効くということは、
まだ多少改善の余地がありそう
一番内側のループは
vmulpd
vmulpd
vroundpd
vfmsub213pd
vfmsub132pd
vsubpd
なんと浮動小数点で計算してます
759:デフォルトの名無しさん
17/11/28 22:53:54.93 7WoPw74F.net
n=10000000000の時は
0000010101 でした
出題者さま、合ってます？
また、たまたまですが
n=10000000004では
0101010101
n=10000000005では
1010101010
になります
760:デフォルトの名無しさん
17/11/28 23:30:15.70 9HoDrqB3.net
一番内側のループのコード
URLﾘﾝｸ(fast-uploader.com)
PORT5がガラ空きで、処理のほとんどがPORT0,PORT1
こんなんでもHTTが効く
やっぱり浮動小数点はレイテンシがデカい
AVX512になれば
レジスタの数が倍になるので
8パラにしてレイテンシを隠蔽出来るんだけど
もちろんレジスタ長が倍になる方が大きい
761:デフォルトの名無しさん
17/11/29 13:17:33.09 mHyZby47.net
>>728は後半部分が間違ってるか。log((x+1)/x) = log(1+1/x) の展開を用いるのが正解で。
log(・)の中身を1に近づけた方が収束が早くなるが、
こういった分解 log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)はどうみつけるのか。
これは数値が(x+1)/x の形だけど、(x+1)/(x-1)の分解もあるのか。こっちだと計算するベキ項が一つ飛ばしにできる。>>728のように。
762:デフォルトの名無しさん
17/11/29 13:34:57.75 8/kTvoZy.net
2 = (81/80)^3 * (25/24)^5 * (16/15)^7
3 と 5 の指数の合計が0になる組み合わせを検索すれば良い
763:デフォルトの名無しさん
17/11/29 13:37:30.83 8/kTvoZy.net
log(81/80) = log(162/160) = log((161+1)/(161-1))
わかってて書いてるんだと思ったが
>>729のlogの中身はこの値
764:デフォルトの名無しさん
17/11/29 13:42:05.17 mHyZby47.net
>>728はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。
765:デフォルトの名無しさん
17/11/29 13:45:31.51 mHyZby47.net
指数も固定でなくていいはずで、
16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。
766:デフォルトの名無しさん
17/11/29 14:44:26.09 8/kTvoZy.net
分母分子の素因数の数と同じ項数が必要
例えば素因数が 2, 3, 5, 7 の4種類の場合、
1個差もしくは2個差のペアを4個探す
例えば
126/125
225/224
2401/2400
4375/4374
これらを適当に掛け算して2^nになるようにすると
項が4個の式がみつかる
767:デフォルトの名無しさん
17/11/30 00:31:43.08 H4qIjcIH.net
分母、分子とも 2, 3, 5, 7, 11, 13, 17 のみしか素因数を持たない形の場合、
以下が一番計算する項の数が少ないようです
log(2) = 72*log(126/125)+27*log(225/224)-19*log(2401/2400)+31*log(4375/4374)
768:デフォルトの名無しさん
17/11/30 05:07:54.11 fMs2N0Mh.net
>>740
その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。
A.D. Fokker: Unison Vectors and Periodicity Blocks
URLﾘﾝｸ(www.huygens-fokker.org)
List of 7-prime limit accidentals - The?Sagittal?forum
URLﾘﾝｸ(forum.sagittal.org)
769:デフォルトの名無しさん
17/11/30 05:28:17.43 fMs2N0Mh.net
log(2)とは無関係で、単に一個差のやつで適当な素因数分解できるやつに名前がついてるだけ?
An Investigation into the Extraction of Melodic and Harmonic Features from Digital Audio
unit interval name
4375/4374 Ragisma
2401/2400 Breedsma
225/224 Septimal Kleisma
145/144 Difference between 29:16 and 9:5
126/125 Small Septimal Semicomma
121/120 Undecimal Seconds Comma
81/80 Syntonic Comma
URLﾘﾝｸ(scholar.sun.ac.za)
770:デフォルトの名無しさん
17/11/30 11:02:35.16 fMs2N0Mh.net
log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、
音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。
log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。
771:片山博文MZ
17/11/30 12:12:48.85 NsMGt5if.net
お題。横x[cm]、縦y[cm]の長方形のステンレスの１枚の板がある。この板からm枚の複数の長方形の部材を切り出す。
部材のサイズは配列で与えられる。
部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。
ただし、部材の縦または横が変わるとそれぞれ一点減点となる。
すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。
772:片山博文MZ
17/11/30 12:19:33.84 NsMGt5if.net
テストデータ。
x=10, y=10,
{
{5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5}
}
x=5, y=12
{
{2, 5}, {3, 3}, {2,9}, {3, 2}, {4,3}
}
773:片山博文MZ
17/11/30 12:28:07.36 NsMGt5if.net
部材の縦と横は入れ替わってもよい。
可能ならば、切り出し方法をSVG形式で出力せよ。
774:片山博文MZ
17/11/30 12:51:59.04 NsMGt5if.net
切り出し方法は、
切り出す部材のx座標、y座標、幅、高さ
のリストとして出力せよ。
775:片山博文MZ
17/11/30 12:56:57.25 NsMGt5if.net
切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。
776:デフォルトの名無しさん
17/11/30 13:08:21.37 tkxPMdZc.net
斜めもOK？
777:デフォルトの名無しさん
17/11/30 13:08:55.87 tkxPMdZc.net
人間用のパズルで、斜めにしないと解けないのとかありそう
778:デフォルトの名無しさん
17/11/30 14:23:24.17 SHLZLl2M.net
問題文の条件が“だいたい”“なるべく”なんて
あいまい表現だらけ
これでプログラミングの問題かよ
779:片山博文MZ
17/11/30 16:18:01.24 NsMGt5if.net
斜めは考えなくてもよい。
訂正。
すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。
780:680
17/11/30 17:10:37.24 8ZVWPbH7.net
>>732
そこにある3つとも正解です
当初は L = Σ1/(k*2^k) として
2^n * L の小数部分を愚直に求める方法を想定していました
781:デフォルトの名無しさん
17/11/30 17:26:52.63 r8WkgLop.net
普通に多倍長で計算したら計算量的に終わらないですよね？
n=314159265を求めるのに
冪剰余は使ってますよね？
おそらく私も同じような方法と思います
FMA3命令とOpenMPで高速化してるだけで
782:デフォルトの名無しさん
17/11/30 22:49:50.18 TklDiPhy.net
愚直という言い方は良く割りませんでしたね
仰る通り冪剰余は用います
783:片山博文MZ
17/12/01 14:26:32.50 fw1UFg83.net
再出題。横cx[cm]、縦cy[cm]の長方形または正方形のステンレスの１枚の板がある。この板からm枚の複数の長方形または正方形の部材を切り出す。
m枚の部材のサイズは(縦, 横)の配列で与えられる。
すべての部材を切り出すことができれば、切り出し方法を出力せよ。切り出しが不可能ならば「impossible」と出力せよ。
切り出し方法は、
(部材インデックス、部材の一番左のx座標、部材の一番上のy座標、幅、高さ)
のリストとして出力せよ。斜めの方向の切り出しは考えなくてもよい。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。ただし、x軸は右の向き、y軸は下向きとする。
テストデータ。
cx=10, cy=10, m=5, {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5}
cx=5, cy=12, m=5, {2, 5}, {3, 3}, {2, 8}, {3, 2}, {4, 3}