プログラミングのお題スレ 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/

**デフォルトの名無しさん** · 2023/07/05(水) 16:32:04.27

計算結果を62進数の文字列で出力せよ。

**デフォルトの名無しさん** · 2023/07/05(水) 17:55:35.60

出るよ。

**884** · 2023/07/05(水) 22:10:28.44

>>886
>Perl
>計算面倒だから文字列の状態で数値部分を10進数に変換してから eval 使うという手抜きプログラム

それでOK。出題者が事前に書いたRとPowerShellのプログラムもまさにそのやり方。構文解析を
自前で書かせるつもりはなかった。整数同士の割り算は結果が言語により異なるので問題から外した。

www.ideone.com/L0fgm6
www.ideone.com/J2cLd2　(実行結果は上と同じ)

RubyとPythonもevalを使えるので似たように書けるはず。なんかPとRで始まる言語ばかりだな。

**638** · 2023/07/05(水) 23:15:53.66

Parser generator使って自前で構文解析＆計算させようとして苦戦していた俺涙目

**デフォルトの名無しさん** · 2023/07/06(木) 00:20:52.37

>>890
オレもParser generatorでやろうと思ってるよ
eval なんか使えないからね
でも日曜日までまとまった時間ないからまたまた超遅レスになる予定

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/06(木) 20:52:00.35

お題: 緯度と経度から距離と方位を求める。

地球が球体であると仮定し、地球の半径を6378[km]とする。
緯度と経度を角度[deg]で与える。
北緯と西経は正の値で、南緯と東経は負の値で与えるものとする。
二点ABの緯度と経度を与えるとき、ABの距離d[km]と、AからBへ向かう方位角φ[deg]を求めよ。
方位角は北:0度、東:90度、南:180度、西:270度とする(時計回り)。

例)
A(139.74477, 35.6544), B(39.8261, 21.4225)
→(9491, 293).

参考) https://keisan.casio.jp/exec/system/1257670779

**デフォルトの名無しさん** · 2023/07/06(木) 23:43:20.91

>>892
R
www.ideone.com/S5Jubo

**デフォルトの名無しさん** · 2023/07/07(金) 01:04:00.47

>>892
haskell
角が合わんorz寝よ

https://ideone.com/8Rk7Fp

**デフォルトの名無しさん** · 2023/07/07(金) 11:02:22.14

>>892
完全にぴったり地球の表裏側2点の場合の方位角は？

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/07(金) 13:25:49.78

>>895
定義しない、または任意。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/08(土) 00:02:54.35

お題: 緯度経度を三次元座標に変換。

地球を半径6378[km]の球体だと仮定し、地球の中心を三次元空間の原点とする。この空間は右手系である。
原点より緯度0度経度0度の地点に向かう向きをx軸方向とする。
また原点より北極点に向かう向きをz軸方向とする。
入力として与えられた緯度経度のペア[deg^2]を三次元座標[km^3]に変換せよ。

例)
(0, 0)→(6378, 0, 0).
(90, 0)→(0, 0, 6378).
(45, 0)→???　(0, -45)→???
(45, -45)→???　(30, -45)→???

**638** · 2023/07/08(土) 18:46:12.49

>>884 Perl5、見易くするためインデントは全角スペースに置換してあります。

