【九度OJ 1214】|【剣指offer 34】ブス数

タイトルの説明:
因子2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
入力:
入力は整数N(1<=N<=1500)を含む.
出力:
複数組のテストデータがある可能性があり、各組のデータに対してN番目のブス数を出力します.
方法一:(ざらざらしている)

import java.util.Scanner;

public class CopyOfMain {

	public boolean isPrime(int number){
		boolean flag = true;
		for(int i = 2; i <= Math.sqrt(number); i++){
			if(number % i == 0){
				flag = false;
				break;
			}
		}
		return flag;
	}
	public boolean isUgly(int number){
		if(isPrime(number)){
			if(number == 2 || number == 3 || number == 5 || number == 1)
				return true;			
			else{
				return false;
			}
		}
		boolean flag = false;
		for(int i = 2; i < Math.sqrt(number) + 1; i++){
			int a = number % i;
			if(a == 0){
				flag = isUgly(i)&&isUgly(number/i);
			}
		}
		return flag;
	}
	public void countUgly(int count){
		if(count <= 6)
			System.out.println(count);
		else{
			int j = 6;
			int number = 7;
			while(j < count){
				if(isUgly(number++)){
					j++;
				}
			}
			System.out.println(number-1);
		}
	}
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		CopyOfMain m = new CopyOfMain();
		m.countUgly(s.nextInt());
	}

}

どう思う!非常に非効率的な最後のRuntimeout
方法2

import java.util.Scanner;

public class Copy_2_of_Main {

	public boolean isUgly(int number) {
		while (number % 2 == 0)
			number /= 2;
		while (number % 3 == 0)
			number /= 3;
		while (number % 5 == 0)
			number /= 5;
		return number == 1;
	}

	public void countUgly(int count) {
		int j = 0;
		int number = 1;
		while (j < count) {
			if (isUgly(number++)) {
				j++;
			}
		}
		System.out.println(number - 1);
	}

	public static void main(String[] args) {
		// Scanner s = new Scanner(System.in);
		Copy_2_of_Main m = new Copy_2_of_Main();
		// m.countUgly(s.nextInt());
		for (int i = 1; i < 20; i++)
			m.countUgly(i);
	}

}

は依然として効率の問題であり、非醜数を追加的に計算する.
方法3:(参考http://www.cnblogs.com/mingzi/archive/2009/08/04/1538491.html)

import java.util.Scanner;

public class Main {

	public void countUgly(int count) {
		if(count <= 0)return;
		int[] array = new int[count];
		int pos = 0;
		array[0] = 1;
		int i = 0;
		int j = 0;
		int k = 0;
		while (pos < count - 1) {
			while (array[pos] >= array[i] * 2)
				i++;
			while (array[pos] >= array[j] * 3)
				j++;
			while (array[pos] >= array[k] * 5)
				k++;
			array[++pos] = Min(array[i] * 2, array[j] * 3, array[k] * 5);
		}
		System.out.println(array[pos]);
	}

	public int Min(int a, int b, int c) {
		a = Math.min(a, b);
		return Math.min(a, c);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		Main m = new Main();
		while(s.hasNext())
			m.countUgly(s.nextInt());
	}

}

は、非醜数の整数に時間を費やさずに醜数のみを計算しようとした.ブス数の定義によると、ブス数は別のブス数に乗算されるべきだ.
2
、
3
または
5
の結果(
1
を除く).そのため、配列を作成することができます.中の数字は順序の悪い数です.中の各丑数は前の丑数に乗じて
2
、
3
または
5
手に入れた.1つの配列サイズの丑数シーケンスが既知である場合、次の丑数は必ず既知の最大丑数より大きく、この丑数は既知の配列内の丑数である.
乗算
2
、
3
または
5
と入力します.したがって、既知の配列の丑数に2、3、5を乗じて得られた最初の既知の最大丑数よりも大きい値を見つけてから、この3つの値を比較することができます.最小の値は要求された丑数です.
このアルゴリズムは非醜数の整数で計算する必要がないので,時間的複雑さはずっと低い.