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

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

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

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

宿題は宿題スレがあるのでそちらへ。

※前スレ
プログラミングのお題スレ Part20
https://mevius.5ch.net/test/read.cgi/tech/1624028577/

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/14(金) 22:26:17.98

>>938
移動量も最短にした方がいいか？

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/14(金) 22:31:38.64

>>939
移動量も最短にする。また、動けるとき、かつ待てるときは待つよりも先に動く方を優先するという条件を追加します。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/14(金) 22:44:41.18

>>940
さらに次の3つの条件を追加します。
西か東か迷った場合は西を優先します。
北か南か迷った場合は北を優先します。
南/北の向きか東/西の向きかを迷った場合は東/西の向きを優先します。

**デフォルトの名無しさん** · 2023/07/15(土) 03:29:30.91

>>927 Ruby
def solution( mk )
mb = 1
a = [0]
print "0x%X\n→(" % mk
while mk > 0
a.dup.each{|b| a << b + mb } if mk.odd?
mb <<= 1
mk >>= 1
end
puts a.map{|x| '0x%X' % x }.join(', ') + ')'
end

solution( 0 ) # 0の場合 0x0でいいのかな？
solution( 0x13 )
solution( 0x45 )
solution( 0x92C )

**デフォルトの名無しさん** · 2023/07/15(土) 08:05:25.03

>>925
ツッコミどころが多すぎる
正しくはこうでは?

10^(-30)
=1.010_0010_0100_0010_0101_1111_...×2^(-100)

さらに、...部分は1111...と続くので、単精度にするなら切り上げになって、

1.010_0010_0100_0010_0110_0000×2^(-100)

よって、単精度での内部表示は

0_00011011_010_0010_0100_0010_0110_0000

整数0xa24260をセットして2^123で割ればいける

2のべき乗での割り算すら信用できないなら、ldexpあたりを使うのはどうか。pythonならこちら
(pythonは単精度が無いので結果は少しずれる)

from math import ldexp
print(ldexp(0xa24260, -123))

もしくは、バイト列経由で直接変換もあり。pythonならこちら

from struct import pack, unpack
print(unpack('f', pack('I', 0b0_00011011_010_0010_0100_0010_0110_0000))[0])

**915** · 2023/07/15(土) 10:11:42.89

今からIEEE754に準拠してない処理系が制作される事は無いでしょうから
(ホビーや学習用途は別ね)、
今日の処理系で、2のべき乗での割り算で仮数部が変わるって事は
無いと思われます(アンダーフローやオーバーフローは除外)。

…IBM hexadecimal floating-pointって基数が16だったな。
(仮数部が変わらないのは16のべき乗での乗除算のみ)
あれを常用してる人ってまだ居るのか？ｗ

>>943
FORTRANならEQUIVALENCE文で…

**デフォルトの名無しさん** · 2023/07/15(土) 16:01:33.91

https://www.wolframalpha.com/input?i=8%C3%97%281%2F10%29%5E30%E3%82%924%E9%80%B2%E6%95%B0%E8%A1%A8%E7%A4%BA&lang=ja

を3ビット移動

**デフォルトの名無しさん** · 2023/07/15(土) 16:07:59.58

そもそも浮動小数点ライブラリなら
x^y = exp( y * log 2 )
で実装してるんじゃないかな
そもそものexpやlogが“最近値”を与えてくれることなど規格にはないやろ
それは数値計算の理論勉強してたらすぐわかる、メチャクチャ難しくてほとんど実装不能になってしまう
だから規格上は“±その周辺の値で表示できる値の中では最良”、すなわち“表現可能な上界の最小値または表現可能な下界の最大値”、それならギリギリ実用可能な速度くらいは出せるけど、それとて難しい、そこまで今のライブラリが保証してくれてるかあやしい
まぁその手のライブラリ使わずに“最近値”を出すことはメチャクチャ手間かかるけどできなくはない、しかしそれが限界、その値を変数に確実にセットする方法がない

**デフォルトの名無しさん** · 2023/07/15(土) 16:25:05.71