use feature qw{signatures}; no warnings 'experimental';
use Parse::RecDescent;
sub ope($valp, @args) { my $val = $valp->();
　while (@args) { my ($op, $parm) = splice @args, 0, 2; $op->($val, $parm->()); } $val }
%d = map{$_ => $i++} 0..9,'A'..'Z','a'..'z';
%e = map{$d{$_} => $_} keys %d;
use List::Util 'reduce';
sub dec($d62) { reduce {$a*62 + $b} map{$d{$_}} split '', $d62 }
my $parse = new Parse::RecDescent <<'End';
　expr: <leftop:term addsub term> {sub { ::ope @{$item[1]} }}
　addsub: '+' {sub { $_[0] += $_[1] }} | '-' {sub { $_[0] -= $_[1] }}
　term: <leftop:factor muldiv factor> { sub {::ope @{$item[1]} }}
　muldiv: '*' {sub { $_[0] *= $_[1] }} | '/' {sub { $_[0] /= $_[1] }}
　factor: dig62 | '(' expr ')' { $item[2] }
　dig62: /[0-9A-Za-z]+/ {sub { ::dec $item[1] }}
End
sub enc($d) { my $r = $d % 62; $d = int(($d - $r) / 62); $d ? (enc($d) . $e{$r}) : $e{$r}; }
for (<DATA>) {
　$n = $parse->expr($_)->();
　$n = $n < 0 ? '-' . enc(-$n) : enc($n);
　print "$_ = $n\n";
}
__DATA__
123 + ABC
4 - K
2023-7-4
printf - (Hello + world)
Windows * 11
The - quick - brown * fox + jumped - over + the - lazy * dog
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ

**638** · 2023/07/08(土) 18:47:35.93

>>898 の実行結果:

$ perl 21_884_calc_dig26.pl
123 + ABC
　= BDF
4 - K
　= -G
2023-7-4
　= 201s
printf - (Hello + world)
　= odFAME
Windows * 11
　= XFWRSlos
The - quick - brown * fox + jumped - over + the - lazy * dog
　= -Q1YGAW2x
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ
　= HITvzYcgj

※ Parse::RecDescentという再帰降下型Parser generatorのperl moduleを使用したので、
　動作させるにはそのインストールされている必要がありますが、ideonなどのオンライン
　プログラムサービスには多分インストールされていなくて動作しないんじゃないかなともいます

**デフォルトの名無しさん** · 2023/07/08(土) 21:33:55.36

>>897
R
www.ideone.com/RHXhIq
変哲は、普通に書くとsinとcosが合わせて4個か5個必要な所を2個にしたことだけ。

**884** · 2023/07/08(土) 21:40:41.86

>>898
ならば出題者からもeval任せでない自前の実装プログラムをどうぞ。

C
www.ideone.com/erwpI4

「C言語による最新アルゴリズム事典」に載っている10進小数の四則演算式評価プログラムを
ちょっと改変したらサッと作れた。

C++
www.ideone.com/MFEuc6

Cプログラムのグローバル変数と下請け関数をクラスに入れて隠蔽した。readch関数のかわりに、
空白を読み飛ばすようにオーバーライドした++演算子を使ってすっきり書いた。

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

イヤ、スクラッチで書いても意味ないでしょ？

**638** · 2023/07/08(土) 22:09:14.33

四則演算の式評価なら１数十stepでParserを手書きできるということでそれもありじゃね？

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

うーん、まぁそれはそうも言えるかな
しかしその手の話は結局“車輪の再発明”してるだけだからな
parsingみたいに重たい処理は可能なら既存の実績のあるparser generator使えるならそれ使うのか本筋な気はするけどね
初学者がparsingの基礎の練習問題として使うのはありかな

**638** · 2023/07/08(土) 22:16:05.45

GCCやCLangも何とparserはyaccなど使わずに手書きなんだそうだ。
理由は下記サイトなど参照。きめ細かいエラー処理など可能になるかもしれないがコードはとても込み入って大変そうだわ。

c - Are GCC and Clang parsers really handwritten? - Stack Overflow

https://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten

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

まぁ物によるだろうけどほとんどのプログラミング言語は最低でも文脈依存文法以上を解析できるパーサーでないと解析できない
ましてや今日のコンパイラは何行目の何文字目がおかしいのか、それがどんな間違いなのかも示して修正案まで出してくれる、そこまでの作業を一般的なパーサー生成機に落とし込むこと1から考えるよりはパーサーそのもの自分で作る方が早いかもしれんわな
ただ今回のは四則演算とカッコだけなんだから文脈自由文法の解析機で解析できるから素人が作った解析機を使わない意味は実用上はまずない、まさに車輪の再発明の典型になってしまう
しかしまぁここはある意味“再発明を楽しむスレ”でもあるからなw

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

