X



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

0101デフォルトの名無しさん
垢版 |
2023/09/28(木) 08:18:15.29ID:q8VwFY1b
お題
文字列S=abcdefghij(10文字)が与えられて
配列[0,4,7]が与えられる
このときSの0番目を4番目、4番目を7番目、7番目を0番目に移動した文字列を出力するプログラムを書いてください
0103デフォルトの名無しさん
垢版 |
2023/09/28(木) 13:09:43.08ID:tckV2TlV
>>101 Ruby
文字列S='abcdefghij'
配列=[0,4,7]

文字列 = 文字列S.dup
配列.zip( 配列.rotate ).each{|i,j| 文字列[i] = 文字列S[j] }
puts 文字列
0104蟻人間 ◆T6xkBnTXz7B0
垢版 |
2023/09/28(木) 13:15:33.53ID:eLIN3EHU
お題: コンソールに指定したUTF-8文字列のQRコードを表示するプログラム。
0105デフォルトの名無しさん
垢版 |
2023/09/28(木) 14:55:17.75ID:7+/lnWbq
use std::io::{stdin, Read};
use std::error::Error;
use qrcode::QrCode;

fn read() -> Result<String, Box<dyn Error>> {
Ok(stdin().lock().bytes().map(|c| c.expect("char") as char).collect())
}

fn main() -> Result<(), Box<dyn Error>> {
let qr = QrCode::new(read()?.as_bytes())?;
let s = qr.render().light_color(' ').dark_color('#').build();
println!("{}", s);
Ok(())
}
0106蟻人間 ◆T6xkBnTXz7B0
垢版 |
2023/09/28(木) 21:17:30.48ID:yc7Vl2N1
お題: 指定されたフォントのひらがなの各文字について
ひらがなの線に囲まれて閉じた領域の個数を調べ、最もその個数の多い文字ベスト3を出力せよ。
0108デフォルトの名無しさん
垢版 |
2023/09/28(木) 22:59:15.05ID:isk1iJ0r
pythonならcv2使ってやるかな
010917
垢版 |
2023/09/29(金) 10:58:18.12ID:eBy6R6wt
>>97
bash のコマンドラインで以下のように入力すると標準入力から入力して「、」が「,」に、「。」が改行に変換されて標準出力に出力される。
(起動する環境は bash でなければならないということはないと思うが、他のシェルは確認していない)。

sed 's/、/,/g;s/。/\n/g'

もちろん日本語入出力可能な端末を使用して、尚且つ sed がその入力をまともに受け付けてくれなければちゃんと動かない。
0110デフォルトの名無しさん
垢版 |
2023/09/29(金) 11:02:02.85ID:F8aJXNq9
お題: 指定されたフォントのひらがなの各文字について
ひらがなの線に囲まれて閉じた領域の面積を調べ、各文字毎にそれぞれの面積の順序を最も大きい物から順に出力せよ。
またその情報を元に輪郭のhierarchy情報をcv2で利用出来る形で出力せよ
0111デフォルトの名無しさん
垢版 |
2023/09/30(土) 17:32:44.04ID:xxjzuZuq
お題
文字列が入力されます
赤と緑を入れ替えて
黒と白を入れ替えて
黄と青を入れ替えてください


入力: 緑のカバンに500万入れて白の紙で黄色のカバン言うて書きながら赤のカバン言いながら置いてくれたら俺黒のカバン言いながら取りに行くわ
出力: 赤のカバンに500万入れて黒の紙で青色のカバン言うて書きながら緑のカバン言いながら置いてくれたら俺白のカバン言いながら取りに行くわ
0112デフォルトの名無しさん
垢版 |
2023/09/30(土) 18:00:29.42ID:oqu6hf3+
>>111 node

const swap = (text, [w1, w2]) => text.split(w1).map(v => v.replaceAll(w2, w1)).join(w2)

const swapAll = (text, rules) => rules.reduce(swap, text)

const text = '緑のカバンに500万入れて白の紙で黄色のカバン言うて書きながら赤のカバン言いながら置いてくれたら俺黒のカバン言いながら取りに行くわ'

const rules = [['赤', '緑'], ['黒', '白'], ['黄', '青']]

const replaced = swapAll(text, rules)
// console.log(replaced)
console.log(replaced === '赤のカバンに500万入れて黒の紙で青色のカバン言うて書きながら緑のカバン言いながら置いてくれたら俺白のカバン言いながら取りに行くわ')
// true
0114デフォルトの名無しさん
垢版 |
2023/09/30(土) 20:00:09.54ID:iuoy3pEW
>>111 ウェブブラウザのJavaScript
https://pastebin.com/YvymwTeN

ユーザースクリプトの体裁で書いたけどブラウザーのConsoleでも動かせる
Firefox: Ctrl+Shift+K
Chrome: Ctrl+Shift+J
https://mevius.5ch.net/test/read.cgi/tech/1691038333/111 を開いてそこで実行
結果はレスに直接追記

重複がないからXPathのtranslate()でいけるな思った、それだけ
011617
垢版 |
2023/10/02(月) 01:52:26.35ID:hWT/DRlk
>>104
1. qrencode というプログラムをインストールする。(例: RedHat系Linuxなら yum install qrencode)

2. qrencode で出力に ansi 等を指定して文字列で出力する。

例: qrencode -t ansi やっほー

3. 画面に出て来たQRコードをスマホで撮影する等して確認する。

