プログラミングのお題スレ Part16

プログラミングのお題スレ Part16 at TECH

[前50を表示]
450:課題は｢最短手順を求める｣のみ

451:蟻人間
19/12/26 15:19:10.12 Npbug+/w.net
お題: 半角英数からなるユーザーIDとパスワードで認証できるアカウントのシステムを以下の要件で作る。
1.新規登録を選んでユーザーIDとパスワードとメールアドレスを入力するとアカウント登録ができる。
2. 複数アカウント対応。ユーザーIDの重複はダメ。
3. アカウント一覧を選ぶとアカウントの一覧とログイン状態が見える。
4. ログインを選んでユーザーIDとパスワードの入力が一致すればログインできる。
5. ログアウトを選べばログアウトできる。
6. パスワードを忘れたとき、アカウントの回復を選んでメルアド入力すると、メールが来てパスワードがリセットされる。

452:デフォルトの名無しさん
19/12/26 19:06:46.63 ArA1I+l7.net
>>432
　URLﾘﾝｸ(ideone.com)
　
　よくある経路復元方式に変更。
　(大量な文字列のコピーが減った)

453:デフォルトの名無しさん
19/12/26 19:20:20.20 nVG7mTn1.net
>>429を少し速くした
URLﾘﾝｸ(ideone.com)

454:デフォルトの名無しさん
19/12/26 21:44:10.91 nVG7mTn1.net
URLﾘﾝｸ(ideone.com)
vectorを使いまわしするようにしたら速くなった

455:デフォルトの名無しさん
19/12/27 00:16:14.43 N7T+QvJX.net
URLﾘﾝｸ(ideone.com)
まだ省くことができた

456:蟻人間
19/12/27 18:58:01.81 0l4cUgpw.net
Web系もプログラミングの一種なんだけど、日本のIT教育では軽視されてるみたいなんだ。

457:デフォルトの名無しさん
19/12/27 20:56:28.17 JVKHwIo7.net
<('o')>ﾌｰﾝ

458:
19/12/27 21:03:47.38 9iE1xeZJ.net
>>444
web 系をはじめるには、どういう環境で学べばいいですか？

459:デフォルトの名無しさん
19/12/27 21:12:37.24 IA42SgXa.net
URLﾘﾝｸ(ideone.com)
>>440のアルゴリズムの方が速いね

460:デフォルトの名無しさん
19/12/27 21:14:11.36 IA42SgXa.net
↑が100回
これが1回
URLﾘﾝｸ(ideone.com)

