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

レス数が950を超えています。1000を超えると書き込みができなくなります。
2022/11/13(日) 19:00:36.84ID:ZCYlhUwL
プログラミングのお題スレです。

【出題と回答例】
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/01(土) 11:05:28.08ID:6ckc7dLG
>>863
キャラコードゼロになってるよ。
2023/07/01(土) 11:06:23.46ID:6ckc7dLG
>>866
まとめた方が早いだろ。
2023/07/01(土) 13:53:06.23ID:2N653o6Y
大学でちゃんと講義受けてたのかどうか知らんけど

各数値は小数点以下2桁まで表示せよ。

もうこう言う言い回しをするのはやめた方がいい
870デフォルトの名無しさん
垢版 |
2023/07/01(土) 16:42:08.76ID:J+nsogj/
>>867
初期化ミスってた。こっそり直しておいた。
871デフォルトの名無しさん
垢版 |
2023/07/01(土) 20:22:54.21ID:OW14MEis
>>864
例は
(1, 0, 0)→(Fire()).
(0, 0, 2)→(Turn(0, π/2), Fire()).
(0, 3, 0)→(Turn(0, -π/2), Fire()).
(1, 2, 1)→???
じゃないの?

だとしてR
www.ideone.com/ddFJ7j
2023/07/01(土) 20:51:13.02ID:6ckc7dLG
>>871
ごめんごめん、正しくは右手系でz軸が上向き。訂正。

(1, 0, 0)→(Fire()).
(0, 0, 2)→(Turn(0, π/2), Fire()).
(0, 3, 0)→(Turn(-π/2, -π/2), Fire()).

砲塔の向きを記憶すると書いてある。また(0, 3, 0)でy軸方向を向くのにPanが必要だから、こうだろう。すみません。
873デフォルトの名無しさん
垢版 |
2023/07/01(土) 21:05:37.20ID:OW14MEis
>>872
(0, 0, 2)つまり真上から(0, 3, 0)つまり水平真北へ向きを変えるには、水平方向回転は不要で
下向き90度の垂直方向回転だけでできるんじゃないの?

もしそうでなく>>872のように水平回転も必要という仕様なら、>>871の6行目を
　　Pan <- c(0, -diff(atan2(P[, 2], P[, 1])))
に変えれば良い。
2023/07/01(土) 21:13:00.67ID:6ckc7dLG
>>873
うん、水平回転も必要。真上を向いていると垂直方向の意味がわからないからね。
2023/07/02(日) 17:45:16.73ID:bkSdQ5Ko
お題：半角スペースで区切られた単語が並ぶ文字列がある
この文字列を単語に分割してソートして配列にして返す関数を実装せよ
2023/07/02(日) 18:54:51.40ID:Tqn0qozx
>> 875
Haskell
https://ideone.com/7CWlDd
877デフォルトの名無しさん
垢版 |
2023/07/02(日) 20:55:09.72ID:SNPDeW60
>>875
PowerShell

function ExtractAndSortWords($s) {[RegEx]::Matches($s, "\w+") |% {$_.value} | sort}

ExtractAndSortWords "The quick brown fox jumped over the lazy dog." |% {$_}

[実行結果]
brown
dog
fox
jumped
lazy
over
quick
The
the
878638
垢版 |
2023/07/03(月) 00:25:45.25ID:HgLiPfoF
>>875 Perl5、出現した単語の重複を許容するか、あるいはuniqにするか明確でないけど、下記は許容する方法

sub f { sort shift =~ /(\w+)/g }


実行結果
https://ideone.com/FjaIX7
2023/07/03(月) 14:52:44.63ID:JGR8BE7g
お題：放物運動の飛距離。

重量5[kg]の物体が、入力として与えられた仰角[deg]と初速[m/s]で発射され、自由落下する。
空気抵抗は、速度に比例する大きさの力とする。地平は平面と見なす。
時刻t[s]に対してdt=0.1[s]とし、台形求積法を使用するものとする。