4. 終わり。
0118デフォルトの名無しさん
垢版 |
2023/10/06(金) 16:54:06.65ID:jg1c5xSH
[クライシスアクター」「豊島保養所」←画像検索&拡散!

他スレに丸ごとコピペよろしっく!!
ネットでできる反レプティリアン・反イルミ活動です!!!!!
動画サイトのコメ欄もねらい目だぞーーーー!!!!!!!
0119デフォルトの名無しさん
垢版 |
2023/10/06(金) 16:54:28.09ID:jg1c5xSH
[クライシスアクター」「豊島保養所」←画像検索&拡散!

他スレに丸ごとコピペよろしく!!
ネットでできる反レプティリアン・反イルミ活動です!!!!!
動画サイトのコメ欄もねらい目だぞ!!!!!!!
0120デフォルトの名無しさん
垢版 |
2023/10/08(日) 19:28:55.20ID:faQf3SiN
お題:n階建てのビルに定員4人のエレベーターがある。エレベーターは各階でボタンが押されるとその階に向かう。住人達はエレベータを呼んで乗るとエレベーター内で次に向かう階へのボタンを押す。ボタンを押すのは乗員全員である。乗るのを待っている住人が定員より多かった場合、エレベーターは乗れなかった住人を優先的に回収する。住人は列の先頭から順番にエレベーターに乗り込む。エレベーターは乗員を降ろしている間に住人を追加で乗せることはなく、すべての乗員を降ろしてから次の住人の回収に向かうものとする。

もっとも効率がいいエレベーターの停止順序を求め、入力に対して停止階のリストを出力せよ。
エレベーターの初期位置は1階とする。

入力
階数
乗員数 住人たちがいる階 乗員iが向かう階 乗員iが向かう階 …
5
1 1 5
2 4 3 2
3 2 1 3 5

出力
停止階 停止階 …
1 5 4 3 2 1 3 5

入力
10
5 1 1 2 3 4 4
9 4 10 10 10 1 8 6 6 6 5

出力
1 2 3 4 1 4 1 10 4 6 8 4 5
01219
垢版 |
2023/10/08(日) 20:24:03.46ID:zYJ3wh+h
>>120
「もっとも効率がいいエレベーターの停止順序」とは?
1.停止回数がもっとも少ない
2.移動した階数の和が最も小さい
3.ほか
など、どのような指標?
0127デフォルトの名無しさん
垢版 |
2023/10/14(土) 00:00:08.85ID:sMwx6jpS
お題:角カッコの列が入力されるのでカッコの対応が取れていたら1,取れていなかったら0と表示せよ

< [[]]
> 1

< [[]
> 0
012817
垢版 |
2023/10/14(土) 02:22:24.53ID:BgrcFKKf
>>127
Perl

bash 等のシェルのコマンドラインで以下のように入力すると標準入力から入力して結果を標準出力に出力する。

perl -ne '$n=0;while(/(.)/g){if($1eq"["){$n++}elsif($1eq"]"){$n--}}$f=$n==0?1:0;print"$f\n"'

実行例
[[]]
1
[[]
0
[[[[]][[]]]
0
[[[[]][[]]]]
1
0130デフォルトの名無しさん
垢版 |
2023/10/14(土) 10:19:17.10ID:BRbCCPQd
>>127 Ruby
%W( [[]] [[] [[[[]][[]]] [[[[]][[]]]] ][ #{} ).each{|s|
w = s.dup
{} while w.sub!( /\[\]/, '' )
puts "#{(s != '' && w == '')? 1 : 0} #{s.inspect}"
}

# 1 "[[]]"
# 0 "[[]"
# 0 "[[[[]][[]]]"
# 1 "[[[[]][[]]]]"
# 0 "]["
# 0 ""
0132デフォルトの名無しさん
垢版 |
2023/10/16(月) 08:51:26.93ID:kgcCjrnK
1)
BY
RG

2)
RG
BY

3)
GR
YB

1-3を回転対称で同じとみなせるグループと線対称で同じとみなせるグループに分類せよ

4色を2x2の升にランダムに一つづつ配置して4x3x2通りのパターンを作成し
それぞれを上の基準でグループ分けせよ
0134デフォルトの名無しさん
垢版 |
2023/10/18(水) 20:40:59.79ID:4ifgnZXl
お題:Pythonのmath.ulp()と同機能の関数
引数が正規化数限定のサブセットでも可(その旨を明記)。
Pythonで実装する場合は(もちろん)math.ulp()を使ってはならない。
0135134
垢版 |
2023/10/18(水) 20:46:23.24ID:4ifgnZXl
簡単なお題:
>>133のサブセット(求めたulpも正規化数限定)
0136デフォルトの名無しさん
垢版 |
2023/10/18(水) 20:56:02.06ID:L3TY2GGf
import struct

def my_ulp(x):
# 浮動小数点数xをバイト列に変換
b = struct.pack("d", x)
# バイト列を整数に変換
i = int.from_bytes(b, "little")
# 符号部(1ビット)を取り出す
s = i >> 63
# 指数部(11ビット)を取り出す
e = (i >> 52) & 0x7ff
# 仮数部(52ビット)を取り出す
m = i & 0xfffffffffffff
# 指数部が0や最大値ならエラー
if e == 0 or e == 0x7ff:
raise ValueError("x is not a normalized number")
# 仮数部の最下位ビット(1ビット)を求める
lsb = m & 1
# 符号部と指数部を元に戻す
i = (s << 63) | ((e - lsb) << 52)
# 整数をバイト列に変換
b = i.to_bytes(8, "little")
# バイト列を浮動小数点数に変換
return struct.unpack("d", b)[0]
0137134
垢版 |
2023/10/18(水) 21:44:13.43ID:4ifgnZXl
>>135
間違えましたorz
0138134
垢版 |
2023/10/18(水) 21:52:04.82ID:4ifgnZXl
>>136
math.ulp()は符号を戻さないらしいです:
ulp(1) == ulp(-1)
0139デフォルトの名無しさん
垢版 |
2023/10/21(土) 04:08:56.28ID:TaroWUwV
お題:文字列「せんだ」「みつを」「ナハナハ」がランダムに100行入力される。せんだ、みつを、ナハナハが順番に入力されたときに1と一行出力せよ
0141デフォルトの名無しさん
垢版 |
2023/10/25(水) 07:23:48.08ID:gFkqcLnH
お題:
(1)Python3.12以降の、math.nextafter()のサブセット
(実装はPythonでなくても構いません)
64ビット長程度の整数iを引数として、
a)iがゼロ:foo(i) = 0.0
b)i > 0:foo(i) = nextafter(0, inf, steps=i)
c)i < 0:foo(i) = nextafter(0, -inf, steps=-i)
を満たすfoo()を書く。
Python3.12を使う場合は、nextafter()を使ってはならない。

(2)(1)の逆関数。
0142141
垢版 |
2023/10/25(水) 07:27:56.03ID:gFkqcLnH
補足:(1)(2)いずれも実用的な時間内で求める事(steps=1相当のnextafter()をループで回すのは不可)。
0143デフォルトの名無しさん
垢版 |
2023/10/25(水) 12:47:47.78ID:Bgy3SEXp
なんだnextafterって
0144141
垢版 |
2023/10/25(水) 23:22:03.23ID:gFkqcLnH
>>143
nextafter()は、浮動小数点数の、(数直線上での)「隣」を求めるやつですね(C99以降?)。
Python3.12のやつは、隣の隣の隣の…を求める事が出来る様に拡張されました。
014521-923
垢版 |
2023/10/26(木) 00:31:46.93ID:7aLp+Ojb
前スレの補足:
V8やLLVMは、自前でstrtod()的なものを実装してました。
tps://arxiv.org/abs/2101.11408
0146デフォルトの名無しさん
垢版 |
2023/10/28(土) 20:54:22.44ID:U0JINWpQ
>>101 octave
https://ideone.com/87WGBO
function s = f(s, i)
s(circshift(i, -1, 2)) = s(i);
end

>>127 ocaml
https://ideone.com/IY1dWU
let chars s =
let rec aux acc i =
if i < 0 then acc else aux (s.[i] :: acc) (i - 1)
in aux [] ((String.length s) - 1)
let f s =
let rec aux = function
([], []) -> 1
| (_, []) -> 0
| ('['::bs, ']'::cs) -> aux (bs, cs)
| (bs, c::cs) -> aux (c::bs, cs)
in aux ([], (chars s))
0147デフォルトの名無しさん
垢版 |
2023/10/31(火) 00:00:13.24ID:mywig6Xf
>>3 c
https://ideone.com/BnNzUC
int has26(const char *p) {
int c, count[26] = {0};
for (; c = tolower(*p); p++) if (isalpha(c)) count[c - 'a']++;
for (c = 'a'; c <= 'z'; c++) if (count[c - 'a'] < 1) return 0;
return 1;
}
const char *f(const char **lines, int n) {
const char *found = 0;
int i, len, minlen;
for (i = 0; i < n; i++)
if (has26(lines[i]))
if (!found)
found = lines[i], minlen = strlen(lines[i]);
else if (len = strlen(lines[i]) < minlen)
found = lines[i], minlen = len;
return found;
}
014917
垢版 |
2023/11/05(日) 02:55:01.08ID:w6RhJs5K
>>148
ChatGPT にそのままテキストを読ませたらこう答えた。
-------------------------------------------------------------------------------------------------
通学に自転車を使わない学生は34人、自転車を使うがバスを使わない学生は39人、バスを使うが自転車を使わない学生は18人です。

100人の学生全体からこれらの人数を引いた残りの学生がバスと自転車の両方を使っている学生の数です。

100人 - 34人 (自転車を使わない学生) - 39人 (バスを使わない学生) - 18人 (自転車を使わない学生) = 9人

したがって、通学にバスと自転車の両方を使う学生は9人です。
-------------------------------------------------------------------------------------------------

ここで徒歩については考慮しないのかとツッコミを入れたらこう答えた。

-------------------------------------------------------------------------------------------------
申し訳ありません、徒歩の学生についての情報が提供されていなかったため、上記の計算では徒歩を選択した学生については考慮されていませんでした。徒歩を選択した学生の数についての情報がなければ、バスと自転車の両方を使う学生の正確な数を計算することはできません。
-------------------------------------------------------------------------------------------------
015017
垢版 |
2023/11/05(日) 02:58:00.24ID:w6RhJs5K
そして更にこういうツッコミを入れる。

最初の34人は自転車を使っていないだけで密かにバスを使っているかも知れないのだが、そのことは考慮しないのか?

ChatGPT
申し訳ありません、私の以前の回答は不完全でした。確かに、最初の34人のうち自転車を使っていないという情報だけでは、彼らがバスを使っているかどうかを確定することはできません。そのため、正確な答えを得るためには追加の情報が必要です。

もし最初の34人のうち何人かが実際にはバスを利用している場合、それを考慮する必要があります。与えられた情報だけからは、バスと自転車の両方を使う学生の正確な数を特定することはできません。必要な情報が揃わない限り、正確な答えを提供することはできません。
0153デフォルトの名無しさん
垢版 |
2023/11/11(土) 20:39:33.71ID:iU/7lT3J
>>85
Ruby で作った。
FileUtils::DryRun を使っているので、実際には変更されません

require 'fileutils'

HEAD = 'abc' # 先頭文字
EXT = '.mp4' # 末尾の拡張子
HEAD_LEN = HEAD.length # 3文字
EXT_LEN = EXT.length # 4文字

# 絶対パスのディレクトリ名の後ろに、* を付けること!
# . で始まる、隠し directory, file を除く
glob_pattern = "C:/Users/Owner/Documents/test/*#{ EXT }"
target_dir = File.dirname( glob_pattern ) # ディレクトリパスだけを取り出す

# 元のファイル名の配列
fname_src_ary = Dir.glob( glob_pattern )
.select { |full_path| File.file?( full_path ) } # ファイルのみ
.select do |full_path|
file_name = File.basename( full_path )
# 先頭文字が abc かつ、末尾が .mp4 だけに絞り込む
file_name.start_with?( HEAD ) && file_name.end_with?( EXT )
end
.map { |full_path| File.basename( full_path ) }

次へ続く
0154153
垢版 |
2023/11/11(土) 20:41:20.19ID:iU/7lT3J
# 変更後のファイル名の配列
fname_dest_ary = fname_src_ary.map do |file_name|
str = String.new( file_name )
# 先頭文字の abc と、末尾の .mp4 を取り除いて、数字だけにする
str.slice!(-EXT_LEN, EXT_LEN)
str.slice!(0, HEAD_LEN)
# 10進数の数値型に変換してから、3桁0埋め文字にする
HEAD + "%03d" % Integer( str, 10 ) + EXT
end

require 'set'
# 変更後のファイル名が既に存在しているか、チェックする。
# abc100.mp4 など、3桁以上の数値もエラー!
fname_src_set = Set.new( fname_src_ary ) # 集合
fname_dest_ary.each { |file_name|
raise "ファイル名: #{ file_name } が重複しています" if
fname_src_set.include?( file_name )
}

# ファイル名を変更する
fname_src_ary.zip( fname_dest_ary ) do |src_filename, dest_filename|
src_path = target_dir + "/" + src_filename
dest_path = target_dir + "/" + dest_filename
FileUtils::DryRun.move( src_path, dest_path )
end

出力
mv C:/Users/Owner/Documents/test/abc0.mp4
C:/Users/Owner/Documents/test/abc000.mp4
mv C:/Users/Owner/Documents/test/abc99.mp4
C:/Users/Owner/Documents/test/abc099.mp4
0156デフォルトの名無しさん
垢版 |
2023/11/25(土) 20:07:06.40ID:zpqT0hBE
お題:ランダムに1から9999までの整数を得た時、何回で全種類出揃うか確認せよ
擬似乱数列生成法については指定しないものとする

ruby
https://ideone.com/rucuHk
require 'set'
r = 1..9999
c = r.to_a.fill(0)
s = r.to_set
while !s.empty?
n = rand(r)
c[n - r.first] += 1
s.delete n
end
p c.sum

84736
0158デフォルトの名無しさん
垢版 |
2023/11/26(日) 10:44:04.74ID:dd78ITN+
プログラミングの依頼はここでいいでしょうか。
ココナラで依頼したのですが見送りになってしまいました。
お金は出すので製品版を作って欲しいです。
できないなら何が定義できていないのか教えて下さい。

AIによる詩作成

まずAIが詩を作成するための学習ツールを作ります
AIがリンゴの形相を分解するには辞書が必要となる
リンゴを検索し辞書を比較し関連性の高いワード
リンゴ⊇(赤い、丸い、果物…)を拾うのだ
これが学習ツールであり
一致したワードからさらに形相に分解する
リンゴ⊇(赤い、丸い、果物、酸っぱい…)
その中の果物を形相分解するには
果物⊇(リンゴ、サクランボ、なし…)
その中のなしを様相分解すると
なし⊇(果物、丸い、黄緑…)
ここから詩を作るには『黄緑のリンゴ』などになる
形相分解すると客観的な『深さ』(今回は三段階)を持った詩になる
0159デフォルトの名無しさん
垢版 |
2023/11/26(日) 10:50:43.54ID:d/KzVdDP
>>156
設定があいまいなんだが
shuffleとかselectとかchoice系なら
高々9999回で必ず全部出る
0161158
垢版 |
2023/11/26(日) 12:29:54.58ID:dd78ITN+
製品版なら10万円出します
AIでなくても詩作成ツールでいいです
0163デフォルトの名無しさん
垢版 |
2023/11/26(日) 21:12:35.28ID:SfQeb61a
>>157
これだと150001回以上となる場合が本来よりも起こりにくくなってしまい駄目だった。
活かしながら書き換えると https://ideone.com/qv7bL9
016417
垢版 |
2023/11/27(月) 10:19:46.26ID:VB+FhCy9
>>158
ここは誰かがお題を出して答えたい人が答えるスレなので、どんなお題を書いても構わないが、誰も答えないことはよくある。
また、バグがあっても気づかずにそのままになる事もある。多分大半のプログラムは作った本人以外は検証しないので。
ごく稀に他人がバグを発見することはあるが、発見されてもわざわざ指摘するとは限らないし修正もされないかも知れない。
0166デフォルトの名無しさん
垢版 |
2023/11/27(月) 12:57:15.00ID:lzpjbGZv
>>156 Ruby
>>156 の例が個別の出現回数をカウントしていたのでそれに合わせた

c = [0] * 9999
9999.times {
redo unless ( c[ rand(9999) ] += 1 ) == 1
}
p c.sum
016717
垢版 |
2023/11/27(月) 13:09:30.74ID:VB+FhCy9
>>156
また Kotlin
https://paiza.io/projects/yYQ9bdMb0_d91607skNw4Q

今度は add ではなく remove でやるようにした。
これでその Ruby の例に近くはなるがカウントする方法は前と同じで個別にはやってない。
0168デフォルトの名無しさん
垢版 |
2023/11/27(月) 18:30:50.07ID:O6HTjvgJ
>>156
Perl
perl -E 'for ($r = 9999; $n < $r; $_++) { $h{int(rand($r)) + 1} ||= ++$n }; say'
79596
0169156
垢版 |
2023/11/27(月) 20:35:49.92ID:VuTnBSK2
>>156 c
https://ideone.com/K1fD78
・lispのひとの(>>162)をパク…参考にしました
・乱数生成部分は https://c-faq.com/lib/randrange.html からコピペしました
int main() {
int a[9999] = {0}, size = sizeof a / sizeof *a, sum, min, max, r, i, j, k;
srand(time(0));
#define randi(size) ((int)((double)rand() / ((double)RAND_MAX + 1) * (size)))
for (r = size; 0 < r; ) if (!a[randi(size)]++) r--;
for (sum = min = max = a[0], i = 1; i < size; i++) {
sum += a[i];
min = min < a[i] ? min : a[i];
max = a[i] < max ? max : a[i];
}
printf("%d\n%f\n[%d, %d]\n", sum, (double)sum / size, min, max);
for (i = min; i <= max; i++) {
for (k = j = 0; j < size; j++) if (i == a[j]) k++;
printf("%d\t%d\n", i, k);
}
return 0;
}
017017
垢版 |
2023/11/28(火) 15:35:44.30ID:cIauX08C
>>156
今度はC言語
https://paiza.io/projects/c6ALnYb4rksMFGZT03mcCw

1~9999ではなく実際には0~9998でやっているが、表示する必要もないし一々1足したり後で引いたりも馬鹿らしいのでそのままにした。
0171デフォルトの名無しさん
垢版 |
2023/11/30(木) 06:46:26.20ID:/rzYr39l
お題:英字の羅列された文字列が与えられる。この文字列を分析して数字列を出力せよ。数字の表記ルールは、その文字の両隣の文字がASCIIコードにおける奇数だったら1、そうでなければ0.
0172デフォルトの名無しさん
垢版 |
2023/11/30(木) 09:19:30.52ID:AZ5oWFgm
前提としてエラー入力はなくて
出力は両隣がある時のみでいいのかな

use itertools::{Itertools, assert_equal};

fn convert(input: &[u8]) -> Vec<u8> {
 input
 .iter()
 .tuple_windows()
 .map(|(prev, _curr, next)| (prev & next & 1) + b'0')
 .collect()
}

fn main() {
 assert_equal(&convert(b"ABC"), b"1");
 assert_equal(&convert(b"abcIJKpqrXYZ"), b"1001010000");
}
017517
垢版 |
2023/12/02(土) 14:30:47.66ID:FLL1Kaqa
>>171
Kotlin
https://paiza.io/projects/xZXVc46Ys3qUlGX4DAIxzw

両隣が存在する文字のみを対象に処理をするようにした。なので3文字未満はエラーになる。3文字の場合は2文字目だけを対象にして一つ結果を出す。
0176デフォルトの名無しさん
垢版 |
2023/12/04(月) 20:26:07.07ID:LtCaDuZa
>>171 Ruby
def solution1( str )
a = 0
str.chars.inject(''){|s,c|
s << ( (5 & (a = 7 & a << 1 | c.ord & 1) == 5)? '1' : '0' )
}[2..-1] || ''
end

solution( '' ) #=> ""
solution( 'AB' ) #=> ""
0179デフォルトの名無しさん
垢版 |
2023/12/13(水) 09:27:48.18ID:NbIWTS6w
お題
ビールの空きビンをN本集めると新品のビール1本と交換してもらえる

あなたが新品のビールをP本持っている

そのとき、あなたが飲めるビールはR本である

N, Pを引数としてRを返す関数を定義してください
018017
垢版 |
2023/12/13(水) 15:17:15.28ID:WwinWAeQ
>>179
Kotlin または Kotlin script

fun beer(n: Int, p: Int) = p + p / n
018117
垢版 |
2023/12/13(水) 15:19:45.81ID:WwinWAeQ
ごめん。これだと1回分しか計算してないね。ということで >>180 はボツ。
018217
垢版 |
2023/12/13(水) 15:47:32.26ID:WwinWAeQ
>>179
Kotlin
https://paiza.io/projects/1gGtpt6dxb6-vzoATj_Qkg

作り直した。
もっと簡略化できそうな感じもしたがやってない。何か画期的な計算方法やアルゴリズムに気付いたらまた作る。
0185デフォルトの名無しさん
垢版 |
2023/12/14(木) 00:03:09.36ID:uNhVrYF2
>>179
R

R <- function(N, P) ((P - 1) * N) %/% (N - 1) + 1
0187デフォルトの名無しさん
垢版 |
2024/01/16(火) 00:33:05.98ID:n8j0XaXx
お題:時刻の文字列が与えられる。その時刻から1秒後の時刻を出力せよ。


入力:00:00:00
出力:00:00:01
入力:23:59:59
出力:00:00:00
01889
垢版 |
2024/01/16(火) 02:37:52.68ID:SfyAs2IF
>>187 Perl5

use Time::Piece;
use Time::Seconds;
for (qw{00:00:00 23:59:59}) {
 $t = Time::Piece->strptime($_, '%T') + 1;
 print "入力:$_\n出力:", $t->strftime('%T'), "\n";
}

※見易くするためインデントを全角スペースに置換してあります


実行結果
~ $ perl 22_187_1秒後.pl
入力:00:00:00
出力:00:00:01
入力:23:59:59
出力:00:00:00
01899
垢版 |
2024/01/16(火) 02:38:47.78ID:SfyAs2IF
>>188

use Time::Seconds;
これ要らなかった…orz
0191デフォルトの名無しさん
垢版 |
2024/01/16(火) 20:54:27.73ID:OiJoE8pV
>>187 PowerShell
"00:00:00", "23:59:59" |% {[String]([DateTime]$_).AddSeconds(1).TimeOfDay}
0193デフォルトの名無しさん
垢版 |
2024/01/16(火) 23:32:13.09ID:+Emu7d1R
>>187 js

const decode = (s) => s.split(":").map(Number);
const encode = (nums) => nums.map((v) => String(v).padStart(2, "0")).join(":");
const inct = (s, sec = 1) => {
const a = decode(s);
const ss = [
{ n: a[0], max: 24 },
{ n: a[1], max: 60 },
{ n: a[2], max: 60 },
];
let up = sec;
const b = ss
.reverse()
.map(({ n, max }) => {
n += up;
up = Math.floor(n / max);
return n % max;
})
.reverse();
return encode(b);
};
console.log(inct("00:00:00"));// 00:00:01
console.log(inct("23:59:59"));// 00:00:00
console.log(inct("00:00:00", 100));// 00:01:40
0194デフォルトの名無しさん
垢版 |
2024/01/17(水) 00:04:27.61ID:g7dwo5vO
>>187 ocaml
https://ideone.com/aEsvl6
let sec_of_hms hms =
let at i = int_of_string (String.sub hms i 2) in at 0 * 60 * 60 + at 3 * 60 + at 6
let hms_of_sec sec =
Printf.sprintf "%02d:%02d:%02d" (sec mod 86400 / 3600) (sec mod 3600 / 60) (sec mod 60)
let (<<) f g x = f (g x)
let f = hms_of_sec << (+) 1 << sec_of_hms
0195デフォルトの名無しさん
垢版 |
2024/01/17(水) 01:45:50.10ID:xvgJymQe
>>187
Rust (date/timeライブラリ不使用版)

fn next_time(cur: &str) -> String {
 let [sec, min, hour] = cur
 .rsplitn(3, ':')
 .map(|s| s.parse().unwrap())
 .zip([60, 60, 24])
 .scan(1, |carry, (mut value, limit)| {
  value += *carry;
  (*carry, value) = if value == limit { (1, 0) } else { (0, value) };
  Some(value)
 })
 .collect::<ArrayVec<_, 3>>()[..] else { unreachable!() };
 format!("{hour:02}:{min:02}:{sec:02}")
}

fn main() {
 assert_eq!(next_time("00:00:00"), "00:00:01");
 assert_eq!(next_time("23:59:59"), "00:00:00");
}
019717
垢版 |
2024/01/19(金) 19:43:44.34ID:hxZRcaHh
>>187
Kotlin

今度は Java のライブラリは使わずに時分秒を保持するクラスを自分で作ってそこで秒に足すとか文字列にするとかやるようにした。

https://paiza.io/projects/7YcPDBTxVFt9EVczvBJ8gQ
0198デフォルトの名無しさん
垢版 |
2024/01/20(土) 23:08:19.98ID:PCaU0wMN
>>187 dart 2.3.0
https://ideone.com/khq9gr
void main() {
var sec_of_hms = (hms) => hms.split(':').fold(0, (acc, s) => acc * 60 + int.parse(s));
var hms_of_sec = (sec) => [sec % 86400 ~/ 3600, sec % 3600 ~/ 60, sec % 60].map((x) => x.toString().padLeft(2, '0')).join(':');
var f = (hms) => hms_of_sec(sec_of_hms(hms) + 1);
print(f('00:00:00'));
print(f('23:59:59'));
}
0200デフォルトの名無しさん
垢版 |
2024/01/21(日) 21:15:52.66ID:BWkvMixc
>>187 c
https://ideone.com/wRIYl2
int hmstosec(const char *hms) {
int h, m, s;
return sscanf(hms, "%d:%d:%d", &h, &m, &s) == 3 ? h * 3600 + m * 60 + s : 0;
}
char *sectohms(char *buff, int sec) {
sprintf(buff, "%02d:%02d:%02d", sec % 86400 / 3600, sec % 3600 / 60, sec % 60);
return buff;
}
char *f(char *buff, const char *hms) {
return sectohms(buff, hmstosec(hms) + 1);
}

>>187 c
https://ideone.com/3gj90n
int hmstosec(const char *hms) {
#define _(i) ((hms[i] - '0') * 10 + (hms[i + 1] - '0'))
return _(0) * 3600 + _(3) * 60 + _(6);
#undef _
}
char *sectohms(char *buff, int sec) {
#define _(i, value) buff[i] = '0' + (value) / 10, buff[i + 1] = '0' + (value) % 10
return _(0, sec % 86400 / 3600), buff[2] = ':', _(3, sec % 3600 / 60), buff[5] = ':', _(6, sec % 60), buff[8] = '\0', buff;
#undef _
}
char *f(char *buff, const char *hms) {
return sectohms(buff, hmstosec(hms) + 1);
}
0204デフォルトの名無しさん
垢版 |
2024/01/23(火) 23:54:34.15ID:39Fs96AV
>>187を時間ライブラリ無しで作成できている言語は現時点で
193のJavaScript
194のOCaml
195のRust
197のKotlin
198のDart
199のC++
200のC
201のLisp
以上
020517
垢版 |
2024/01/24(水) 00:08:17.22ID:n4ooUyFj
>>187
Perl

bashのコマンドラインから長い長いワンライナーで。

$ perl -ne 'if(/(\d+):(\d+):(\d+)/){$h=$1;$m=$2;$s=$3;printf"入力:%02d:%02d:%02d\n",$h,$m,$s;$s++;if($s>=60){$m++;$s=0;if($m>=60){$h++;$m=0;if($h>=24){$h=0}}}printf"出力:%02d:%02d:%02d\n",$h,$m,$s}'
1:2:3
入力:01:02:03
出力:01:02:04
0:0:0
入力:00:00:00
出力:00:00:01
23:59:59
入力:23:59:59
出力:00:00:00
$
0206デフォルトの名無しさん
垢版 |
2024/02/02(金) 06:41:15.23ID:CC6U77IS
お題
入力データをグループ分けして出力せよ

入力データの、= の左右は同じグループである。
出力する順番は、入力データの出現順とする

UnionFind を使えば良いかも

入力データ
["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
"a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
"b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"]

出力
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
["e1", "e2", "e3"]]