461:デフォルトの名無しさん
19/12/27 22:14:31.51 novkoLBo.net
>>426 類似問題
素数を20個使って、総合計で2020を作る。
(同じ素数を複数使ってよい）
何種類できるか(組合せで)。 -->?
(同じ数字は区別しない -> ソートして数列が異なるもので1種類)
ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。
※ 2020で20個なら、まだint64_tでおさまる

462:デフォルトの名無しさん
19/12/27 22:54:15.08 IA42SgXa.net
↑
>>429の+1を消すだけ

463:デフォルトの名無しさん
19/12/27 22:58:27.12 Wx5tgQ31.net
お題: 「Happy New Year!!」と出力するプログラムを2020年元日に投稿せよ

464:デフォルトの名無しさん
19/12/27 23:32:30.61 novkoLBo.net
>>450
やっぱり(既にできていて)、その程度なのだろう。
自分の方も、ユニーク時は更新が伝播しないように
逆順で処理していたのを、伝播するよう正順に戻すだけ。
>>449
　URLﾘﾝｸ(ideone.com)

465:デフォルトの名無しさん
19/12/27 23:43:22.25 IA42SgXa.net
>>452
お題
同じ数は4個まで

466:デフォルトの名無しさん
19/12/28 01:41:03.72 HU/ZZyYG.net
>>447のだと
for (j = N - 1; j >= 0; j--) {
これを
for (j = 0; j < N; j++) {
こう逆にすると重複の計算ができるんだね

467:デフォルトの名無しさん
19/12/28 03:25:23 HeaGj5a1.net
>>423

m≧n≧1 のとき
　ピン2に大円盤が1枚以下のときは、ピン0⇔ピン1間、ピン1⇔ピン3間で
　n枚組の円盤を移動できますね。 (3ピン手順)

　A: 1,2,････,x　のx個組　ただし x=f(m-1,n)
　B: x+1,...,x+n　のn個組
　C: x+n+1,････,x+2n+1 のn個組
　D: x+2n+1
とする。

468:デフォルトの名無しさん
19/12/28 03:28:09 HeaGj5a1.net
　ABCD, -, -, -
　B

469:CD, -, -, A 　　手順２　BC(2..n)D, -, C(1), A 　ABC(2..n)D, -, C(1), - 　ABC(2..n)D, -, -, C(1) 　BC(2..n)D, -, -, AC(1) 　　手順２　BC(3..n)D, -, C(2), AC(1) 　ABC(3..n)D, -, C(2), C(1) 　　手順３　ABC(3..n)D, -, -, C(1..2) 　････　同様にしてC(k)とDを移動する。(k=1..n) 　････　ABD, -, -, C 　BD, -, -, AC 　　手順２　B, -, D, AC 　AB, -, D, C 　　手順３　AB, -, -, CD 　B, -, -, ACD 　B(2..n), -, B(1), ACD 　AB(2..n), -, B(1), CD 　AB(2..n), -, -, B(1)CD 　B(2..n), -, -, AB(1)CD 　B(3..n), -, B(2), AB(1)CD 　AB(3..n), -, B(2), B(1)CD 　　手順３　AB(3..n), -, -, B(1..2)CD

470:デフォルトの名無しさん
19/12/28 03:34:05 HeaGj5a1.net
　B(3..n), -, -, AB(1..2)CD
　･････
　同様にしてB(k) を移動する。(k=1..n)
　･･････
　B(n), -, -, AB(1..n-1)CD
　-, -, B(n), AB(1..n-1)CD
　A, -, B(n), B(1..n-1)CD
　　手順３’
　A, -, -, BCD
　-, -, -, ABCD

∴　f(m,n) ≧ f(m-1,n) + 2n + 1,

・手順２
　BC(k..n)D, -, -, *
　C(k..n)D, B, -, *
　C(k+1..n)D, B, C(k), *
　BC(k+1..n)D, -, C(k), *　

・手順３
　*, -, C(k), C(1..k-1)
　*, C(1..k-1), C(k), -
　*, C(1..k-1), -, C(k)
　*, -, -, C(1..k)

・手順３’
　*, -, B(k), B(1..k-1)CD
　*, B(1..k-1), B(k), CD
　*, B(1..k-1), -, B(k)CD
　*, -, -, B(1..k)CD

471:デフォルトの名無しさん
19/12/28 12:49:55.64 eBmyBfXD.net
いつまでハノイのメモ帳続けるんだよｗ

472:デフォルトの名無しさん
19/12/28 16:57:29.50 hZH7LPev.net
>>453
本気でやるには、"もらう"へ作り変える必要もあり、辛い
4つ程度なら、4倍回して出しちゃうだろう。
　(四重ループで汚すぎるのでソースは非公開)
　4と6の結果のみ載せておこう、あっているかも微妙。
　
合計: 2020 使用個数: 20 複数制限: 4-->
15100329420197868
[2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7, 11, 11, 17, 1913]
[89, 89, 89, 97, 97, 97, 101, 101, 101, 101, 103, 103, 103, 103, 107, 107, 107, 107, 109, 109]
********************************************* 0.43922sec ********************
合計: 2020 使用個数: 20 複数制限: 6-->
16509239212753751
[2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 1951]
[97, 97, 97, 97, 97, 97, 101, 101, 101, 101, 101, 101, 103, 103, 103, 103, 103, 103, 107, 107]
********************************************* 0.30568sec ********************

473:デフォルトの名無しさん
19/12/28 19:46:33.82 mH66EenF.net
>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
URLﾘﾝｸ(ideone.com)
Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。
64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
URLﾘﾝｸ(ideone.com)

474:デフォルトの名無しさん
19/12/28 21:25:10.79 4BOt7DVD.net
>>453
>>447を使って書いた
URLﾘﾝｸ(ideone.com)
メモリの使用を抑えたのも書いたけど遅くなった

475:デフォルトの名無しさん
19/12/28 22:48:40.84 AtehPr/g.net
お題
最小値のあるインデックスから離れるほど数字が大きくなる数列があります
増加量はランダムです
その数列の中から効率よく最小値を探してください
入力: 115, 109, 107, 101, 92, 85, 76, 66, 65, 62, 53, 49, 40, 38, 35, 25, 23, 17, 9, 2, 0, 5, 8, 10, 11, 20, 30, 37, 42, 47
出力: 0
入力: 110, 104, 96, 93, 84, 83, 87, 93, 98, 103, 113, 120, 121, 128, 133, 134, 142, 152, 159, 169, 171, 174, 183, 186, 196, 203, 210, 212, 221, 224
出力: 83
入力: 138, 135, 127, 124, 122, 112, 103, 98, 92, 87, 77, 73, 71, 63, 59, 51, 41, 36, 45, 54, 63, 71, 81, 88, 90, 98, 105, 112, 114, 119
出力: 36

476:デフォルトの名無しさん
19/12/28 23:28:52.09 mH66EenF.net
>>462
二分探索で答えてもらいたいんだろ。
URLﾘﾝｸ(ideone.com)

477:デフォルトの名無しさん
19/12/28 23:34:06.76 AtehPr/g.net
>>463
私が用意してた答えは二分探索ではありませんでした�

478:ｪ二分探索でできるんですねすごいです

479:デフォルトの名無しさん
19/12/28 23:38:08.54 mH66EenF.net
>>463 訂正。signが抜けていた。
URLﾘﾝｸ(ideone.com)

480:デフォルトの名無しさん
19/12/28 23:42:14.62 mH66EenF.net
再度訂正。1行目が消えていた。
URLﾘﾝｸ(ideone.com)

481:デフォルトの名無しさん
19/12/28 23:45:03.69 4BOt7DVD.net
最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った

482:デフォルトの名無しさん
19/12/29 00:04:58.67 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)

483:デフォルトの名無しさん
19/12/29 00:15:11.87 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)

484:デフォルトの名無しさん
19/12/29 00:41:31.56 wJ/DeyFk.net
>>466 最小値が複数ある場合の条件分けが抜けていた。
URLﾘﾝｸ(ideone.com)
Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。

485:デフォルトの名無しさん
19/12/29 02:13:42.53 2ZGuf6bc.net
>>462
Java 三分探索で2/3に範囲を狭めてく
URLﾘﾝｸ(paiza.io)
1/2に減らせる二分探索には敵わない
傾きを二分探索するって発想はなかったわー

486:デフォルトの名無しさん
19/12/29 02:17:13.97 2ZGuf6bc.net
>>468
実装の効率はパないすね、効率はそういう意味でもありましたホントです

487:デフォルトの名無しさん
19/12/29 09:24:17.66 Y3W4ZjXN.net
いやいや
ただのリニア検索より遅いのはあり得ん

488:デフォルトの名無しさん
19/12/29 19:39:43.67 Jtzyjysr.net
でも出てる中で一番速いけど。

489:デフォルトの名無しさん
19/12/29 21:33:41.90 wJ/DeyFk.net
>>474
そりゃ、例の数列では要素数が少なくてアルゴリズムの差が出にくいからだろ。
「効率よく」とわざわざ書いてある問題なんだから、もっと大きなデータを与えた
場合も想定して答えるのが普通。
例えば、100万から1までの連番の後に2から50万までの連番が続く数列を与えれば
アルゴリズム間の違いは歴然。
Rで二分探索、min関数、sort関数で求めたときの1回あたり平均実行時間を計測すると、
0.132, 2.08, 55.2ミリ秒で桁が違う (PCでは二分探索はもう少し速かった)。
計算量オーダーがO(log n), O(n), O(n log n)だから当たり前だが。
URLﾘﾝｸ(ideone.com)
C++の >>468に同じデータを与えると108ミリ秒かかり、何とRのsort関数より遅い。
Rの関数はCで書かれているものが多いから、この差はつまりはCとC++のSTLの
性能差によるものだろう。
URLﾘﾝｸ(ideone.com)

490:デフォルトの名無しさん
19/12/29 21:37:04.80 Jtzyjysr.net
>>475
>>469の場合だとどんな感じ？

491:デフォルトの名無しさん
19/12/29 21:41:48.80 2ZGuf6bc.net
なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない

492:デフォルトの名無しさん
19/12/29 22:06:29.15 Y3W4ZjXN.net
>>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる
例としてはイマイチ

493:デフォルトの名無しさん
19/12/29 22:38:51.59 Byl7yBSZ.net
このスレだけマジで何言ってんのか理解できない
やっぱまずいよなあ、数学勉強し直さなきゃなあ

494:デフォルトの名無しさん
19/12/29 22:43:46.32 KptD7+e9.net
>>426
1)数百万規模でありそう。