x^y = exp( y log (x))ね
この計算に入る前に「x=2, yが整数であるかどうか検査する、その場合には仮数部は弄らず指数部だけyに応じて増減させる」なんて処理してるライブラリはないやろ
有無を言わさずy log(x)計算、→exp計算、丸め誤差上等でやってるやろ、そこで単精度計算ならちょっと余裕もってビット幅大きめのアキュムレータに入れてるかもしれんけどどんなに大きな精度のアキュムレーターを用意したとて出てくる値が“最近値”になる保証はない、そこまで保証しようとすると恐ろしくコストがかかってしまう
汎用の数値計算ライブラリでそこまで保証されてるわけないと思う、単精度計算なら±2^(-24)=単精度の内部表現で可能な幅までは保証するのが限界だと思う、それとてかなりコストがかかるし
まぁどのみち2^(-23)以上の精度が必要ならそもそも言語の標準ライブラリなんか使わんからな

**915** · 2023/07/15(土) 18:15:18.86

>>946
規格で正確な値(を最近値に丸めたもの)を求められてるのは
加減乗除とsqrt()とfma()でしたっけ？
pow()は、glibcが誤差0.523ulpとか(0.5ulpが限界値)、
イイ線行ってるそうですね。
tps://members.loria.fr/PZimmermann/papers/accuracy.pdf

**デフォルトの名無しさん** · 2023/07/15(土) 21:46:41.49

おお、llvmすげぇ

**915** · 2023/07/15(土) 23:31:05.73

>>949
llvmの多くの項目がNA(non available)なのは、
実装されてないからではないかと。

この中では、OpenLibmがfdlibmの「血」を残してる方なのかな？
tps://www.netlib.org/fdlibm/

**デフォルトの名無しさん** · 2023/07/16(日) 00:22:02.04

うん、多分実装されてない分は自分でやれと
実装されてるところは軒並み0.5
まぁこれも本当に確率100%で必ず最近値出すんではなくて外れる確率が0.000001%とかなんだろうな
例えば単精度演算は毎回倍精度にキャストして計算してから丸めればほぼほぼ最近値にならない確率0.0000001%とかになるからな
逆に言えば他のライブラリはその手のキャストも何もしないで“丸め誤差上等”でやってるんやろな

**915** · 2023/07/16(日) 01:29:25.23

>>951
ちゃんとやろうとすると、CRlibmみたいに、部分的にでも
6倍精度とかで計算しないとならないっぽいです。
glibcのexp()は768bitで計算する場合があるそうで。

…世間的には、それ程の精度を求めない用途もあって、
実際、libmのhypot()(じゃなくてもいいのですが)が遅いので自分で
実装しますたと云う報告がネット上でも散見されます
(もちろん精度は落ちる)

**デフォルトの名無しさん** · 2023/07/16(日) 08:49:44.74

まじですか
768bitって何をどう計算してるんやろ？
結果が24bitで768bitなら求める答えの72倍のアキュムレーター使うのかな？
そんな事ないよな、アキュムレータは48bitくらいで36回計算するからのべ768bitとかいう事なのかな？
まぁそれだけの事やって「末尾の最後の1ビットの正確性を求める意味あんのか問題」は発生するわな
”みんなが使う汎用ライブラリ”だとどうしてもそういう“誰も求めてない精度”に無意味にこだわってしまう部分があるんかも

**915** · 2023/07/16(日) 10:57:33.80

>>953
丸めて切り上げ/切り捨てのぎりぎりのとこを精査するのに
768bitで計算する場合もあるそうです(そういう
ぎりぎりのとこでない場合はやらないので、それなりに速い)。

**デフォルトの名無しさん** · 2023/07/16(日) 11:52:54.00

>>954
まじですか？
そんな最後の1ビット正確に決定するために768bitもの無駄な計算するくらいなら誤差±2^(-23)でいいからとっとと値返してくれた方がいいのに
なので当然通常“最後の1ビット”の正確性までは規格に入れてないんだよな、それでもライブラリ作成者は自己満のために誰も求めない“最後の1ビット”にこだわる
これは高校くらいまでの近似計算の「小数第××位まで求めよ」のノリが抜けてない事の現れでもあるんだよな
もう計算論の近似計算の世界ではゲームチェンジが起こってる事に気づけてない

**915** · 2023/07/16(日) 12:36:42.33

>>955
誤差なし(±0.5ulp以内)を追及する人達(CORE-MATH)も居れば、
double-double演算とかの「飛び道具」を使うのをよしとしない人達も居て、
えーっと、みんな違ってみんないい(こなみ)

**デフォルトの名無しさん** · 2023/07/16(日) 13:03:43.49