専門家の作った解析機を使わない意味はないだorz
まぁただパーサー生成機の作ったパーサーはもちろん「どんな文法でも対応できる」ために効率を犠牲にする場合もあるので速度とかをギチギチにチューンするつもりなら意味はあるか
実際今回のも()と+,-,×だけやからな

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/09(日) 09:04:09.08

お題: 飛翔体のシミュレーション。
クレムリン(北緯55度東経37度)から東京(北緯35度東経139度)に向けて初速12[km/s]、重量30[kg]の飛翔体が発射される。
地球は半径6378[km]の球体と仮定し、重力加速度を9.8[m/s^2]とする。
飛翔体は噴射せず自由落下すると仮定する。空気抵抗は考慮しない。
発射時刻をt=0[s]とするとき、t=120とt=240のときの飛翔体の座標[deg^2]を求めよ。
(この情報はフィクションであり、架空のものです。実際の軍事情報とは関係ありません)

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

最後の注意書きが寒い
だったら最初から固有名詞出さなきゃ良いのに

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/09(日) 16:39:33.98

>>908
防衛装備移転三原則に反する恐れがあるので、このお題は撤回致します。回答しないで下さい。

**デフォルトの名無しさん** · 2023/07/09(日) 18:30:16.18

自分の書き込みにそんなに勝ちがあると思ってるのかこいつ
スベってるよ

**デフォルトの名無しさん** · 2023/07/09(日) 18:54:23.02

>>875
Kotlin
https://paiza.io/projects/GqQNgKH7i2A0Vn4TIlLENQ

**デフォルトの名無しさん** · 2023/07/09(日) 21:17:36.11

>>884
haskell
https://ideone.com/6hUFuO

**638** · 2023/07/10(月) 15:31:23.20

>>897 Perl5、見やすくするためインデントは全角スペースに置換してあります。
　たまには回答して進ぜるけど、もしかして回答欲しくて簡単なお題だしたん？

use Math::Trig qw{pi deg2rad spherical_to_cartesian};
use constant ra => 6378;
for (<DATA>) {
　($lo, $la) = map{deg2rad($_)} /(-?\d+)/g;
　# 球面→cartesian座標変換library使用
　$phy = pi / 2.0 - $lo;
　($x, $y, $z)　= spherical_to_cartesian(ra, $la, $phy);
　printf "L) (%.3f, %.3f)[rad] -> (%.1f, %.1f, %.1f)\n", $lo, $la, $x, $y, $z;
　# 手書き
　$ralo = ra * cos($lo);
　printf "H) (%.3f, %.3f)[rad] -> (%.1f, %.1f, %.1f)\n", $lo, $la,
　　$ralo * cos($la),　$ralo * sin($la), ra * sin($lo);
}
__DATA__
(0, 0)
(90, 0)
(45, 0)
(45, -45)

実行結果
$ perl 21_897_緯度経度→xyz.pl
L) (0.000, 0.000)[rad] -> (6378.0, 0.0, 0.0)
H) (0.000, 0.000)[rad] -> (6378.0, 0.0, 0.0)
L) (1.571, 0.000)[rad] -> (0.0, 0.0, 6378.0)
H) (1.571, 0.000)[rad] -> (0.0, 0.0, 6378.0)
L) (0.785, 0.000)[rad] -> (4509.9, 0.0, 4509.9)
H) (0.785, 0.000)[rad] -> (4509.9, 0.0, 4509.9)
L) (0.785, -0.785)[rad] -> (3189.0, -3189.0, 4509.9)
H) (0.785, -0.785)[rad] -> (3189.0, -3189.0, 4509.9)