空気抵抗係数 k=0.24[kg/m].
重力加速度 g=9.8[m/s^2].

空気抵抗のある場合の飛距離と、空気抵抗のない場合の飛距離を求め、比較せよ。

入力例）
(30, 8)→???
(45, 8)→???
(60, 8)→???
(60, 12)→???
880デフォルトの名無しさん
垢版 |
2023/07/03(月) 23:48:04.74ID:+izrFQr7
>>879
時間刻み幅が粗すぎて着地時刻を適切に判定できないから、飛距離も求められない。
軌跡のグラフを描いて大体の位置を読み取るしかない。

R
www.mycompiler.io/view/K4qPKREzkRI

[コードを実行] ボタンを押すとグラフが表示される。白丸が空気抵抗なし、黒丸があり。
2023/07/04(火) 00:24:53.30ID:xKkoXb5c
>>880
天才がおる。
君ならICBMの計算も出来そうだ。
ちょっと試してみようか。
882デフォルトの名無しさん
垢版 |
2023/07/04(火) 18:50:11.09ID:o8LQKs7n
>>875
Kotlin

なんとなく拡張関数で作った。まあでもsplit使っちゃってて肝心な所は自分では何も書いてないな。

https://paiza.io/projects/j1jz6yNCVfWZLIv8d5RFjA
883デフォルトの名無しさん
垢版 |
2023/07/04(火) 22:31:05.24ID:0YaO2gnD
>>880の14行目は
　　a <- c(0, -g) - k * (v + a * dt) ^ 2 / m
でなく
　　a <- c(0, -g) - k * (v + aprev * dt) ^ 2 / m
の方が良かった。精度が少しだけ上がる。
884デフォルトの名無しさん
垢版 |
2023/07/04(火) 22:31:52.02ID:0YaO2gnD
お題：62進数の計算

62進数の整数の加・減・乗算から成る式の文字列が入力される。計算結果を62進数の文字列で出力せよ。
ただし、10進数の0～9, 10～35, 36～61に相当する数字にはそれぞれ0～9, A～Z, a～zを用い、
計算の途中経過と最終結果は64ビット符号付き整数の範囲内に収まると想定して良い。

[例]
入力: 123 + ABC
出力: 123 + ABC = BDF

[問題]
2023-7-4
printf - (Hello + world)
Windows * 11
The - quick - brown * fox + jumped - over + the - lazy * dog
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ
2023/07/05(水) 00:02:51.51ID:f5gUiL1f
>>884

Haskell
https://ideone.com/eguY57
886デフォルトの名無しさん
垢版 |
2023/07/05(水) 16:19:03.51ID:eWV2G44w
>>884
Perl

計算面倒だから文字列の状態で数値部分を10進数に変換してから eval 使うという手抜きプログラム。
その代わり割り算や割った余りも出せる。( / と % )。ただし結果の出力が整数でしか出ない。
結果が負の値になってもマイナス付けて出せるようにした。

https://paiza.io/projects/zf3aXm60nlM59-TjhoiEyQ
887デフォルトの名無しさん
垢版 |
2023/07/05(水) 16:32:04.27ID:5Lz4OcyC
計算結果を62進数の文字列で出力せよ。
888デフォルトの名無しさん
垢版 |
2023/07/05(水) 17:55:35.60ID:eWV2G44w
出るよ。
889884
垢版 |
2023/07/05(水) 22:10:28.44ID:uOCDoNkY
>>886
>Perl
>計算面倒だから文字列の状態で数値部分を10進数に変換してから eval 使うという手抜きプログラム

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

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

