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

**デフォルトの名無しさん** · 2019/11/17(日) 09:00:22.10

プログラミングのお題スレです。

【出題と回答例】
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/

**デフォルトの名無しさん** · 2019/12/30(月) 21:43:46.47

>>504
実装とかによるけど大抵の実装だとほぼO(1)だよ

**デフォルトの名無しさん** · 2019/12/30(月) 22:39:47.32

ほぼ1ってなんだよwww

オーダー1の実装だと
値の範囲という別のオーダーが生まれる

**デフォルトの名無しさん** · 2019/12/30(月) 22:44:20.79

>>506
平均のことかと

**デフォルトの名無しさん** · 2019/12/30(月) 22:53:03.82

ああ平均か
最悪値は非常に悪いよね

**デフォルトの名無しさん** · 2019/12/30(月) 22:55:25.07

てっきり超巨大ハッシュテーブルを作るのかと思った

**デフォルトの名無しさん** · 2019/12/30(月) 22:58:46.54

たしかにハッシュテーブルの最悪の計算量はO(n)だけれども
そうなることってマレだよ

むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで
それ以上になると計算コストがバク上がりしてた
最近のライブラリだとテーブルサイズが可変になってるので問題ない

あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが
数年前に話題になったかな

ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと
ハッシュテーブル使うときはO(1)で考えて良いと思う

**デフォルトの名無しさん** · 2019/12/30(月) 23:12:19.04

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 になる

**デフォルトの名無しさん** · 2019/12/30(月) 23:30:39.44

最近は結構インテリジェントに作られてるんだね
unordered_set/map もたまには使ってみようかな

**デフォルトの名無しさん** · 2019/12/31(火) 07:26:10.17

制約論理型言語だと変数の上限下限を自動的に切ってくれる。

**デフォルトの名無しさん** · 2019/12/31(火) 09:03:13.10

お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ

フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)

**デフォルトの名無しさん** · 2019/12/31(火) 10:24:38.95