**デフォルトの名無しさん** · 2023/07/11(火) 15:24:57.95

お題：神経質なipow10()
整数を引数とし、その10のべき乗を浮動小数点数で返す関数を書け。
結果が浮動小数点数で厳密に表現出来ない場合(10の-1乗=0.1とか)、
浮動小数点数として、(結果を)厳密に最近値に丸めた値を返すこと。

**デフォルトの名無しさん** · 2023/07/11(火) 15:51:15.42

高校時代全く数学できなかったんだろうなぁ

**915** · 2023/07/12(水) 01:10:01.78

正の整数の範囲だけなら、CPythonのmath.pow()もそう悪くないんだ…
(10**23と10**210が外れ)。
tps://sagecell.sagemath.org/?z=eJxdjUEKwyAURPeB3GG601REt4WeRVxo86H6xQhNb18lLaWd5Zt5TKycsD03UCpcG-KdfXOUI89THF3ybf2UhR-dcgWBMqrPtyC-gk5-d9a4sBecYeVlntBDcXjCGm0USOJ0PU46wbJ08t6NlEq5CVI_hl7DLqT6sw4qXzvIOGU=&lang=python&interacts=eJyLjgUAARUAuQ==

**デフォルトの名無しさん** · 2023/07/12(水) 09:36:32.37

この手の計算ライブラリではあるある
真値が無理数の場合次善策として“最近の値”を出す事、当然それ出してくれると思いがちだけどそんな値出してくれるライブラリなどほとんどない
原理的に出せないわけではない、適当にレジスタの精度を設定して上から、下からの近似値を出す、求める桁数まで一致してればそれが“最近”、一致してなければ精度上げて再計算‥を繰り返せば必ず最後は一致する‥でもそのために貴重な時間リソースが無駄になる、なので普通は“精度は±××、上からの近似の中では最良”くらいが関の山、それすら守ってなくても普通、ましてや“小数第何位までは確実に合ってる”などとは全く期待できない
そのあたりの“実用上それで十分、それ以上の事やって誰得？”と割り切れるまでが一週目

**915** · 2023/07/12(水) 15:28:21.53

"1e23" とかの文字列を構成して、Cのstrtod()やsscand()的な関数を使って変換する分には誤差が出ないっぽいのですけど
(これの誤差が出るライブラリは駆逐されたらしい)、
これはこれで「負け」た気分になるのが…ｗ

**915** · 2023/07/12(水) 15:35:55.97

>>919
sscanfですたorz

**デフォルトの名無しさん** · 2023/07/12(水) 17:47:05.90

分母が2べきでない限り内部的に分母が2べきの有理数で保持するタイプの浮動小数は“定数”を10進のリテラルで与えるとそこで誤差が出たり、あるいはその逆もある、いわゆる基数変換誤差
多くの場合、基数変換誤差は計算の最初と最後でしかでないのでそもそもあまり話題にはならない、大昔のインタプリタ言語とかだったら計算結果を毎回10進表示に変換して文字列として保持してるようなやつもあっただろうけど、もう流石にそのタイプは駆逐されてるんじゃなかろか
大体そもそも他の組み込み関数の誤差評価がもっと大甘なのにそこだけ頑張っても意味がない

**デフォルトの名無しさん** · 2023/07/12(水) 18:35:23.52

COBOLはまだまだ健在ですよ

**915** · 2023/07/13(木) 05:18:24.50

何で「負け」なのかと云うと、
IEEE754的な意味での「再現性」を担保する為に
(binary64の数値を有効桁17桁で10進文字列に変換して、
それをstrtod()とかするとbit perfectで元に戻るってやつ)、
strtod()とかは内部で多倍長演算をやってるので…。
(glibcの実装(GNU MPに丸投げ？)と、ルーセントの中の人
が書いたやつ(そのほか)の2系統あり)。

…なんとかズル出来ないのか？ｗ

**915** · 2023/07/13(木) 05:22:25.37

