プログラミングのお題スレ Part22 (877ﾚｽ)
上下前次1-新
1(4): 2023/08/03(木)13:52 ID:/xW45k0z(1) AAS
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:codepad.org
外部ﾘﾝｸ:compileonline.com
外部ﾘﾝｸ:rextester.com
外部ﾘﾝｸ:runnable.com
外部ﾘﾝｸ:code.hackerearth.com
外部ﾘﾝｸ:melpon.org
外部ﾘﾝｸ:paiza.io
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part21
2chｽﾚ:tech
848(1): 09/14(日)02:17 ID:ymjVQadn(1) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・なんとなく動いてる版
・チマチマと次を探して行く
・G[20]まで出すのがやっと(4.05s)
849(2): 09/14(日)21:00 ID:Yva1i9w5(1/2) AAS
>>845
R
外部ﾘﾝｸ:ideone.com
>>846より行列計算が速くなった。変数名mとnが逆だったのを直した。
C++に移植
外部ﾘﾝｸ:ideone.com
850(1): 09/14(日)22:50 ID:Yva1i9w5(2/2) AAS
>>845
Fortranに移植
外部ﾘﾝｸ:ideone.com
行列計算を短く書けて、しかも実行が速い。
851(2): 848 09/15(月)00:34 ID:aTaxsjKO(1/2) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン
852(1): 851 09/15(月)00:58 ID:aTaxsjKO(2/2) AAS
外部ﾘﾝｸ:ideone.com
・動きは >>851 といっしょ
・若干の整理
853: 09/15(月)22:27 ID:g8zilsSB(1) AAS
>>850では行末に無駄な半角空白文字が出力される。消すには最後から3行目のnthPartition(m, n)を
trim( )で囲めば良い。
854(1): 852 09/16(火)01:02 ID:3CKXdG+H(1) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更
855(1): 854 09/17(水)22:30 ID:U8XLHdaR(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・とりうるパターン数に着目し迫る
・tallyは2.7以降
856(1): 09/17(水)22:43 ID:RlLGu0ST(1/2) AAS
>>845
C++
外部ﾘﾝｸ:ideone.com
行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。
857: 09/17(水)23:39 ID:RlLGu0ST(2/2) AAS
>>856
BigInt化してm = 2000, n = 2¹⁰²⁴で実行したら違いが明確になった。
(1) >>849のBigInt版
外部ﾘﾝｸ:ideone.com
(2) >>856のBigInt版
外部ﾘﾝｸ:ideone.com
加減算・代入回数を削減した(2)の方が確かに速く、(1)の約4分の3の実行時間。
858(1): 855 09/18(木)21:13 ID:mk4sIpUK(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・揃ってからcumsum、のリズムを廃止
859(1): 858 09/19(金)21:59 ID:e72KvXSi(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・若干の整理（loop廃止、fill三回へ置き換え）
860(1): 859 09/20(土)21:39 ID:zrmIrXrK(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・内部表現の変更
112225→[2,3,0,0,1]
861(1): 860 09/22(月)21:37 ID:9W7EeSnZ(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
cc[合計][幅] = とりうるパターン数
>>845 ruby
外部ﾘﾝｸ:ideone.com
・m = 2000, n = 1 << 1024
862(1): 861 09/23(火)01:13 ID:XS9iE/WB(1) AAS
>>845 c++
外部ﾘﾝｸ:ideone.com
・ruby版861の移植
・m = 2000, n = 1 << 1024
863: 862 09/26(金)21:58 ID:rAOVnJgT(1) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・実りの無い再帰を省略
・結果を配列で集めず整数で集める
>>845 c++
外部ﾘﾝｸ:ideone.com
・rubyの移植版
>>845 ocaml
外部ﾘﾝｸ:ideone.com
・rubyの移植版
・任意精度整数は昔ながらのnumのBig_int使用
・ZarithのZは確かに速かったけどideoneでは使えずボツ
864(2): 10/19(日)18:23 ID:UPYRyJKx(1) AAS
お題
硬貨の種類と金額が与えられます。
硬化の合計がちょうど金額と同じになるように硬貨を選ぶとき、使用枚数の最小値を求めてください。
支払いが不可能なときは-1を出力します。
各硬貨は無制限に使用できます。
額面の大きい硬貨を優先して選ぶ貪欲法が常に最適解を与えるとは限らないことに注意。
入力
硬貨：[1,7,10]
金額：14
出力
使用枚数：2
865: 10/19(日)21:36 ID:1trCfbwI(1) AAS
>>864
R
外部ﾘﾝｸ:ideone.com
866: 10/22(水)21:34 ID:vm0Iby1T(1) AAS
>>864
金額が大きい場合でも高速に求められるようにした。
R
外部ﾘﾝｸ:ideone.com
C++
外部ﾘﾝｸ:ideone.com
867(2): 10/26(日)09:31 ID:Y3+SSpql(1/5) AA×
868(1): 10/26(日)09:50 ID:Y3+SSpql(2/5) AAS
あ、ただの素数判定でも良いです。
ちなみに、66..61の場合は6661までは素数ですが66661は素数じゃなくなりました。
なので、33..31もどこかで素数じゃなくなるのか？それともずっと素数になりそうなのか？って疑問が持ち上がりました。
869(2): 10/26(日)10:13 ID:XLS0tlS8(1/2) AAS
>>867
興を削いですまんが、「33...331は素数か」でググったら、AIが（あまり大きくない桁数で）答えを示してくれた…
870(1): 10/26(日)10:19 ID:0X7G2IAI(1) AAS
near-repdigit素数とかで研究されてるらしい
結果だけ知りたいなら↓がまとめてる
外部ﾘﾝｸ[htm]:stdkmd.net
871(1): 869 10/26(日)10:21 ID:XLS0tlS8(2/2) AAS
>>869
ちなみに、以下の思考経路だったのでプログラミング的な思考がゼロだった訳では無い。
1.多倍長整数で組むべきかな？
2.でも64bit整数の範囲で合成数だったら馬鹿馬鹿しいな
3.組む前にカンニングしちゃえ
4.>>869
872: 10/26(日)17:08 ID:Y3+SSpql(3/5) AAS
>>869-871
いえいえ、ああ、やっぱりずっと素数という訳にはいかないんですね…。
何か素数の秘密に触れるヒントか？と心躍ったけど、そんな訳なかったですね(´・ω・｀)
あやうく数学スレで鼻息荒く書き込むところでした。
ありがとうございました<(_ _)>
873(1): 10/26(日)17:55 ID:N6SeZsiy(1) AAS
29bitで収まる範囲内
333333331 = 17 × 19607843
これを求められなかったHaskellはすごく遅い？
874: 10/26(日)23:06 ID:Y3+SSpql(4/5) AAS
>>873
速いアルゴリズムに変えたら何とか1分ほどでその数字まで届きました。
（そもそも、>867 のは美しいとか短いとかの枕詞が付くコードですし。33...31に気付かなかったら4桁ぐらいが実用的ならおｋだったので）
改良版Haskell
pfactorization = f primes
where primes =2:3:5#primes
where n#x@(m:q:y)=[n|gcd m n<2]++(n+2)#last(x:[m*q:y|q^2-3<n])
というか、それより1桁少ない方が少し時間かかりますね。
19607843 < 33333331 なので、素数比較回数が多いのかと。
875: 10/26(日)23:07 ID:Y3+SSpql(5/5) AAS
あ、f の方を忘れた。
f のコードは変更なしです。
876: 11/07(金)05:48 ID:ckPLmv2U(1) AAS
>>868
cだとこんな感じでいいのかな？
3333333333333331くらいまで一瞬でできる
#include <stdio.h>
int main(void) {
long long d, n;
printf("Enter a number: ");
scanf("%lld", &n);
for (d = 2; d * d <= n; d++) {
if (n % d == 0)
break;
}
if (d * d <= n)
printf("%lld is divisible by %lld\n", n, d);
else
printf("%lld is prime.\n", n);
return 0;
}
877: 11/25(火)16:00 ID:COUmbZtB(1) AAS
お題：ulp()の実装
Pythonのmath.ulp()に相当する関数の実装
特殊値(非数や無限大や非正規化数)の考慮は任意
引数がゼロの場合はDBL_MINやDBL_TRUE_MINに相当する値を
返すこと(プラットホーム依存)
発展的なお題：
共用体やfrexp()やldexp()を使わずに実装
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.526s*