RubyとPythonもevalを使えるので似たように書けるはず。なんかPとRで始まる言語ばかりだな。
890638
垢版 |
2023/07/05(水) 23:15:53.66ID:RHYedEAt
Parser generator使って自前で構文解析＆計算させようとして苦戦していた俺涙目
2023/07/06(木) 00:20:52.37ID:8lEmyrt+
>>890
オレもParser generatorでやろうと思ってるよ
eval なんか使えないからね
でも日曜日までまとまった時間ないからまたまた超遅レスになる予定
2023/07/06(木) 20:52:00.35ID:qCiseCT1
お題: 緯度と経度から距離と方位を求める。

地球が球体であると仮定し、地球の半径を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
893デフォルトの名無しさん
垢版 |
2023/07/06(木) 23:43:20.91ID:jglGRjQ9
>>892
R
www.ideone.com/S5Jubo
2023/07/07(金) 01:04:00.47ID:wU+5w+HX
>>892
haskell
角が合わんorz寝よ

https://ideone.com/8Rk7Fp
895デフォルトの名無しさん
垢版 |
2023/07/07(金) 11:02:22.14ID:UaYcujNV
>>892
完全にぴったり地球の表裏側2点の場合の方位角は？
2023/07/07(金) 13:25:49.78ID:WCk9ojNW
>>895
定義しない、または任意。
2023/07/08(土) 00:02:54.35ID:pNCQQCuc
お題: 緯度経度を三次元座標に変換。

地球を半径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)→???
898638
垢版 |
2023/07/08(土) 18:46:12.49ID:fDz284w7
>>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
899638
垢版 |
2023/07/08(土) 18:47:35.93ID:fDz284w7
>>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などのオンライン
　プログラムサービスには多分インストールされていなくて動作しないんじゃないかなともいます
900デフォルトの名無しさん
垢版 |
2023/07/08(土) 21:33:55.36ID:CSKg1TdC
>>897
R
www.ideone.com/RHXhIq
変哲は、普通に書くとsinとcosが合わせて4個か5個必要な所を2個にしたことだけ。
901884
垢版 |
2023/07/08(土) 21:40:41.86ID:CSKg1TdC
>>898
ならば出題者からもeval任せでない自前の実装プログラムをどうぞ。

C
www.ideone.com/erwpI4

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

C++
www.ideone.com/MFEuc6