>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムでO(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。

**デフォルトの名無しさん** · 2019/12/31(火) 12:24:58.82

>>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

**デフォルトの名無しさん** · 2019/12/31(火) 12:26:30.15

>>515じゃなくて>>514だった。

**デフォルトの名無しさん** · 2019/12/31(火) 13:18:28.06

>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
https://ideone.com/OY6Adr

**デフォルトの名無しさん** · 2019/12/31(火) 17:23:41.22

>>514
>>516
515です。コード上げてなかった。
https://ideone.com/SPRgPf

**513** · 2019/12/31(火) 18:46:25.67

>>513
64ビットに収まるようにしたので簡単でしたかね

C++
https://ideone.com/VRdN4q

**デフォルトの名無しさん** · 2019/12/31(火) 18:47:43.73

>>514でした
すみません

**デフォルトの名無しさん** · 2019/12/31(火) 19:45:18.11

>>449
https://ideone.com/nisdwQ
C++。問題勘違いして全探索かいたんだよ～。
おわらねー。Orz

**デフォルトの名無しさん** · 2019/12/31(火) 20:25:50.73

>>522
100億人に2020になる素数をプレゼント出来そうだ。

**デフォルトの名無しさん** · 2019/12/31(火) 20:58:55.61

>>523
100億！！？？？マジで？？
そら手に余るわ。教えてくれてありがとう。

プレゼントするときは、「あなたに特別な2020を！」って感じか。

**デフォルトの名無しさん** · 2020/01/01(水) 07:48:09.89

>>523
素数2個の2020は41人しかあげられない。

【さん吉】 · 2020/01/01(水) 12:10:34.36

あけおめ

**デフォルトの名無しさん** · 2020/01/01(水) 12:56:41.11

お題

a^n + b^n + c^n = 2020
の整数解のうちnが最大の物を求めよ

【大吉】 · 2020/01/01(水) 15:06:53.67

あけおめ～

**デフォルトの名無しさん** · 2020/01/01(水) 15:29:53.46

A HAPPY NEW YEAR !!!

というコード。

**デフォルトの名無しさん** · 2020/01/02(木) 04:45:53.28

>>451

**デフォルトの名無しさん** · 2020/01/02(木) 14:00:53.09

(´；ω；｀)

**デフォルトの名無しさん** · 2020/01/03(金) 03:43:04.42

お題

a^3 + b^3 + c^3 = 2020 * 2
の整数解を求めよ。

**デフォルトの名無しさん** · 2020/01/03(金) 03:49:51.76

追加

a^3 + b^3 + c^3 = 2020 / 2･2
の整数解を求めよ。

**デフォルトの名無しさん** · 2020/01/03(金) 03:54:35.20

>>486
Kotlin
https://paiza.io/projects/5OHDudzLFUjSV6DAdxFcfw

こんなので良いの？単に掛け算して一致するか比較しているだけなんだけど。
オマケとして重複しないようにはしているが。

**デフォルトの名無しさん** · 2020/01/03(金) 04:17:21.42

>>532
C
https://paiza.io/projects/vMRPBddVA6FgCl6AHaGXOw

どう?

**デフォルトの名無しさん** · 2020/01/03(金) 04:18:44.02

>>533
最後の 2･2 の部分って何? 2.2? こっちで文字化けしてちゃんと表示されてないだけ?

**デフォルトの名無しさん** · 2020/01/03(金) 09:45:42.54

>>536
2020 / 2･2 = 2020 / 2 * 2 = 2020

**デフォルトの名無しさん** · 2020/01/03(金) 12:48:37.25

>>532
200万以下だと38通り
(並び替えも数えるとその6倍)

>>533
2020は解無し
1010は100万までには解は無い
505は100万までに18個

**デフォルトの名無しさん** · 2020/01/03(金) 12:51:02.88

>>527
n乗して64bitの範囲だとn=2しか発見出来なかった

**デフォルトの名無しさん** · 2020/01/03(金) 20:05:33.33

>>532
C
https://ideone.com/ctjDC0

38個見つけるのに1時間くらいかかりました
38個目 (1661082, 440694, -1671358)

こういうのはC/C++が得意でしょう
他の言語で出来ます？ (挑戦)

**デフォルトの名無しさん** · 2020/01/04(土) 17:22:50.50

お題
>>514に関連して、F(F(80))の桁数を求めよ。

計算式は簡単だが…

**デフォルトの名無しさん** · 2020/01/04(土) 17:47:47.60

over　flow周りはあってるんだかわからん
https://i.imgur.com/PndnV6t.png

**デフォルトの名無しさん** · 2020/01/04(土) 19:01:02.66

Mathematica ?

**デフォルトの名無しさん** · 2020/01/04(土) 20:28:18.17

お題: 文字列を逆順にしてコピーするreverse関数を定義せよ（既存のライブラリを使ってはならない）

**デフォルトの名無しさん** · 2020/01/04(土) 20:40:17.01

>>544 Ruby

puts 'ABCDEF'.chars.then{|a| a.size.times.map{a.pop}}.join

# => FEDCBA

**デフォルトの名無しさん** · 2020/01/04(土) 20:46:16.21

>>544　PowerShell

function reverse($s) {-join $s[-1..-$s.length]}
reverse 文字列を逆順にしてコピーするreverse関数を定義せよ

-- 実行結果 --
よせ義定を数関esreverるすーピコてしに順逆を列字文

**デフォルトの名無しさん** · 2020/01/04(土) 21:12:58.70

>>544 Ruby
def reverse( s ); s.chars.inject(:prepend); end

**デフォルトの名無しさん** · 2020/01/04(土) 21:13:39.03

>>544 C
https://ideone.com/8mVMpf

**デフォルトの名無しさん** · 2020/01/04(土) 21:26:02.66

>>544
Java
https://paiza.io/projects/t01pm19B5qJfhk_bOyJXMQ

**デフォルトの名無しさん** · 2020/01/05(日) 00:51:01.04

>>544
Kotlin
https://paiza.io/projects/RdcgXqdUDC52BTO0y9n1zw

Kotlin の String には reversed() という文字列順序逆転のための拡張関数が最初からあって紛らわしいので rev() という名前で自作した。

**デフォルトの名無しさん** · 2020/01/05(日) 08:25:52.70

>>532
　{a, b, c} = {-12, -4, 18}　{-4, 2, 16}　など
>>533
　{a, b, c} = {-6, -2, 9}　{-2, 1, 8}　など

**デフォルトの名無しさん** · 2020/01/05(日) 08:35:04.57

>>544 Ruby
def rev(s)
(1..s.size).map{|i|s[-i]}.join
end

**デフォルトの名無しさん** · 2020/01/05(日) 11:04:36.67

>>544 Common Lisp
https://ideone.com/cORf5W
https://ideone.com/NbfBax

**デフォルトの名無しさん** · 2020/01/05(日) 15:25:24.03

>>544 Python
def reverse(s):
return s[::-1]

**デフォルトの名無しさん** · 2020/01/05(日) 16:01:41.83

>>540
こういうのを見ると我々は離散数学についてはほぼ無力と思う。

**デフォルトの名無しさん** · 2020/01/05(日) 17:02:46.74

>>555
勉強しとけ

**デフォルトの名無しさん** · 2020/01/05(日) 21:49:56.17

>>544　R
https://ideone.com/mfvWPO

>>546のPowerShellと違って、U+10000以上の文字が含まれていても正しく逆順にできる。

**デフォルトの名無しさん** · 2020/01/05(日) 21:52:10.17

>>542
仮数部も指数部も間違っている。整数で1の位まで正確に求められるよ。

**デフォルトの名無しさん** · 2020/01/05(日) 22:31:31.58

>>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　など。

**デフォルトの名無しさん** · 2020/01/05(日) 22:41:01.23

>>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}　など。

