哪位大牛帮小弟解决一个程序问题?

时间:2022-11-29 14:14:35
题目:
此题是正整数分解的问题。要求给出任意正整数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

#2


解题 已经不是编程问题了吧
应该是逻辑思维问题了吧

#3


找出质因数,然后求组合数
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5

#4


引用 3 楼 ouyh12345 的回复:
找出质因数,然后求组合数
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5

整数的质因数分解可以得到,就是组合数的时候确实比较麻烦,感觉像是一个NPC问题呀!万一要是有相同的质因数就麻烦了,比如24=2*2*2*3

#5


引用 2 楼 hongwenjun 的回复:
解题 已经不是编程问题了吧
应该是逻辑思维问题了吧

这个是我的错误,本来以为写俩例子,但是在编辑框里编完,一发贴就前提了好几行,莫怪莫怪!

#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


引用 6 楼 qq120848369 的回复:
走素因子分解还是简单问题复杂化了.

对于一个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能……

会不会有所遗漏啊?

#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(本身)

#1


题目:
此题是正整数分解的问题。要求给出任意正整数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

#4


引用 3 楼 ouyh12345 的回复:
找出质因数,然后求组合数
如30=2*3*5,则30=1*(2*3*5)=2*(3*5)=3*(2*5)=5*(2*3)=2*3*5

整数的质因数分解可以得到,就是组合数的时候确实比较麻烦,感觉像是一个NPC问题呀!万一要是有相同的质因数就麻烦了,比如24=2*2*2*3

#5


引用 2 楼 hongwenjun 的回复:
解题 已经不是编程问题了吧
应该是逻辑思维问题了吧

这个是我的错误,本来以为写俩例子,但是在编辑框里编完,一发贴就前提了好几行,莫怪莫怪!

#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


引用 6 楼 qq120848369 的回复:
走素因子分解还是简单问题复杂化了.

对于一个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能……

会不会有所遗漏啊?

#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(本身)