X



プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2016/12/01(木) 16:58:30.97ID:gTkHDluD
プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part8©2ch.net
http://echo.2ch.net/test/read.cgi/tech/1444216746/

【出題と回答例】
1 名前:デフォルトの名無しさん
  お題:お題本文

2 名前:デフォルトの名無しさん
  >>1 使用言語
  回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。
0340デフォルトの名無しさん
垢版 |
2017/07/08(土) 11:54:07.74ID:H5pSyGdF
>>334 Squeak/Pharo Smalltalk

| sqrt |
sqrt := [:n :m |
 "ref. https://xar.sh/post/67066374255/ "
 | a b |
 a := 5 * n. b := 5.
 [:exit | [
  a >= b ifTrue: [a := a - b. b := b + 10] ifFalse: [
   b log > m ifTrue: [exit value] ifFalse: [
    a := a * 100. b := b // 10 * 100 + (b \\ 10)
   ]
  ]
 ] repeat] valueWithExit.
 b
].

#(3 5 7) collect: [:i | i -> (((sqrt value: i value: i*1000) asString first: i*1000) occurrencesOf: $0)]

"=> {3->309 . 5->493 . 7->738}"
0341デフォルトの名無しさん
垢版 |
2017/07/08(土) 12:18:57.24ID:hDxZO8qP
>>339
N = 29とN=41の場合が間違ってる可能性? それ以外は正しい模様
N = 29 => 2912、N = 41 => 4094 じゃなかろうか

>>340
合ってる
0344デフォルトの名無しさん
垢版 |
2017/07/08(土) 13:31:31.09ID:3gkxwDpM
>>341
> N = 29 => 2912、N = 41 => 4094 じゃなかろうか

それが正しいようです
GNU MPだとどうしても最後の桁は四捨五入?されるようで
任意のNに対して正確な答えを出すのは面倒なので修正は断念
0347デフォルトの名無しさん
垢版 |
2017/07/09(日) 11:25:12.20ID:nhQrw0mT
N=100000, 1億桁のくらいなら現実的な時間で出来る

丸めは切り捨て?四捨五入?
0349346
垢版 |
2017/07/09(日) 12:21:20.78ID:4Kodr3MO
>>347
GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので
floor() であらかじめ切り捨ててから get_str() した
0350デフォルトの名無しさん
垢版 |
2017/07/09(日) 12:57:37.64ID:DBjzEn12
ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか?
連続するゼロの個数の最大だろ?
無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。
0352デフォルトの名無しさん
垢版 |
2017/07/09(日) 13:28:51.97ID:DBjzEn12
もとめる桁数のほうに上限があったのか、それを見逃してた。
0354デフォルトの名無しさん
垢版 |
2017/07/09(日) 13:51:59.10ID:DBjzEn12
どっちも間違えたな、ゼロの総数だったか。
0355デフォルトの名無しさん
垢版 |
2017/07/09(日) 19:14:37.92ID:6MYOcrZ9
>>349
floorを行った後の結果に誤差は無い
という検証は出来てるの?
何もしてないなら、それはたまたま偶然当たったっていうだけだぞ

ていうか、君には聞いてない
出題者の意図を聞いてる
0356デフォルトの名無しさん
垢版 |
2017/07/11(火) 15:16:56.21ID:1hL73PK3
√2でなるべく長い0の連続をみつけるは?
0357デフォルトの名無しさん
垢版 |
2017/07/11(火) 15:49:47.43ID:QxseLuPf
>>355
君には向いて無いよ
0358 ◆QZaw55cn4c
垢版 |
2017/07/11(火) 16:29:49.99ID:ZfeFayuI
>>355
>floorを行った後の結果に誤差は無い
>という検証は出来てるの?

ぱっとみ当然だと思うんだが

>>356
何桁求めるか指定しないと意味がないのでは?
0359 ◆QZaw55cn4c
垢版 |
2017/07/11(火) 16:35:18.57ID:ZfeFayuI
>>358
ん、考え直した
10進に変換した結果にて 99999 とかが末尾にあるようでは、余分の計算はしないといけないね
0360デフォルトの名無しさん
垢版 |
2017/07/11(火) 18:55:08.87ID:dSS1j36W
[][Tebla][]

}

000-"Yob*RtStrike"[%Kil\]MO,fla>%$9999VLTS

001-GYORLith"0\R"/"ESUBA"%$%

HADO-"EM","L","O","NU"###END
0366デフォルトの名無しさん
垢版 |
2017/07/14(金) 07:59:21.83ID:PYQ8V1MO
>>365
あはは・・・。
コード書き捨てるのは良いけど、道具書き捨てるのは俺には向いてないわ。
なので、標準待ち。
0368デフォルトの名無しさん
垢版 |
2017/07/14(金) 09:38:45.73ID:PYQ8V1MO
>>367
Boostも良いんだけどね。残念なことにあれは実験環境で準標準って扱いなんだよなぁ。
あれから取り入れられるライブラリも多いんだけど、標準じゃないからね。
残念なことに。
0369デフォルトの名無しさん
垢版 |
2017/07/14(金) 12:49:16.12ID:gnKUWanp
まあ標準ライブラリしか使わない縛りをしたければ好きにすればいいんじゃない?
0371デフォルトの名無しさん
垢版 |
2017/07/14(金) 14:31:43.15ID:DwybRUfK
競プロみたいな相手方の環境使う物だと標準と準標準の差はでかい
自分の環境なら導入すればいいだけだが
0373デフォルトの名無しさん
垢版 |
2017/07/15(土) 12:42:06.98ID:odVkuNfb
>>361
厳密解を出しているのなら、チャレンジ
(わかって近似値解狙いなら気にしないで)