Ruby で、UnionFind を自作してみた。
下はユニットテストです

https://paiza.io/projects/e6nk1EOu3utyWpV3iuWAFQ?language=ruby
https://paiza.io/projects/kjeVtTKeDwEnWVrBU5_nbg?language=ruby
0207デフォルトの名無しさん
垢版 |
2024/02/02(金) 10:50:23.49ID:fEMhv+T7
>>206
Rust

fn foo<'a, 'b>(input: &'b [&'a str]) -> Vec<Vec<&'a str>> {
 struct Data<'a> { name: &'a str, rep: usize, coll: Option<Vec<usize>>, }
 let mut data = Vec::<Data>::new();
 let mut map = HashMap::<&str, usize>::new();
 for s in input {
  let (index0, index1) = s.splitn(2, '=')
   .map(|s| match map.get(s) {
    Some(&index) => data[index].rep,
    None => {
     let index = data.len();
     map.insert(s, index);
     data.push(Data { name: s, rep: index, coll: Some(vec![index]), });
     index
    },
   })
   .sorted().tuple_windows().next().unwrap();
  if index0 != index1 {
   let coll0 = data[index0].coll.take().unwrap();
   let coll1 = data[index1].coll.take().unwrap();
   coll1.iter().for_each(|&index| data[index].rep = index0);
   data[index0].coll = Some(itertools::merge(coll0, coll1).collect());
  }
 }
 data.iter().map(|data| &data.coll).flatten()
  .map(|coll| coll.iter().map(|&index| data[index].name).collect()).collect()
}
0208デフォルトの名無しさん
垢版 |
2024/02/02(金) 10:53:02.58ID:fEMhv+T7
>>207の動作確認用追加分