Cプログラムのグローバル変数と下請け関数をクラスに入れて隠蔽した。readch関数のかわりに、
空白を読み飛ばすようにオーバーライドした++演算子を使ってすっきり書いた。
2023/07/08(土) 22:03:59.24ID:+KTtE1Ht
イヤ、スクラッチで書いても意味ないでしょ？
903638
垢版 |
2023/07/08(土) 22:09:14.33ID:fDz284w7
四則演算の式評価なら１数十stepでParserを手書きできるということでそれもありじゃね？
2023/07/08(土) 22:12:28.67ID:+KTtE1Ht
うーん、まぁそれはそうも言えるかな
しかしその手の話は結局“車輪の再発明”してるだけだからな
parsingみたいに重たい処理は可能なら既存の実績のあるparser generator使えるならそれ使うのか本筋な気はするけどね
初学者がparsingの基礎の練習問題として使うのはありかな
905638
垢版 |
2023/07/08(土) 22:16:05.45ID:fDz284w7
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.55ID:LeSv46FO
まぁ物によるだろうけどほとんどのプログラミング言語は最低でも文脈依存文法以上を解析できるパーサーでないと解析できない
ましてや今日のコンパイラは何行目の何文字目がおかしいのか、それがどんな間違いなのかも示して修正案まで出してくれる、そこまでの作業を一般的なパーサー生成機に落とし込むこと1から考えるよりはパーサーそのもの自分で作る方が早いかもしれんわな
ただ今回のは四則演算とカッコだけなんだから文脈自由文法の解析機で解析できるから素人が作った解析機を使わない意味は実用上はまずない、まさに車輪の再発明の典型になってしまう
しかしまぁここはある意味“再発明を楽しむスレ”でもあるからなw
2023/07/09(日) 07:18:47.36ID:LeSv46FO
専門家の作った解析機を使わない意味はないだorz
まぁただパーサー生成機の作ったパーサーはもちろん「どんな文法でも対応できる」ために効率を犠牲にする場合もあるので速度とかをギチギチにチューンするつもりなら意味はあるか
実際今回のも()と+,-,×だけやからな
2023/07/09(日) 09:04:09.08ID:S0HvsOQY
お題: 飛翔体のシミュレーション。
クレムリン(北緯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.36ID:x2TUQyIt
最後の注意書きが寒い
だったら最初から固有名詞出さなきゃ良いのに
2023/07/09(日) 16:39:33.98ID:vyR210yR
>>908
防衛装備移転三原則に反する恐れがあるので、このお題は撤回致します。回答しないで下さい。
2023/07/09(日) 18:30:16.18ID:trhah0Kt
自分の書き込みにそんなに勝ちがあると思ってるのかこいつ
スベってるよ
912デフォルトの名無しさん
垢版 |
2023/07/09(日) 18:54:23.02ID:GCtDZZpJ
>>875
Kotlin
https://paiza.io/projects/GqQNgKH7i2A0Vn4TIlLENQ
2023/07/09(日) 21:17:36.11ID:HwvqYkKm
>>884
haskell
https://ideone.com/6hUFuO
914638
垢版 |
2023/07/10(月) 15:31:23.20ID:FUofuCtL
>>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.95ID:zBgA5NaS
お題：神経質なipow10()
整数を引数とし、その10のべき乗を浮動小数点数で返す関数を書け。
結果が浮動小数点数で厳密に表現出来ない場合(10の-1乗=0.1とか)、
浮動小数点数として、(結果を)厳密に最近値に丸めた値を返すこと。
2023/07/11(火) 15:51:15.42ID:nXEJ21bU
高校時代全く数学できなかったんだろうなぁ
917915
垢版 |
2023/07/12(水) 01:10:01.78ID:OtxkddAG
正の整数の範囲だけなら、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.37ID:OzccPY9R
この手の計算ライブラリではあるある
真値が無理数の場合次善策として“最近の値”を出す事、当然それ出してくれると思いがちだけどそんな値出してくれるライブラリなどほとんどない
原理的に出せないわけではない、適当にレジスタの精度を設定して上から、下からの近似値を出す、求める桁数まで一致してればそれが“最近”、一致してなければ精度上げて再計算‥を繰り返せば必ず最後は一致する‥でもそのために貴重な時間リソースが無駄になる、なので普通は“精度は±××、上からの近似の中では最良”くらいが関の山、それすら守ってなくても普通、ましてや“小数第何位までは確実に合ってる”などとは全く期待できない
そのあたりの“実用上それで十分、それ以上の事やって誰得？”と割り切れるまでが一週目
919915
垢版 |
2023/07/12(水) 15:28:21.53ID:6VP/LOOe
"1e23" とかの文字列を構成して、Cのstrtod()やsscand()的な関数を使って変換する分には誤差が出ないっぽいのですけど
(これの誤差が出るライブラリは駆逐されたらしい)、
これはこれで「負け」た気分になるのが…ｗ
920915
垢版 |
2023/07/12(水) 15:35:55.97ID:9l9n30C9
>>919
sscanfですたorz
921デフォルトの名無しさん
垢版 |
2023/07/12(水) 17:47:05.90ID:MwP3bMsR
分母が2べきでない限り内部的に分母が2べきの有理数で保持するタイプの浮動小数は“定数”を10進のリテラルで与えるとそこで誤差が出たり、あるいはその逆もある、いわゆる基数変換誤差
多くの場合、基数変換誤差は計算の最初と最後でしかでないのでそもそもあまり話題にはならない、大昔のインタプリタ言語とかだったら計算結果を毎回10進表示に変換して文字列として保持してるようなやつもあっただろうけど、もう流石にそのタイプは駆逐されてるんじゃなかろか
大体そもそも他の組み込み関数の誤差評価がもっと大甘なのにそこだけ頑張っても意味がない
2023/07/12(水) 18:35:23.52ID:wgfcR5Sc
COBOLはまだまだ健在ですよ
923915
垢版 |
2023/07/13(木) 05:18:24.50ID:102DBCHI
何で「負け」なのかと云うと、
IEEE754的な意味での「再現性」を担保する為に
(binary64の数値を有効桁17桁で10進文字列に変換して、
それをstrtod()とかするとbit perfectで元に戻るってやつ)、
strtod()とかは内部で多倍長演算をやってるので…。
(glibcの実装(GNU MPに丸投げ？)と、ルーセントの中の人
が書いたやつ(そのほか)の2系統あり)。

…なんとかズル出来ないのか？ｗ
924915
垢版 |
2023/07/13(木) 05:22:25.37ID:102DBCHI
要するに牛刀割鶏感がでかい
いまさら気にしても仕方がなくもないけど
925デフォルトの名無しさん
垢版 |
2023/07/13(木) 05:46:44.20ID:UahP4Rhb
そもそもコレ変数へ値をそんな自由に“セット”する方法がないんだよな
例えば値が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するとかできるかもしれないけど最近の型にうるさい言語だとそれとてできない
926デフォルトの名無しさん
垢版 |
2023/07/13(木) 06:10:46.95ID:FkuVPs5p
0xc28260÷2^24乗ね
この計算をさせて本当に内部的に変数に0_00011000_100_0010_1000_0010_0110_0000
がセットされたかどうか確認する方法もない
もう一回2^24かけて0xc28260かけて戻ってくるかチェックするとかして間接的に確かめるしかない
Cとかputhonとかならできるのかもしれないけど
2023/07/13(木) 21:54:33.63ID:pFytGTyV
お題: 入力として32ビット整数のビットマスクが与えられる。
ビットマスクに含まれる有効なビットの組み合わせをブルートフォースせよ。

例)
0x13
→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x45
→(0x1, 0x4, 0x5, 0x40, 0x41, 0x44, 0x45).
0x92C
→？？？
2023/07/13(木) 22:05:50.51ID:zo6OijSK
>>927
>→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x0 は含まないルール？
2023/07/13(木) 22:06:44.17ID:pFytGTyV
>>928
あ、ゼロ忘れてた。ゼロもお願いします。
930デフォルトの名無しさん
垢版 |
2023/07/13(木) 23:34:46.42ID:Gk3QqB7S
>>927
Haskell
https://ideone.com/FqDur8
931デフォルトの名無しさん
垢版 |
2023/07/13(木) 23:41:47.50ID:qsjHWAGp
sort意味なしorz
932デフォルトの名無しさん
垢版 |
2023/07/14(金) 00:29:53.20ID:iQAPuZ6f
>>927
R
https://www.ideone.com/gL23rg
2023/07/14(金) 12:13:37.67ID:i4ROjxmQ
お題: ぶつかる迷路。

