d********w 发帖数: 363 | 1 打印一个整数的所有可能乘积组合,并按因子从大到小输出,例如
PrintFactors 12
12 * 1
6 * 2
4 * 3
3 * 2 * 2
其中4*3, 3*4是同样的,就没有必要打印了
在比如
PrintFactors 32
32 * 1
16 * 2
8 * 4
8 * 2 * 2
4 * 4 * 2
4 * 2 * 2 * 2
2 * 2 * 2 * 2 * 2
大家有什么好的方法,直观是把所有的可能(构成no1*no2字符串)都存入到hash表中用
来排重 | g**********y 发帖数: 14569 | 2 不用那么复杂,这种题就是brutal force + DFS
public class Decompose {
private void decompose(int N) {
dfs(N, N, "");
}
private void dfs(int N, int hi, String s) {
if (N == 1) {
if (s.contains("*")) {
System.out.println(s);
}
else {
System.out.println(s + "*1");
}
return;
}
for (int i=hi; i>1; i--) {
if (N%i == 0) {
dfs(N/i, i, s.length()==0? s+i : s+"*"+i);
}
}
}
public static void main(String[] args) {
new Decompose().decompose(1024);
}
} | s*******f 发帖数: 1114 | 3 int GetNextPrime(){ // substitute this with more excellent algorithm
static int primes[] = {2,3,5,7,11};
static int idx = 0;
return primes[idx++];
}
void PrintFactors(int n){
if (n < 0){
n = -n;
}
if (n == 0){
return;
}
int prime = 1;
while (prime <= sqrt(double(n))){
prime = GetNextPrime();
while (n % prime == 0){
printf("%d ", prime);
n /= prime;
}
}
if (n > 1){
printf("%d ", n);
}
}
【在 d********w 的大作中提到】 : 打印一个整数的所有可能乘积组合,并按因子从大到小输出,例如 : PrintFactors 12 : 12 * 1 : 6 * 2 : 4 * 3 : 3 * 2 * 2 : 其中4*3, 3*4是同样的,就没有必要打印了 : 在比如 : PrintFactors 32 : 32 * 1
|
|