use std::collections::HashMap;
use itertools::Itertools;

fn main() {
 let input = [
  "a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
  "a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
  "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"
 ];
 let output = [
  vec!["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
  vec!["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
  vec!["e1", "e2", "e3"]
 ];
 assert_eq!(foo(&input), output);
}
0209デフォルトの名無しさん
垢版 |
2024/02/02(金) 22:48:33.27ID:UezRkqGy
>>206 ruby
https://ideone.com/eF5lww
f = -> a {
w = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a.each_with_object([]) {|s, acc|
x, xa, y, ya = s.split('=').map {|k| [k, acc.find {|b| b.include? k}]}.flatten(1)
if xa && ya then xa.concat (acc.delete ya) << x << y
elsif xa then xa << x << y
elsif ya then ya << x << y
else acc << [x, y]
end
}.map {|a| a.uniq.sort_by {|s| w[s]}}.sort_by {|a| w[a[0]]}
}
0210デフォルトの名無しさん
垢版 |
2024/02/02(金) 22:51:42.74ID:UezRkqGy
>>206 rust
https://ideone.com/MEZMPO
fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, p)).collect::<HashMap<_, _>>();
let mut acc = Vec::<Vec<&str>>::new();
for xy in a.iter().map(|s| s.split('=').collect::<Vec<_>>()) {
match (acc.iter().position(|b| b.contains(&xy[0])), acc.iter().position(|b| b.contains(&xy[1]))) {
(Some(xi), Some(yi)) => {
let ys = acc[yi].clone();
acc[xi].extend(ys);
acc[xi].extend(xy);
acc.remove(yi);
},
(Some(xi), None) => acc[xi].extend(xy),
(None, Some(yi)) => acc[yi].extend(xy),
_ => acc.push(xy),
}
}
for b in acc.iter_mut() {
b.sort_by(|c, d| h.get(d).cmp(&h.get(c)));
b.dedup();
}
acc.sort_by(|c, d| h.get(d[0]).cmp(&h.get(c[0])));
acc
}
0211デフォルトの名無しさん
垢版 |
2024/02/02(金) 23:24:19.60ID:UezRkqGy
>>206 ruby
https://ideone.com/daI0QL
・若干の修正
f = -> a {
w = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a.each_with_object([]) {|s, acc|
x, xa, y, ya = s.split('=').map {|k| [k, acc.find {|b| b.include? k}]}.flatten(1)
if xa && ya then xa.concat (acc.delete ya)
elsif xa then xa << y
elsif ya then ya << x
else acc << [x, y]
end
}.map {|a| a.sort_by {|s| w[s]}}.sort_by {|a| w[a[0]]}
}
0212デフォルトの名無しさん
垢版 |
2024/02/02(金) 23:24:45.86ID:UezRkqGy
>>206 rust
https://ideone.com/dO4xea
・若干の修正
fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, p)).collect::<HashMap<_, _>>();
let mut acc = Vec::<Vec<&str>>::new();
for xy in a.iter().map(|s| s.split('=').collect::<Vec<_>>()) {
match (acc.iter().position(|b| b.contains(&xy[0])), acc.iter().position(|b| b.contains(&xy[1]))) {
(Some(xi), Some(yi)) => {
let ys = acc[yi].clone();
acc[xi].extend(ys);
acc.remove(yi);
},
(Some(xi), None) => acc[xi].push(xy[1]),
(None, Some(yi)) => acc[yi].push(xy[0]),
_ => acc.push(xy),
}
}
acc.iter_mut().for_each(|b| b.sort_by(|c, d| h.get(d).cmp(&h.get(c))));
acc.sort_by(|c, d| h.get(d[0]).cmp(&h.get(c[0])));
acc
}
02169
垢版 |
2024/02/04(日) 16:39:59.23ID:jTY6zdRX
>>208 Perl5

use feature qw{:5.16 signatures};
no warnings qw(experimental::signatures);
@s = qw[a1=a2 b1=b2 b3=b2 c1=c2 e1=e2 a3=a4 c3=c4 e1=e3 a2=a4 c3=c1 b3=a4 c2=d1 a4=a5 d2=c1 b4=b3 d3=c3];
for (map{[sort /(\w+)=(\w+)/]} @s) {
 ($l, $r) = @$_;
 $g{$r} //= $g{$l} //= $g{$r} // $l;
 $h{$g{$r}} = $g{$l} if $g{$l} ne $g{$r};
}
$h{$k} = sub($e){$h{$e} ? __SUB__->($h{$e}) : $e}->($v) while ($k, $v) = each %h;
$g{$_} = $h{$g{$_}} // $g{$_} for keys %g;
push @{$r{$v}}, $k while ($k, $v) = each %g;
say "@$_" for values %r;

※見易くするためインデントを全角スペースに置換してあります


実行結果
$ perl 22_206_grouping.pl
b3 a3 a5 b4 a4 a1 b1 a2 b2
c1 d1 d3 c3 c2 d2 c4
e3 e1 e2
02179
垢版 |
2024/02/04(日) 18:22:17.66ID:jTY6zdRX
>>208 宛てじゃなかった
>>206 の回答だったわ… orz
0218デフォルトの名無しさん
垢版 |
2024/02/04(日) 18:32:39.04ID:fS5H2fbQ
>>206
>>215をPowerShellに移植

$in =
  "a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2", "a3=a4", "c3=c4", "e1=e3",
  "a2=a4", "c3=c1", "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"

$in -split "=" |% {$h = @{}; $n = 0} {if (!$h[$_]) {$h[$_] = $n++}}
$eq = $in |% {, $h[$_ -split "="]}

$g = 1..$n
do {
  $changed = $false
  $eq |% {
    $i, $j = $_
    switch ($g[$i] - $g[$j]) {
      {$_ -gt 0} {$g[$i] = $g[$j]; $changed = $true}
      {$_ -lt 0} {$g[$j] = $g[$i]; $changed = $true}
    }
  }
} while ($changed)

$h.keys | sort {$h[$_]} | group {$g[$h[$_]]} |% {"[$($_.group -join ", ")]"}

-- 実行結果 --
[a1, a2, b1, b2, b3, a3, a4, a5, b4]
[c1, c2, c3, c4, d1, d2, d3]
[e1, e2, e3]
0219デフォルトの名無しさん
垢版 |
2024/02/04(日) 19:02:37.59ID:fS5H2fbQ
>>218の5行目の if (!$h[$_]) を if ($h[$_] -eq $null) に訂正
0223221
垢版 |
2024/02/05(月) 20:08:21.07ID:tt/WRhkt
>>206 ruby
https://ideone.com/j2xPyB
>>221から若干のアレンジ
・SortedSet単位でのみいじるようにした
f = -> a {
g = -> a {a.combination(2) {|x, y| break g.(a.tap {x.merge y; a.delete y}) if x.intersect? y}}
h = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a = a.map {|s| s.split('=').map {|k| h[k]}.to_set SortedSet}
g.(a).map {|set| set.map &h.invert.method(:[])}
}
0225223
垢版 |
2024/02/05(月) 23:51:15.55ID:tt/WRhkt
>>206 rust
https://ideone.com/Ma1WGV
>>223の移植
・色々迷いアリ
 .map(|k| *h.get(k).unwrap())のところは当初
 .map(|k| h.get(k).map(|&i| i)).flatten()などとしていたが
 正解がわからないので迷った挙げ句に短く書けるほうを採用
・これに限らずrustは不慣れなので色々珍妙なことをしている可能性アリ
0226225
垢版 |
2024/02/06(火) 22:07:13.88ID:6T/Xuns0
>>206 rust
https://ideone.com/m5INyJ
>>225から若干の修正
・不必要なループ回数を訂正
・二重forを一重に(でもかえって煩雑に)
・まだまだ迷いアリ
 .map(|k| *h.get(k).unwrap())は結局
 .flat_map(|k| h.get(k)).cloned()に置き換え
 こっちのほうが個人的にはスッキリ感アリ

>>206 rust
https://ideone.com/hT5zGF
・上記のmutナシ版
・パフォーマンス的な観点もナシ
0229226
垢版 |
2024/02/09(金) 22:33:42.16ID:JDB9tF7l
>>226
すべてruby移植版rust
DでもE見た目派生まとめ

mutあり版
https://ideone.com/m5INyJ // for if return
https://ideone.com/R8wcOJ // match find
https://ideone.com/ifI5EX // if let find

mutなし版
https://ideone.com/hT5zGF // for if return
https://ideone.com/1PNKbR // match find
https://ideone.com/btKWb1 // if let find

集合同士の組み合わせに重なりが一個もなかったときに
最後に返す a がポツーンと片隅に居るのが落ち着かなかったので
match/if letで書き直してみたがそれはそれで難があり?
条件部分が奥に入ってしまったのがなんかイヤだったり?
一行目が長くなりすぎる、という理由で二行に分けたり?
やっぱ元のfor if returnのリズムのほうが眼球に入りやすい?
0233223
垢版 |
2024/02/12(月) 23:45:12.86ID:ix8w7wd+
>>206 octave
https://ideone.com/VtqJcV
・組み合わせつくって集合のペアごとに調べることをやめた
・集合間で重複する要素に着目して集合を減らすようにした

