精华内容
下载资源
问答
  • 整数因子分解问题.zip

    2020-06-01 18:10:44
    利用C++实现整数因子分解问题,通过input.txt文件输入数据,最终的结果输出到output.txt文件中,对该过程有较好的理解
  • 整数因子分解问题

    千次阅读 2019-03-30 13:59:42
    比如说题中例子12,如果把分解后的第一项设a,并且12%a为0,那么12/a的整数分解问题就是一个相同的递归过程。程序设计也很简单,只需要在一个遍历循环中嵌套一个函数即可实现。 主要代码如下: void deposi(int num,...

    问题的分析:

    该问题实际可以看成一个递归的过程。比如说题中例子12,如果把分解后的第一项设a,并且12%a为0,那么12/a的整数分解问题就是一个相同的递归过程。程序设计也很简单,只需要在一个遍历循环中嵌套一个函数即可实现。

    主要代码如下:

    void deposi(int num,int *count) {
    	if (num == 1) {
    		(*count) += 1;
    	}
    	else {
    		for (int i = 2;i <= num;i++) {
    			if (num%i == 0) {
    				deposi(num / i, count);
    			}
    		}
    	}
    }
    
    

    算法复杂度分析:

    递归调用次数上限为log2(n),每次进行循环次数为n,嵌套循环。复杂度上限为n^log2(n),是一个相当大的复杂度。

    算法改进:

    参考相关资料后,设计出动态规划算法。主要思想即,使程序具备一定的记忆存储功能。
    举个简单的例子,12的因子可以写成1,2,3,4,6,12。对于1,2,3均只含有本身一个分解。对于4,含有因子1和2,1和2的分解方式均为一种,所以4可以分解为14和22。同理,对于12的因子1,2,3,4,6,所以有12=112,26,34,43(4包含两种分解方式),6*2(6包含三种分解方式),可以得出12一共存在1+1+1+2+3=8种分解方式。
    代码分两块完成,分别实现找因子和统计分解方式。

    改进后的算法复杂度分析:

    int yinzi(int num, int* a) {
    	int k = 0, i;
    	for (i = 1;i < sqrt(num);i++) {
    		if (num%i == 0) {
    			a[k++] = i;
    			a[k++] = num / i;
    		}
    	}
    	if (i*i == num) {
    		a[k++] = i;
    	}
    	return k;
    }
    
    

    寻找因子只使用一层循环,复杂度为O(n)。

    void kk(int* a,int* b, int k) {
    	b[0] = 1;
    	for (int i = 1;i < k;i++) {
    		b[i] = 0;//init
    		for (int j = 0;j < i;j++) {
    			if (a[i] % a[j] == 0) {
    				b[i] += b[j];
    			}
    		}
    	}
    }
    
    

    统计分解方式种使用嵌套循环,复杂度为O(n^2)。
    所以总的复杂度为O(n^2),较递归遍历有巨大的改进。因为递归中存在大量重复运算,而动态规划的主要优点就是避免了重复运算。

    作业的代码

    #include <iostream>
    #include <fstream>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    
    void deposi(int num,int *count) {
    	if (num == 1) {
    		(*count) += 1;
    	}
    	else {
    		for (int i = 2;i <= num;i++) {
    			if (num%i == 0) {
    				deposi(num / i, count);
    			}
    		}
    	}
    }
    
    //动态规划
    int yinzi(int num, int* a) {
    	int k = 0, i;
    	for (i = 1;i < sqrt(num);i++) {
    		if (num%i == 0) {
    			a[k++] = i;
    			a[k++] = num / i;
    		}
    	}
    	if (i*i == num) {
    		a[k++] = i;
    	}
    	return k;
    }
    void kk(int* a,int* b, int k) {
    	b[0] = 1;
    	for (int i = 1;i < k;i++) {
    		b[i] = 0;//init
    		for (int j = 0;j < i;j++) {
    			if (a[i] % a[j] == 0) {
    				b[i] += b[j];
    			}
    		}
    	}
    }
    
    void main() {
    	int num_in;
    	ifstream inFile("D:\\suanfa\\课程学习\\IntegerDecomposition\\input.txt");
    	ofstream outFile("D:\\suanfa\\课程学习\\IntegerDecomposition\\output.txt");
    	inFile >> num_in;
    	cout << "输入=" << num_in << endl;
    	int count = 0;
    	deposi(num_in, &count);
    	cout << count << endl;
    	outFile << count;
    	//动态规划 所有因子的分解方式的累加和,包含关系
    	int *a = new int[num_in];
    	int *b = new int[num_in];
    	int k = yinzi(num_in, a);
    	sort(a, a + k);//a->a+k-1
    	kk(a, b, k);
    	cout << b[k-1] << endl;
    	inFile.close();
    	outFile.close();
    	system("pause");
    }
    

    对了,sort处也存在算法复杂度,但它<O(nlgn),也就小于O(n^2)。

    展开全文
  • 整数因子分解问题 算法设计思路: n=x1*x2*x3*…*xm,分治思想设计(分解过程): n=x1*(x2*x3*…*xm); n=x1*x2*(x3*…*xm); … n=x1*x2*x3*…*xm; 分治过程: void factor(int n){ int i; if(n==1)total++; else ...
  • 题意: 给定n个数a1,a2····an,依次求出相邻两个数值和,将得到一个新数列,重复上述操作,最后结果将变为一个数,问这个数除以m的余数与那些数无关?...将所有的加法过程列出来可以得到,n...

    题意:

    给定n个数a1,a2····an,依次求出相邻两个数值和,将得到一个新数列,重复上述操作,最后结果将变为一个数,问这个数除以m的余数与那些数无关?

    例如n=3,m=2时,第一次得到a1+a2,a2+a3,再求和得到a1+2*a2+a3,它除以2的余数和a2无关。1=<n<=10^5, 2=<m<=10^9

    解法:

    将所有的加法过程列出来可以得到,n个数合并成1个数需要n-1步,且最后的表达式写成初始项相加的形式 每一项的系数恰好就是一个二项式系数。

    问除以m的余数与那些数无关,其实就是问这些因子中哪些是m的倍数。我们还是用分解m质因子的方法,将m的质因子全部先分解出来,然后遍历每个二项式系数,看他们能否整除这些质因子(如果这个二项式系数改写成质因子的幂次形式,的这个幂小于m中的这个幂,就不行) 。

    除此之外还要学习的就是怎么计算这个幂次,尤其是被除数为分数的时候,分子的幂次的贡献为正,分母为负

     1 #include<cstdio>
     2 #include<vector>
     3 #include<cstring>
     4 using namespace std;
     5 int vis[100000 + 5];
     6 
     7 int work_quality_factor(int n, int quality_fac[], int frequency[])
     8 {//n是待分解的数,quality_fac[]会存放它包含的质因子,而frequency[]存放对应次数
     9  //如q_f[k]=7,fre[k]=2就表示质因数分解后里面包含有7,且次数是2
    10  //函数返回有几种质因子,比如分解了25就返回1,分解28返回2
    11     int res, temp, i;
    12     res = 0;
    13     temp = n;
    14     for (i = 2; i*i <= temp; i++)
    15         if (temp%i == 0)
    16         {
    17             quality_fac[res] = i;
    18             frequency[res] = 0;
    19             while (temp%i == 0)
    20             {
    21                 temp = temp / i;
    22                 frequency[res]++;
    23             }
    24             res++;
    25         }
    26     if (temp > 1)
    27     {
    28         quality_fac[res] = temp;
    29         frequency[res++] = 1;
    30     }
    31     return res;
    32 }
    33 
    34 int main() {
    35     int n, m;
    36     while (scanf("%d%d", &n, &m) != EOF) {
    37         n--;
    38         memset(vis, 0, sizeof(vis));
    39         int fac[100], frq[100];
    40         int primenum = work_quality_factor(m, fac, frq);
    41 
    42         for (int i = 0; i < primenum; i++) {
    43             int min_e = frq[i], x, e = 0;
    44             // c(n,k)=c(n,k-1)*(n-k+1)/k
    45             for (int k = 1; k < n; k++) {
    46                 //分成上下两部分除,上面的幂次的贡献为正,下面为负
    47                 x = n - k + 1;
    48                 while (x%fac[i]==0) { x /= fac[i]; e++; }
    49                 x = k;
    50                 while (x%fac[i]==0) { x /= fac[i]; e--; }
    51                 if (e < min_e)vis[k] = 1;
    52             }
    53         }
    54         
    55         vector<int>ans;
    56         for (int i = 1; i < n; i++)
    57             if (!vis[i])ans.push_back(i + 1);
    58         printf("%d\n", ans.size());
    59         if (!ans.empty()) {
    60             printf("%d", ans[0]);
    61             for (int i = 1; i < ans.size(); i++)
    62                 printf(" %d", ans[i]);
    63         }
    64         printf("\n");
    65     }
    66     return 0;
    67 }

     

    转载于:https://www.cnblogs.com/romaLzhih/p/9499460.html

    展开全文
  • 整数分解因子

    千次阅读 2015-09-22 23:40:50
    输入正整数n,分解整数n的质因子,并输出。 分析: 对n进行分解质因数,应先找到一个最小的质数k,是一个逐步分解过程。因为我们知道任何n=2k1∗3k2∗5k3∗7k4...n=2^{k_1}*3^{k_2}*5^{k_3}*7^{k_4}...都可以...

    输入正整数n,分解正整数n的质因子,并输出。
    分析:
    对n进行分解质因数,应先找到一个最小的质数k,是一个逐步分解的过程。因为我们知道任何n=2k13k25k37k4...都可以分解成如下形式。
    代码如下:

    1. 递归实现
    2. 循环实现
    import java.util.ArrayList;
    import java.util.Scanner;
    
    /**
     * 质因数分解
     * @author ShaoCheng
     *
     */
    public class PrimeFactor {
        public static void main(String[] args){
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            ArrayList<Integer> res = new ArrayList<>();
            ArrayList<Integer> res1 = new ArrayList<>();
            primeFactor(res, n);
            primeFactorLoop(res1, n);
            System.out.println(res);
            System.out.println(res1);
            scanner.close();
        }
    
        /**
         * 递归实现质因子分解
         * @param res 存放分解出来的质因子
         * @param n 输入正整数
         */
        public static void primeFactor(ArrayList<Integer> res, int n){
            if(n <= 1)
                return;
            for(int i = 2; i <= n; i++){
                if(n % i == 0){
                    n /= i;
                    res.add(i);
                    primeFactor(res, n);
                    break; //成功分解后跳出
                }
            }
        }
    
        /**
         * 循环实现
         * @param res 存放分解出来的质因子
         * @param n 输入正整数
         */
        public static void primeFactorLoop(ArrayList<Integer> res, int n){
            if(n <= 1)
                return;
            for(int i = 2; i <= n; i++){ //从质数因子2开始找
                if(n % i == 0){ //找到质数因子
                    n /= i;
                    res.add(i);
                }
                //看当前的n能否继续被已经找到的质因子整除殆尽
                for(int j = 0; j < res.size(); j++){
                    int factor = res.get(j);
                    if(n % factor != 0)
                        break;
                    n /= factor;
                    res.add(factor);
                }
            }
        }
    }
    展开全文
  • 因子分解

    2020-11-18 18:41:24
    证明过程有点复杂,但是道理还是很容易讲通的,因为每个大于1的数都有一个素因子,因此我们先用最小的素数2分解(如果因数有2的话),直到不能分解时,选用下一个素数继续分解。以780为例,此时得到780=2*360,对360...

    每一个大于1的正整数都可被唯一的写成素数的乘积。证明过程有点复杂,但是道理还是很容易讲通的,因为每个大于1的数都有一个素因子,因此我们先用最小的素数2分解(如果因数有2的话),直到不能分解时,选用下一个素数继续分解。以780为例,此时得到780=2*360,对360还可以进行3次公因数2的提取,得到45,然后再从3开始分解,直到待分解的数为素数时停止。

    在数学上素因子分解可以帮助我们寻找多位数的最大公因数和最小公倍数。

    后续的思考:这个代码的问题还是很多的,有些做法是用递归做的,个人觉得递归会比迭代更好。另外,仔细想想其实is_prime这个函数是 完全不需要的

    #include<stdio.h>
    #include<math.h>
    #include<string.h>
    int is_prime(int n);
    int main()
    {
        int d,i,remain,n=0,tot=0;   //数组的索引代表素因子,元素代表该素因子的幂。
        scanf("%d", &d);
        remain = d;
        if(is_prime(d))                //不讨论质数本身
            return 0;
        printf("%d=", d);
        for (i = 2; remain != 0;i++)
        {
            if(is_prime(i)){
              if(remain%i==0){
                
                    for (int j = 0;remain%i==0;j++)
             {
                 n++;
                 remain /= i;
             }
             printf("%d^%d*",i,n);
    
              }
              else{
                  continue;
              }
            }
            else{
                continue;
            }
        }
    
        return 0;
    }
    int is_prime(int n)
    {
        int num = floor(sqrt(n));
        if(n==1)
            return 0;
        else
        {
            for (int i = 2; i <= num;i++){
                if(n%i==0)
                    return 0;
            }
        }
        return 1;
    }
    
    
    展开全文
  • 问题:给定一个正整数,求解其素因子分解式。 素因子分解适合于以递归的方式处理:给定一个数N,首先找到将它分解为两个较小的数的乘积(姑且称之为二因子分解):N=N1*N2。然后进一步对N1和N2分别对其进行二因子...
  • 算法思想:1、判断是否为素数,如果是,将该数加入素因子集合,返回。... * 获取正整数的所有素因子 * n为正整数 * primes保存所有的素因子,如:8=2*2*2,12=2*2*3 */ static void getPrime(int n, vector
  • 定义:给出一个正整数,将其携程几个素数的乘积,这个过程称为整数分解。 例题:HDU_1164 https://vjudge.net/problem/HDU-1164 一、试除法 算法:令m = n,从2~sqrt(N) 一一枚举,如果当前数能够整除m,那么当前...
  • 求正整数的质因子

    2015-12-18 14:35:01
    (1)如果这个质数恰等于(小于的时候,继续执行循环)n,则说明分解质因数的过程已经结束,另外 打印出即可。 (2)但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数n.重复执行第二步。 (3)如果n不...
  • 它为代数学生提供了通过标准方法带整数系数的三项式来解决二次方程式的实践。 该应用程序的计算是使用JavaScript完成的,并且页面是由两个使用钩子的React功能组件呈现的。 求解二次方程(例如,2×2 - 3×+ 1 = 0...
  • 原理:唯一分解定理:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N等于P1的a1次方乘以P2的a2次方一直乘到Pn的an次方,这里P1<P2<P3…<Pn均为质数,其中指数ai是正整数。 ...
  • 程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成:(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。(2)如果nk,但n能被k整除,则应打印出k的值,并用n除以k的商,...
  • (1)如果这个质数恰等于(小于的时候,继续执行循环)n,则说明分解质因数的过程已经结束,另外 打印出即可。 (2)但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数n.重复执行第二步。 (3)如果n不...
  • 质因数分解

    2014-05-22 09:28:00
    整数分解(Integer factorization)又叫质因数分解(质因子分解)是指把一个正整数写成几个素数的乘积。 最简单的算法是,从2到N进行试除,能整除的时候就说明找到了一个新的因子,而这个过程中由于是从较小的数開...
  • 求n的质因子

    千次阅读 2018-09-26 20:50:32
    因子(或质因数)在数论里是指能整除给定正整数的质数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数...将一个正整数表示成质因数乘积的过程和得到的表示结果叫做质因数分解。显示质因数分解结果时,如...
  • 质数因子

    2018-04-22 19:59:37
    程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰等于(小于的时候,继续执行循环)n,则说明分解质因数的过程已经结束,另外 打印出即可。(2)但n能被k整除,则应...
  • PTA(四)连续因子

    2020-08-07 17:54:02
    给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。 1.1输入格式: 输入在一行中给出一个正整数 N(1<N<231 ​)。 1.2输出格式: 首先在第 1 行输出最长连续因子的个
  • 素数因子

    千次阅读 2015-05-15 16:40:33
    (1)如果这个质数恰等于(小于的时候,继续执行循环)n,则说明分解质因数的过程已经结束,另外 打印出即可。 (2)但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数n.重复执行第二步。 (3)如果n不...
  • 因子和阶乘

    2017-02-07 15:28:57
    = 1 * 2 * 3 * …* n分解成素因子相乘的形式,从小到大输出各个素数(2、3、5….)的指数。例如825 = 3 * 5^2 * 11,应表示成(0、1、2、0、1),即分别有0、1、2、0、1个2、3、5、7、11参加相乘。你的程序应该忽略...
  • 根据样例分析,可以xy\frac xyyx​是有限小数的条件是分母只能包含因子2和5,直觉证明,整数在进行除法的过程中,如果需要去补0,则相当于*10,而10只包含因子2和5,所以出现其他因子就不是有限循环小数。...
  • 条件:给定任意一个一个正整数N 要求:求其因子的个数 首先给出结论:对于任意的整型N,分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn; 则N的因子个数M为 M=(x1+1) * (x2+1) * …… *(xn+1); 证明过程:....
  • 数论之因子的个数

    2012-08-18 18:14:05
    条件:给定任意一个一个正整数N 要求:求其因子的个数 首先给出结论:对于任意的整型N,分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn; 则N的因子个数M为 M=(x1+1) * (x2+1) * …… *(xn+1);   证明...
  • (1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。 (2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,  重复执行第一步。 (3)如果n不能被k整除,则用k+1...
  • 这天,她在研究正整数因子个数的时候,想到了一个“快速迭代”算法。设 为 的因子个数,将 迭代下去,rin猜想任意正整数最终都会变成 。 例如: 。 她希望你帮她验证一下。她会给你一个正整数 ,让你输出它在迭代...

空空如也

空空如也

1 2 3 4
收藏数 80
精华内容 32
关键字:

整数因子分解过程