495:デフォルトの名無しさん
19/12/30 08:49:27.55 1DW7Hzfm.net
>>475
最適化されたCとC++のSTLならCのほうが分があるということ？

496:デフォルトの名無しさん
19/12/30 09:13:40.00 W9rqQHA3.net
突き詰めた機械語にコンバートされるCと
汎用性のSTL
どちらに分があるのか

497:デフォルトの名無しさん
19/12/30 11:48:55.51 1DW7Hzfm.net
戦争になりそうだが、俺は膝にassertを受けちまってな
皆の力にはなれない、すまない

498:デフォルトの名無しさん
19/12/30 13:23:07.59 I3iMR+1

499:Y.net

500:デフォルトの名無しさん
19/12/30 15:32:52.11 fFRqMrLq.net
いいっすねー、新しいお題用意してるからちょっとまってて

501:デフォルトの名無しさん
19/12/30 15:44:13.04 fFRqMrLq.net
お題
四角形の縦の長さの数列と
四角形の横の長さの数列と
四角形の面積が与えられます
縦の長さと横の長さを組み合わせて
与えられた面積と一致する四角形をいくつ
作ることができるか求めてください
入力: 41, 9, 25, 92, 48, 15, 69, 61, 85, 22, 82, 79, 7, 34, 86, 29, 36, 77, 16, 79, 57, 8, 9, 58, 86, 0, 24, 83, 63, 46
入力: 12, 79, 11, 65, 9, 33, 44, 54, 30, 43, 76, 23, 24, 86, 15, 35, 21, 97, 57, 96, 6, 3, 59, 51, 29, 58, 93, 94, 49, 8
入力: 195?