"14432" と "887654329"

両方とも既出の"貪欲つぶし"(?)数列

"14432"は 20秒 (ゼロインデック順で02341)
"887654329"は 80秒(同123456708)でいける。
0374デフォルトの名無しさん
垢版 |
2017/07/15(土) 14:59:21.20ID:OEoVgGO0
>>373
http://ideone.com/cBzPSj
C++。それ解くとほかの問題が解けなくなる。
厳密解のつもりだったが、ちょっと自分の領分超えてるなぁ。
うまくいかないものだ。
真実が奥の方にあると貪欲法は弱いな。Orz
0375デフォルトの名無しさん
垢版 |
2017/07/16(日) 16:33:07.01ID:8ZBD9z9c
お題:
自分用多倍長整数演算関数

…って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの
制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。
0378デフォルトの名無しさん
垢版 |
2017/07/16(日) 20:34:05.63ID:yctBkD01
掛け算の実装がキモだろう。
ここがボトルネックになるはず。
ここができると円周率とか、ルート計算も高速化できるはず。
0379 ◆QZaw55cn4c
垢版 |
2017/07/16(日) 20:36:24.09ID:eA1jggM5
>>378
うん,FFTを使うそうだが‥いまいちよくわからない
0380375
垢版 |
2017/07/16(日) 20:41:46.81ID:8ZBD9z9c
>>376
仕事で言語を選べる立場になってみたいものだわ。
この言語でやってってののは多々あるけど…orz

>>377
Karatsuba-Ofman法を目指してごーごー
0381デフォルトの名無しさん
垢版 |
2017/07/17(月) 22:48:25.95ID:5edeqhg+
>>296
手計算で計算出来るレベルにまで計算量を減らせた
もちろん数学的な裏付け付きで
ある条件を見たせば一瞬で求まる

"123456789123456789" > 98秒
残念ながら、これだけはその条件を満たしてない
0384デフォルトの名無しさん
垢版 |
2017/07/18(火) 07:41:44.22ID:Ew0RSScO
まだコードになってないんで、
コードになったらアップします

寿司を食べる時間 < レーンの回転周期
という前提をつけちゃおうと思ったけど、
つけない方が良さそうですね

寿司を食べる時間がレーンの回転周期の整数倍の寿司は
ちょっと特別な処理が必要
0387386
垢版 |
2017/07/18(火) 09:39:56.20ID:YLlwVFMJ
>>339
つ mpz_sqrt()
0388デフォルトの名無しさん
垢版 |
2017/07/19(水) 18:12:29.37ID:Np9hKHT2
>>296
>>373
http://ideone.com/B9vl8l
C++。結局、i7-6700のmem2G使って7分で解けた。
どうしようもない位遅いな。
でも一応題意には添えたと思う。
もう見たくない・・・。Orz

高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。
よくわからんけど、数学で頑張ってる人に期待だ。
0389386
垢版 |
2017/07/20(木) 01:57:16.81ID:Q7XnESC/
100のべき乗に変更
ttp://sagecell.sagemath.org/?q=mciykc
0390デフォルトの名無しさん
垢版 |
2017/07/21(金) 15:21:18.13ID:7e+pM3K/
>>296
http://ideone.com/mXPglY
C++。試しに再起化してみたら処理速度倍になった。
自分の環境では3分ちょいで解ける。
相変わらずメモリ馬鹿食いするけど。
もう俺には無理。

俺の中では終了でーす。Orz
0391デフォルトの名無しさん
垢版 |
2017/07/22(土) 08:54:36.28ID:OQXA8cUK
>>388
数学で頑張ってる人だけど、
もうちょっとまって

>>296の問題だけなら簡単だけど、
まだ全体を解明できてない

というか、忙しくて>>381から進んでない
0396デフォルトの名無しさん
垢版 |
2017/07/23(日) 14:15:20.13ID:ipiEUPYV
C/C++ で最長1000行ぐらいとみて、2日ぐらいあれば、とりあえず動く
土日で仕上がってくるんじゃないかと期待してたんだが
0398デフォルトの名無しさん
垢版 |
2017/07/23(日) 14:21:31.79ID:7fREas1L
ていうか、
コードに対する条件とか
サポートする機能とか
条件が無さすぎる
0399デフォルトの名無しさん
垢版 |
2017/07/23(日) 14:24:57.75ID:ipiEUPYV
速度‥か‥

