[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
927(7): 蟻人間 ◆T6xkBnTXz7B0 [sage] 2023/07/13(木) 21:54:33.63 ID:pFytGTyV(1/2) AAS
お題: 入力として32ビット整数のビットマスクが与えられる。
ビットマスクに含まれる有効なビットの組み合わせをブルートフォースせよ。
例)
0x13
→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x45
→(0x1, 0x4, 0x5, 0x40, 0x41, 0x44, 0x45).
0x92C
→？？？
928(1): デフォルトの名無しさん [sage] 2023/07/13(木) 22:05:50.51 ID:zo6OijSK(1) AAS
>>927
>→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x0 は含まないルール？
930: デフォルトの名無しさん [] 2023/07/13(木) 23:34:46.42 ID:Gk3QqB7S(1) AAS
>>927
Haskell
外部ﾘﾝｸ:ideone.com
932: デフォルトの名無しさん [] 2023/07/14(金) 00:29:53.20 ID:iQAPuZ6f(1/2) AAS
>>927
R
外部ﾘﾝｸ:www.ideone.com
935(1): 638 [sage] 2023/07/14(金) 16:41:43.17 ID:9h33JNqm(1/2) AAS
>>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
942: デフォルトの名無しさん [sage] 2023/07/15(土) 03:29:30.91 ID:deBIZu3e(1) AAS
>>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 )
964(1): デフォルトの名無しさん [sage] 2023/07/21(金) 07:58:12.84 ID:XtiUJMX6(1/2) AAS
>>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
})
})
}
969: デフォルトの名無しさん [sage] 2023/07/22(土) 07:20:14.13 ID:Ya5NOP1D(1) AAS
>>966なるほど！
専ブラではなくWebブラウザから見るとインデントスペースが消えてしまうのですね
>>927
Rust全文
外部ﾘﾝｸ:play.rust-lang.org
抜粋 (全角スペース使用)
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()
})
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.048s