502:デフォルトの名無しさん
19/12/30 15:45:24.75 fFRqMrLq.net
195の後ろの文字化けは無視してください
195と書きたかったのです

503:デフォルトの名無しさん
19/12/30 15:47:28.48 fFRqMrLq.net
入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです

504:デフォルトの名無しさん
19/12/30 16:18:52.49 pgNmBWor.net
四角形の縦の長さの定義は？
まさか四角形＝長方形じゃないでしょ

505:デフォルトの名無しさん
19/12/30 16:21:26.52 fFRqMrLq.net
>>489
ではそのまさかということで
四角形とは長方形のことです！

506:デフォルトの名無しさん
19/12/30 16:26:20.78 fFRqMrLq.net
問題を書いたときは長方形以外の四角形がこの世に存在するとは思いもよらなかったので四角形と書いたのです

507:デフォルトの名無しさん
19/12/30 18:39:14.57 JZjS6BbQ.net
オーダーは n log n
問題には
数列に同じ値が複数あった場合に1個とするのか別カウントするのかという曖昧性がある

508:デフォルトの名無しさん
19/12/30 18:41:24.69 fFRqMrLq.net
>>492
同じ値は別カウントで良いです

509:デフォルトの名無しさん
19/12/30 18:54:14.71 JZjS6BbQ.net
数列が整数限定
数列の数が大きい
面積が小さい
なら
素因数分解っていうアプローチもあるのかな？

510:デフォルトの名無しさん
19/12/30 19:25:46.59 fFRqMrLq.net
>>486
同じ値を別カウントにするとベラボーに難しいですね
同じ値は1個とカウントして良いです

511:デフォルトの名無しさん
19/12/30 19:25:50.71 2F+fuXCx.net
>>486
数万程度なら、Rで何の工夫もなしに素直に書いても瞬時に求められるな。
URLﾘﾝｸ(ideone.com)

512:デフォルトの名無しさん
19/12/30 19:28:13.92 fFRqMrLq.net
>>496
マジですか・・・すごいです

513:デフォルトの名無しさん
19/12/30 19:31:03.47 fFRqMrLq.net
>>462
そういえばこの問題って.NETのLINQとかJavaのStreamとか
使ってソートすればたぶんヒープが使われて逐次処理が行われるんで
全部の値をソートせずに答えが求められるんじゃないかと思った
ほぼ線形探索

514:デフォルトの名無しさん
19/12/30 19:34:34.59 2F+fuXCx.net
>>486
数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。

515:デフォルトの名無しさん
19/12/30 19:38:11.16 JZjS6BbQ.net
>>495
アルゴリズム的にはどっちもかわらん
特定の言語で記述しにくいってことはあるかもしれないけど

516:デフォルトの名無しさん
19/12/30 19:39:21.71 fFRqMrLq.net
>>500
マジですか・・・

517:デフォルトの名無しさん
19/12/30 20:14:35.59 2F+fuXCx.net
>>484
Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で
ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては
基数ソート、それ以外に対してはシェルソートが選択されると書かれている。
ということで、method引数を明示的に指定して実行時間を比較してみると、
基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが
何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。
RのクイックソートでもC++ STLのsortよりはまだ速い。URLﾘﾝｸ(ideone.com)
二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。
(キャッシュの影響があるのかも知れないが)。URLﾘﾝｸ(ideone.com)
Rの関数はCかFortranで書かれているものが多いが、binsearch関数はRで書かれているし、
戻り値のフラグ判定が文字列照合という非効率な処理だから、二分探索としては
あまり速くない。

518:デフォルトの名無しさん
19/12/30 20:30:55.63 0ybHI6rZ.net
>>492
重複なしなら
縦の数列をハッシュテーブルに入れる
横の数値に対して...
・0 ならスキップ
・面積を横の数値で割った余りが０でないならスキップ
・面積を横の数値で割った値がハッシュテーブルになければスキップ
・カウントアップ
を繰り返せばいいだけだからO(n)
（要するに >>496なんだけど）
重複ありで別カウントならハッシュテーブルの代わりにディクショナリにして値に個数を入れといてカウントアップ時に縦横の個数を掛けたものを加算すればいいだけ

519:デフォルトの名無しさん
19/12/30 20:46:19.63 JZjS6BbQ.net
ハッシュテーブルの検索はオーダー1じゃないと思うんだ