**デフォルトの名無しさん** · 2020/01/05(日) 22:48:30.69

>>541
C++
https://ideone.com.VJk9QA

倍精度だと微妙に精度が足りないので
擬似4倍精度で計算してみた

4倍精度や多倍長が使える言語やライブラリを使えば一瞬で書けるんだけど

**デフォルトの名無しさん** · 2020/01/05(日) 22:49:34.33

↑
https://ideone.com/VJk9QA
でした

**デフォルトの名無しさん** · 2020/01/05(日) 23:29:51.01

>>562
正解。

Rには多倍長浮動小数点パッケージRmpfrがあるので、120ビット精度での計算をさっと書ける。
多倍長整数パッケージgmpにはフィボナッチ数列の第n項を求める関数があるので、第80項を
自分で求める必要すらない。
https://ideone.com/VcxXIm

C/C++にもlong double型があるので楽勝!と思っていると罠に嵌まる。Visual C++では
long doubleは移植性（単にコンパイルが通るという意味で）のために定義されているだけで、
double精度しかないので使えない。GNU C++ではlong doubleが本当のlong doubleなので使える。
https://ideone.com/3puKYQ

これをVisual C++やGNU Cで実行すると、1の位が2大きい不正確な値が表示されてしまう。
https://ideone.com/Md5qZz

**デフォルトの名無しさん** · 2020/01/05(日) 23:41:09.00

GNU C++にも罠があって、https://ideone.com/3puKYQ はideoneでは結果が正しく
表示されているが、Windows版でコンパイルすると「-0桁」になってしまう。
printfの%Lf書式指定子が何故か正常に機能しないようなので、long longに変換して
%lld書式指定子を使う必要がある。

**デフォルトの名無しさん** · 2020/01/05(日) 23:58:45.24

>>562は擬似4倍精度の四則演算やルートがコンパクトにまとまっており参考になるかと思います

logは手抜きですが

**デフォルトの名無しさん** · 2020/01/06(月) 00:24:13.90

x87の80bit形式久々に聞いた
intelの失敗仕様

本当のlong doubleって言ったら128bitの事だと思う

**デフォルトの名無しさん** · 2020/01/07(火) 12:16:08.47

本当の？

**デフォルトの名無しさん** · 2020/01/07(火) 13:02:38.21

大きさと精度が一致しないということでは。
例えば、16ビット整数の加算において255+1で桁あふれが発生するのは、勘弁してほしい。
16ビット整数であれば精度も16ビットあってほしい。

**デフォルトの名無しさん** · 2020/01/07(火) 13:13:00.08

intelの拡張小数は箱も中身も80bitだぞ
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど

**デフォルトの名無しさん** · 2020/01/07(火) 13:43:12.96

GCCのlong doubleは128ビットあるから。

**デフォルトの名無しさん** · 2020/01/07(火) 22:24:41.07

ひさびさにx87命令を使ってみた
masm形式なのでideoneでは動作しませんが
https://ideone.com/CdzenK

**デフォルトの名無しさん** · 2020/01/07(火) 22:38:44.27

↑の出力結果

4893806799921043 (4893806799921042 + 0.855469)

丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ

2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります

**デフォルトの名無しさん** · 2020/01/07(火) 23:09:32.62

https://pc.watch.impress.co.jp/docs/article/toku0101/plan8.htm

**デフォルトの名無しさん** · 2020/01/08(水) 17:55:41.24

お題
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ

フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)

**デフォルトの名無しさん** · 2020/01/08(水) 18:47:53.52

フィフィフィボナッチ数列はお腹いっぱい

◆QZaw55cn4c · 2020/01/08(水) 19:48:23.85

>>571
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！

**デフォルトの名無しさん** · 2020/01/08(水) 20:00:11.84

お前は昭和何年からタイムスリップしてきたんだ

