プログラミングのお題スレ 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(月) 15:47:28.48

入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです

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

四角形の縦の長さの定義は？
まさか四角形＝長方形じゃないでしょ

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

>>489
ではそのまさかということで
四角形とは長方形のことです！

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

問題を書いたときは長方形以外の四角形がこの世に存在するとは思いもよらなかったので四角形と書いたのです

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

オーダーは n log n

問題には
数列に同じ値が複数あった場合に1個とするのか別カウントするのかという曖昧性がある

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

>>492
同じ値は別カウントで良いです

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

数列が整数限定
数列の数が大きい
面積が小さい

なら
素因数分解っていうアプローチもあるのかな？

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

>>486
同じ値を別カウントにするとベラボーに難しいですね
同じ値は1個とカウントして良いです

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

>>486
数万程度なら、Rで何の工夫もなしに素直に書いても瞬時に求められるな。
https://ideone.com/tLSpKT

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

>>496
マジですか・・・すごいです

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

>>462
そういえばこの問題って.NETのLINQとかJavaのStreamとか
使ってソートすればたぶんヒープが使われて逐次処理が行われるんで
全部の値をソートせずに答えが求められるんじゃないかと思った
ほぼ線形探索

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

>>486
数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。

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

>>495
アルゴリズム的にはどっちもかわらん
特定の言語で記述しにくいってことはあるかもしれないけど

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

>>500
マジですか・・・

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

>>484
Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で
ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては
基数ソート、それ以外に対してはシェルソートが選択されると書かれている。

ということで、method引数を明示的に指定して実行時間を比較してみると、
基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが
何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。
RのクイックソートでもC++ STLのsortよりはまだ速い。https://ideone.com/g2JEPF

二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。
(キャッシュの影響があるのかも知れないが)。https://ideone.com/Dm65Sp

Rの関数はCかFortranで書かれているものが多いが、binsearch関数はRで書かれているし、
戻り値のフラグ判定が文字列照合という非効率な処理だから、二分探索としては
あまり速くない。

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

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

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

ハッシュテーブルの検索はオーダー1じゃないと思うんだ

**デフォルトの名無しさん** · 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

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