まぁしかし“払うコスト”に対する“リターン”が少なすぎる気はする
例えば内部表現の精度が2^24まである単精度の計算をする場合、もちろん理想は“誤差±1/2×2^(-24)”で返してくれるとありがたい
しかし現実できるか？
例えばアキュムレータをを32ビット用意して計算する、マクローリン展開で求めるとして100回で打ち切るとする、打ち切り誤差は入力のサイズによるけど十分小さい、丸め誤差は2^(-32)×100で誤差トータルは2^(-25)程度、返すのが24bitだから丸められる2^8の可能性のうち真値のポジションから最大100ずれたところでウロチョロしてるわけでその“ウロチョロ”が二項分布、真値の分布が256個の箱の一様分布として外れ値になるの確率がどのくらいやろ？暗算ではできないけど言うほどない、この言うほどない誤差を返さないただそれだけのために768bitも計算繰り返すとかどうなんって感じ

**915** · 2023/07/16(日) 13:09:49.90

>>957
768bitの話は、倍精度(53bit精度)のexp()の過去のバージョンでした。
glibcでも問題になったんでしょう(たぶん)

**デフォルトの名無しさん** · 2023/07/16(日) 14:04:25.82

でしょうね
流石に768bitはない
せめてそこまで行けば完全に最近値が決定できるならともかくそこまで行っても最近値を100%決めるのは無理なんじゃないでしょうか？
24ビットの値返すのに768bitまで計算するなら744bit、2^744の可能性につきあってそこまで行っても両端の100通りの可能性は残り、最近値を返せない可能性は0にはなってない、まぁほとんど0だけど
多分llvmの実装は単精度でも最初からアキュムレータに64bit(レジスタ2個分)で計算するんやろな、あまりのビットが40bitあって100/2^40とか1000/2^40とかはほとんど0だからほぼ確率1で最近値返しますよ、それで十分でしょって実装なのではなかろかと、実際それで十分
最近のcpuはなんかレジスタ2個分に分けて計算してもレジスタ1個で計算するのと時間大して変わらないという話もききますしね

**915** · 2023/07/16(日) 14:30:41.46

>>959
以前は最近値だったそうです(その代わり遅い)
tps://sourceware.org/git/?p=glibc.git;a=commit;h=6fd0a3c6a887a91b1554730c977657a7e65334cc

**デフォルトの名無しさん** · 2023/07/16(日) 15:00:29.88

その記事はglibcで色々実験してみたの報告ですね
どっかに“旧glibcは最近値をとことんまで出す”って別資料の記事見かけました？
もちろん入力された有理数xに対してexp(x)を時間無制限ならその与えられた桁数までの最近値を計算するアルゴリズムはすぐ作れるので(一般にGaussの超幾何関数からくる連分数表示が可能な実数ならそのような事が可能)そういうライブラリを実装するのはまぁ無理ではないんですけどね
実際円周率をリソースが食い尽くされるまで延々と計算し続けるプログラムとかよくネットで転がってますし、確か昔のrubyのサンプルプログラムにも収録されてたような

**デフォルトの名無しさん** · 2023/07/20(木) 22:27:12.42

>>933-934
R
https://ideone.com/NOtyLC

>>940-941の条件はやっぱり面倒なので省略した。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/21(金) 02:40:44.37

>>962
難しいお題だったので、簡単に解説お願いします。

**デフォルトの名無しさん** · 2023/07/21(金) 07:58:12.84

>>927
Rust

fn foo(input: u32) -> impl Iterator<Item = u32> {
(0..=input).filter(move |n| n & input == *n)
}

ただしこれではループがO(n)
ループをO(log N)にするならこちら

fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input).map(|p| 1 << p).collect();
(0..(1 << table.len())).map(move |bits| bits_iter(bits).map(|p| table[p as usize]).sum())
}

補助bitsイテレータ
fn bits_iter(n: u32) -> impl Iterator<Item = u32> {
let mut n = n;
std::iter::from_fn(move || {
(n != 0).then(|| {
let p = n.trailing_zeros();
n &= !(1 << p);
p
})
})
}

**デフォルトの名無しさん** · 2023/07/21(金) 08:19:47.60

>>964
rustfmtがギリギリ2行にまとめてしまうが見にくいので手動で以下へ補正
(改行の違いだけでコード自体は同じです)

fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input)
.map(|p| 1 << p)
.collect();
(0..(1 << table.len()))
.map(move |bits| {
bits_iter(bits)
.map(|p| table[p as usize])
.sum()
})
}

**デフォルトの名無しさん** · 2023/07/21(金) 13:18:40.51

見やすさどうこうならオンラインの実行環境に入れたほうが見やすい

**デフォルトの名無しさん** · 2023/07/21(金) 20:43:39.96

>>963
まず
　①Rを自由に動かしてコマンドリストを得てから、SをRと衝突しないように動かしてコマンドリストを得る。
次に優先権を逆転させ、
　②Sを自由に動かしてコマンドリストを得てから、RをSと衝突しないように動かしてコマンドリストを得る。
そして、①と②でコマンドリストが短い方を解として採用する。

コマンドリストを得る方法は基本的には>>856と同じ幅優先探索だが、>>856のように2次元の数値配列を作り
各マスへ最短何個のコマンドで到達できるかを記録するだけでは今回の問題の複雑な動きには対処できないから、
3次元の論理配列を作り1個のコマンドで各マスへ到達できるか否か、2個のコマンドで各マスへ到達できるか否か、
3個のコマンドで～、…を記録していくように変えた。

26行目はB[Q]が何回も現れてごちゃごちゃしているので、変数をもう1個作って
　　b <- B[Q]
　　A[i + 1, , ][Q[b != Inf & b != i + 1 & (b != i | b[1] != i + 1), , drop = FALSE]] <- TRUE
と書く方が行数は増えるがすっきりする。36行目も同様。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/21(金) 21:36:35.00

>>967
三次元の論理配列。。。なんかすごい。

これって衝突回避システムに応用できるかな？

**デフォルトの名無しさん** · 2023/07/22(土) 07:20:14.13

>>966
なるほど！
専ブラではなくWebブラウザから見るとインデントスペースが消えてしまうのですね

>>927
Rust全文
https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=f627f3a5de4a0c467f015a8b1527c141

抜粋　(全角スペース使用)
fn foo(input: u32) -> impl Iterator<Item = u32> {
　let table: Vec<u32> = bits_iter(input)
　　.map(|p| 1 << p)
　　.collect();
　(0..(1 << table.len())).map(move |bits| {
　　bits_iter(bits)
　　　.map(|p| table[p as usize])
　　　.sum()
　})
}

**デフォルトの名無しさん** · 2023/07/22(土) 11:35:32.67

デスクトップアプリで5ch専ブラを造れ

**デフォルトの名無しさん** · 2023/07/23(日) 12:51:38.77

山下の乱で速攻作ったのがCUIのやつだった
GUIにしたらこんなんだろうな
https://i.imgur.com/f4xau5O.jpg

**デフォルトの名無しさん** · 2023/07/23(日) 22:13:46.62

スレ違いなんだけど今回の騒動出遅れてよくわからんのわけとこの山下ってのが5chに対して反乱分子起こしたん？
それは何故？
もうニュー速+とかでも過去の話でスレも立ってないしググっても出てこない
何がどうなったん？

**デフォルトの名無しさん** · 2023/07/25(火) 09:52:03.45

トーク過疎ってんな
こりゃクーデター失敗かな

**デフォルトの名無しさん** · 2023/07/25(火) 14:53:46.34

本能寺が変

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/26(水) 21:23:20.74

お題: 化学の共有結合。

x, y, zをそれぞれ任意の自然数とする。入力(x, y, z)に対して炭素原子(C)x個、酸素原子(O)y個、水素原子(H)z個のすべてを
共有結合で連結するときの連結結果の組み合わせをすべて出力するプログラムを書け。
出力形式は自由とする。

入力例)
(0, 1, 2)→？
(1, 1, 4)→？
(1, 0, 4)→？

**デフォルトの名無しさん** · 2023/07/27(木) 09:04:26.01

H2O2ってなんていう結合だっけ

**デフォルトの名無しさん** · 2023/07/27(木) 12:12:58.81

>>931
ごめんなさい、わからない
例えば上の例ではFooは単相型なの？
具体的に何型？
ちょっと昔からのweb情報ではできないと書いてあるページはあるけど上の例ではできてるでしょ？

**デフォルトの名無しさん** · 2023/07/27(木) 12:13:17.86

誤爆orz

**デフォルトの名無しさん** · 2023/07/27(木) 15:18:31.87

