プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part15
http://mevius.5ch.net/test/read.cgi/tech/1564310397/
プログラミングのお題スレ Part16
■ このスレッドは過去ログ倉庫に格納されています
2019/11/17(日) 09:00:22.10ID:xqEdXdr6
569デフォルトの名無しさん
2020/01/07(火) 13:13:00.08ID:4oL1Xwrc intelの拡張小数は箱も中身も80bitだぞ
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど
570デフォルトの名無しさん
2020/01/07(火) 13:43:12.96ID:PuPIfAOU GCCのlong doubleは128ビットあるから。
571デフォルトの名無しさん
2020/01/07(火) 22:24:41.07ID:Y9qs9jpB572デフォルトの名無しさん
2020/01/07(火) 22:38:44.27ID:Y9qs9jpB ↑の出力結果
4893806799921043 (4893806799921042 + 0.855469)
丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ
2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります
4893806799921043 (4893806799921042 + 0.855469)
丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ
2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります
573デフォルトの名無しさん
2020/01/07(火) 23:09:32.62ID:Y9qs9jpB574デフォルトの名無しさん
2020/01/08(水) 17:55:41.24ID:E2HYW9Z+ お題
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
575デフォルトの名無しさん
2020/01/08(水) 18:47:53.52ID:bVQLyL/p フィフィフィボナッチ数列はお腹いっぱい
>>571
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！
577デフォルトの名無しさん
2020/01/08(水) 20:00:11.84ID:naqRCa+g お前は昭和何年からタイムスリップしてきたんだ
578デフォルトの名無しさん
2020/01/08(水) 20:33:31.36ID:DEoUiUkq579デフォルトの名無しさん
2020/01/08(水) 21:16:17.44ID:E2HYW9Z+580デフォルトの名無しさん
2020/01/08(水) 23:38:33.13ID:3Vg9kR1l >>544 Perl5
use feature qw{say signatures};
sub reverse($s) {
map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');
use feature qw{say signatures};
sub reverse($s) {
map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');
581デフォルトの名無しさん
2020/01/10(金) 10:41:25.62ID:lJ/gG0sx お題：自分用expm1()的なもの。底はe以外でも良い。不正な引数でのエラー処理は
考慮しなくても良い。
考慮しなくても良い。
582デフォルトの名無しさん
2020/01/10(金) 13:20:18.79ID:KXQq2+DU 目的が高精度なのかSIMDなのか単に出題者が勉強したいだけなのか
もしかしてx87命令を使わせたい？
もしかしてx87命令を使わせたい？
583デフォルトの名無しさん
2020/01/10(金) 20:53:23.97ID:1usNcOvE >>581
expm1()って何？
expm1()って何？
584デフォルトの名無しさん
2020/01/10(金) 21:01:53.36ID:jjOShzcG エキスペディション・マグニチュードワンのことやろな
585581
2020/01/10(金) 22:06:13.03ID:lJ/gG0sx586デフォルトの名無しさん
2020/01/10(金) 22:10:45.27ID:lApN4p1F 四則演算も使ったらダメなのかい
588デフォルトの名無しさん
2020/01/11(土) 06:32:12.11ID:wIXPHQcF 出題者が方法を知りたいだけだよね？
なら質問スレ/宿題スレの方が適切
なら質問スレ/宿題スレの方が適切
589デフォルトの名無しさん
2020/01/11(土) 09:22:26.15ID:R1f0qLP3 お題
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。
590デフォルトの名無しさん
2020/01/11(土) 10:27:02.77ID:LQrvWU7L >>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]
require 'Prime'
p Prime.take(100).then{|p| Prime.take(p.last).select.with_index{p.include?(-~_2)}}
# => [3, 5, 7, [中略], 3761, 3911]
591デフォルトの名無しさん
2020/01/11(土) 10:31:32.27ID:LQrvWU7L typo
# => [3, 5, 11, 17, 31, [中略], 3733, 3761, 3911]
# => [3, 5, 11, 17, 31, [中略], 3733, 3761, 3911]
592デフォルトの名無しさん
2020/01/11(土) 10:52:09.93ID:VG9fEjGe お題
5の倍数の素数を5の倍数素数という
5の倍数素数を全て求めよ
5の倍数の素数を5の倍数素数という
5の倍数素数を全て求めよ
593デフォルトの名無しさん
2020/01/11(土) 11:10:43.29ID:V+Dyph4l 5の倍数の素数ってどういうことですか？
文字通りの意味なら5だけだと思うんですけど
文字通りの意味なら5だけだと思うんですけど
594デフォルトの名無しさん
2020/01/11(土) 13:10:43.10ID:JM9/51Sk >>544 Perl4
use feature qw{say signatures};
sub rev($s) {
$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string');
てす
use feature qw{say signatures};
sub rev($s) {
$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string');
てす
595デフォルトの名無しさん
2020/01/11(土) 13:14:26.71ID:JM9/51Sk >>594 Perl5 だった…orz
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…
596デフォルトの名無しさん
2020/01/11(土) 14:01:21.01ID:M68szGrA >>592
echo 5
echo 5
597デフォルトの名無しさん
2020/01/11(土) 20:08:39.02ID:go77StkR お題
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。
598デフォルトの名無しさん
2020/01/11(土) 20:55:04.41ID:r5wulSj/ ナベアツ理論か。
599デフォルトの名無しさん
2020/01/12(日) 00:39:46.42ID:PW2KE/yt >>595
書き込めないコマンドは、一杯ある。
「ｌｓ −ｌ」とか
5ch は、特定の命令によって、表示の見た目を変えることができるから、
単に、表示する文字列に変換するだけじゃなくて、
投稿されたテキストから、命令を抽出したりしているから、
バグりそうなテキストを排除しているのだろう
書き込めないコマンドは、一杯ある。
「ｌｓ −ｌ」とか
5ch は、特定の命令によって、表示の見た目を変えることができるから、
単に、表示する文字列に変換するだけじゃなくて、
投稿されたテキストから、命令を抽出したりしているから、
バグりそうなテキストを排除しているのだろう
600デフォルトの名無しさん
2020/01/12(日) 10:30:24.93ID:Cuf7XVQy601デフォルトの名無しさん
2020/01/12(日) 16:28:53.41ID:Svv4a/Ag お題: バイナリ―サーチを実装せよ（自分の記憶だけで書かなければならない）
602デフォルトの名無しさん
2020/01/12(日) 16:52:57.01ID:qRMFtMw7603デフォルトの名無しさん
2020/01/12(日) 17:33:54.06ID:kqg5PnqA >>601 Ruby
def bs(ary, &cond)
return ary[0] && cond.call(ary[0]) ? ary[0] : ary[1] && cond.call(ary[1]) ? ary[1] : nil if ary.size < 3
mid = ary.size / 2
bs(ary[cond.call(ary[mid]) ? 0..mid : mid + 1..-1], &cond)
end
p bs([1,3,5,7,9]){|i| i > 0} # => 1
p bs([1,3,5,7,9]){|i| i > 3} # => 5
p bs([1,3,5,7,9]){|i| i > 9} # => nil
def bs(ary, &cond)
return ary[0] && cond.call(ary[0]) ? ary[0] : ary[1] && cond.call(ary[1]) ? ary[1] : nil if ary.size < 3
mid = ary.size / 2
bs(ary[cond.call(ary[mid]) ? 0..mid : mid + 1..-1], &cond)
end
p bs([1,3,5,7,9]){|i| i > 0} # => 1
p bs([1,3,5,7,9]){|i| i > 3} # => 5
p bs([1,3,5,7,9]){|i| i > 9} # => nil
>>601
C++
https://mevius.5ch.net/test/read.cgi/tech/1434079972/33
std::set<int> の再実装にて、内部にバイナリーサーチを含んでいます
C++
https://mevius.5ch.net/test/read.cgi/tech/1434079972/33
std::set<int> の再実装にて、内部にバイナリーサーチを含んでいます
>>601
＞（自分の記憶だけで書かなければならない）
これは重要かつ役に立つ訓練のしかたですね、この前は pthread の mutex と cond が理解できているかどうかを、この縛りのもとにコードを書いて試みました
＞（自分の記憶だけで書かなければならない）
これは重要かつ役に立つ訓練のしかたですね、この前は pthread の mutex と cond が理解できているかどうかを、この縛りのもとにコードを書いて試みました
606デフォルトの名無しさん
2020/01/12(日) 18:20:53.87ID:Xff8C4Cf >（自分の記憶だけで書かなければならない）
お題は全てそういうものだと思ってたが
みんなカンニングして回答してるの？
お題は全てそういうものだと思ってたが
みんなカンニングして回答してるの？
607デフォルトの名無しさん
2020/01/12(日) 19:59:45.88ID:qRMFtMw7 お題1
10ビットの乱数を10個作成して
2進数に変換して出力してください
10ビットに満たない数は0埋めしてください
例)
1101101110
1000100011
0100111001
1110000001
1001001100
0010001111
1111001000
1010110111
1100001001
0100110111
お題2
縦方向、または、横方向に1が連続しているところを調べて
最も1が連続しているところの1の数を出力してください
ビット数や乱数の数が増えてもちょっぱやで処理できるとなお良いです
10ビットの乱数を10個作成して
2進数に変換して出力してください
10ビットに満たない数は0埋めしてください
例)
1101101110
1000100011
0100111001
1110000001
1001001100
0010001111
1111001000
1010110111
1100001001
0100110111
お題2
縦方向、または、横方向に1が連続しているところを調べて
最も1が連続しているところの1の数を出力してください
ビット数や乱数の数が増えてもちょっぱやで処理できるとなお良いです
608デフォルトの名無しさん
2020/01/12(日) 20:38:11.83ID:xWFTg64o >>600
正解。あなたには簡単すぎただろうが。
Rで書いた解答例はPCでは2秒台で実行できたのに、ideoneでは制限時間5秒以内に
終わらなかったので、C++で書いた方を貼る。https://ideone.com/DFDdtr
>>600とほぼ同じだが、掛け算が減る分だけ速いな。
正解。あなたには簡単すぎただろうが。
Rで書いた解答例はPCでは2秒台で実行できたのに、ideoneでは制限時間5秒以内に
終わらなかったので、C++で書いた方を貼る。https://ideone.com/DFDdtr
>>600とほぼ同じだが、掛け算が減る分だけ速いな。
609デフォルトの名無しさん
2020/01/12(日) 21:27:08.47ID:xWFTg64o610デフォルトの名無しさん
2020/01/12(日) 21:44:57.86ID:qRMFtMw7 >>609
ありがとうございます、そして申し訳ないです
11
11
こうなってたら4と出力してほしくて
連続じゃないですね、隣接といえばよかったかもしれません
縦方向、横方向に1が隣接してる領域のうち最大の領域の1の数を出力して欲しいのです
ありがとうございます、そして申し訳ないです
11
11
こうなってたら4と出力してほしくて
連続じゃないですね、隣接といえばよかったかもしれません
縦方向、横方向に1が隣接してる領域のうち最大の領域の1の数を出力して欲しいのです
611デフォルトの名無しさん
2020/01/12(日) 21:45:02.91ID:xWFTg64o612デフォルトの名無しさん
2020/01/12(日) 21:48:51.97ID:qRMFtMw7 すみません・・・平にご容赦いただきたく
613デフォルトの名無しさん
2020/01/12(日) 21:48:57.49ID:xWFTg64o614デフォルトの名無しさん
2020/01/12(日) 21:52:58.77ID:qRMFtMw7 >>613
矩形じゃなくていいです8個パターンです！
矩形じゃなくていいです8個パターンです！
615デフォルトの名無しさん
2020/01/13(月) 04:22:53.20ID:5GjUS2iX 質問なら質問スレに
宿題なら宿題スレに
回答を用意してない出題は禁止
宿題なら宿題スレに
回答を用意してない出題は禁止
616デフォルトの名無しさん
2020/01/13(月) 04:47:28.11ID:5GjUS2iX 昔ながらのPAINTアルゴリズム
検索すれば色々と出てくるよ
検索すれば色々と出てくるよ
617デフォルトの名無しさん
2020/01/13(月) 05:51:52.90ID:9cAJpR6a >>589 J
smoutput 10 10 $ p: <: p: i.100
実行結果
3 5 11 17 31 41 59 67 83 109
127 157 179 191 211 241 277 283 331 353
367 401 431 461 509 547 563 587 599 617
709 739 773 797 859 877 919 967 991 1031
1063 1087 1153 1171 1201 1217 1297 1409 1433 1447
1471 1499 1523 1597 1621 1669 1723 1741 1787 1823
1847 1913 2027 2063 2081 2099 2221 2269 2341 2351
2381 2417 2477 2549 2609 2647 2683 2719 2749 2803
2897 2909 3001 3019 3067 3109 3169 3229 3259 3299
3319 3407 3469 3517 3559 3593 3637 3733 3761 3911
smoutput 10 10 $ p: <: p: i.100
実行結果
3 5 11 17 31 41 59 67 83 109
127 157 179 191 211 241 277 283 331 353
367 401 431 461 509 547 563 587 599 617
709 739 773 797 859 877 919 967 991 1031
1063 1087 1153 1171 1201 1217 1297 1409 1433 1447
1471 1499 1523 1597 1621 1669 1723 1741 1787 1823
1847 1913 2027 2063 2081 2099 2221 2269 2341 2351
2381 2417 2477 2549 2609 2647 2683 2719 2749 2803
2897 2909 3001 3019 3067 3109 3169 3229 3259 3299
3319 3407 3469 3517 3559 3593 3637 3733 3761 3911
618デフォルトの名無しさん
2020/01/13(月) 09:11:38.57ID:a0NWv3WS >>607はAOJにあった島の数の問題じゃないの
そうじゃなくてもぷよぷよは大抵コレでしょ
そうじゃなくてもぷよぷよは大抵コレでしょ
619デフォルトの名無しさん
2020/01/13(月) 12:20:35.97ID:AM9JqLhx620デフォルトの名無しさん
2020/01/13(月) 14:02:08.92ID:7B3b+WrT621デフォルトの名無しさん
2020/01/13(月) 18:55:55.99ID:7n+Qr/32 >>566
>>569
8087は、第3の実数フォーマット、一時実数を許している点でユニークである。
このフォーマットは、(符号が1ビット)、指数が15ビットで、有効数字が64ビットである。
このフォーマットで格納されている数値は、拡張精度数と言われている。
単精度および倍精度実数と異なり、一時実数は入力および出力値を表わすことを意図していない。
････(中略)･････
それでは、何故80ビットではなく4倍精度すなわち128ビットを一時実数に使わなかったのか。
1つの理由は、4倍精度は少なくとも性能(速度)が半分になることである。
他の理由は、4倍精度を基本フォーマットとして用いると、中間結果のためにより長いフォーマットが必要となることである。
(後略)
・出典
J.F.パーマー・S.P.モース(著)「8087入門」啓学出版 (1985/Feb) 御牧 義 (訳) 2900円
第2章 データフォーマット、p.19-20
>>569
8087は、第3の実数フォーマット、一時実数を許している点でユニークである。
このフォーマットは、(符号が1ビット)、指数が15ビットで、有効数字が64ビットである。
このフォーマットで格納されている数値は、拡張精度数と言われている。
単精度および倍精度実数と異なり、一時実数は入力および出力値を表わすことを意図していない。
････(中略)･････
それでは、何故80ビットではなく4倍精度すなわち128ビットを一時実数に使わなかったのか。
1つの理由は、4倍精度は少なくとも性能(速度)が半分になることである。
他の理由は、4倍精度を基本フォーマットとして用いると、中間結果のためにより長いフォーマットが必要となることである。
(後略)
・出典
J.F.パーマー・S.P.モース(著)「8087入門」啓学出版 (1985/Feb) 御牧 義 (訳) 2900円
第2章 データフォーマット、p.19-20
622デフォルトの名無しさん
2020/01/13(月) 19:02:27.52ID:7n+Qr/32 John F. Palmer, Ph.D. は8087の設計者、
Stephen P. Morse, Ph.D. は8086の設計者だそうな。
Stephen P. Morse, Ph.D. は8086の設計者だそうな。
623デフォルトの名無しさん
2020/01/13(月) 19:38:23.04ID:cBNIohlK x87で遊んでた頃は
将来は4倍精度とか8倍精度とかが当たり前になると思ってたけど
まさか単精度や半精度の時代になるとは
将来は4倍精度とか8倍精度とかが当たり前になると思ってたけど
まさか単精度や半精度の時代になるとは
624デフォルトの名無しさん
2020/01/14(火) 21:06:38.50ID:vjAz2zAO625デフォルトの名無しさん
2020/01/14(火) 21:13:25.69ID:vjAz2zAO 20命令で4個のdoubleのexpm1の計算が出来ます
8パラにしてレイテンシを隠蔽すれば
1個あたり2.5クロックくらい
8パラにしてレイテンシを隠蔽すれば
1個あたり2.5クロックくらい
626デフォルトの名無しさん
2020/01/15(水) 12:05:09.83ID:z1LU+PP1 将来、行列演算もFPU化されると、逆行列の桁落ちが問題になるだろうな････
それを見越して、入出力は64bitのまま内部演算だけ80bitにしたんぢゃね？
それを見越して、入出力は64bitのまま内部演算だけ80bitにしたんぢゃね？
627デフォルトの名無しさん
2020/01/15(水) 13:12:03.91ID:BnAK3ul/ 思想がどんなに優れてても使われなきゃしょうがない
レジスタが8個しか無いから内部だけ80bitでもほとんど精度改善にならないし
メモリに80bit保存するのも使いにくい
互換性の問題もあって
コンパイラや最適化で値がかわってしまうのも都合が悪い
だから演算にx87命令を使ったとしても内部64bit精度がデフォ
x87全盛期に作られたSuperPIも64bit精度の演算を使ってる
80bit精度で計算すれば速度アップ出来るにも関わらず
レジスタが8個しか無いから内部だけ80bitでもほとんど精度改善にならないし
メモリに80bit保存するのも使いにくい
互換性の問題もあって
コンパイラや最適化で値がかわってしまうのも都合が悪い
だから演算にx87命令を使ったとしても内部64bit精度がデフォ
x87全盛期に作られたSuperPIも64bit精度の演算を使ってる
80bit精度で計算すれば速度アップ出来るにも関わらず
628デフォルトの名無しさん
2020/01/15(水) 17:38:16.89ID:xp2qVCg5629デフォルトの名無しさん
2020/01/15(水) 21:04:20.76ID:/kpg6gtq お題:
9つの物がある。
重さが20以下で価値の合計が最大になる組み合わせを求めなさい。
(Part7から再出)
[重さ, 価値]
[
[3, 5],
[5, 6],
[6, 3],
[3, 5],
[5, 9],
[2, 1],
[7, 5],
[4, 6],
[8, 3],
]
9つの物がある。
重さが20以下で価値の合計が最大になる組み合わせを求めなさい。
(Part7から再出)
[重さ, 価値]
[
[3, 5],
[5, 6],
[6, 3],
[3, 5],
[5, 9],
[2, 1],
[7, 5],
[4, 6],
[8, 3],
]
630デフォルトの名無しさん
2020/01/15(水) 21:18:06.99ID:1ZW9vAE3 ナップサック問題か
631デフォルトの名無しさん
2020/01/15(水) 21:27:46.82ID:woCrNz65 重さ < 価値
となる物を集めると丁度重さが20だから
これが解
となる物を集めると丁度重さが20だから
これが解
632デフォルトの名無しさん
2020/01/16(木) 21:02:25.92ID:ZS18thyn 【お題】以下の31個の数の下6桁を求めよ。
20200101の1, 2, 3, ..., 20200101乗の総和
20200102の1, 2, 3, ..., 20200102乗の総和
20200103の1, 2, 3, ..., 20200103乗の総和
:
20200131の1, 2, 3, ..., 20200131乗の総和
20200101の1, 2, 3, ..., 20200101乗の総和
20200102の1, 2, 3, ..., 20200102乗の総和
20200103の1, 2, 3, ..., 20200103乗の総和
:
20200131の1, 2, 3, ..., 20200131乗の総和
633デフォルトの名無しさん
2020/01/17(金) 06:54:23.06ID:bFwt3c1k634デフォルトの名無しさん
2020/01/17(金) 12:14:19.25ID:onsz9c/m >>629
16, 7: 0 0 1 0 0 1 0 0 1
17, 9: 0 0 0 0 0 1 1 0 1
18, 26: 1 1 0 1 1 1 0 0 0
19, 27: 1 1 0 0 1 1 0 1 0
20, 31: 1 1 0 1 1 0 0 1 0
16, 7: 0 0 1 0 0 1 0 0 1
17, 9: 0 0 0 0 0 1 1 0 1
18, 26: 1 1 0 1 1 1 0 0 0
19, 27: 1 1 0 0 1 1 0 1 0
20, 31: 1 1 0 1 1 0 0 1 0
635デフォルトの名無しさん
2020/01/17(金) 18:26:22.50ID:KcAYJrW8636デフォルトの名無しさん
2020/01/17(金) 20:33:32.20ID:VgNyCBhj >>635
正解。
Rによる2種類の解答例
(1) https://ideone.com/7B7IhY
(2) https://ideone.com/Y8jx8o
(1)は等比数列の総和の公式を利用しているので分かりやすいが、途中計算の最大値が
(20200130 * 1000000 - 1) ^ 2 ≒ 2 ^ 88.4 になるかも知れず、64ビット整数の
範囲に収まらないため、Cでは手軽に書けない。Rでは多倍長整数パッケージgmpを
使って書ける。
(2)は部分和をちまちま足していく方式で、途中計算の最大値が (1000000 - 1) ^ 2
≒ 2 ^ 39.9 で済むため、Cでも64ビット整数で計算できる。Rでも多倍長計算が必要な
(1)より速い (正味の実行時間が(1)は0.016秒、(2)は0.004秒)。
正解。
Rによる2種類の解答例
(1) https://ideone.com/7B7IhY
(2) https://ideone.com/Y8jx8o
(1)は等比数列の総和の公式を利用しているので分かりやすいが、途中計算の最大値が
(20200130 * 1000000 - 1) ^ 2 ≒ 2 ^ 88.4 になるかも知れず、64ビット整数の
範囲に収まらないため、Cでは手軽に書けない。Rでは多倍長整数パッケージgmpを
使って書ける。
(2)は部分和をちまちま足していく方式で、途中計算の最大値が (1000000 - 1) ^ 2
≒ 2 ^ 39.9 で済むため、Cでも64ビット整数で計算できる。Rでも多倍長計算が必要な
(1)より速い (正味の実行時間が(1)は0.016秒、(2)は0.004秒)。
637デフォルトの名無しさん
2020/01/17(金) 21:12:46.79ID:KcAYJrW8 お題
f(n) = n^1 + n^2 + ... + n^n の時
f^20200117 (20200117) の下9桁を求めよ
※ f^n (x) = f(f(f(....f(x)))...) 【fがn個】
f(n) = n^1 + n^2 + ... + n^n の時
f^20200117 (20200117) の下9桁を求めよ
※ f^n (x) = f(f(f(....f(x)))...) 【fがn個】
638デフォルトの名無しさん
2020/01/18(土) 00:45:25.84ID:meR2Lc88639デフォルトの名無しさん
2020/01/18(土) 05:21:08.23ID:et7QELfi640デフォルトの名無しさん
2020/01/18(土) 22:25:47.12ID:uIn7pF9I >>637
https://ideone.com/WvoPeq
Rでは時間が掛かりすぎるのでコンパイラ言語を使うが、C/C++だと出題者と同じで
つまらないから、Fortranで書いてみた。nが奇数の場合にしか求められないし、
合っているかどうか分からない。
https://ideone.com/WvoPeq
Rでは時間が掛かりすぎるのでコンパイラ言語を使うが、C/C++だと出題者と同じで
つまらないから、Fortranで書いてみた。nが奇数の場合にしか求められないし、
合っているかどうか分からない。
641デフォルトの名無しさん
2020/01/18(土) 23:02:35.37ID:/9q/+LXn642デフォルトの名無しさん
2020/01/18(土) 23:12:37.20ID:/9q/+LXn >>641だと偶数でもOKです
643デフォルトの名無しさん
2020/01/18(土) 23:31:05.83ID:uIn7pF9I >>641
時間は掛かるがRで下9桁の値を順々にいくつか求めて配列rに記録してから、
プロンプトで any(duplicated(r)) や which(duplicated(r)) と入力して
周期性を見つけただけ。理論的な根拠はない。
時間は掛かるがRで下9桁の値を順々にいくつか求めて配列rに記録してから、
プロンプトで any(duplicated(r)) や which(duplicated(r)) と入力して
周期性を見つけただけ。理論的な根拠はない。
644デフォルトの名無しさん
2020/01/18(土) 23:34:38.18ID:/9q/+LXn thx
周期が既知なら
mod(20200117, 312500) 回だけで済むのでは？
周期が既知なら
mod(20200117, 312500) 回だけで済むのでは？
645デフォルトの名無しさん
2020/01/18(土) 23:45:49.85ID:uIn7pF9I >>644
まあそうだが、それではあまりにもマジックナンバーすぎるので、周期が本当に
312500であるかチェックするコードを31行目に念のため入れた。周期性が
確認できなければ、STOP Errorと表示してプログラムを中断する。
まあそうだが、それではあまりにもマジックナンバーすぎるので、周期が本当に
312500であるかチェックするコードを31行目に念のため入れた。周期性が
確認できなければ、STOP Errorと表示してプログラムを中断する。
646デフォルトの名無しさん
2020/01/19(日) 00:38:02.65ID:msO9WicL 【お題】
無向グラフGが入力として与えられ、Gがサイクルを持てば、
Gの中の最小サイクルの経路とそのコストを出力するプログラムをかけ
＊条件
・グラフサイズ(頂点数)は10頂点程度(任意でよい)
・各辺の重みはランダムとする
・入力は隣接行列表現とする
無向グラフGが入力として与えられ、Gがサイクルを持てば、
Gの中の最小サイクルの経路とそのコストを出力するプログラムをかけ
＊条件
・グラフサイズ(頂点数)は10頂点程度(任意でよい)
・各辺の重みはランダムとする
・入力は隣接行列表現とする
647デフォルトの名無しさん
2020/01/19(日) 08:33:00.83ID:r8dbXOf2 お題: 文字列aの真ん中に文字列bを挿入する関数chopを定義しなさい
648デフォルトの名無しさん
2020/01/19(日) 08:40:19.34ID:dOSa/ZjO >>647 Ruby
def chop(str); str.tap{|s| s[s.size / 2, 0] = ?b}; end
puts chop('hogefuga') # => hogebfuga
def chop(str); str.tap{|s| s[s.size / 2, 0] = ?b}; end
puts chop('hogefuga') # => hogebfuga
649デフォルトの名無しさん
2020/01/19(日) 08:42:44.39ID:dOSa/ZjO 問題誤読してた
def chop(a, b)
a.tap{|s| s[s.size / 2, 0] = b}
end
puts chop('hogehoge', 'HOGE') # => hogeHOGEhoge
def chop(a, b)
a.tap{|s| s[s.size / 2, 0] = b}
end
puts chop('hogehoge', 'HOGE') # => hogeHOGEhoge
650デフォルトの名無しさん
2020/01/19(日) 10:33:55.37ID:9NcxNk8h お題 (>>346)
1〜1000 の整数の内、3の倍数または5の倍数であるものだけを選んで、その合計を求めよ。
1〜1000 の整数の内、3の倍数または5の倍数であるものだけを選んで、その合計を求めよ。
651デフォルトの名無しさん
2020/01/19(日) 10:37:40.30ID:9NcxNk8h 3の倍数
[1000/3] = 333個
S(3) = 3+6+9+････+999 = 333 * (3+999)/2 = 166833,
5の倍数
[1000/5] = 200個
S(5) = 5+10+15+････+1000 = 200 * (5+1000)/2 = 100500,
3の倍数かつ5の倍数 （15の倍数）
[1000/15] = 66個
S(15) = 15+30+45+････+990 = 66 * (15+990)/2 = 33165,
∴ S(3) ＋ S(5) - S(15) = 100500 + 166833 - 33165 = 234168.
[1000/3] = 333個
S(3) = 3+6+9+････+999 = 333 * (3+999)/2 = 166833,
5の倍数
[1000/5] = 200個
S(5) = 5+10+15+････+1000 = 200 * (5+1000)/2 = 100500,
3の倍数かつ5の倍数 （15の倍数）
[1000/15] = 66個
S(15) = 15+30+45+････+990 = 66 * (15+990)/2 = 33165,
∴ S(3) ＋ S(5) - S(15) = 100500 + 166833 - 33165 = 234168.
652デフォルトの名無しさん
2020/01/19(日) 13:04:07.51ID:CR4NZ4aH 15の倍数含めないんじゃないの？
https://paiza.io/projects/EeMOFbswluii2y-uytbeqA
https://paiza.io/projects/EeMOFbswluii2y-uytbeqA
653デフォルトの名無しさん
2020/01/19(日) 18:23:22.44ID:t01ujcAX >>629 Perl5
use List::Util qw{max};
$W = 20;
$n = @wv = ([3, 5],[5, 6],[6, 3],[3, 5],[5, 9],[2, 1],[7, 5],[4, 6],[8, 3]);
@w = map{$$_[0]} @wv;
@v = map{$$_[1]} @wv;
$wt[$n][$_] = 0 for 0..$W;
for ($i = $n - 1; $i >= 0; $i--) {
for $j (0..$W) {
$ws = $wt[$i + 1][$j];
$ws = max($wt[$i + 1][$j - $w[$i]] + $v[$i], $ws) if $j >= $w[$i];
$wt[$i][$j] = $ws;
}
}
print "価値合計最大: $wt[0][$W]\n";
$j = $W;
for $i (0..$n-1) {
$ws = $wt[$i][$j];
if ($wt[$i + 1][$j] != $ws) {
print "[$w[$i], $v[$i]] ";
$ws -= $v[$i];
for (; 0 <= $j; $j--) { last if $wt[$i + 1][$j] == $ws; }
}
}
$ perl 16_629_nsp_dp.pl
価値合計最大: 31
[3, 5]
[5, 6]
[3, 5]
[5, 9]
[4, 6]
use List::Util qw{max};
$W = 20;
$n = @wv = ([3, 5],[5, 6],[6, 3],[3, 5],[5, 9],[2, 1],[7, 5],[4, 6],[8, 3]);
@w = map{$$_[0]} @wv;
@v = map{$$_[1]} @wv;
$wt[$n][$_] = 0 for 0..$W;
for ($i = $n - 1; $i >= 0; $i--) {
for $j (0..$W) {
$ws = $wt[$i + 1][$j];
$ws = max($wt[$i + 1][$j - $w[$i]] + $v[$i], $ws) if $j >= $w[$i];
$wt[$i][$j] = $ws;
}
}
print "価値合計最大: $wt[0][$W]\n";
$j = $W;
for $i (0..$n-1) {
$ws = $wt[$i][$j];
if ($wt[$i + 1][$j] != $ws) {
print "[$w[$i], $v[$i]] ";
$ws -= $v[$i];
for (; 0 <= $j; $j--) { last if $wt[$i + 1][$j] == $ws; }
}
}
$ perl 16_629_nsp_dp.pl
価値合計最大: 31
[3, 5]
[5, 6]
[3, 5]
[5, 9]
[4, 6]
654デフォルトの名無しさん
2020/01/19(日) 20:22:32.64ID:MJwntUeD >>652
PowerShellには論理XOR演算子があるので簡潔に書けるな。
(1..1000 |? {$_ % 3 -xor $_ % 5} | measure -sum).sum
-- 実行結果 --
201003
PowerShellには論理XOR演算子があるので簡潔に書けるな。
(1..1000 |? {$_ % 3 -xor $_ % 5} | measure -sum).sum
-- 実行結果 --
201003
655デフォルトの名無しさん
2020/01/19(日) 21:28:24.55ID:RfLx+x9F >>652
なぜそう思った？
なぜそう思った？
656デフォルトの名無しさん
2020/01/19(日) 21:32:35.60ID:CR4NZ4aH >>655
だけ と強調してたから15を含めない意図があったのかと思った
だけ と強調してたから15を含めない意図があったのかと思った
657デフォルトの名無しさん
2020/01/19(日) 21:35:30.71ID:RrNuywTU 「3の倍数または5の倍数であるものだけ」という文言をそう理解するのは宇宙でお前だけだと思う
658デフォルトの名無しさん
2020/01/19(日) 22:24:05.06ID:RfLx+x9F 妊娠してるか体が不自由な人だけ使ってください
659デフォルトの名無しさん
2020/01/19(日) 23:13:47.04ID:xkwic4JQ >>658
妊娠してる障害者はすわれないやんけ！
妊娠してる障害者はすわれないやんけ！
660デフォルトの名無しさん
2020/01/20(月) 07:26:08.24ID:MadDRkAO 日本語の選択が排他的かどうかは状況しだいだから難しいところだと思うけどね
レストランで「コーヒーか紅茶が付きます」と言えばどちらか一方でしょ
ケースバイケース
こう解釈したらこういうプログラムになるというふうに思考を広げることはできるっしょ
レストランで「コーヒーか紅茶が付きます」と言えばどちらか一方でしょ
ケースバイケース
こう解釈したらこういうプログラムになるというふうに思考を広げることはできるっしょ
661デフォルトの名無しさん
2020/01/20(月) 08:18:28.86ID:ItoFGwWk662デフォルトの名無しさん
2020/01/20(月) 10:07:25.78ID:DzK/Jy6Q ０個選んで答えは０
コンピュータ言語読み書きしてたらこういう
発想が自然に感じられるが
日常言語の世界ではナンセンス杉
コンピュータ言語読み書きしてたらこういう
発想が自然に感じられるが
日常言語の世界ではナンセンス杉
663デフォルトの名無しさん
2020/01/20(月) 14:10:00.56ID:gT/yNp+O >651 のようにした
common lisp
(loop for i from 1 to 1000 when (= (* (mod i 3) (mod i 5)) 0) sum i)
234168
common lisp
(loop for i from 1 to 1000 when (= (* (mod i 3) (mod i 5)) 0) sum i)
234168
664デフォルトの名無しさん
2020/01/20(月) 15:41:16.18ID:/G9h8LiI >>651 Ruby
def si(n,m); n.step(m,n).inject(:+); end
p n3 = si( 3, 1000 ) #=> 166833
p n5 = si( 5, 1000 ) #=> 100500
p n15 = si( 15, 1000 ) #=> 33165
p n3 + n5 - 2 * n15 #=> 201003
def si(n,m); n.step(m,n).inject(:+); end
p n3 = si( 3, 1000 ) #=> 166833
p n5 = si( 5, 1000 ) #=> 100500
p n15 = si( 15, 1000 ) #=> 33165
p n3 + n5 - 2 * n15 #=> 201003
665デフォルトの名無しさん
2020/01/20(月) 21:46:25.06ID:eV9B9Eib >>629
Rで全探索
https://ideone.com/XDwD7C
物が9個しかないので512通りの組み合わせを全探索してもすぐ終わるし、
上のプログラムの2番目の問題のように、合計価値が最大となる組み合わせが
複数ある場合でもすべて挙げられるし、重さが小数や大きな整数の場合でも
同様に解けるから、全探索が時間的に可能なら全探索の方が良いんじゃないか?
Rで全探索
https://ideone.com/XDwD7C
物が9個しかないので512通りの組み合わせを全探索してもすぐ終わるし、
上のプログラムの2番目の問題のように、合計価値が最大となる組み合わせが
複数ある場合でもすべて挙げられるし、重さが小数や大きな整数の場合でも
同様に解けるから、全探索が時間的に可能なら全探索の方が良いんじゃないか?
666デフォルトの名無しさん
2020/01/20(月) 22:42:22.14ID:vyZs8dgX667デフォルトの名無しさん
2020/01/20(月) 23:01:52.63ID:kEPXORSp 問題に適した解法なら>>631が最強
668デフォルトの名無しさん
2020/01/20(月) 23:10:30.44ID:vyZs8dgX (´･ω･`)「・・・・・」
669デフォルトの名無しさん
2020/01/21(火) 14:48:52.44ID:/dftakVp >>650
Kotlin script
KotlinもBooleanのxor使えたよ。こういう場合は優先順位の問題で括弧が必要になるけどね。
println((1..1000).filter { (it % 3 == 0) xor (it % 5 == 0) }.sum())
Kotlin script
KotlinもBooleanのxor使えたよ。こういう場合は優先順位の問題で括弧が必要になるけどね。
println((1..1000).filter { (it % 3 == 0) xor (it % 5 == 0) }.sum())
■ このスレッドは過去ログ倉庫に格納されています