>>223
g.(a).map {|set| set.map &h.invert.method(:[])}じゃなくて単に
g.(a).map {|set| h.keys.values_at *set}で良かった
0234デフォルトの名無しさん
垢版 |
2024/02/14(水) 09:32:06.19ID:JjlrBdlD
お題:数値が入力されるのでその数値に最も近い回分数を出力せよ
回分数とは回分になっている数(負数含まず)のことである
最も近い回分数が2つある場合は2つとも出力せよ

入力 0
出力 0

入力 17
出力 22

入力 100
出力 99
出力 101
0238デフォルトの名無しさん
垢版 |
2024/02/15(木) 21:30:35.17ID:MveN6p4/
>>234
Rust

fn foo(n: usize) -> (usize, Option<usize>) {
 let n2b = |n: usize| { let mut o = Some(n); iter::from_fn(|| { let n = o.take()?; o = (n >= 10).then(|| n / 10); Some((n % 10) as i8) }).collect::<Vec<i8>>() };
 let b2n = |b: &[i8]| b.iter().rev().fold(0_usize, |n, b| n * 10 + *b as usize);
 let pal = |b: &mut [i8]| { let len = b.len() / 2; let (l, u) = b.split_at_mut(len); iter::zip(l, u.iter().rev()).for_each(|(l, u)| *l = *u); };
 let inc = |b: &mut [i8]| { let len = b.len() / 2; let mut c = 1; b[len..].iter_mut().for_each(|b| { *b += c; if *b > 9 { *b = 0; c = 1; } else { c = 0; }}); };
 let dec = |b: &mut [i8]| { let len = b.len() / 2; let mut c = 1; b[len..].iter_mut().for_each(|b| { *b -= c; if *b < 0 { *b = 9; c = 1; } else { c = 0; }}); };
 let fix = |b: &mut [i8]| { if b.last() == Some(&0) { if b.len() & 1 == 0 { b[(b.len() - 1) / 2] = 9; } true } else { false } };
 
 let mut b = n2b(n);
 pal(&mut b);
 let n1 = b2n(&b);
 match n.cmp(&n1) {
  Ordering::Equal => return (n, None),
  Ordering::Greater => inc(&mut b),
  Ordering::Less => dec(&mut b),
 }
 if fix(&mut b) { b.pop(); }
 pal(&mut b);
 let n2 = b2n(&b);
 match n.abs_diff(n1).cmp(&n.abs_diff(n2)) {
  Ordering::Less => (n1, None),
  Ordering::Greater => (n2, None),
  Ordering::Equal => (n1, Some(n2)),
 }
}
0239デフォルトの名無しさん
垢版 |
2024/02/15(木) 22:00:50.95ID:fu0tHwRa
>>234
>>237は入力が1〜9のとき出力が正しくなかった。function内の1行目に if ($n -le 9) {return $n} を
挿入すると修正される。

Rでは添字の開始値は1で添字0では空のデータが返るので、入力が1〜9のときの場合分けは不要。
[]演算子と+演算子を文字列でも使えるように再定義した。
https://ideone.com/PP5swB

Dでは添字範囲指定は半開区間なので、入力が1〜9のときの場合分けは不要。
https://ideone.com/hvNBia
02419
垢版 |
2024/02/16(金) 02:56:10.41ID:7jtCAGu+
>>234 Perl5

for $n (0,17,100,123459321) {
 my %a;
 for (0..$n) {
  $i = $n - $_;
  $a{$i} = $i if 0 <= $i and $i =~ /^((\d)(?1)\2|\d?)$/;
  $j = $n + $_;
  $a{$j} = $j if $j =~ /^((\d)(?1)\2|\d?)$/;
  last if keys %a;
 }
 @a = keys %a;
 print "$n -> @a\n";
}

※見やすくするためインデントを全角スペースに置換してあります。

実行結果

$ perl 22_234_palindromic_number.pl
0 -> 0
17 -> 22
100 -> 99 101
123459321 -> 123464321 123454321
02429
垢版 |
2024/02/16(金) 03:13:10.80ID:7jtCAGu+
>>241

  last if keys %a;
 }
 @a = keys %a;



  last if @a = keys %a;
 }

とコンパクトに書けるんだった、まぁいいや
02439
垢版 |
2024/02/16(金) 14:47:55.29ID:TIAwaOOw
>>234 Perl5、小さい方の検索は0で止まるので負の値を避ける必要はなかった、書き直し。

$r = qr/^((\d)(?1)\2|\d?)$/;
for $n (0,17,100,123459321) {
 my %a;
 for (0..$n) {
  $a{$n - $_} = 1 if ($n - $_) =~ $r;
  $a{$n + $_} = 1 if ($n + $_) =~ $r;
  last if @a = keys %a;
 }
 print "$n -> @a\n";
}
02469
垢版 |
2024/02/17(土) 02:10:36.54ID:K8P5qDCx
>>234 Python3

def f(k):
  s = str(k)
  return s == s[::-1]
for n in [0, 17, 100, 123459321]:
  l = set()
  for i in range(n + 1):
    if f(n - i): l.add(n - i)
    if f(n + i): l.add(n + i)
    if l:
      print(n, l)
      break

※見易くするためインデントは全角空白に置換してあります

実行結果

$ python3 22_234_palindromic_number..py
0 {0}
17 {22}
100 {99, 101}
123459321 {123454321, 123464321}
0257デフォルトの名無しさん
垢版 |
2024/02/18(日) 18:26:09.28ID:ovKjFpQ6
>>253-256 アスペで不合格w
0259デフォルトの名無しさん
垢版 |
2024/02/18(日) 19:41:35.69ID:rWy6ZYAH
>>234 dart
https://ideone.com/e23wRv
void main() {
var rev = (n) => int.parse(n.toString().split('').reversed.join());
var f = (n) => Iterable.generate(n + 1).map((i) => [n - i, n + i].where((x) => x == rev(x))).firstWhere((a) => a.isNotEmpty).toSet().toList();
print([0, 17, 100].map((n) => [n, f(n)]));
}
026117
垢版 |
2024/02/20(火) 10:47:13.25ID:YmH8jdAc
>>254
しらみ潰しって、どんなテストしたの?
0262デフォルトの名無しさん
垢版 |
2024/02/20(火) 12:59:46.62ID:qzcGLGiS
しらみ潰しとは例えば1から順番に見つかるまで全てを試していく最悪な方法を指す
今回の場合だと与えた数から順番に見つかるまで±1を続けて全てを試していって探すプログラムが該当する
02639
垢版 |
2024/02/20(火) 17:18:07.59ID:X5uoFLgg
「どんなテストしたの?」
って質問だよ
0264◆QZaw55cn4c
垢版 |
2024/02/20(火) 20:48:17.02ID:RtAsHDVN
>>262
私は >>248
だけれども、解法としてはそれしかないと思いますね
0266デフォルトの名無しさん
垢版 |
2024/02/21(水) 13:54:29.89ID:ve9Dz9D8
>>264
私は解答は提出していないが、ざっくりと自分が思いついた方法

まず、以下のような操作を考える
A. 1234という入力に対して1234321を返す
B. 1234という入力に対して12344321を返す
ここで、xという入力に対してA,Bが返す数をA(x),B(x)と表すことにする

次に、与えられた数の桁数で場合分け
(1)与えられた数字の桁数が奇数の場合
例として5桁の数字を考える
N=a*10000+b*1000+c*100+d*10+e*1 (a~eは1桁の自然数, aは0でない)
が与えられたとき、
M=a*100+b*10+c*1
とすると、N=10000の場合を除いて、Nに最も近い回文数は
A(M), A(M+1), A(M-1)
の3つの候補に絞られる(厳密にはA(M)とNとの大小比較からA(M±1)の何れかは明らかに候補にならないので2つを考えれば良い)
N=10000の場合は9999と10001が答え

(2)与えられた数の桁数が偶数の場合
例として6桁の数を考える
(1)と同様に
N=a*100000+b*10000+c*1000+d*100+e*10+f*1
に対して
M=a*100+b*10+c*1
とすると、N=100000の場合を除いて
B(M), B(M+1), B(M-1)
のどれかがNに最も近い回文数(厳密には以下略)
N=100000の場合は99999と100001が答え

十分大きな数に対しては虱潰しに回文判定していくより速く求まる
0267デフォルトの名無しさん
垢版 |
2024/02/21(水) 16:02:55.06ID:Sko4Sglv
>>266
N=17
のときは?
0268259
垢版 |
2024/02/21(水) 23:06:20.13ID:DX/jvS2m
>>259
Iterable.generate(n).map(f)は単に
Iterable.generate(n, f)で良かったと判明
0269デフォルトの名無しさん
垢版 |
2024/02/21(水) 23:42:23.78ID:bqTl0uQM
>>234
>>249をC++で書き換え(入力値は64ビット整数の範囲内限定)
https://ideone.com/e1AM8A

元々はCで書き、4行目はなし、15行目と24行目はstrrev(s + i);だったが、Windowsのgccでは
コンパイルできたのにideoneではできなかったので、仕方なくC++にしてstd::reverseで代用した。
0271デフォルトの名無しさん
垢版 |
2024/02/22(木) 01:30:35.61ID:9s07Ijs0
>>234
Rust

fn nearest_palindrome_numbers(n: usize) -> Vec<usize> {
 let mut dd = DecimalDigits::new(n);
 dd.palindrome_using_upper_half();
 let n1 = dd.to_number();
 match compare(n, n1) {
  Equal => return vec![n],
  Greater => dd.increment_upper_half(),
  Less => dd.decrement_upper_half(),
 }
 if dd.is_most_upper_zero() {
  return vec![n - 1, n + 1];
 }
 dd.palindrome_using_upper_half();
 let n2 = dd.to_number();
 match compare_absolute_diff((n, n1), (n, n2)) {
  Less => return vec![n1],
  Greater => return vec![n2],
  Equal => return if n1 < n2 { vec![n1, n2] } else { vec![n2, n1] },
 }
}
0272266
垢版 |
2024/02/22(木) 01:47:44.56ID:c61GBvnr
>>267
N=17=1*10+7*1のとき、Nは2桁(偶数桁)でM=1*1=1
B(M)=B(1)=11はNより小さいのでB(M-1)は考えなくてよい
B(M+1)=B(2)=22なので11,22が答えの候補
11より22のほうが17に近いので22が答え

ちょっとNに対するMの説明が足りてなかったけど言葉で上手く言い表せないすみません(上位半分以上かつ最小の桁数を抜き出す、的な)
0274デフォルトの名無しさん
垢版 |
2024/02/22(木) 21:04:16.48ID:3p8Kt6H4
>>234
>>269の一部でC++の機能をどうせ使ってしまったので、この際、全部をC++流に変えたら
C流よりすっきり書けた。
https://ideone.com/38bo2E
0275273
垢版 |
2024/02/22(木) 21:48:36.22ID:+nyM4OV5
>>273
> [1000, [1001]]

誤:ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u)]
正:ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u), p.(s.to_i.pred.abs.to_s)]