まず共有結合とはどんなものなのかを調べてからでないと作れないが、今のところ調べてまで作りたいとは思わない。

**638** · 2023/07/27(木) 17:33:36.23

>>975
結果を図で表すのがﾏﾝﾄﾞｸｾ

**デフォルトの名無しさん** · 2023/07/28(金) 06:23:08.46

情報科学的元素共有結合の勝手な定義を書いとかなければ問題にならない

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/28(金) 12:57:32.49

共有結合について高校化学でよく言われるのは、次の通り。

炭素原子は「結合の手」を4個持っている。
酸素原子は「結合の手」を2個持っている。
水素原子は「結合の手」を1個持っている。
結合の手を余らさないように連結する。
分子の右手型左手型の区別は考えなくてよい。
連結のときの他の原子との重なりは考えなくてもよい。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/30(日) 17:36:04.42

お題: パソコン、スマホ、またはタブレットに大きな顔を表示して、音声入力と
音声出力で会話ができるようにする。

**デフォルトの名無しさん** · 2023/07/31(月) 02:56:25.48

>>983
1. Skype をインストールする。
2. 友達と動画で通話する。

ただし、掛ける相手が居ない場合は実現できない。

**デフォルトの名無しさん** · 2023/07/31(月) 10:04:39.36

H2Oってなんで真っすぐじゃなくてくの字に折れてるんだろ

**デフォルトの名無しさん** · 2023/07/31(月) 10:05:41.12

>>984
スマホが2台あれば解決
PC+スマホでもOK

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/31(月) 14:11:26.12

お題: 気体の状態方程式より温度を求める。

半径ゼロで70000個の水素分子のみが底面半径4[cm]、高さh[cm]の円すい形の密閉空間内をまんべんなく飛び回る。
密閉空間の高さh[cm]を入力とするとき、圧力P=1.013*10^5 [Pa]、密閉空間の体積V[m^3]、水素分子の物質量n[mol]、気体定数R=8.31について、
気体の状態方程式PV=nRTより導かれる絶対温度T[K]を出力せよ。
入力例)
10→？
20→？
50→？

**デフォルトの名無しさん** · 2023/07/31(月) 14:46:35.12

70000個ってどうやって数えたん？

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/31(月) 14:55:02.47

>>988
そりゃあ、一つ一つ丁寧にピンセットでつまんで容器に入れたんでしょう。

**デフォルトの名無しさん** · 2023/07/31(月) 18:09:03.77

現代の地球人の技術力ではT=0にでもしないと無理そうだし
もしそうなら水素は固体化してて
Vの大部分は真空でPはほぼ0なんじゃないかな

**デフォルトの名無しさん** · 2023/08/01(火) 07:02:39.12

はいはい unsafe { 未定義動作 }

**638** · 2023/08/01(火) 07:13:10.69

なぜ中高理科の試験問題をここで…

**デフォルトの名無しさん** · 2023/08/01(火) 10:53:13.82

T = PV/nR
= 1.013*10^5 * (4.000)^2*3.142*h/1000
/( 70000*8.314 * 6.022*10^23 *10^3 )
= 1.453*10^(-29)*h ( K )

**蟻人間** ◆T6xkBnTXz7B0 · 2023/08/01(火) 12:37:22.46

分子が多すぎて現実的なシミュレーションは難しいね。

**デフォルトの名無しさん** · 2023/08/01(火) 13:12:18.01

T = PV/nR
= 1.013*10^5 * (4.000)^2*3.142*h/1000
/( 70000 / (6.022*10^23) *10^3 * 8.314 )
= 5.269*10^18*h ( K )

**デフォルトの名無しさん** · 2023/08/02(水) 09:29:52.97

h=0で誤動作する罠

**デフォルトの名無しさん** · 2023/08/02(水) 23:17:43.36

そもそも分子の運動をシュミレーションしてp,v,nTの関係を調べさせるつもりなら出題がおかしい
それなら入力が温度、分子量、体積で出力が圧力やろ

**デフォルトの名無しさん** · 2023/08/03(木) 03:48:48.75

シミュレーション

**デフォルトの名無しさん** · 2023/08/03(木) 13:32:25.90

PV=ｎRTは高校物理

**デフォルトの名無しさん** · 2023/08/03(木) 13:32:47.33

熱力学は
ヘンリーの法則
ラウールの法則
に従う

**1001** · Over 1000

このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 262日 18時間 32分 12秒