要するに牛刀割鶏感がでかい
いまさら気にしても仕方がなくもないけど

**デフォルトの名無しさん** · 2023/07/13(木) 05:46:44.20

そもそもコレ変数へ値をそんな自由に“セット”する方法がないんだよな
例えば値が10^(-30)として二進展開して

2^(-30)
=1.100_0010_1000_0010_0101_1111_...×2^(-103)

という巡回小数になる
単精度での内部表示は

0_00011000_100_0010_1000_0010_0110_0000

になる、なるとわかってもこの値を変数にセットす方法がない
おそらく整数0xc68660をセットして2^24で割ればいける時もあるかもしれないけどそれとて言語の保証外、浮動小数点型の変数に何か値をセットしてそれを2べきの整数で割ったとて、いくら“割る数”が2べきであっても仮数部わ変わらず指数部だけ変わってくれる保証をしてる言語の方が少ない
実験すればそれでうまくいくかどうかわかるかもしれないけどregulationでそれでうまくいくと保証されてるわけではない、せいぜい“多分うまく行ってる”くらいしかわからない
Cとかなら[char]型でa[0]a[1]a[2]a[3]に値入れてfloat &bにb=aするとかできるかもしれないけど最近の型にうるさい言語だとそれとてできない

**デフォルトの名無しさん** · 2023/07/13(木) 06:10:46.95

0xc28260÷2^24乗ね
この計算をさせて本当に内部的に変数に0_00011000_100_0010_1000_0010_0110_0000
がセットされたかどうか確認する方法もない
もう一回2^24かけて0xc28260かけて戻ってくるかチェックするとかして間接的に確かめるしかない
Cとかputhonとかならできるのかもしれないけど

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/13(木) 21:54:33.63

お題: 入力として32ビット整数のビットマスクが与えられる。
ビットマスクに含まれる有効なビットの組み合わせをブルートフォースせよ。

例)
0x13
→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x45
→(0x1, 0x4, 0x5, 0x40, 0x41, 0x44, 0x45).
0x92C
→？？？

**デフォルトの名無しさん** · 2023/07/13(木) 22:05:50.51

>>927
>→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x0 は含まないルール？

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/13(木) 22:06:44.17

>>928
あ、ゼロ忘れてた。ゼロもお願いします。

**デフォルトの名無しさん** · 2023/07/13(木) 23:34:46.42

>>927
Haskell
https://ideone.com/FqDur8

**デフォルトの名無しさん** · 2023/07/13(木) 23:41:47.50

sort意味なしorz

**デフォルトの名無しさん** · 2023/07/14(金) 00:29:53.20

>>927
R
https://www.ideone.com/gL23rg

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/14(金) 12:13:37.67

お題: ぶつかる迷路。

入力として与えられたフロア図の表すフロアのA地点にロボットRがあり、B地点にロボットSがある。しかし、RとSは同時に同じ場所を占有することはできない（衝突する）。

フロア図の例（上が北）:
＃＃＃＃＃＃＃
＃＿Ａ＿＿＿＃
＃＿＃＿＃＃＃
＃＿＃＿＿Ｂ＃
＃＃＃＃＃＃＃

＃：カベ、＿：空きスペース、Ａ：A地点、B：B地点。

ロボットRとSは次の5つのコマンドが使用できる。

コマンド0：一つ待つ。
コマンド1：西に1つ動く。
コマンド2：東に1つ動く。
コマンド3：北に1つ動く。
コマンド4：南に1つ動く。

RがB地点に、SがA地点に到達するまで、RとSを最短のコマンドリストで動かせ。
到達できないときは「ERROR」と表示して終了せよ。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/07/14(金) 13:10:06.13

>>933

出力は題意のコマンドリスト２つです。

回答例)
((2, 2, 0, 0, 1, 4, 4, 2, 2), (1, 1, 3, 3, 1))

**638** · 2023/07/14(金) 16:41:43.17