入力として与えられたフロア図の表すフロアの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」と表示して終了せよ。
2023/07/14(金) 13:10:06.13ID:i4ROjxmQ
>>933

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

回答例)
((2, 2, 0, 0, 1, 4, 4, 2, 2), (1, 1, 3, 3, 1))
935638
垢版 |
2023/07/14(金) 16:41:43.17ID:9h33JNqm
>>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
936638
垢版 |
2023/07/14(金) 18:16:11.02ID:9h33JNqm
>>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
937915
垢版 |
2023/07/14(金) 19:28:34.12ID:Q8y8QZ/7
仕事で書いたら怒られるやつｗ
(プラットホームや、ライブラリのバージョンとかに依存する可能性があるから)
tps://sagecell.sagemath.org/?z=eJy1krFqwzAQhneD3-FKhsjguFJsUmooHdK1UOjQsTi27BzYklEUkrxEpy6FQpcOfoi-Tto-RqTaISElzdSbdHe679fxK1eygirRU8CqlkpDLReuk9tqxlOsknLbuGlT13GdjOeA5iKjBL3YdcCEYaQG0mU20mTGYcBGYQw9GN-t9FSKMGAsiMgDikwuZjCKJqi93YgNxfVcCWDcjh7QhoYFJ2hwDvdJwW_tTmNelqREMV_CchRBUeIkhetjgsNfcozG_yjH6IFeSKOTekdgZrTtdBXjDmE0oD6gZy3rwef763fz8fXcrJ_e1i_NvouPtZJa6lXNd352nLyUiSad94QYHmG-Z6neDzeXChBQgEpEwckgpBe-2eNyi8G9nwJnV38I2qgVCk3si9tTP5OC970Noga8Nw==&lang=python&interacts=eJyLjgUAARUAuQ==
938デフォルトの名無しさん
垢版 |
2023/07/14(金) 22:15:33.11ID:iQAPuZ6f
>>933
・を「一つ待つ」として、最短のコマンドリストは>>934の

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

