此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如: 例如:12 = 1 * 12 30 = 1 * 30
= 3 * 4 = 2 * 3 * 5
= 2 * 6 = 6 * 5
= 2 * 2 * 3 = 2 * 15
总合计有4种因子分解的方法。 = 3 * 10
总合计有5种因子分解的方法。
本题目的要求即为输入正整数n ,输出因子分解方式的个数。即 T(12) = 4, T(30) = 5
10 个解决方案
#1
题目:
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如: 例如: 30 = 1 * 30
= 2 * 3 * 5
= 6 * 5
= 2 * 15
= 3 * 10
总合计有5种因子分解的方法。
本题目的要求即为输入正整数n ,输出因子分解方式的个数。即 T(12) = 4, T(30) = 5
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如: 例如: 30 = 1 * 30
= 2 * 3 * 5
= 6 * 5
= 2 * 15
= 3 * 10
总合计有5种因子分解的方法。
本题目的要求即为输入正整数n ,输出因子分解方式的个数。即 T(12) = 4, T(30) = 5
#2
解题 已经不是编程问题了吧
应该是逻辑思维问题了吧
应该是逻辑思维问题了吧
#3
找出质因数,然后求组合数
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5
#4
整数的质因数分解可以得到,就是组合数的时候确实比较麻烦,感觉像是一个NPC问题呀!万一要是有相同的质因数就麻烦了,比如24=2*2*2*3
#5
这个是我的错误,本来以为写俩例子,但是在编辑框里编完,一发贴就前提了好几行,莫怪莫怪!
#6
走素因子分解还是简单问题复杂化了.
对于一个n,我们用1...sqrt(n)去试除n,这样就获得了所有的 因子。
将这些因子从小到大排列,然后做递归。
比如因子是:2 6 8 12 ,n=1152
如果你选择了2,那么今后的因子只能从2 7 9 19选(当然前提是n能整出它们),n=1152/2;
下一次递归你可以选择6,那么今后的因子只能从6 8 12选(当然前提是n能整出它们),n=1152/2/6.
就这样。
对于一个n,我们用1...sqrt(n)去试除n,这样就获得了所有的 因子。
将这些因子从小到大排列,然后做递归。
比如因子是:2 6 8 12 ,n=1152
如果你选择了2,那么今后的因子只能从2 7 9 19选(当然前提是n能整出它们),n=1152/2;
下一次递归你可以选择6,那么今后的因子只能从6 8 12选(当然前提是n能整出它们),n=1152/2/6.
就这样。
#7
会不会有所遗漏啊?
#8
(当然前提是n能整出它们)
#9
linux-6v95:/home/owenliang/csdn/cAndCpp # cat main.cpp
#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 10000
int yin[SIZE];
int selectYin[SIZE];
int nYin;
void printResult(int,int);
void getYinZi(int num)
{
nYin=0;
for(int i=2;i<num;++i)
{
if(num%i==0)
{
yin[nYin++]=i;
}
}
printResult(0,num);
}
void printResult(int cur,int n)
{
if(n==1)
{
for(int i=0;i<cur;++i)
{
for(int j=0;j<selectYin[i];++j)
{
cout<<yin[i]<<" ";
}
}
cout<<endl;
return;
}
if(cur>=nYin)
{
return;
}
int m=1,cnt=0;
while(n%m==0)
{
selectYin[cur]=cnt;
printResult(cur+1,n/m);
m*=yin[cur];
++cnt;
}
}
int main()
{
int num;
cin>>num;
getYinZi(num);
return 0;
}
linux-6v95:/home/owenliang/csdn/cAndCpp # ./main
64
8 8
4 16
4 4 4
2 32
2 4 8
2 2 16
2 2 4 4
2 2 2 8
2 2 2 2 4
2 2 2 2 2 2
linux-6v95:/home/owenliang/csdn/cAndCpp #
#10
可以这样考虑,当某个数n分解成几个数乘积 x1 * x2 * x3时,肯定有大小之分,我们肯定能找到其中最小的数,比如是x1,则x2,x3肯定比x1大,我们在确定了x1之后,剩下的任务即找出所有n/x1能分解成几组数相乘,并且分解的每组中每个数都要比x1大,所以解法是:
一,2...sqrt(n)找到所有能被n整除的数,如n=12时找到2,3
二,针对找出的2,3,分别处理:
1)最小数是2时,递归求12/2也就是6的分组数,同时注意每个数不得小于2(本身算合法的一组,即 1*本身).
2)最小数是3时,递归求12/3也就是4的分组数,同时注意每个数不得小于3(本身除外),所以只有自己本身这一组。
三,把1)跟2)的相加,再加1(本身)
一,2...sqrt(n)找到所有能被n整除的数,如n=12时找到2,3
二,针对找出的2,3,分别处理:
1)最小数是2时,递归求12/2也就是6的分组数,同时注意每个数不得小于2(本身算合法的一组,即 1*本身).
2)最小数是3时,递归求12/3也就是4的分组数,同时注意每个数不得小于3(本身除外),所以只有自己本身这一组。
三,把1)跟2)的相加,再加1(本身)
#1
题目:
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如: 例如: 30 = 1 * 30
= 2 * 3 * 5
= 6 * 5
= 2 * 15
= 3 * 10
总合计有5种因子分解的方法。
本题目的要求即为输入正整数n ,输出因子分解方式的个数。即 T(12) = 4, T(30) = 5
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如: 例如: 30 = 1 * 30
= 2 * 3 * 5
= 6 * 5
= 2 * 15
= 3 * 10
总合计有5种因子分解的方法。
本题目的要求即为输入正整数n ,输出因子分解方式的个数。即 T(12) = 4, T(30) = 5
#2
解题 已经不是编程问题了吧
应该是逻辑思维问题了吧
应该是逻辑思维问题了吧
#3
找出质因数,然后求组合数
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5
#4
整数的质因数分解可以得到,就是组合数的时候确实比较麻烦,感觉像是一个NPC问题呀!万一要是有相同的质因数就麻烦了,比如24=2*2*2*3
#5
这个是我的错误,本来以为写俩例子,但是在编辑框里编完,一发贴就前提了好几行,莫怪莫怪!
#6
走素因子分解还是简单问题复杂化了.
对于一个n,我们用1...sqrt(n)去试除n,这样就获得了所有的 因子。
将这些因子从小到大排列,然后做递归。
比如因子是:2 6 8 12 ,n=1152
如果你选择了2,那么今后的因子只能从2 7 9 19选(当然前提是n能整出它们),n=1152/2;
下一次递归你可以选择6,那么今后的因子只能从6 8 12选(当然前提是n能整出它们),n=1152/2/6.
就这样。
对于一个n,我们用1...sqrt(n)去试除n,这样就获得了所有的 因子。
将这些因子从小到大排列,然后做递归。
比如因子是:2 6 8 12 ,n=1152
如果你选择了2,那么今后的因子只能从2 7 9 19选(当然前提是n能整出它们),n=1152/2;
下一次递归你可以选择6,那么今后的因子只能从6 8 12选(当然前提是n能整出它们),n=1152/2/6.
就这样。
#7
会不会有所遗漏啊?
#8
(当然前提是n能整出它们)
#9
linux-6v95:/home/owenliang/csdn/cAndCpp # cat main.cpp
#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 10000
int yin[SIZE];
int selectYin[SIZE];
int nYin;
void printResult(int,int);
void getYinZi(int num)
{
nYin=0;
for(int i=2;i<num;++i)
{
if(num%i==0)
{
yin[nYin++]=i;
}
}
printResult(0,num);
}
void printResult(int cur,int n)
{
if(n==1)
{
for(int i=0;i<cur;++i)
{
for(int j=0;j<selectYin[i];++j)
{
cout<<yin[i]<<" ";
}
}
cout<<endl;
return;
}
if(cur>=nYin)
{
return;
}
int m=1,cnt=0;
while(n%m==0)
{
selectYin[cur]=cnt;
printResult(cur+1,n/m);
m*=yin[cur];
++cnt;
}
}
int main()
{
int num;
cin>>num;
getYinZi(num);
return 0;
}
linux-6v95:/home/owenliang/csdn/cAndCpp # ./main
64
8 8
4 16
4 4 4
2 32
2 4 8
2 2 16
2 2 4 4
2 2 2 8
2 2 2 2 4
2 2 2 2 2 2
linux-6v95:/home/owenliang/csdn/cAndCpp #
#10
可以这样考虑,当某个数n分解成几个数乘积 x1 * x2 * x3时,肯定有大小之分,我们肯定能找到其中最小的数,比如是x1,则x2,x3肯定比x1大,我们在确定了x1之后,剩下的任务即找出所有n/x1能分解成几组数相乘,并且分解的每组中每个数都要比x1大,所以解法是:
一,2...sqrt(n)找到所有能被n整除的数,如n=12时找到2,3
二,针对找出的2,3,分别处理:
1)最小数是2时,递归求12/2也就是6的分组数,同时注意每个数不得小于2(本身算合法的一组,即 1*本身).
2)最小数是3时,递归求12/3也就是4的分组数,同时注意每个数不得小于3(本身除外),所以只有自己本身这一组。
三,把1)跟2)的相加,再加1(本身)
一,2...sqrt(n)找到所有能被n整除的数,如n=12时找到2,3
二,针对找出的2,3,分别处理:
1)最小数是2时,递归求12/2也就是6的分组数,同时注意每个数不得小于2(本身算合法的一组,即 1*本身).
2)最小数是3时,递归求12/3也就是4的分组数,同时注意每个数不得小于3(本身除外),所以只有自己本身这一组。
三,把1)跟2)的相加,再加1(本身)