**デフォルトの名無しさん** · 2020/01/08(水) 20:33:31.36

>>574
R
https://ideone.com/lpnhLq

**デフォルトの名無しさん** · 2020/01/08(水) 21:16:17.44

正解

C++
https://ideone.com/iSMABZ

**デフォルトの名無しさん** · 2020/01/08(水) 23:38:33.13

>>544 Perl5

use feature qw{say signatures};
sub reverse($s) {
　map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');

**デフォルトの名無しさん** · 2020/01/10(金) 10:41:25.62

お題：自分用expm1()的なもの。底はe以外でも良い。不正な引数でのエラー処理は
考慮しなくても良い。

**デフォルトの名無しさん** · 2020/01/10(金) 13:20:18.79

目的が高精度なのかSIMDなのか単に出題者が勉強したいだけなのか
もしかしてx87命令を使わせたい？

**デフォルトの名無しさん** · 2020/01/10(金) 20:53:23.97

>>581
expm1()って何？

**デフォルトの名無しさん** · 2020/01/10(金) 21:01:53.36

エキスペディション・マグニチュードワンのことやろな

**581** · 2020/01/10(金) 22:06:13.03

>>582
SIMDやx87命令は考えてませんでした。
四則演算とexpm1()以外のライブラリ関数は使用可って事で。
やっぱし無難にテイラー展開で求めるのが楽？

>>583
例えば
ttps://linuxjm.osdn.jp/html/LDP_man-pages/man3/expm1.3.html

**デフォルトの名無しさん** · 2020/01/10(金) 22:10:45.27

四則演算も使ったらダメなのかい

**581** · 2020/01/10(金) 22:42:31.47

>>586
訂正：
四則演算と、「expm1()以外の」ライブラリ関数は使用可

**デフォルトの名無しさん** · 2020/01/11(土) 06:32:12.11

出題者が方法を知りたいだけだよね？
なら質問スレ/宿題スレの方が適切

**デフォルトの名無しさん** · 2020/01/11(土) 09:22:26.15

お題
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。

**デフォルトの名無しさん** · 2020/01/11(土) 10:27:02.77

>>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]

**デフォルトの名無しさん** · 2020/01/11(土) 10:31:32.27

typo

# => [3, 5, 11, 17, 31, [中略], 3733, 3761, 3911]

**デフォルトの名無しさん** · 2020/01/11(土) 10:52:09.93

お題
5の倍数の素数を5の倍数素数という
5の倍数素数を全て求めよ

**デフォルトの名無しさん** · 2020/01/11(土) 11:10:43.29

5の倍数の素数ってどういうことですか？
文字通りの意味なら5だけだと思うんですけど

**デフォルトの名無しさん** · 2020/01/11(土) 13:10:43.10

>>544 Perl4

use feature qw{say signatures};
sub rev($s) {
　$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string');

てす

**デフォルトの名無しさん** · 2020/01/11(土) 13:14:26.71

>>594　Perl5 だった…orz
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…

**デフォルトの名無しさん** · 2020/01/11(土) 14:01:21.01

>>592
echo 5

**デフォルトの名無しさん** · 2020/01/11(土) 20:08:39.02

お題
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。

**デフォルトの名無しさん** · 2020/01/11(土) 20:55:04.41

ナベアツ理論か。

**デフォルトの名無しさん** · 2020/01/12(日) 00:39:46.42

>>595
書き込めないコマンドは、一杯ある。
「ｌｓ　－ｌ」とか

5ch は、特定の命令によって、表示の見た目を変えることができるから、
単に、表示する文字列に変換するだけじゃなくて、

投稿されたテキストから、命令を抽出したりしているから、
バグりそうなテキストを排除しているのだろう

**デフォルトの名無しさん** · 2020/01/12(日) 10:30:24.93

>>597
C++
https://ideone.com/30RQZF

**デフォルトの名無しさん** · 2020/01/12(日) 16:28:53.41

お題: バイナリ―サーチを実装せよ（自分の記憶だけで書かなければならない）

**デフォルトの名無しさん** · 2020/01/12(日) 16:52:57.01

>>601
Java
https://paiza.io/projects/y4RxMakkRM6x88qm5GGMvA

**デフォルトの名無しさん** · 2020/01/12(日) 17:33:54.06

>>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

◆QZaw55cn4c · 2020/01/12(日) 17:39:35.02

>>601
C++
https://mevius.5ch.net/test/read.cgi/tech/1434079972/33
std::set<int> の再実装にて、内部にバイナリーサーチを含んでいます