520:デフォルトの名無しさん
19/12/30 21:43:46.47 0ybHI6rZ.net
>>504
実装とかによるけど大抵の実装だとほぼO(1)だよ

521:デフォルトの名無しさん
19/12/30 22:39:47.32 JZjS6BbQ.net
ほぼ1ってなんだよwww
オーダー1の実装だと
値の範囲という別のオーダーが生まれる

522:デフォルトの名無しさん
19/12/30 22:44:20.79 fFRqMrLq.net
>>506
平均のことかと

523:デフォルトの名無しさん
19/12/30 22:53:03.82 JZjS6BbQ.net
ああ平均か
最悪値は非常に悪いよね

524:デフォルトの名無しさん
19/12/30 22:55:25.07 JZjS6BbQ.net
てっきり超巨大ハッシュテーブルを作るのかと思った

525:デフォルトの名無しさん
19/12/30 22:58:46.54 fFRqMrLq.net
たしかにハッシュテーブルの最悪の計算量はO(n)だけれども
そうなることってマレだよ
むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで
それ以上になると計算コストがバク上がりしてた
最近のライブラリだとテーブルサイズが可変になってるので問題ない
あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが
数年前に話題になったかな
ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと
ハッシュテーブル使うときはO(1)で考えて良いと思う

526:デフォルトの名無しさん
19/12/30 23:12:19.04 p3QJuMJ/.net
Ruby のハッシュでは、データ数と共に、バケット数を増やしていく。
バケット数は、2 の累乗の次に現れる素数。
2^n + a, 2 <= n <= 30
8 + 3 = 11
16 + 3 = 19
32 + 5 = 37
64 + 3 = 67
128 + 3 = 131
256 + 27 = 283
512 + 9 = 521
データ数が、バケット数の5倍を超えると、ハッシュが再構成される。
再構成時には、極端に遅くなる
11 * 5 = 55 だから、データ数が56 個になると、バケット数が19 になる。
19 * 5 = 95 だから、データ数が96 個になると、バケット数が37 になる

527:デフォルトの名無しさん
19/12/30 23:30:39.44 JZjS6BbQ.net
最近は結構インテリジェントに作られてるんだね
unordered_set/map もたまには使ってみようかな

528:デフォルトの名無しさん
19/12/31 07:26:10.17 kRQlhKMg.net
制約論理型言語だと変数の上限下限を自動的に切ってくれる。

529:デフォルトの名無しさん
19/12/31 09:03:13.10 hkax3Wzu.net
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)

530:デフォルトの名無しさん
19/12/31 10:24:38.95 NKLtpqnc.net
>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムで

531:O(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。

532:デフォルトの名無しさん
19/12/31 12:24:58.82 5aZymNkm.net
>>515
Rは整数が32ビットまでで桁あふれするから、Juliaで書く。
F = Int64[1 1; 1 0]
n = (F ^ 80)[1, 2]
P = Int64[1 0; 0 1]
R = F
while n > 0
　　global r = n % 2
　　global n = div(n, 2)
　　if r > 0
　　　　global P = P * R .% 100000000
　　end
　　global R = R * R .% 100000000
end
println(P[1, 2])
-- 実行結果 --
21055810

533:デフォルトの名無しさん
19/12/31 12:26:30.15 5aZymNkm.net
>>515じゃなくて >>514だった。

534:デフォルトの名無しさん
19/12/31 13:18:28.06 5aZymNkm.net
>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
URLﾘﾝｸ(ideone.com)

535:デフォルトの名無しさん
19/12/31 17:23:41.22 NKLtpqnc.net
>>514
>>516
515です。コード上げてなかった。
URLﾘﾝｸ(ideone.com)

536:513
19/12/31 18:46:25.67 H+c+1UtF.net
>>513
64ビットに収まるようにしたので簡単でしたかね
C++
URLﾘﾝｸ(ideone.com)

537:デフォルトの名無しさん
19/12/31 18:47:43.73 H+c+1UtF.net
>>514でした
すみません

538:デフォルトの名無しさん
19/12/31 19:45:18.11 5fWgt8Ro.net
>>449
URLﾘﾝｸ(ideone.com)
C++。問題勘違いして全探索かいたんだよ～。
おわらねー。Orz

539:デフォルトの名無しさん
19/12/31 20:25:50.73 W8YPZd1D.net
>>522
100億人に2020になる素数をプレゼント出来そうだ。

540:デフォルトの名無しさん
19/12/31 20:58:55.61 5fWgt8Ro.net
>>523
100億！！？？？マジで？？
そら手に余るわ。教えてくれてありがとう。
プレゼントするときは、「あなたに特別な2020を！」って感じか。

541:デフォルトの名無しさん
20/01/01 07:48:09.89 W9Zu1XGU.net
>>523
素数2個の2020は41人しかあげられない。

542:
20/01/01 12:10:34.36 WIYGoppO.net
あけおめ

543:デフォルトの名無しさん
20/01/01 12:56:41.11 WIYGoppO.net
お題
a^n + b^n + c^n = 2020
の整数解のうちnが最大の物を求めよ

544:
20/01/01 15:06:53.67 /JBKhr80.net
あけおめ～

545:デフォルトの名無しさん
20/01/01 15:29:53.46 qVK/11PV.net
A HAPPY NEW YEAR !!!
というコード。

546:デフォルトの名無しさん
20/01/02 04:45:53.28 cCzcmPOa.net
>>451

547:デフォルトの名無しさん
20/01/02 14:00:53.09 2eGsq/cP.net
(´；ω；｀)

548:デフォルトの名無しさん
20/01/03 03:43:04.42 ct9N0pK8.net
お題
a^3 + b^3 + c^3 = 2020 * 2
の整数解を求めよ。

549:デフォルトの名無しさん
20/01/03 03:49:51.76 ct9N0pK8.net
追加
a^3 + b^3 + c^3 = 2020 / 2･2
の整数解を求めよ。

550:デフォルトの名無しさん
20/01/03 03:54:35.20 pVliia9g.net
>>486
Kotlin
URLﾘﾝｸ(paiza.io)
こんなので良いの？単に掛け算して一致するか比較しているだけなんだけど。
オマケとして重複しないようにはしているが。

551:デフォルトの名無しさん
20/01/03 04:17:21.42 pVliia9g.net
>>532
C
URLﾘﾝｸ(paiza.io)
どう?

552:デフォルトの名無しさん
20/01/03 04:18:44.02 pVliia9g.net
>>533
最後の 2･2 の部分って何? 2.2? こっちで文字化けしてちゃんと表示されてないだけ?

553:デフォルトの名無しさん
20/01/03 09:45:42.54 +RiBlMC+.net
>>536
2020 / 2･2 = 2020 / 2 * 2 = 2020

554:デフォルトの名無しさん
20/01/03 12:48:37.25 3k7MKqlh.net
>>532
200万以下だと38通り
(並び替えも数えるとその6倍)
>>533
2020は解無し
1010は100万までには解は無い
505は100万までに18個

555:デフォルトの名無しさん
20/01/03 12:51:02.88 3k7MKqlh.net
>>527
n乗して64bitの範囲だとn=2しか発見出来なかった

556:デフォルトの名無しさん
20/01/03 20:05:33.33 3k7MKqlh.net
>>532
C
URLﾘﾝｸ(ideone.com)
38個見つけるのに1時間くらいかかりました
38個目 (1661082, 440694, -1671358)
こういうのはC/C++が得意でしょう
他の言語で出来ます？ (挑戦)

557:デフォルトの名無しさん
20/01/04 17:22:50.50 HJ66bOYq.net
お題
 >>514に関連して、F(F(80))の桁数を求めよ。
計算式は簡単だが…

558:デフォルトの名無しさん
20/01/04 17:47:47.60 6lKY6ugm.net
over　flow周りはあってるんだかわからん
URLﾘﾝｸ(i.imgur.com)

559:デフォルトの名無しさん
20/01/04 19:01:02.66 hAlxX0tq.net
Mathematica ?

560:デフォルトの名無しさん
20/01/04 20:28:18.17 rMjoeVI8.net
お題: 文字列を逆順にしてコピーするreverse関数を定義せよ（既存のライブラリを使ってはならない）

561:デフォルトの名無しさん
20/01/04 20:40:17.01 YRTK1M0u.net
>>544 Ruby
puts 'ABCDEF'.chars.then{|a| a.size.times.map{a.pop}}.join
# => FEDCBA

562:デフォルトの名無しさん
20/01/04 20:46:16.21 HJ66bOYq.net
>>544　PowerShell
function reverse($s) {-join $s[-1..-$s.length]}
reverse 文字列を逆順にしてコピーするreverse関数を定義せよ
-- 実行結果 --
よせ義定を数関esreverるすーピコてしに順逆を列字文

563:デフォルトの名無しさん
20/01/04 21:12:58.70 AqMdau2S.net
>>544 Ruby
def reverse( s ); s.chars.inject(:prepend); end

564:デフォルトの名無しさん
20/01/04 21:13:39.03 rMjoeVI8.net
>>544 C
URLﾘﾝｸ(ideone.com)

565:デフォルトの名無しさん
20/01/04 21:26:02.66 e7dEja3I.net
>>544
Java
URLﾘﾝｸ(paiza.io)

566:デフォルトの名無しさん
20/01/05 00:51:01.04 Y4p4/H36.net
>>544
Kotlin
URLﾘﾝｸ(paiza.io)
Kotlin の String には reversed() という文字列順序逆転のための拡張関数が最初からあって紛らわしいので rev() という名前で自作した。

567:デフォルトの名無しさん
20/01/05 08:25:52.70 h+ccWvVu.net
>>532
　{a, b, c} = {-12, -4, 18}　{-4, 2, 16}　など
 >>533
　{a, b, c} = {-6, -2, 9}　{-2, 1, 8}　など

568:デフォルトの名無しさん
20/01/05 08:35:04.57 OU8kozEP.net
>>544 Ruby
def rev(s)
(1..s.size).map{|i|s[-i]}.join
end

569:デフォルトの名無しさん
20/01/05 11:04:36.67 Z8HxF2cT.net
>>544 Common Lisp
URLﾘﾝｸ(ideone.com)
URLﾘﾝｸ(ideone.com)

570:デフォルトの名無しさん
20/01/05 15:25:24.03 +tGOF19X.net
>>544 Python
def reverse(s):
return s[::-1]

571:デフォルトの名無しさん
20/01/05 16:01:41.83 8nvrboOv.net
>>540
こういうのを見ると我々は離散数学についてはほぼ無力と思う。

572:デフォルトの名無しさん
20/01/05 17:02:46.74 x729cdax.net
>>555
勉強しとけ

573:デフォルトの名無しさん
20/01/05 21:49:56.17 2Fq0AHrI.net
>>544　R
URLﾘﾝｸ(ideone.com)
>>546のPowerShellと違って、U+10000以上の文字が含まれていても正しく逆順にできる。

574:デフォルトの名無しさん
20/01/05 21:52:10.17 2Fq0AHrI.net
>>542
仮数部も指数部も間違っている。整数で1の位まで正確に求められるよ。

575:デフォルトの名無しさん
20/01/05 22:31:31.58 h+ccWvVu.net
>>540　ｻﾝｸｽ
 >>532 の解
{13, 11, 8}
{15, 9, -4}
{8, 1, -2} * 2
{9, -2, -6} * 2
{16, -6, -15} * 2
{74, -23, -73}
{43, -27, -39} * 2
{171, -75, -166}
{169, 64, -172} * 2
{516, 93, -517}
{414, 385, -504} * 2
{530, 337, -572}
{1098, 939, -1291}
{1290, 171, -1291}
{1626, -957, -1507}
{2251, -712, -2227}
{3107, -587, -3100}
{3299, 1018, -3331}
{3509, -2525, -3004}
{4022, -3163, -3221}
{2673, 1114, -2736} * 2
{13571, -9259, -11948}
{15291, -8419, -14388}
{10102, 674, -10103} * 2
{43943, 28524, -47631}
{23689, -3382, -23666} * 2　など。

576:デフォルトの名無しさん
20/01/05 22:41:01.23 h+ccWvVu.net
>>533 の解
{8, 1, -2}
{9, -2, -6}
{16, -6, -15}
{43, -27, -39}
{169, 64, -172}
{414, 385, -504}
{530, 337, -572}
{2673, 1114, -2736}
{10102, 674, -10103}
{23689, -3382, -23666}
　･･･　･･･
{830541, 220347, -835679}　など。

577:デフォルトの名無しさん
20/01/05 22:48:30.69 bLPoA6E7.net
>>541
C++
URLﾘﾝｸ(ideone.com.VJk9QA)
倍精度だと微妙に精度が足りないので
擬似4倍精度で計算してみた
4倍精度や多倍長が使える言語やライブラリを使えば一瞬で書けるんだけど

578:デフォルトの名無しさん
20/01/05 22:49:34.33 bLPoA6E7.net
↑
URLﾘﾝｸ(ideone.com)
でした

579:デフォルトの名無しさん
20/01/05 23:29:51.01 2Fq0AHrI.net
>>562
正解。
Rには多倍長浮動小数点パッケージRmpfrがあるので、120ビット精度での計算をさっと書ける。
多倍長整数パッケージgmpにはフィボナッチ数列の第n項を求める関数があるので、第80項を
自分で求める必要すらない。
URLﾘﾝｸ(ideone.com)
C/C++にもlong double型があるので楽勝!と思っていると罠に嵌まる。Visual C++では
long doubleは移植性（単にコンパイルが通るという意味で）のために定義されているだけで、
double精度しかないので使えない。GNU C++ではlong doubleが本当のlong doubleなので使える。
URLﾘﾝｸ(ideone.com)
これをVisual C++やGNU Cで実行すると、1の位が2大きい不正確な値が表示されてしまう。
URLﾘﾝｸ(ideone.com)

580:デフォルトの名無しさん
20/01/05 23:41:09.00 2Fq0AHrI.net
GNU C++にも罠があって、URLﾘﾝｸ(ideone.com) はideoneでは結果が正しく
表示されているが、Windows版でコンパイルすると「-0桁」になってしまう。
printfの%Lf書式指定子が何故か正常に機能しないようなので、long longに変換して
%lld書式指定子を使う必要がある。

581:デフォルトの名無しさん
20/01/05 23:58:45.24 Z3Lsb/Mg.net
>>562は擬似4倍精度の四則演算やルートがコンパクトにまとまっており参考になるかと思います
logは手抜きですが

582:デフォルトの名無しさん
20/01/06 00:24:13.90 MKFPBGLf.net
x87の80bit形式久々に聞いた
intelの失敗仕様
本当のlong doubleって言ったら128bitの事だと思う

583:デフォルトの名無しさん
20/01/07 12:16:08 lAASQTDH.net
本当の？

584:デフォルトの名無しさん
20/01/07 13:02:38.21 PuPIfAOU.net
大きさと精度が一致しないということでは。
例えば、16ビット整数の加算において255+1で桁あふれが発生するのは、勘弁してほしい。
16ビット整数であれば精度も16ビットあってほしい。

585:デフォルトの名無しさん
20/01/07 13:13:00.08 4oL1Xwrc.net
intelの拡張小数は箱も中身も80bitだぞ
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど

586:デフォルトの名無しさん
20/01/07 13:43:12.96 PuPIfAOU.net
GCCのlong doubleは128ビットあるから。

587:デフォルトの名無しさん
20/01/07 22:24:41.07 Y9qs9jpB.net
ひさびさにx87命令を使ってみた
masm形式なのでideoneでは動作しませんが
URLﾘﾝｸ(ideone.com)

588:デフォルトの名無しさん
20/01/07 22:38:44.27 Y9qs9jpB.net
↑の出力結果
4893806799921043 (4893806799921042 + 0.855469)
丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ
2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります

589:デフォルトの名無しさん
20/01/07 23:09:32 Y9qs9jpB.net
URLﾘﾝｸ(pc.watch.impress.co.jp)

590:デフォルトの名無しさん
20/01/08 17:55:41.24 E2HYW9Z+.net
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)

