题目 :

给出n个一位数字 , 可以有重复 , 对这n位数字进行排列 ,有多少种不同的组合理解 :

理解 :

设 R ={r , r ,…..,r} R为n个要全排列的元素集合

  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<stdlib.h>
  4. int divisors[100];
  5. int divisorsNum;
  6. int getNextSmall(int n){
  7.     if(n==1){
  8.         return 1;
  9.     }else{
  10.         for(int i = 0;i<divisorsNum;i++){
  11.             if(divisors[i]==n){
  12.                 return divisors[i-1];
  13.             }
  14.         }
  15.     }
  16.     return -1;
  17. }
  18. int isPrime(int n){
  19.     for(int i =2;i<=sqrt(n);i++){
  20.         if((n/i)*i==n){
  21.             return 0;
  22.         }
  23.     } 
  24.     return 1;
  25. }  
  26. int function(int n,int m){
  27.     printf("%d %d \n",n,m);
  28. //    system("pause");
  29.     if(m==-1){
  30.         printf("出错");
  31.         system("pause"); 
  32.     }
  34.     //如果n是质数 那么只有一种情况 
  35.     if(isPrime(n) == 1 || n ==2 ||m==1){
  36.         return 1;
  37.     }
  38.     //n的因子不可能大于 m 
  39.     else if(n<m){
  40.         return function(n,n);
  41.     }
  42.     //类似于 q(12,12) = q(12,6) +1 
  43.     else if(n==m){
  44.         return function(n,getNextSmall(n)) + 1;
  45.     }
  46.     //类似于 q(12,6) = q(2,6) + q(12,4) 
  47.     //                  包括6     不包括6 
  48.     else if(n>m){
  49.         int nextSmall = getNextSmall(m);
  50.         return function(n/m,m) + function(n,nextSmall);
  51.     }
  52. } 
  53. int main()
  54. {
  55.     int n;
  56.     while(1){
  57.         printf("请输入一个数 : "); 
  58.         scanf("%d",&n);
  59.         divisorsNum = 0;
  60.         //获得所有因子 
  61.         for(int i =1;i<=n;i++){
  62.             if(n==(n/i)*i){
  63.                 divisors[divisorsNum] = i;
  64.                 divisorsNum++; 
  65.             }
  66.         }    
  67.         //获得所有组成
  68.         printf("---> %d 的因式分解个数(非质数包括 [1,%d] 和 [%d,1]) : %d\n",n,n,n,function(n,n)); 
  69.     } 
  70.     return 0;
  71. }