どう書く？orgにて、なぜかどうしても気になる問題があって頭を悩ませてしょうがないのでまじめに考えてみました。
2^i * 3^j * 5^k なる整数
2^i * 3^j * 5^k なる整数
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:1 = 2^0 * 3^0 * 5^0
2 = 2^1 * 3^0 * 5^0
3 = 2^0 * 3^1 * 5^0
4 = 2^2 * 3^0 * 5^0
5 = 2^0 * 3^0 * 5^1
6 = 2^1 * 3^1 * 5^0
8 = 2^3 * 3^0 * 5^0
9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0
※解答では i, j, k の各値を示す必要はありません。
Java版
package q206;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Q206 {
public static void main(String[] args) {
Q206 q206 = new Q206(2, 3, 5);
q206.printUpTo(100);
}
private final Map<Long, long[]> a = new TreeMap<Long, long[]>();
private final int[] primes;
private final Crawler crawler;
/**
* @param primes
*/
public Q206(int... primes) {
Arrays.sort(primes);
this.primes = primes;
long[] one = new long[primes.length];
a.put(1L, one);
crawler = new Crawler(Arrays.copyOf(one, one.length), 0);
}
/**
* @param limit
*/
public void printUpTo(int limit) {
for(long i = 1; a.size() < limit; i *= primes[primes.length - 1]) {
crawler.crawl(i);
}
int i = 0;
for(Map.Entry<Long, long[]> entry : a.entrySet()) {
StringBuilder builder = new StringBuilder(String.format("%3d : ",
i + 1));
builder.append(String.format("%4d = %2d^%2d", entry.getKey(),
primes[0], entry.getValue()[0]));
for(int j = 1; j < primes.length; j++) {
builder.append(String.format(" * %2d^%2d", primes[j], entry
.getValue()[j]));
}
System.out.println(builder.toString());
i++;
if(i >= limit) {
break;
}
}
}
private class Crawler {
private final long[] pow;
private final int idx;
private long current = 1;
private final List<Crawler> crawlers = new ArrayList<Crawler>();
public Crawler(long[] pow, int idx) {
this.pow = pow;
this.idx = idx;
for(int i = 0; i < primes.length; i++) {
for(int j = 0; j < pow[i]; j++) {
current *= primes[i];
}
}
if(idx < pow.length - 1) {
crawlers.add(new Crawler(Arrays.copyOf(pow, pow.length),
idx + 1));
}
}
public void crawl(long limit) {
while(current < limit) {
current *= primes[idx];
pow[idx]++;
a.put(current, Arrays.copyOf(pow, pow.length));
if(idx < pow.length - 1) {
crawlers.add(new Crawler(Arrays.copyOf(pow, pow.length),
idx + 1));
}
}
for(Crawler crawler : crawlers) {
crawler.crawl(limit);
}
}
}
}Ruby版
class Q206
attr_reader :a, :primes
def initialize(primes)
@primes = primes.sort
one = Array.new(primes.size){0}
@a = { 1 => one }
@crawler = Crawler.new(@primes, @a, one.dup, 0)
end
def upto(limit)
i = 1
while @a.size < limit
@crawler.crawl(i)
i *= @primes[-1]
end
j = 0
@a.keys.sort.each do |key|
j += 1
yield j, key, @a[key]
if j >= limit
break;
end
end
end
class Crawler
def initialize(primes, a, pow, idx)
@primes = primes
@a = a
@pow = pow
@idx = idx
@cur = 1
primes.size.times do |i|
pow[i].times do
@cur *= primes[i]
end
end
@crawlers = []
if idx < pow.size - 1
@crawlers.push(Crawler.new(@primes, @a, @pow.dup, @idx+1))
end
end
def crawl(limit)
while @cur < limit
@cur *= @primes[@idx]
@pow[@idx] += 1
@a[@cur] = @pow.dup
if @idx < @pow.size - 1
@crawlers.push(Crawler.new(@primes, @a, @pow.dup, @idx+1))
end
end
@crawlers.each do |crawler|
crawler.crawl(limit)
end
end
end
end
q206 = Q206.new([2,3,5])
q206.upto(100) do |i,num,a|
printf "%3d : %4d = %2d^%2d", i, num, q206.primes[0], a[0]
1.upto(q206.primes.size-1) do |j|
printf " * %2d^%2d", q206.primes[j], a[j]
end
puts ''
end
