プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
いやあってるか。
A(k) = (1/k)>>kと置くと、
log2 - ΣA(k) < A(n) (級数はn-1までの和) で
ΣA(k) (n+1以上の和) < A(n) が成立するのか。 やはり、どこか間違ってるな。
上のとおりだと、log2 - ΣA(k) (級数はn-1までの和)は、
A(n) を含むので、A(n)より小さいはずがない。 >>701
＞ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ
対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、
必要に応じてまた脳みそに搭載できるようにならないものか…
そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね >>680
>>696の方法で作ってみました
n=10^10の時に48.3秒くらいです >>723 はHaswell (4770) 3.4GHz固定での結果で
Skylake (6700K) 定格だと38.4秒でした
ちゃんとCPUも進化してるんですね >>681
>>690
C++だとどうやって計算してるかが非常に気になります
32bitを越える値同士の乗算(結果が64bitを越える)部分
アセンブラだと
64bit x 64bit ===> 128bit
128bit / 64bit ===> 64bit
等があるのでそれを使っちゃってますが 冪剰余を求めるのに
(a * b) % c
みたいなのがたくさん出てきませんか？
aもbもcも32bitの範囲を微妙に越えてて 誤差部分の間違いが判った。これでよさげだ。
ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。
誤差項ありのマクローリン展開は、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 これが収束速いようだ。
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)) >>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 だから速く計算できるのだ >>727
残りの項を等比数列と見なせば
簡単に誤差の上限が出ます >>724
Haswellで33.96秒に縮まりました
シングルスレッドだと182.54秒で5.3倍
HTTが効くということは、
まだ多少改善の余地がありそう
一番内側のループは
vmulpd
vmulpd
vroundpd
vfmsub213pd
vfmsub132pd
vsubpd
なんと浮動小数点で計算してます n=10000000000の時は
0000010101 でした
出題者さま、合ってます？
また、たまたまですが
n=10000000004では
0101010101
n=10000000005では
1010101010
になります 一番内側のループのコード
http://fast-uploader.com/file/7067434368942/
PORT5がガラ空きで、処理のほとんどがPORT0,PORT1
こんなんでもHTTが効く
やっぱり浮動小数点はレイテンシがデカい
AVX512になれば
レジスタの数が倍になるので
8パラにしてレイテンシを隠蔽出来るんだけど
もちろんレジスタ長が倍になる方が大きい >>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のように。 2 = (81/80)^3 * (25/24)^5 * (16/15)^7
3 と 5 の指数の合計が0になる組み合わせを検索すれば良い log(81/80) = log(162/160) = log((161+1)/(161-1))
わかってて書いてるんだと思ったが
>>729のlogの中身はこの値 >>728はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。 指数も固定でなくていいはずで、
16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。 分母分子の素因数の数と同じ項数が必要
例えば素因数が 2, 3, 5, 7 の4種類の場合、
1個差もしくは2個差のペアを4個探す
例えば
126/125
225/224
2401/2400
4375/4374
これらを適当に掛け算して2^nになるようにすると
項が4個の式がみつかる 分母、分子とも 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) >>740
その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。
A.D. Fokker: Unison Vectors and Periodicity Blocks
http://www.huygens-fokker.org/docs/fokkerpb.html
List of 7-prime limit accidentals - The?Sagittal?forum
http://forum.sagittal.org/viewtopic.php?f=6&;t=252 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
http://scholar.sun.ac.za/handle/10019.1/100826 log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、
音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。
log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。 お題。横x[cm]、縦y[cm]の長方形のステンレスの１枚の板がある。この板からm枚の複数の長方形の部材を切り出す。
部材のサイズは配列で与えられる。
部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。
ただし、部材の縦または横が変わるとそれぞれ一点減点となる。
すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。 テストデータ。
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}
} 部材の縦と横は入れ替わってもよい。
可能ならば、切り出し方法をSVG形式で出力せよ。 切り出し方法は、
切り出す部材のx座標、y座標、幅、高さ
のリストとして出力せよ。 切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。 人間用のパズルで、斜めにしないと解けないのとかありそう 問題文の条件が“だいたい”“なるべく”なんて
あいまい表現だらけ
これでプログラミングの問題かよ 斜めは考えなくてもよい。
訂正。
すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。 >>732
そこにある3つとも正解です
当初は L = Σ1/(k*2^k) として
2^n * L の小数部分を愚直に求める方法を想定していました 普通に多倍長で計算したら計算量的に終わらないですよね？
n=314159265を求めるのに
冪剰余は使ってますよね？
おそらく私も同じような方法と思います
FMA3命令とOpenMPで高速化してるだけで 愚直という言い方は良く割りませんでしたね
仰る通り冪剰余は用います 再出題。横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} 頭の悪そうな文章だな
正方形⊂長方形
ステンレスの板の座標上の位置指定が無い
余裕がある場合の条件の意味が曖昧 ステンレスの板の左上座標は原点にあるものとする。
切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。 >>758
相変わらず曖昧な表現
全ての長方形の上辺と左辺がどこかに接していれば良いのか？
そうじゃないのか？
このような条件のを1個だけ見つければ良いのか
すべて見つけるのか 全ての部材の上辺と左辺が別の部材の辺、もしくは、元の板の端に接していること。
このような条件のをすべて見つけること。 なんか、工学関係でこのような問題があるらしいが、まだ解決策があるかどうかわからん。これが解ければ、実用化待ったなし。 実用性なら
切りやすさとか余り素材の形状とか
そういうのが重要だろうに
問題として中途半端過ぎる なにやら揉めてますね
そろそろうんざりなので次のお題どうぞ お題ってこういうのでもいいのかな
a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
このように10個の整数を要素に持つ配列がある（整数の値は不定）
b = エントリーポイント
c = 移動する数量
d = 移動する距離
を与えることにより、配列の要素を移動させるプログラムを作りなさい
ただし配列の右端の要素を一つ移動させると、配列の左端に移動するものとする
例
a = 3, b = 1, c = 5, a = 0124567839
b = 1, c = 3, d = 1, a = 0412356789
b = 7, c = 1, d = 5, a = 1273456890
b = 0, c = 8, d = 1, a = 8012345679
b = 4, c = 5, d = 4, a = 6783901245
b = 9, c = 5, d = 4, a = 5679012384
b = 7, c = 3, d = 1, a = 9123456078 >>768
一番上の例は
b = 3, c = 1, d = 5, a = 0124567839
の間違いです >>768
https://ideone.com/zZdIlU
C++。なかなか素直な問題なのに邪悪な思念で見ていたため手間取った。
マニュアルを熟知していると簡単かもしれない。 >>768
b + c が10を超えることはありますか？ >>773訂正
b,c,dが10を越えることはありますか？ >>771はb,c,dが任意の自然数でも大丈夫なようにしておいた みなさんプログラム作るの早いですね
>>774
一応a、b、cの条件は、このようになると思います。
0 <= a <= 9
0 <= b <= 8
0 <= c <= 10 - b - 1
bとcは0では意味がないので、こっちのほうがいいのかな
0 <= a <= 9
1 <= b <= 8
1 <= c <= 10 - b - 1 >>776
すみません、間違えました、abcじゃなくてbcdですね
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - b - 1 >>777
すみません、訂正の訂正です。dは10-c-1ですorz
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - c - 1 >>770,771
せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね
それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね
>>772
Mathematicaは残念ながら持っていないので検証できませんでした
b = 8 c = 6 d = 2 a = 8901236745
b = 4 c = 3 d = 2 a = 0123784569
b = 4 c = 5 d = 2 a = 8123904567
b = 2 c = 5 d = 2 a = 0178234569
b = 0 c = 5 d = 3 a = 5670123489
b = 9 c = 3 d = 4 a = 3459016782
b = 5 c = 1 d = 7 a = 1253467890
b = 4 c = 6 d = 2 a = 8923014567
b = 6 c = 7 d = 2 a = 8901253467
b = 7 c = 5 d = 4 a = 5789016234
b = 4 c = 2 d = 2 a = 0123674589
b = 6 c = 4 d = 5 a = 4678950123
b = 7 c = 4 d = 4 a = 4789056123
b = 4 c = 5 d = 4 a = 6783901245
b = 8 c = 1 d = 5 a = 1238456790
b = 0 c = 2 d = 6 a = 2345670189
b = 3 c = 7 d = 1 a = 9120345678
b = 9 c = 4 d = 2 a = 4901256783
b = 8 c = 3 d = 6 a = 3456890712
b = 2 c = 5 d = 3 a = 0178923456 >>780
お、あんた偉いな。
出題者でちゃんと答え合わせやってくれる人が稀でレスポンス薄いことが多いんだよ。
ちゃんと動いてよかったよ。 >>774
自分は10超えてもらったら困るなぁ。
10っていうか、配列の要素数だな。
修正はそんなに難しくないけど。 >>781
1行プログラムすごいですね
さすがスクリプト言語
>>782
そうなんですか、でもいろいろな言語で回答されるから、出題者も大変かもしれないですね
私は問題の意味すらよく分からないことが多いので、もっぱら見る専ですが >>785
b = 6、 c = 6、 d = 2
のときの動作がおかしいようです
8901452367
となるはずが
0167892345
となっており、移動する"678901"の並びが崩れてしまっています >>786
問題勘違いしてました。素直にぐるぐる回すように修正しました。
https://paiza.io/projects/ncIY4LljeBahWZPJpd8ZPQ
下の「入力」タブの方にスペース区切りで b, c, d の値を1行づつ並べて入れてから実行させると「出力」に結果が出ます。
とりあえず >>768 に書いてある値を入力にセットしたところ出力は同じになりました。 >>787
入出力の確認をしただけですが、今回は問題ないようです
paiza使うと簡単に確認できて便利ですね >>768
僕の頭だとどうしても右端から左端に行くときの動きがイメージできないので、解答締め切ったあとでもいいのでちょろっと教えてもらえると嬉しいです
上3つまではわかるけどそこから先がそもそも答えにたどり着けない…… >>789
ヒント。
(インデックス++)%配列の長さ
を繰り返すとどうなりますか？%は余剰デス。 >>789
上の３つまでは分かるということなので、３つめのcの値を一つずつ増やしてみると、こんな感じになります
"7"、"78"、"789"、"7890"と並ぶ数値が増えていっているのが分かると思います
c+d の合計は9が最高なので、これ以上cを増やすにはdを減らさなくてはなりません
b = 7 c = 1 d = 5 a = 1273456890
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 3 d = 5 a = 3478956012
b = 7 c = 4 d = 5 a = 4578906123
今度はcを2に固定して、dの値を一つずつ増やすと、こんな感じになります
"78"の並びが一つずつ右へずれていっているのが分かると思います
c+d の合計は9が最高なので、これ以上dを増やすにはcを減らさなくてはなりません
b = 7 c = 2 d = 1 a = 0123456978
b = 7 c = 2 d = 2 a = 8123456907
b = 7 c = 2 d = 3 a = 7823456901
b = 7 c = 2 d = 4 a = 2783456901
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 2 d = 6 a = 2347856901
b = 7 c = 2 d = 7 a = 2345786901
こんな感じで分かるでしょうか？私も自分の頭で考えると混乱しますw 自分の考え方は、配列の一部を切り取ってパッディングするんだけど、
まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。
すると、配列の後ろにはすでにパディングが終わった数列のができてる。
で切り取って削除して尻尾にくっつける。
で、さっき回した分を戻してやると完成。
という方法で、>>770を解いた。 自分の考え方は、配列の一部を切り取ってパッディングするんだけど、
まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。
すると、配列の後ろにはすでにパディングが終わった数列のができてる。
で切り取って削除して尻尾にくっつける。
で、さっき回した分を戻してやると完成。
という方法で、>>770を解いた。 あちゃー
二重投稿になったある。
そんなに大事でもないのだけど。 C++は比較的不自由な言語なので頭使うのは鍛えられるよ。
パーツが少ないのでほとんど自作しないといけない。 コンパイルが必要とかでスクリプト系の言語より
使うことに不便があるかもしれないが、
できるアプリが自由で高速・軽量！
ライブラリもＳＴＬやboost以外にも、探せば便利なのがいっぱい。 よそのライブラリ使うとイデオンで動かないからなぁ。
まぁ、業務ではライセンスに合ったものを使えばいいよ。 >>789
塊が移動すると考えれば良い。
例えば 7, 4, 2 だとすると、 789 と先頭の 0 が移動する塊だ。
で、ちょっと分かり易くするためにこの塊を伏せて * で書くとするとこうなる。
*123456***
それでこの塊を右に一つずらす。その時に1は食われて尻尾から吐き出される。
**234561**
移動量2なのでもう一回右にずらす。すると2が食われて尻尾から吐き出される。
***345612*
それでは * から 7890 に戻してみよう。
8903456127
できあがり。 >>793
これ間違ってるな。
最後尻尾にくっつけるんじゃなくて、適所にインサートだった。
で戻す。
書いた日から時間たってるからすまん。 >>790
>>791
>>798
ありがとうございます
やっと理解できました
がんばって解いてみます log2だけど、これ使うといいらしいよ。分割統治法のBSA法というやつらしい。
2個ずつの積を繰り返すことで計算回数が減らせる。
{{1, a0}, {0, r}}*{{1, a1}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/rであり、
{{1, a0}, {0, r}}*{{1, a1}, {0, r}}*{{1, a2}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/r + a2/r^2。
上の式を実際に計算してみる。
http://www.wolframalpha.com/input/?i=%7B%7B1,+a0%7D,+%7B0,+r%7D%7D*%7B%7B1,+a1%7D,+%7B0,+r%7D%7D*%7B%7B1,+a2%7D,+%7B0,+r%7D%7D >>801
普通のlog 2の計算には使えても
>>680 には使えないかと >>731 から更に縮まりました
もう誰も興味が無いかも知れませんが
コードいる？ n=10^10で19.28秒にまで縮めた
n=10^13くらいまでなら夜寝てる間に終わる
>>804
期待してます！ 804だけど考えてみたら面倒なんだな。
有理数(整数)で完全に求めてから割り算するのは時間かかりそうだから、
展開も、割り算も、有限で打ち切って求める精度がでるようにするのが普通? お題
辺の長さが10,000以下の整数である直方体について
すべての面の対角線も整数となるものを全て求める >>807
答えは浮かんだけど、
手元にインタプリタがないので書けない。 >>805 のソース一式とexeです。
>>680 の回答となります。
http://fast-uploader.com/file/7068204781334/
実行ファイルは、拡張子をexe_からexeに変えてください。
OSはWindows 64bit Vista以降
CPUはHaswell以降
で動作します。 作ってみたけど、オッセ―。
なんか数学的にやらないとダメぽ。
>>810
検索したら出てきた。
ただのHYPODだった。 あ〜ん。足し算10兆回かかるとかむりげーじゃ。
どうしようかこれ。 >>807
https://ideone.com/5Tu6fx
C++。ギブアップ。遅すぎだ。
デバッグ不完全だからそこを忘れないで。
多分1日かけても終わらないと思う。 >>807
特に大きな工夫もなく普通に3重ループで出来ましたよ
151個かな ぶ。おれは・・・いったい・・・。
だめだなぁ。才能ないなぁ。 ■ このスレッドは過去ログ倉庫に格納されています
