25/09/19 21:59:08.62 e72KvXSi.net
>>847 ruby 2.5.5
URLﾘﾝｸ(ideone.com)
・若干の整理（loop廃止、fill三回へ置き換え）
862:859
25/09/20 21:39:31.29 zrmIrXrK.net
>>847 ruby 2.5.5
URLﾘﾝｸ(ideone.com)
・内部表現の変更
112225→[2,3,0,0,1]
863:860
25/09/22 21:37:36.11 9W7EeSnZ.net
>>847 ruby 2.5.5
URLﾘﾝｸ(ideone.com)
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
cc[合計][幅] = とりうるパターン数
>>847 ruby
URLﾘﾝｸ(ideone.com)
・m = 2000, n = 1 << 1024
864:861
25/09/23 01:13:48.01 XS9iE/WB.net
>>847 c++
URLﾘﾝｸ(ideone.com)
・ruby版861の移植
・m = 2000, n = 1 << 1024
865:862
25/09/26 21:58:13.14 rAOVnJgT.net
>>847 ruby
URLﾘﾝｸ(ideone.com)
・実りの無い再帰を省略
・結果を配列で集めず整数で集める
>>847 c++
URLﾘﾝｸ(ideone.com)
・rubyの移植版
>>847 ocaml
URLﾘﾝｸ(ideone.com)
・rubyの移植版
・任意精度整数は昔ながらのnumのBig_int使用
・ZarithのZは確かに速かったけどideoneでは使えずボツ
866:デフォルトの名無しさん
25/10/19 18:23:02.12 UPYRyJKx.net
お題
硬貨の種類と金額が与えられます。
硬化の合計がちょうど金額と同じになるように硬貨を選ぶとき、使用枚数の最小値を求めてください。
支払いが不可能なときは-1を出力します。
各硬貨は無制限に使用できます。
額面の大きい硬貨を優先して選ぶ貪欲法が常に最適解を与えるとは限らないことに注意。
入力
硬貨：[1,7,10]
金額：14
出力
使用枚数：2
867:デフォルトの名無しさん
25/10/19 21:36:07.90 1trCfbwI.net
>>866
R
URLﾘﾝｸ(ideone.com)
868:デフォルトの名無しさん
25/10/22 21:34:32.83 vm0Iby1T.net
>>866
金額が大きい場合でも高速に求められるようにした。
R
URLﾘﾝｸ(ideone.com)
C++
URLﾘﾝｸ(ideone.com)
869:デフォルトの名無しさん
25/10/26 09:31:44.23 Y3+SSpql.net
お題というか、協力してほしい感じなんですが、素因数分解関数をHaskellで書いて色んな数を素因数分解して遊んでいたら確認したい事実に出くわしたので。
31 <- 素数
331 <- 素数
3331 <- 素数
33331 <- 素数
333331 <- 素数
と、３が５個並んで末尾が１の数字までは素数という事が分かりましたが、いかんせん、ノートだと力不足。
それにCとかで書き直したらもっと先まで行けるかも？という事で、この先、どこまで33...31が素数なのかを調べて欲しいのです。
協力お願いします<(_ _)>
一応、Haskellではこんなコードです。
factorization n = f primes n
where primes = 2:(sieve [3,5..])
where sieve (p:xs) = p:(sieve [x | x <- xs, x `mod` p /= 0])
f (p:ps) n | n <= p = [n]
f (p:ps) n | n `mod` p == 0 = p:f (p:ps) (n `div` p)
f (p:ps) n = f ps n
870:デフォルトの名無しさん
25/10/26 09:50:23.90 Y3+SSpql.net
あ、ただの素数判定でも良いです。
ちなみに、66..61の場合は6661までは素数ですが66661は素数じゃなくなりました。
なので、33..31もどこかで素数じゃなくなるのか？それともずっと素数になりそうなのか？って疑問が持ち上がりました。
871:デフォルトの名無しさん
25/10/26 10:13:01.91 XLS0tlS8.net
>>869
興を削いですまんが、「33...331は素数か」でググったら、AIが（あまり大きくない桁数で）答えを示してくれた…
872:デフォルトの名無しさん
25/10/26 10:19:15.38 0X7G2IAI.net
near-repdigit素数とかで研究されてるらしい
結果だけ知りたいなら↓がまとめてる
URLﾘﾝｸ(stdkmd.net)
873:869
25/10/26 10:21:11.68 XLS0tlS8.net
>>871
ちなみに、以下の思考経路だったのでプログラミング的な思考がゼロだった訳では無い。
1.多倍長整数で組むべきかな？
2.でも64bit整数の範囲で合成数だったら馬鹿馬鹿しいな
3.組む前にカンニングしちゃえ
4.>>871
874:デフォルトの名無しさん
25/10/26 17:08:32.87 Y3+SSpql.net
>>871-873
いえいえ、ああ、やっぱりずっと素数という訳にはいかないんですね…。
何か素数の秘密に触れるヒントか？と心躍ったけど、そんな訳なかったですね(´・ω・｀)
あやうく数学スレで鼻息荒く書き込むところでした。
ありがとうございました<(_ _)>
875:デフォルトの名無しさん
25/10/26 17:55:12.41 N6SeZsiy.net
29bitで収まる範囲内
333333331 = 17 × 19607843
これを求められなかったHaskellはすごく遅い？
876:デフォルトの名無しさん
25/10/26 23:06:07.50 Y3+SSpql.net
>>875
速いアルゴリズムに変えたら何とか1分ほどでその数字まで届きました。
（そもそも、>869 のは美しいとか短いとかの枕詞が付くコードですし。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 なので、素数比較回数が多いのかと。
877:デフォルトの名無しさん
25/10/26 23:07:37.04 Y3+SSpql.net
あ、f の方を忘れた。
f のコードは変更なしです。
878:デフォルトの名無しさん
25/11/07 05:48:17.42 ckPLmv2U.net
>>870
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;
}
879:デフォルトの名無しさん
25/11/25 16:00:02.31 COUmbZtB.net
お題：ulp()の実装
Pythonのmath.ulp()に相当する関数の実装
特殊値(非数や無限大や非正規化数)の考慮は任意
引数がゼロの場合はDBL_MINやDBL_TRUE_MINに相当する値を
返すこと(プラットホーム依存)
発展的なお題：
共用体やfrexp()やldexp()を使わずに実装
880:デフォルトの名無しさん
25/12/06 16:35:13.06 LjhUSqqq.net
お題：ページャーがある。範囲表示に使う配列を出力せよ。現在のページ番号はp，総ページ数はn、切り取る範囲はrとする。
例
p=1, n=10, r=5
[1,2,3,4,5]
p=3, n=10, r=5
[1,2,3,4,5]
p=5, n=10, r=5
[3,4,5,6,7]
p=8, n=10, r=5
[6,7,8,9,10]
p=10, n=10, r=5
[6,7,8,9,10]
881:デフォルトの名無しさん
25/12/06 19:35:04.35 cqDpuJik.net
>>880
R
URLﾘﾝｸ(ideone.com)
お題に指定がない仕様は適当に決めた。