>>927　Perl5

for (qw(0x13 0x45 0x92C)) {
　$n = eval;
　@a = map{sprintf "0x%x", $_} grep{($_ & $n) == $_} 0..$n;
　print "$_: @a\n";
}

※インデントは全角スペースに置換してあります。

実行結果
$ perl 21_927.pl
0x13: 0x0 0x1 0x2 0x3 0x10 0x11 0x12 0x13
0x45: 0x0 0x1 0x4 0x5 0x40 0x41 0x44 0x45
0x92C: 0x0 0x4 0x8 0xc 0x20 0x24 0x28 0x2c 0x100 0x104 0x108 0x10c 0x120 0x124 0x128 0x12c 0x800 0x804 0x808 0x80c 0x820 0x824 0x828 0x82c 0x900 0x904 0x908 0x90c 0x920 0x924 0x928 0x92c

**638** · 2023/07/14(金) 18:16:11.02

>>935　これだとコード書くの安直で楽だけど、効率悪いんだよね、特に値が大きいとき。
　効率に配慮すると、こうか↓

sub f {
　if (@_) {
　　my $b = shift;
　　@_ ? map{$_, $_ | 2**$b} f(@_) : ($_, $_ | 2**$b);
　}
}
for (qw(0x13 0x45 0x92C)) {
　$n = eval;
　@b = grep{$n & 2**$_} 0..31;
　@s = map{sprintf "0x%x", $_} f(@b);
　print "$_: @s\n";
}

※インデントは全角スペースで置換してありま

実行結果:
$ perl 21_927_effective_bit_mask.pl
0x13: 0x0 0x1 0x2 0x3 0x10 0x11 0x12 0x13
0x45: 0x0 0x1 0x4 0x5 0x40 0x41 0x44 0x45
0x92C: 0x0 0x4 0x8 0xc 0x20 0x24 0x28 0x2c 0x100 0x104 0x108 0x10c 0x120 0x124 0x128 0x12c 0x800 0x804 0x808 0x80c 0x820 0x824 0x828 0x82c 0x900 0x904 0x908 0x90c 0x920 0x924 0x928 0x92c

**915** · 2023/07/14(金) 19:28:34.12

仕事で書いたら怒られるやつｗ
(プラットホームや、ライブラリのバージョンとかに依存する可能性があるから)
tps://sagecell.sagemath.org/?z=eJy1krFqwzAQhneD3-FKhsjguFJsUmooHdK1UOjQsTi27BzYklEUkrxEpy6FQpcOfoi-Tto-RqTaISElzdSbdHe679fxK1eygirRU8CqlkpDLReuk9tqxlOsknLbuGlT13GdjOeA5iKjBL3YdcCEYaQG0mU20mTGYcBGYQw9GN-t9FSKMGAsiMgDikwuZjCKJqi93YgNxfVcCWDcjh7QhoYFJ2hwDvdJwW_tTmNelqREMV_CchRBUeIkhetjgsNfcozG_yjH6IFeSKOTekdgZrTtdBXjDmE0oD6gZy3rwef763fz8fXcrJ_e1i_NvouPtZJa6lXNd352nLyUiSad94QYHmG-Z6neDzeXChBQgEpEwckgpBe-2eNyi8G9nwJnV38I2qgVCk3si9tTP5OC970Noga8Nw==&lang=python&interacts=eJyLjgUAARUAuQ==

**デフォルトの名無しさん** · 2023/07/14(金) 22:15:33.11

>>933
・を「一つ待つ」として、最短のコマンドリストは>>934の

R: →→・・←↓↓→→
S: ←←↑↑←

の他にも、Sは同上で

R: →・・→←↓↓→→
R: →↓↑→←↓↓→→
R: →→←→←↓↓→→
R: →→→←←↓↓→→

もあり、あまりすっきりしない問題なので解く気が起きないな。

**蟻人間** ◆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