の他にも、Sは同上で

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

もあり、あまりすっきりしない問題なので解く気が起きないな。
2023/07/14(金) 22:26:17.98ID:PGyidJ8C
>>938
移動量も最短にした方がいいか？
2023/07/14(金) 22:31:38.64ID:PGyidJ8C
>>939
移動量も最短にする。また、動けるとき、かつ待てるときは待つよりも先に動く方を優先するという条件を追加します。
2023/07/14(金) 22:44:41.18ID:PGyidJ8C
>>940
さらに次の3つの条件を追加します。
西か東か迷った場合は西を優先します。
北か南か迷った場合は北を優先します。
南/北の向きか東/西の向きかを迷った場合は東/西の向きを優先します。
2023/07/15(土) 03:29:30.91ID:deBIZu3e
>>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 )
943デフォルトの名無しさん
垢版 |
2023/07/15(土) 08:05:25.03ID:DpclFvGX
>>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])
944915
垢版 |
2023/07/15(土) 10:11:42.89ID:HHeu+C79
今からIEEE754に準拠してない処理系が制作される事は無いでしょうから
(ホビーや学習用途は別ね)、
今日の処理系で、2のべき乗での割り算で仮数部が変わるって事は
無いと思われます(アンダーフローやオーバーフローは除外)。

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

>>943
FORTRANならEQUIVALENCE文で…
945デフォルトの名無しさん
垢版 |
2023/07/15(土) 16:01:33.91ID:STkOcJIm
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ビット移動
946デフォルトの名無しさん
垢版 |
2023/07/15(土) 16:07:59.58ID:STkOcJIm
そもそも浮動小数点ライブラリなら
x^y = exp( y * log 2 )
で実装してるんじゃないかな
そもそものexpやlogが“最近値”を与えてくれることなど規格にはないやろ
それは数値計算の理論勉強してたらすぐわかる、メチャクチャ難しくてほとんど実装不能になってしまう
だから規格上は“±その周辺の値で表示できる値の中では最良”、すなわち“表現可能な上界の最小値または表現可能な下界の最大値”、それならギリギリ実用可能な速度くらいは出せるけど、それとて難しい、そこまで今のライブラリが保証してくれてるかあやしい
まぁその手のライブラリ使わずに“最近値”を出すことはメチャクチャ手間かかるけどできなくはない、しかしそれが限界、その値を変数に確実にセットする方法がない
947デフォルトの名無しさん
垢版 |
2023/07/15(土) 16:25:05.71ID:P30TlPMe
x^y = exp( y log (x))ね
この計算に入る前に「x=2, yが整数であるかどうか検査する、その場合には仮数部は弄らず指数部だけyに応じて増減させる」なんて処理してるライブラリはないやろ
有無を言わさずy log(x)計算、→exp計算、丸め誤差上等でやってるやろ、そこで単精度計算ならちょっと余裕もってビット幅大きめのアキュムレータに入れてるかもしれんけどどんなに大きな精度のアキュムレーターを用意したとて出てくる値が“最近値”になる保証はない、そこまで保証しようとすると恐ろしくコストがかかってしまう
汎用の数値計算ライブラリでそこまで保証されてるわけないと思う、単精度計算なら±2^(-24)=単精度の内部表現で可能な幅までは保証するのが限界だと思う、それとてかなりコストがかかるし
まぁどのみち2^(-23)以上の精度が必要ならそもそも言語の標準ライブラリなんか使わんからな
948915
垢版 |
2023/07/15(土) 18:15:18.86ID:HHeu+C79
>>946
規格で正確な値(を最近値に丸めたもの)を求められてるのは
加減乗除とsqrt()とfma()でしたっけ？
pow()は、glibcが誤差0.523ulpとか(0.5ulpが限界値)、
イイ線行ってるそうですね。
tps://members.loria.fr/PZimmermann/papers/accuracy.pdf
949デフォルトの名無しさん
垢版 |
2023/07/15(土) 21:46:41.49ID:0NaOek0L
おお、llvmすげぇ
950915
垢版 |
2023/07/15(土) 23:31:05.73ID:HHeu+C79
>>949
llvmの多くの項目がNA(non available)なのは、
実装されてないからではないかと。

