2^i * 3^j * 5^k なる整数
Posted feedbacks - D
因数分解する方針で。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | import std.stdio;
struct HammingNumbers {
static bool isHammingNumber(uint n) {
static bool[uint] memo;
if(n == 1) return true;
if(auto p = n in memo) return *p;
if(n % 2 == 0)
return memo[n] = isHammingNumber(n / 2);
if(n % 3 == 0)
return memo[n] = isHammingNumber(n / 3);
if(n % 5 == 0)
return memo[n] = isHammingNumber(n / 5);
return memo[n] = false;
}
static int opApply(int delegate(ref const(size_t), ref const(uint)) dg) {
size_t i = 0;
uint n = 1;
while(true) {
if(isHammingNumber(n)) {
if(auto result = dg(i, n))
return result;
i++;
}
n++;
}
}
}
void main(){
foreach(i, n; HammingNumbers) {
if(i == 100) break;
writeln(i, ": ", n);
}
}
|
leque
#7554()
Rating1/3=0.33
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:
※解答では i, j, k の各値を示す必要はありません。
[ reply ]