当前位置: 代码迷 >> 数据结构与算法 >> 整数分解(解决后马上送分!),该如何解决
  详细解决方案

整数分解(解决后马上送分!),该如何解决

热度:465   发布时间:2016-05-23 09:14:06.0
整数分解(解决后马上送分!)
吧一个整数分解,要所有的组合情况。。
比如6=1*6=2*3  

我的思路是:
先把n分解成质因数,把各个分解好的质因数方在一个数组里面
然后对这些数进行排列组合

其中要排除重复的情况,比如12=2*2*3   要区分两个2的情况

这个思路似乎很麻烦。。

有没好点的提示???

解决后马上送分!!

------解决方案--------------------
分解成质因子的乘机后,用使用过的素数已经它们的次数来表示,也就是使用两个数组。
比如12=2^2*3,表示成两个数组:
prime[]={2,3};
index[]={2,1}
然后每次对每个素数选择一个次数,不超过index[]数组中的次数,就产生一个约数了。
你可以看看帖子:http://community.csdn.net/Expert/topic/5580/5580674.xml
里面函数trynum里面正好用到了产生所有约数的代码,里面的第一个do{}while()循环就是(只是这个代码只产生一半的约数:n=a*b,那么只产生a不产生b,所以代码更加复杂一些)

------解决方案--------------------
我的想法是。
比如,对于12,先从2循环到不小于12的开发的整数——4。
12/2,能除得尽,所以,在数组0位置存一个数,同时得到结果6
现在,又拿6做被除数,从2开始循环到不小于6的开方的整数——3。
(注意,这里选用2开始循环不是一定的,因为前面的循环是从2开始,所以,这里从不小于2的整数开始循环。所以,最后分解12得的乘积的乘数,都是从小到大,除掉了许动重复。)
还有一个问题,因为,我分解6的时候,是从2循环到3。但是,6可以不用分解,也能得到一个分解12的乘积,2×6。
所以在循环的后面,我加了句代码。直接把6存入要打印的数组。

具体代码如下:
(虽然和用组合质因子的方法比较起来偏慢。但是相对代码比较简单。同时,我做了实验。分解1000000的时间不到1秒。应该速度还算快的。)

public class Main {
private static final int n=12;
private static int sum[]=new int[100];
public static void main(String args[]) {
f(0,n,2);
}
public static void f(int x,int y,int z){
int a=(int)Math.ceil(Math.sqrt(y));
for (int i = z; i < a+1; i++) {
if (y%i==0) {
sum[x]=i;
f(x+1,y/i,i);
}
}
if ( y> =z && y <n ){
sum[x]=y;g(x);
}
}
public static void g(int x){
System.out.print(sum[0]);
for (int i = 1; i < x+1; i++) {
System.out.print( "* "+sum[i]);
}
System.out.print( "\n ");
}
}
------解决方案--------------------
改了下,不会出现问题了i> =a[Compare]是为了防止重复。
#include <math.h>
#include <stdio.h>
void factor(int* a,int n,int k)
{
int i,j,Compare;
if(k==0)
Compare=0;
else
Compare=k-1;
for(i=2;i <=sqrt(n);i++)
{
if(n%i==0&&i> =a[Compare])
{
a[k]=i;
for(j=0;j <=k;j++)
printf( "%d* ",a[j]);
printf( "%d\n ",n/i);
factor(a,n/i,k+1);
}

}

}
void main()
{
int a[100]={0};
int n;
printf( "Input a number: ");
scanf( "%d ",&n);
factor(a,n,0);
}
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Tue Oct 24 06:38:38 CST 2017
  • 最近登录:Tue Oct 24 06:38:38 CST 2017
  • 最近登录:Tue Oct 24 06:38:38 CST 2017
  • 最近登录:Tue Oct 24 06:38:38 CST 2017
  • 最近登录:Tue Oct 24 06:38:38 CST 2017