とりあえず雑に修正してみたが?
(ノ∀`)アチャー
027617
垢版 |
2024/02/23(金) 18:10:28.85ID:ZR6D6MGM
>>262
>>245のKotlinのプログラムは何も考えてなくて本当に馬鹿正直に±1して一つ一つ検査する方式で作ったんだけど、それでもあなたのテストではダメということになったの?
まあ Int (符号付32bit整数) 使ってるからその限界超えたらダメではあるんだけど、そういう問題ではなく?
0277デフォルトの名無しさん
垢版 |
2024/02/23(金) 18:58:34.05ID:9Umf93zL
>>276
それはしらみつぶしと言われる駄目プログラミングだよ
例えば求める解法が存在する方程式を解くのに値を±1しながら順に代入して試していくのと同じ
0278デフォルトの名無しさん
垢版 |
2024/02/23(金) 21:39:34.55ID:ZR6D6MGM
>>277
あー。プログラムにバグがあってまともに答えが出ないっていうことではなく何の捻りもないプログラムだからダメっていう感想ね。それならわかる。
こちらもアルゴリズム思い浮かばないけどとりあえず作ってみただけだし。ダメというほどではないが良いとも思えないプログラムなので。
0279273
垢版 |
2024/02/23(金) 23:06:54.56ID:RzwC5Hr4
>>234 ruby
https://ideone.com/E9VSE3
・273の[1000, [1001]]バグ修正版
・275とは違う方法で修正してみたがやっつけ感大

>>234 ruby 2.5.5
https://ideone.com/1zqSr1
・いわゆる(?)ジェネレータ版
・「終端を持たない範囲オブジェクト」はRuby 2.6.0から
0282◆QZaw55cn4c
垢版 |
2024/02/24(土) 14:25:41.40ID:NZEL8Kud
異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。
異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき
その組(a, b)...(j, k) および三乗差自体を求めよ
異なる6通りの組で三乗差が相等しい場合があるかも検討せよ
0283デフォルトの名無しさん
垢版 |
2024/02/24(土) 16:47:38.19ID:KRWvIUHe
>>282
[(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)]
a^3 - b^3 == 1412774811
028417
垢版 |
2024/02/24(土) 16:52:08.36ID:Pf8MFN4C
数学、か・・・
0287デフォルトの名無しさん
垢版 |
2024/02/24(土) 22:30:55.28ID:mNVJyIZh
>>282
aが5000以下限定で>>283の解はRで5秒以内に求められた。8〜9行目は下三角行列の要素番号から
行番号と列番号を求めているだけで、>>282を解く特別なアルゴリズムというわけではない。
https://ideone.com/w4X3DC
0289デフォルトの名無しさん
垢版 |
2024/02/25(日) 21:06:57.77ID:CUQUyFSy
>>282
>>287は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、
各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。
https://ideone.com/Tefgkh

n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に
見つからなかった。
0290デフォルトの名無しさん
垢版 |
2024/02/26(月) 22:18:39.21ID:CjcYgBx5
>>282
>>289と似た手順でC++
https://ideone.com/nFRsrK

Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか
使えないので使っていない。
0292デフォルトの名無しさん
垢版 |
2024/02/27(火) 22:30:42.88ID:BJV11H6M
>>282
下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290は下三角行列の全要素を
ソートして無駄なので、列のマージに変更(要するにマージソートを途中段階から開始)
したら少し速くなった。
https://ideone.com/EZSvB3

n = 10000でも5秒以内に終わった。
https://ideone.com/huQiBe
0294デフォルトの名無しさん
垢版 |
2024/02/28(水) 23:21:09.16ID:FCtvUtiC
>>282
>>292とは別の方法で>>290を高速化
https://ideone.com/QxjmyT

1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を
Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを
区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。
Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは
それぞれD = 10002, 15009になる。
0296デフォルトの名無しさん
垢版 |
2024/03/01(金) 22:22:26.10ID:6k2oCbjk
>>282
C++
https://ideone.com/1c4s5I
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。
0297デフォルトの名無しさん
垢版 |
2024/03/01(金) 22:23:18.03ID:6k2oCbjk
>>296の続き
n = 1000000, m = 6で実行すると、12通りの解が見つかった。

[6つ組解]
424910390480793: (75978, 23919), (77385, 33768), (83482, 53935), (141705, 134268), (317982, 316575), (596001, 595602)
620174235433536: (86184, 27132), (87780, 38304), (90237, 48573), (94696, 61180), (160740, 152304), (360696, 359100)
1238805803151000: (107487, 14487), (108540, 34170), (110550, 48240), (119260, 77050), (454260, 452250), (851430, 850860)
1384074844012224: (112152, 29844), (125324, 83600), (130050, 93426), (159372, 138624), (224928, 215412), (357447, 353799)
1936290882196125: (127629, 52254), (133320, 75675), (149285, 111620), (228525, 215430), (246510, 235395), (290214, 282339)
4589726535576000: (170172, 69672), (177760, 100900), (185265, 120945), (304700, 287240), (328680, 313860), (386952, 376452)
4961393883468288: (172368, 54264), (175560, 76608), (180474, 97146), (189392, 122360), (321480, 304608), (721392, 718200)
11072598752097792: (224304, 59688), (250648, 167200), (260100, 186852), (318744, 277248), (449856, 430824), (714894, 707598)
36717812284608000: (340344, 139344), (355520, 201800), (370530, 241890), (609400, 574480), (657360, 627720), (773904, 752904)
52279853819295375: (382887, 156762), (399960, 227025), (447855, 334860), (685575, 646290), (739530, 706185), (870642, 847017)

[7つ組解]
15490327057569000: (249281, 6281), (255258, 104508), (266640, 151350), (298570, 223240), (457050, 430860), (493020, 470790), (580428, 564678)
123922616460552000: (498562, 12562), (510516, 209016), (533280, 302700), (555795, 362835), (597140, 446480), (914100, 861720), (986040, 941580)

6つ組解の(2, 7), (4, 8), (5, 10), (6, 9)番目は各括弧内で自然数比になっている。
6つ組解の5番目の2倍は7つ組解の1番目のうちの6組を構成している。
0298デフォルトの名無しさん
垢版 |
2024/03/01(金) 22:24:42.81ID:6k2oCbjk
>>282
C++
https://ideone.com/tM1cuo
>>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに
解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。
0299◆QZaw55cn4c
垢版 |
2024/03/03(日) 19:08:39.58ID:75HCbpT6
>>297
出題者です。
すごいです。ありがとうございます。私の手元ではまだ6通り解、7通り解のひとつも入手できていないので、参考になりました
私のアルゴリズムは効率が悪いようですね
0300デフォルトの名無しさん
垢版 |
2024/03/03(日) 22:19:54.92ID:ZEDvt9uH
>>282
C++
https://ideone.com/LEU7EV

>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。

>>299
どんなプログラムを書いたのか見せて。
0301デフォルトの名無しさん
垢版 |
2024/03/06(水) 22:35:52.23ID:lIZep5aT
>>282
C++
https://ideone.com/PG6UiY
>>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。

https://ideone.com/6RzW0n
n = 100万の場合にはr2の値によってデータを多数の列へ振り分けるのをやめ、列を1つにして、
その内部でr2の値により2種類に区分し、それぞれの内部で2種類にさらに区分し、…と再帰的に
区分していけば(要するにクイックソートの変形版)、1つの配列内での要素のスワップだけで済み、
キャッシュの効きが改善されるとの予想通り、n = 100万で実行速度は>>296より25%速くなった。
(原理的には>>300より非効率なのでn = 5000では>>300より当然遅い)
0303デフォルトの名無しさん
垢版 |
2024/03/09(土) 22:13:47.64ID:C74EWG6S
>>282
C++
https://ideone.com/xQD1W8
関数mainのループで配列A, B, Pに書き込まずdにだけ書き込むようにし、関数FindDuplicatesで
dの添字Pではなくdそのものをソートするように変えて、n = 1000000の場合に>>301より10%高速化。
関数PrintSolutionでa, bをmainでと同じ方法で再計算するのは非効率だが、PrintSolutionは僅か12回しか
呼ばれないため、全体の実行時間への影響は無視できる。
0306デフォルトの名無しさん
垢版 |
2024/03/10(日) 01:20:18.65ID:8NU5B5F+
>>304
面倒なので全て460円を引くと
A=0円 B=120円 C=140円
10個で760円という問題

面倒なのでさらに20で割ると
A=0円 B=6 C=7円
10個で38円という問題

つまり唯一奇数のCは偶数個が確定
Cが6個以上だと42円以上でオーバーしてNG
Cが4個だと28円で残り10円をA,Bで作れないからNG
Cが2個だと14円で残り24円はBが4個で残り4個がA
Cが0個だと0円で残り38円をA,Bで作れないからNG
つまり解は(A,B,C)=(4,4,2)しかない
0307デフォルトの名無しさん
垢版 |
2024/03/10(日) 11:20:30.42ID:Doj9A/yB
>>306
すごすぎるだろ、日本の未来を頼む
0308デフォルトの名無しさん
垢版 |
2024/03/10(日) 19:06:13.20ID:qBLPZ6x8
>>304
Rで全探索でなくちゃんと解くと
https://ideone.com/F44pCL

解が複数ある場合と全くない場合の例として、600円を540円と520円に変更したときの出力も載せた。
0309デフォルトの名無しさん
垢版 |
2024/03/10(日) 20:08:55.20ID:6qxPF4Wx
2pass案は多少工夫したらかなり速い

n ␣␣m ␣296␣ ␣301-1 ␣301-2 ␣303␣ ␣2pass
5k␣␣5 ␣ 0.5s ␣ 0.1s ␣ 0.5s ␣ 0.4s ␣ 0.1s
25k ␣5 ␣12.7s ␣ 2.5s ␣13.9s ␣11.1s ␣ 1.7s
100k␣5 ␣3m52s ␣49.3s ␣4m13s ␣3m26s ␣38.9s
1M* ␣6 ␣8h23m ␣2h50m ␣8h51m ␣6h43m ␣1h11m
*n=100万は1万サンプルの部分ループ500k≦r<510kから100倍

>>301の296と301-2の比較記述と違う傾向があるのはキャッシュ階層の違いだと思う
2passは301-1に近いけど1pass目でのランダムアクセスサイズを落としながらも
誤判定率を低く抑える(0.2%~2%)工夫をするのがお楽しみだと思う
0311デフォルトの名無しさん
垢版 |
2024/03/27(水) 23:42:08.75ID:sRZ89+IF
>>304

a = (600, 580, 460)
m = min(a)
h = set()

def buy(b, yen):
if yen < m: return
for i in range(0, len(a)):
v = a[i]
if yen >= v:
b[i] += 1
if yen == v:
h.add(str(b))
else:
buy(b, yen - v)
b[i] -= 1

buy([0, 0, 0], 5360)
for s in h: print(s)
0312デフォルトの名無しさん
垢版 |
2024/03/27(水) 23:55:15.74ID:qNf/D02g
>>304
Haskell

[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a * 460 + b * 580 + c * 600 == 5360]

output: [(0,2,7),(4,4,2)]
0313デフォルトの名無しさん
垢版 |
2024/03/28(木) 00:00:41.99ID:0Zoa9Vsx
合計10個という条件忘れてた。

[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a + b + c == 10, a * 460 + b * 580 + c * 600 == 5360]

output: [(4,4,2)]
0314デフォルトの名無しさん
垢版 |
2024/03/31(日) 11:57:53.31ID:enek7T1c
大幅に手直しした
特に前回数値が一部出てこない状態になっていたので色々と手動で最適化した
新しいアイディアを思いつかない限りはシングルスレッドでの限界に近いと思う

n m 301-1 303 2pass 2pass'
5k 5 0.1s 0.4s 0.1s 0.1s
25k 5 2.5s 11.1s 2.3s* 1.7s
100k 5 49.3s 3m26s 38.9s 27.7s
1M* 6 2h50m 6h43m 1h11m 48m10s
2M* 6 17h06m 28h27m 5h47m 3h13m
Max* 6 35h51m 51h23m 11h09m 5h47m

*前回>>309 2pass n=25kの再計測値
*n=1Mは部分ループ500k<=r<510kから100倍
*n=2Mは部分ループ500k<=r<505kから400倍
*Max:=2642245は3乗がUINT64に収まる最大
*n=Maxは部分ループ500k<=r<500k+3785から2642245/3785倍

ヒント含みの数値がこちら

n D1 D2 D3 = 5000 5001 5003 5009
false_positive = 23 / 5001 = 0.46%
total_t_pass1 = 64.220 ms 2.568 ns/iter
total_t_pass2 = 0.044 ms 0.381 ns/iter
real 0m0.097s
0315デフォルトの名無しさん
垢版 |
2024/03/31(日) 11:58:50.32ID:enek7T1c
n D1 D2 D3 = 25000 25003 25005 25006
false_positive = 171 / 25003 = 0.68%
total_t_pass1 = 1654.681 ms 2.647 ns/iter
total_t_pass2 = 1.407 ms 0.329 ns/iter
real 0m1.709s

false_positive = 2211 / 100005 = 2.21%
total_t_pass1 = 27338.298 ms 2.734 ns/iter
total_t_pass2 = 78.402 ms 0.355 ns/iter
real 0m27.692s

n D1 D2 D3 = 1000000 1000002 1000009 1000015
false_positive = 18 / 10000 = 0.18%
total_t_pass1 = 28674.338 ms 2.867 ns/iter
total_t_pass2 = 5.642 ms 0.313 ns/iter
real 0m28.897s

n D1 D2 D3 = 2000000 2000003 2000013 2000015
false_positive = 13 / 5000 = 0.26%
total_t_pass1 = 28777.424 ms 2.878 ns/iter
total_t_pass2 = 8.620 ms 0.332 ns/iter
real 0m29.015s

n D1 D2 D3 = 2642245 2642246 2642253 2642258
false_positive = 315 / 3785 = 8.32%
total_t_pass1 = 29210.857 ms 2.921 ns/iter
total_t_pass2 = 336.864 ms 0.405 ns/iter
real 0m29.800s
0316デフォルトの名無しさん
垢版 |
2024/03/31(日) 22:30:39.09ID:4FIGx2uN
>>304
ぶっちゃけ、他の言語の人と同じっぽくないので心配なんだが…。
自分なりにHaskellで全探索じゃないバージョン書いてみた。

Haskell

[(a, b, c) | a <- [0..10], b <- [0..10 - a], c <- [0..10 - (a + b)], a * 460 + b * 580 + c * 600 == 5360, a + b + c == 10]

答えは同じ[(4,4,2)]。
0317デフォルトの名無しさん
垢版 |
2024/04/01(月) 04:52:23.91ID:iTC1bSa8
少し一般化して、N個の商品があり、i番目の商品はA_i円です
合計M個購入し、価格の合計がS円であるような購入の仕方を998244353で割った余りを求めてください
だとO(N M S)より小さい計算量で解けるのかな
0318デフォルトの名無しさん
垢版 |
2024/04/01(月) 16:50:08.47ID:0Kkx57P3
2個、4個、8個…みたいにメモ化すればMはlogMにできるかもしれんね
空間がlogM倍されそうだが
0319デフォルトの名無しさん
垢版 |
2024/04/13(土) 11:43:17.27ID:itq2kjOw
ヘロンの公式を実装せよ

使用言語:C
0321デフォルトの名無しさん
垢版 |
2024/04/13(土) 23:01:22.75ID:wFZkrOeZ
>>319
https://ideone.com/YCi6qe
ヘロンが作ったもう1つの式である平方根を加算と除算の繰り返しで求める式も使用。
sqrt関数を呼び出すより実行形式ファイルサイズがほんの少しだけ小さくなる。
0323デフォルトの名無しさん
垢版 |
2024/04/14(日) 18:34:21.49ID:MHeAinLP
解答例

#include <stdio.h>
#include <math.h>

void heron(double, double, double);

int main(void)
{
double a, b, c;
printf("3辺a, b, cを入力せよ ");
scanf("%lf,%lf,%lf", &a, &b, &c);

heron(a, b, c);
}

void heron(double x, double y, double z) // heronの定義
{
double s, t;

s = (x+y+z)*0.5;
t = s*(s-x)*(s-y)*(s-z);

printf("3角形の面積は S=%g\n", sqrt(t));

return;
}
0324デフォルトの名無しさん
垢版 |
2024/04/14(日) 18:36:52.16ID:MHeAinLP
>>321 さすがですね
0325デフォルトの名無しさん
垢版 |
2024/04/15(月) 21:01:04.41ID:dSNEYg5r
>>322
p < 0 のとき(= 三角形を作れない場合)は浮動小数点数の特性に関係なく無限ループになる。
sqrt(p) と同様にNANを返すには、if (p < 0) return 0 / (p - p); を追加すれば良い。

p > 0 のときは無限ループにならないはず。以下が検証プログラム。
https://ideone.com/mzemEM

x = sqrt(p), y = p / x とすると、浮動小数点数の特性により x == y とならない場合は存在する。
このとき、xとyの仮数部を整数と見なした値(以降では「仮数整数」と呼ぶ)の差は1なので、
z = (x + y) / 2 はxとyのうち仮数整数が偶数の方に一致する。zを新たなxとして代入しyとzを
再計算すれば、今度はxの仮数整数が偶数なのでzはxに必ず一致し、>>321の収束判定条件が成立する。

具体例で見ると、p = 2 のときはxの仮数整数が奇数なので x != z となるが、zを新たなxとして代入し
再計算すれば x == z が成立する。桁上がりが起こる p = 3.9999999999999996 のときも、同様に
再計算で x == z が成立する。p = 3 のときはxの仮数整数が偶数なので x == z が成立し再計算は不要。
0326デフォルトの名無しさん
垢版 |
2024/04/15(月) 22:06:46.39ID:MxMoolaJ
>>325
解説ありがとう
俺には理解できないレベルだと分かりましたw
俺なら収束の自信が無くてDBL_EPSILONを使った判定と
ループ回数上限を組み合わせて実装しそうだ
0327デフォルトの名無しさん
垢版 |
2024/04/17(水) 05:47:35.77ID:F2fqxIYT
ヘロンの公式はそのままだと、数値計算での安定性が良くないらしいぞ
解決策は、Wikipediaの英語版の方に…
tps://en.wikipedia.org/wiki/Heron%27s_formula#Numerical_stability
0328327
垢版 |
2024/04/17(水) 05:52:23.77ID:F2fqxIYT
そしてこんなとこでもカハンせんせーの名前がが
0329デフォルトの名無しさん
垢版 |
2024/04/17(水) 16:28:33.14ID:7JRzlbtx
の長さ
この公式で計算される面積は、理論的には正しい値です。しかし、実際には、以下の理由で誤差が生じる可能性があります。

数値計算の誤差: 計算機で数値を扱う場合、有限桁しか扱えないため、丸め誤差が生じます。特に、辺の長さの値が大きく異なる三角形の場合、この誤差が顕著になります。
四捨五入誤差: 計算結果を小数点以下n桁まで表示する場合、n桁目以降の数字を切り捨てます。この四捨五入誤差も、面積の誤差に影響を与えます。

by Gemini
0330デフォルトの名無しさん
垢版 |
2024/04/17(水) 23:38:33.35ID:k4k/eSae
>>327に載っている参考文献
 William M. Kahan, ‘Miscalculating Area and Angles of a Needle-like Triangle’
 http://www.cs.berkeley.edu/~wkahan/Triangle.pdf
のTable 1の問題がパソコン等でのC++プログラムでも再現されるか試してみた。
 https://ideone.com/r4toUS

Table 1とは違い、Accurate Δが概ね正確な場合にHeron's Δ'が大きく懸け離れた不正確な値に
なってしまうことはなく、ほぼ同じ値になり差はごく僅かしかない。Table 1のような不安定性は
Table 1の計算に使われたプログラマブル関数電卓に特有の問題で、パソコン等のプログラムでは
再現されない。(パソコン等のdoubleの方が精度が高いので当然と言えば当然だが)

一方、(a, b, c) = (5278.64055, 94721.35941, 99999.99996)の場合は、逆にHeron's Δ' = 0が
正確なのにAccurate Δ = 9.53674324543714が大きく懸け離れた不正確な値になってしまう
重大な欠点がある。これは、Accurate Δの式の根号内の第2因数c - (a - b)が正確には0なのに
3.63797880709171e-12と計算されてしまい、この誤差が他の因数との乗算により増幅されるから。
Heron's Δ'の式の根号内の第4因数s - cは0と計算されるので問題ない。

double向けの入力値(a, b, c) = (31622.77777777662, 0.000000000023, 31622.77777777661)を
作れば、Heron's Δ' = 2.30085990753844e-07, Accurate Δ = 3.20111707955507e-07となり、
相対差は確かに大きくなるが、200ビットで計算したほぼ正確な値3.27490470056059e-07から
見れば両方とも不正確だから、Accurate Δの利点はない。

だから、パソコン等のプログラムでは改良版の式を使う必要がないどころか使うべきではなく、
ヘロンの公式をそのまま使う方が良い。
0331デフォルトの名無しさん
垢版 |
2024/04/18(木) 07:16:50.63ID:8T8m8Yde
>(a, b, c) = (5278.64055, 94721.35941, 99999.99996)
>c - (a - b)が正確には0なのに3.63797880709171e-12と計算されてしまい

この例に限らず、たいていの場合a,b,cはdoubleでexactに格納されて無くて
この例では「c - (a - b)が正確には0」なのをチョイスしただけでは?
0332デフォルトの名無しさん
垢版 |
2024/04/18(木) 07:30:10.21ID:PYBA8OB3
パソロジカルな三角形をパラメトライズして面積を積分する検証はどう?
数式計算での正確な値
Heronで面積計算した時の数値積分
Accurateで面積計算した時の数値積分
を比べるのがフェアかなぁと
0333デフォルトの名無しさん
垢版 |
2024/04/18(木) 07:34:09.77ID:PYBA8OB3
> 200ビットで計算したほぼ正確な値3.27490470056059e-07
この例だけ見るとAccurate Δの方が優れているように見えるので

>>331の様なチェリーピックはどちらの計算式でも出来るので平均的に近似が近い方が精度的に優れているかと
0334デフォルトの名無しさん
垢版 |
2024/04/18(木) 22:41:59.70ID:y7NBfn6/
>>331
その通り。そして、(a, b, c) = (10000.1, 10000.2, 20000.3)とすれば、正しい面積は0なのに
Heron's Δ' = 2.69745899635295とAccurate Δ = 1.34872949817647は両方とも大間違いになる。
この場合のようにHeron's Δ'での問題がAccurate Δで改善されないだけでなく、>>331の引用の
場合のようにHeron's Δ'では結果的に問題ないのにAccurate Δでは新たな問題が生じてしまうのは、
参考文献の11ページで述べられた

 An algorithm stood convicted of numerical instability if it could be replaced by
 a new algorithm at least about as fast and accurate as the old for all data,
 and good for all data for which the old algorithm was bad.

 すべてのデータに対して旧アルゴリズムと少なくとも同じくらい高速かつ正確であり、
 かつ旧アルゴリズムが悪くなるすべてのデータに対して良くなる新アルゴリズムによって
 置き換えることができるとしたら、旧アルゴリズムは数値的に不安定と判定される。

という判定条件を満たさないから、Accurate Δは改良版としての適性を欠く。

>>333
その例では有効桁数がHeron's Δ'は0桁、Accurate Δは1桁しかなく、どちらの品質も絶対的に
劣悪で、それらの間の相対的な優劣に大した意味はない。

そもそも針のように異様に細長い三角形が重箱の隅をつつくような話で、普通はそんな場合は
想定しなくても良く、ヘロンの公式で充分。そこを敢えてつつくなら、ヘロンの公式だけでなく
改良式もぼろが出てしまうだけ。
0335デフォルトの名無しさん
垢版 |
2024/04/18(木) 22:55:38.47ID:n9UdHBZN
総合すると有効桁じゃなくて精度が2桁良いし実装上は大差ないから改良版を使う、と言う方が自然では?
0336デフォルトの名無しさん
垢版 |
2024/05/01(水) 12:56:47.83ID:nIC3qyB/
スレ落ちそうなのであげ
0338デフォルトの名無しさん
垢版 |
2024/05/01(水) 22:59:10.72ID:4hNncNW1
何でこんなに過疎化しちゃったのか。前に頻繁に出題していた人がいなくなったのか。
0340デフォルトの名無しさん
垢版 |
2024/05/02(木) 16:59:52.63ID:DPVqLIsI
>>338
お題が出尽くしたってことはあるんじゃないか?
過去のお題拾ってきてそれを投稿すればいいぐらいまでスレが成熟してしまったのでは?
034217
垢版 |
2024/05/02(木) 18:44:04.16ID:LxBZq7I4
>>340
なるほど。それをやるか。
034317
垢版 |
2024/05/14(火) 05:34:03.62ID:ou5vbzLn
じゃあ10年前のこのお題(URLを書くとNGになるようなので書かない)。

プログラミングのお題スレ Part4
115 :デフォルトの名無しさん:2014/06/21(土) 18:36:45.72 ID:/fMJIWig.net

お題:文字列Aを1回以上繰り返した文字列Bが与えられたとき
文字列Aを求める。ただしAの候補が複数ある場合は最短のものとする。

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa -> a
123412312341231234123123412312341231234123 -> 1234123
oxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxx -> oxoxoxoxoxoxoxoxx
0346 警備員[Lv.18]
垢版 |
2024/05/23(木) 14:16:50.64ID:zV267ZMC
あれ?どんぐりの都合か?URL書いてあると書けなくなったような?
0347 警備員[Lv.18]
垢版 |
2024/05/23(木) 14:17:56.56ID:zV267ZMC
URLの先頭のhを抜いて書いてみよう。

>>343
Kotlin

こちらは普通に自作したやつ。
ttps://paiza.io/projects/OYy-A5rfKg7RqLzv-DKMIA

こちらは正規表現使ってとても小さくなったやつ。
ttps://paiza.io/projects/jgmtMRDhKfcjYfGAglEl3g
0348デフォルトの名無しさん
垢版 |
2024/06/01(土) 10:16:34.91ID:hzaQXY32
お題: コロン区切りの時分秒の時刻が与えられるので時分秒をそれぞれ掛け算した結果を表示せよ

例:
04:05:06
120
0349デフォルトの名無しさん
垢版 |
2024/06/01(土) 11:08:12.83ID:hzaQXY32
お題: バイト列が与えられる。先頭から解析した場合にバイトが1だったら次の4バイトを読み込んで整数として出力し、バイトが2だったら次のバイトを0が来るまで読み込んで文字列として出力せよ

入力
1 1 0 0 0 2 65 66 67 0 1 128 0 0 0

出力
1ABC128
0352 警備員[Lv.19]
垢版 |
2024/06/02(日) 04:45:03.04ID:yi3OE76t
>>348
Perl

bash のコマンドラインから入力して実行(ワンライナー)

$ perl -ne 'if(/(\d+):(\d+):(\d+)/){print $1*$2*$3,"\n"}else{print"入力エラー\n"}'
1:2:3
6
3:4:5
60
04:05:06
120
$
0354デフォルトの名無しさん
垢版 |
2024/06/03(月) 13:25:02.42ID:21u+58W3
>>348
Windows のPowershell 上で、Ruby の1-liner を使う

末尾の改行を削除して、: で分割して、
文字列を数値型に変換してから、全ての要素を掛ける。
%Q で、ダブルクォーテーションをエスケープする。つまり、split(":")

echo '01:2:09' | ruby -ne 'puts $_.chomp.split(%Q[:]).map(&:to_i).inject(:*)'

18
0356デフォルトの名無しさん
垢版 |
2024/06/07(金) 06:27:47.87ID:ZJzD8UbY
お題:引数sとnを取りシーザー暗号化を行う関数を作れ
sは平文、nはずらす文字数(負数可)、返り値は暗号化後の文字列
同様の関数で「Hello, World!」を暗号化し復号化せよ
0357デフォルトの名無しさん
垢版 |
2024/06/07(金) 09:04:03.36ID:tQi+9x5m
#! ruby

class String
def to_c(n)
if %r|^n|=~n
n=(n.sub(%r|^n|,"").to_i+26)%26
lb=("A".."Z").to_a.join
sb=("a".."z").to_a.join
la=lb[n..25]+lb[0..n-1]
sa=sb[n..25]+sb[0..n-1]
return self.tr(lb,la).tr(sb,sa)
else
return self
end
end
end

p "Hello,World!".to_c("n3") #=>"Khoor,Zruog!"
p "Hello,World!".to_c("n-5") #=>"Czggj,Rjmgy!"
p "Hello,World!".to_c("s") #=>"Hello,World!"
p "Khoor,Zruog!".to_c("n-3") #=>"Hello,World!"
p "Czggj,Rjmgy!".to_c("n5") #=>"Hello,World!"
0358デフォルトの名無しさん
垢版 |
2024/06/07(金) 09:04:13.66ID:tQi+9x5m
#! ruby

class String
def to_c(n)
if %r|^n|=~n
n=(n.sub(%r|^n|,"").to_i+26)%26
lb=("A".."Z").to_a.join
sb=("a".."z").to_a.join
la=lb[n..25]+lb[0..n-1]
sa=sb[n..25]+sb[0..n-1]
return self.tr(lb,la).tr(sb,sa)
else
return self
end
end
end

p "Hello,World!".to_c("n3") #=>"Khoor,Zruog!"
p "Hello,World!".to_c("n-5") #=>"Czggj,Rjmgy!"
p "Hello,World!".to_c("s") #=>"Hello,World!"
p "Khoor,Zruog!".to_c("n-3") #=>"Hello,World!"
p "Czggj,Rjmgy!".to_c("n5") #=>"Hello,World!"
0360デフォルトの名無しさん
垢版 |
2024/06/07(金) 23:24:01.54ID:KUK95Vnh
Haskell
範囲外の数値は平文字をそのまま返すこととした。

import Data.Char

cearsar n |(-26) <= n && n <= 26 = map (f n)
where
f x = chr.(+x).ord
cearsar _ = cearsar 0

sample:
ghci> cearsar 50 "Hello, World!"
"Hello, World!"
ghci> cearsar 3 "Hello, World!"
"Khoor/#Zruog$"
ghci> cearsar (-3) "Khoor/#Zruog$"
"Hello, World!"
0361デフォルトの名無しさん
垢版 |
2024/06/07(金) 23:28:58.71ID:KMptjexu
TA = [ * ?\x20 .. ?\x7E ]
TS = TA.join
def caesar( s, n ) s.tr( TS, TA.rotate( n ).join ) end

s = "Hello, World!"
p caesar( s, 0 ) #=> "Hello, World!"
p caesar( s, 1 ) #=> "Ifmmp-!Xpsme\""
p caesar( s, -1 ) #=> "Gdkkn+~Vnqkc "
p caesar( s, 20240607 ) #=> "Jgnnq.\"Yqtnf#"
p caesar( caesar( s, 20240607 ), -20240607 ) #=> "Hello, World!"
p caesar( 'HAL9000', 1 ) #=> "IBM:111"
03629
垢版 |
2024/06/11(火) 14:41:10.23ID:NjINqn/m
>>348 Perl5

($x = '04:05:06') =~ s/:/*/g;
print eval $x;
03639
垢版 |
2024/06/13(木) 14:34:57.00ID:XgNTPGgf
>>349
> 「バイトが1だったら次の4バイトを読み込んで整数として出力し、」
正直、意味がわからんかった

例で見ると
1 1 0 0 0 → 1
1 128 0 0 0 → 128
ということだが

1に続く4バイトを加算して出力するって意味だったのかいな
0365デフォルトの名無しさん
垢版 |
2024/06/13(木) 14:54:19.57ID:lNMgjwmg
>>363
出題者がエンディアンを知らなくて説明もなくリトル環境を前提にしてしまっている
エンディアンを知っている人たちは出題には書かれてないけど例よりリトル前提だと読み取ってこたえている
0366デフォルトの名無しさん
垢版 |
2024/06/13(木) 14:59:03.73ID:fAZ1qthZ
>>365
リトルエンディアンはビットが逆って事じゃ無いぞ

10 00なら
00 10だぞ
03689
垢版 |
2024/06/13(木) 17:03:39.85ID:XgNTPGgf
>>365
ああそういうことか「4バイトを読み込んで整数」と書いてあるのはそういう意味だったのか
ならわかるかも。
オレは4バイト一個一個が整数だと捉えて、それを「4バイトを読み込んで整数」とは何のこっちゃと?になってたわ
03699
垢版 |
2024/06/13(木) 17:07:01.55ID:XgNTPGgf
すまんね68系で育ったもんですぐ連想できなんだ
0370デフォルトの名無しさん
垢版 |
2024/06/14(金) 21:10:23.18ID:H7FTNa+g
>>367
例が間違えてるか説明が足りて無い

要は4バイトを読み込んでと説明してるが「一気に4バイト読み込む」とおかしくなる
1バイトずつ順に4バイトを読み込んでという説明なら例が腑に落ちる
0372 警備員[Lv.23]
垢版 |
2024/06/15(土) 16:15:42.96ID:h/vMPGM+
>>356
Kotlin

面倒なのでASCIIコード(0x20-0x7e)でしかシフトしないやつを作った。
まあでも Kotlin は Java 同様に内部でUnicodeで扱っているので平仮名とか漢字とか全然違う言語の文字とかも比較的楽に追加できると思う。

https://paiza.io/projects/5H9H1zSjDnVshGCf4JaQJg
0374デフォルトの名無しさん
垢版 |
2024/06/20(木) 17:43:48.64ID:0f6ktMCR
お題:迷路生成を様々な言語で

例:
C
https://ideone.com/a527mc
レスを投稿する


ニューススポーツなんでも実況