どうしてもローテートとかキャリーフラグとかを使いたいから、これはアセンブラの領域になるね
よくみかけるアセンブラ中毒者が今頃爪を研いでいるのだろうか?
0401デフォルトの名無しさん
垢版 |
2017/07/23(日) 14:49:34.77ID:TcY6qE9r
>>394

当日に >>305>>390 より10倍以上早いのがでているだろう。
しかも 計算量まで書いてある
0406デフォルトの名無しさん
垢版 |
2017/07/23(日) 16:52:43.21ID:7fREas1L
FFTのライブラリをどこからか持ってくるのでもいいけど、
それなら素直に多倍長ライブラリを持ってくれば
ってことになる
0408デフォルトの名無しさん
垢版 |
2017/07/23(日) 18:50:17.74ID:5CSy1R8t
基数を10のべき乗にするとか(printf()的なものが簡単だから)、乗算はunsigned shortやintとの
乗算に限るとか、除算無しとかいうのは…

プログラムの本体に組み込まれてしまって、再利用可能なライブラリの形で括りだされてる事の
方が少ないかw
0410デフォルトの名無しさん
垢版 |
2017/07/24(月) 18:24:00.06ID:UuUAOyUA
>>408
裁定ラインとしては、乗算は Bigint×Bigint、および除算の実装ですかね、でも足し算の回数での乗算や引き算の回数での除算は嫌ですね
0412デフォルトの名無しさん
垢版 |
2017/07/24(月) 19:10:35.21ID:nJVItCRy
>>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)]
0413デフォルトの名無しさん
垢版 |
2017/07/24(月) 19:11:05.16ID:7nQ6Z7f9
>>296
超高速版が出来ました!
http://ideone.com/FrRkof

一皿9秒が上限であれば、計算オーダーはn
関数自体は何秒でも大丈夫です

コードだけじゃ意味がわからないでしょうけど、とりあえずコードだけ
あまりテストしてないので、バグってたらごめんなさい
0414デフォルトの名無しさん
垢版 |
2017/07/24(月) 23:00:47.69ID:fjGi9Yh0
オーダーnは凄いな
0415デフォルトの名無しさん
垢版 |
2017/07/25(火) 05:40:32.49ID:ubbfnjuS
>>413
うーんわからん。
俺の思考とは別系統かな。
ホントに0秒で解けてるし、素晴らしい。
素直に賞賛。
0416デフォルトの名無しさん
垢版 |
2017/07/25(火) 11:52:16.57ID:bLUUDw7G
回転寿しの問題は、部分的な最短経路が全体の最短経路にならないんだよな
だが最短時間はレーン長の2倍程度の再帰回数で出る
そのあと数十億回再帰して総当たりしてもそれより短くならない
最後の皿から逆方向に探索してもおそらく同じ状況
0417デフォルトの名無しさん
垢版 |
2017/07/25(火) 11:56:47.84ID:bLUUDw7G
例えば、”122” は最短時間6だが、1周目で2番目の要素”2”をパスしないとそうならない
0418411
垢版 |
2017/07/26(水) 19:54:35.63ID:6H34MdHA
>>412
ファレイ数列の中間数(mediant)を再帰的に生成すると、uniqもsortも要らないのだけど、
mが3や5だと大差無いかw
0420デフォルトの名無しさん
垢版 |
2017/07/26(水) 20:52:34.29ID:s8dUUqTb
と思ったら見れました

ファレイ数列を使って何かを解くわけじゃなくて、
ファレイ数列を求める問題?
0421411
垢版 |
2017/07/26(水) 23:20:07.89ID:6H34MdHA
>>420
元の問題はそういうもの(=ファレイ数列の両端(0/1と1/1)無し版を求める問題)と
解釈してますです。
0422デフォルトの名無しさん
垢版 |
2017/07/26(水) 23:26:01.52ID:lPM9zwS7
#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;
}
0423デフォルトの名無しさん
垢版 |
2017/07/26(水) 23:29:22.49ID:lPM9zwS7
これから0と1を除けば良いって問題であれば、
表示のループに以下を加えれば
if (i->den != 1)
0424デフォルトの名無しさん
垢版 |
2017/07/26(水) 23:31:57.11ID:lPM9zwS7
問題の意味も意図も良くわからん

出題者が「そういうものと解釈しています」とか
出題者が >>418 みたいな回答をバカにする発言とか

なんか非常に感じが悪い
0425412
垢版 |
2017/07/27(木) 00:12:38.86ID:qteH6K3e
そもそも>>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)]
0431デフォルトの名無しさん
垢版 |
2017/07/30(日) 10:59:37.37ID:A7gIx2b1
お題:MathematicaのFareySequence[n,k](引数2つ)に相当するものの実装
ttp://reference.wolfram.com/language/ref/FareySequence.html
0433デフォルトの名無しさん
垢版 |
2017/07/30(日) 12:00:36.94ID:EQKnHSgY
っていうか、この関数インデックスに0与えたら何が出力されるんだろう・・・。
早速バグってる気がする。
■ このスレッドは過去ログ倉庫に格納されています

ニューススポーツなんでも実況