この中では、OpenLibmがfdlibmの「血」を残してる方なのかな？
tps://www.netlib.org/fdlibm/
951デフォルトの名無しさん
垢版 |
2023/07/16(日) 00:22:02.04ID:Cy0F/L8f
うん、多分実装されてない分は自分でやれと
実装されてるところは軒並み0.5
まぁこれも本当に確率100%で必ず最近値出すんではなくて外れる確率が0.000001%とかなんだろうな
例えば単精度演算は毎回倍精度にキャストして計算してから丸めればほぼほぼ最近値にならない確率0.0000001%とかになるからな
逆に言えば他のライブラリはその手のキャストも何もしないで“丸め誤差上等”でやってるんやろな
952915
垢版 |
2023/07/16(日) 01:29:25.23ID:34tdZpnq
>>951
ちゃんとやろうとすると、CRlibmみたいに、部分的にでも
6倍精度とかで計算しないとならないっぽいです。
glibcのexp()は768bitで計算する場合があるそうで。

…世間的には、それ程の精度を求めない用途もあって、
実際、libmのhypot()(じゃなくてもいいのですが)が遅いので自分で
実装しますたと云う報告がネット上でも散見されます
(もちろん精度は落ちる)
953デフォルトの名無しさん
垢版 |
2023/07/16(日) 08:49:44.74ID:Q2/lNXhi
まじですか
768bitって何をどう計算してるんやろ？
結果が24bitで768bitなら求める答えの72倍のアキュムレーター使うのかな？
そんな事ないよな、アキュムレータは48bitくらいで36回計算するからのべ768bitとかいう事なのかな？
まぁそれだけの事やって「末尾の最後の1ビットの正確性を求める意味あんのか問題」は発生するわな
”みんなが使う汎用ライブラリ”だとどうしてもそういう“誰も求めてない精度”に無意味にこだわってしまう部分があるんかも
954915
垢版 |
2023/07/16(日) 10:57:33.80ID:34tdZpnq
>>953
丸めて切り上げ/切り捨てのぎりぎりのとこを精査するのに
768bitで計算する場合もあるそうです(そういう
ぎりぎりのとこでない場合はやらないので、それなりに速い)。
955デフォルトの名無しさん
垢版 |
2023/07/16(日) 11:52:54.00ID:YiXq44MV
>>954
まじですか？
そんな最後の1ビット正確に決定するために768bitもの無駄な計算するくらいなら誤差±2^(-23)でいいからとっとと値返してくれた方がいいのに
なので当然通常“最後の1ビット”の正確性までは規格に入れてないんだよな、それでもライブラリ作成者は自己満のために誰も求めない“最後の1ビット”にこだわる
これは高校くらいまでの近似計算の「小数第××位まで求めよ」のノリが抜けてない事の現れでもあるんだよな
もう計算論の近似計算の世界ではゲームチェンジが起こってる事に気づけてない
956915
垢版 |
2023/07/16(日) 12:36:42.33ID:34tdZpnq
>>955
誤差なし(±0.5ulp以内)を追及する人達(CORE-MATH)も居れば、
double-double演算とかの「飛び道具」を使うのをよしとしない人達も居て、
えーっと、みんな違ってみんないい(こなみ)
957デフォルトの名無しさん
垢版 |
2023/07/16(日) 13:03:43.49ID:nweoM3+S
まぁしかし“払うコスト”に対する“リターン”が少なすぎる気はする
例えば内部表現の精度が2^24まである単精度の計算をする場合、もちろん理想は“誤差±1/2×2^(-24)”で返してくれるとありがたい
しかし現実できるか？
例えばアキュムレータをを32ビット用意して計算する、マクローリン展開で求めるとして100回で打ち切るとする、打ち切り誤差は入力のサイズによるけど十分小さい、丸め誤差は2^(-32)×100で誤差トータルは2^(-25)程度、返すのが24bitだから丸められる2^8の可能性のうち真値のポジションから最大100ずれたところでウロチョロしてるわけでその“ウロチョロ”が二項分布、真値の分布が256個の箱の一様分布として外れ値になるの確率がどのくらいやろ？暗算ではできないけど言うほどない、この言うほどない誤差を返さないただそれだけのために768bitも計算繰り返すとかどうなんって感じ
958915
垢版 |
2023/07/16(日) 13:09:49.90ID:34tdZpnq
>>957
768bitの話は、倍精度(53bit精度)のexp()の過去のバージョンでした。
glibcでも問題になったんでしょう(たぶん)
959デフォルトの名無しさん
垢版 |
2023/07/16(日) 14:04:25.82ID:JCFIIFPR
でしょうね
流石に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個で計算するのと時間大して変わらないという話もききますしね
960915
垢版 |
2023/07/16(日) 14:30:41.46ID:34tdZpnq
>>959
以前は最近値だったそうです(その代わり遅い)
tps://sourceware.org/git/?p=glibc.git;a=commit;h=6fd0a3c6a887a91b1554730c977657a7e65334cc
961デフォルトの名無しさん
垢版 |
2023/07/16(日) 15:00:29.88ID:8Io8J2M0
その記事はglibcで色々実験してみたの報告ですね
どっかに“旧glibcは最近値をとことんまで出す”って別資料の記事見かけました？
もちろん入力された有理数xに対してexp(x)を時間無制限ならその与えられた桁数までの最近値を計算するアルゴリズムはすぐ作れるので(一般にGaussの超幾何関数からくる連分数表示が可能な実数ならそのような事が可能)そういうライブラリを実装するのはまぁ無理ではないんですけどね
実際円周率をリソースが食い尽くされるまで延々と計算し続けるプログラムとかよくネットで転がってますし、確か昔のrubyのサンプルプログラムにも収録されてたような
962デフォルトの名無しさん
垢版 |
2023/07/20(木) 22:27:12.42ID:VHXXslhm
>>933-934
R
https://ideone.com/NOtyLC

>>940-941の条件はやっぱり面倒なので省略した。
2023/07/21(金) 02:40:44.37ID:qmbYiZJ4
>>962
難しいお題だったので、簡単に解説お願いします。
2023/07/21(金) 07:58:12.84ID:XtiUJMX6
>>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.60ID:XtiUJMX6
>>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.51ID:p6hqStjf
見やすさどうこうならオンラインの実行環境に入れたほうが見やすい
967デフォルトの名無しさん
垢版 |
2023/07/21(金) 20:43:39.96ID:eNxuBSnx
>>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行目も同様。
レス数が950を超えています。1000を超えると書き込みができなくなります。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況