591:デフォルトの名無しさん
20/01/08 18:47:53.52 bVQLyL/p.net
フィフィフィボナッチ数列はお腹いっぱい

592:
20/01/08 19:48:23.85 npJkZznC.net
>>571
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！

593:デフォルトの名無しさん
20/01/08 20:00:11.84 naqRCa+g.net
お前は昭和何年からタイムスリップしてきたんだ

594:デフォルトの名無しさん
20/01/08 20:33:31.36 DEoUiUkq.net
>>574
R
URLﾘﾝｸ(ideone.com)

595:デフォルトの名無しさん
20/01/08 21:16:17.44 E2HYW9Z+.net
正解
C++
URLﾘﾝｸ(ideone.com)

596:デフォルトの名無しさん
20/01/08 23:38:33.13 3Vg9kR1l.net
>>544 Perl5
use feature qw{say signatures};
sub reverse($s) {
　map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');

597:デフォルトの名無しさん
20/01/10 10:41:25.62 lJ/gG0sx.net
お題：自分用expm1()的なもの。底はe以外でも良い。不正な引数でのエラー処理は
考慮しなくても良い。

598:デフォルトの名無しさん
20/01/10 13:20:18.79 KXQq2+DU.net
目的が高精度なのかSIMDなのか単に出題者が勉強したいだけなのか
もしかしてx87命令を使わせたい？

599:デフォルトの名無しさん
20/01/10 20:53:23.97 1usNcOvE.net
>>581
expm1()って何？

600:デフォルトの名無しさん
20/01/10 21:01:53.36 jjOShzcG.net
エキスペディション・マグニチュードワンのことやろな

601:581
20/01/10 22:06:13.03 lJ/gG0sx.net
>>582
SIMDやx87命令は考えてませんでした。
四則演算とexpm1()以外のライブラリ関数は使用可って事で。
やっぱし無難にテイラー展開で求めるのが楽？
>>583
例えば
URLﾘﾝｸ(linuxjm.osdn.jp)

602:デフォルトの名無しさん
20/01/10 22:10:45.27 lApN4p1F.net
四則演算も使ったらダメなのかい

603:581
20/01/10 22:42:31.47 lJ/gG0sx.net
>>586
訂正：
四則演算と、「expm1()以外の」ライブラリ関数は使用可

604:デフォルトの名無しさん
20/01/11 06:32:12.11 wIXPHQcF.net
出題者が方法を知りたいだけだよね？
なら質問スレ/宿題スレの方が適切

605:デフォルトの名無しさん
20/01/11 09:22:26.15 R1f0qLP3.net
お題
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。

606:デフォルトの名無しさん
20/01/11 10:27:02.77 LQrvWU7L.net
>>589 Ruby 2.7.0
require 'Prime'
p Prime.take(100).then{|p| Prime.take(p.last).select.with_index{p.include?(-~_2)}}
# => [3, 5, 7, [中略], 3761, 3911]

次ページ