计算阶层码数：求n！中某个码数出现的次数

计算阶层码数：求n！中某个码数出现的次数

img


```c++

#include <iostream>
#include <string>

using namespace std;
int c[3000];
void s2BIG(string s,int a[]){
    int l=s.length();
    for(int i=1;i<=l;i++)
    {
        a[i]=s[l-i]-'0';
    }
    a[0]=l;
}

void addBIG(int a[],int b[],int c[])
{
    int al=a[0],bl=b[0],cl=max(al,bl);
    for (int i=1;i<=cl;i++){
        int t=0;
        if(i<=al)
        {
            t+=a[i];
        }
        if(i<=bl)
        {
            t+=b[i];
        }
        c[i]=t;
    }
    for (int i=1;i<cl;i++)
    {
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c[cl]>10)
    {
        c[cl+1]=c[cl]/10;
        c[cl]%=10;
        cl++;
    }
    c[0]=cl;
}
void printBIG(int a[])
{
    for(int i=a[0];i>=1;i--)
    {
        cout<<a[i];
    }
}
void mulBIG(int a[],int b,int c[])
{
    int al=a[0],cl=al;
    long long t[1005]={};
    for(int i=1;i<=cl;i++)
    {
        t[i]=a[i]*b;
    }
    for(int i=1;i<cl;i++)
    {
        t[i+1]+=t[i]/10;
        t[i]%=10;
    }
    while(t[cl]>=10)
    {
        t[cl+1]=t[cl]/10;
        t[cl]%=10;
        cl++;
    }
    for(int i=1;i<=cl;i++)
    {
        c[i]=t[i];
    }
    c[0]=cl;
}
int main(){
    int n,a;
    cin>>n>>a;
    s2BIG("1",c);
    for(int i=1;i<=n;i++)
    {
        mulBIG(c,i,c);
    }
    int cnt=0;
    for(int i=1;i<=c[0];i++)
    {
        if(c[i]==a)
        {
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}

```

啥叫码数？是指8的阶乘的结果中有几个4吗？可以定义连个函数，一个求阶乘，一个判断阶乘中4的个数

// 1000 的阶乘 2568 位  
#include <stdio.h>  
int a[3000];  
  
int fanc(int n)  
{  
    int w=0;  
    int i=0, j=0;  
    int t=n;  
    int k=0;    // 表示数据的位数。  
  
    i=0, k=0;  
    while(t)  
    {  
        a[i++] = t%10;  
        t/=10;  
        k++;  
    }  
  
    for (j=n-1; j>1; j--)  
    {  
        w=0;    // 表示进位  
        for (i=0; i<k; i++)  
        {  
            t = a[i]*j+w;  
            a[i] = t%10;  
            w = t/10;  
        }  
  
        while(w)  
        {  
            a[i++] = w%10;  
            w/=10;  
            k++;  
        }  
    }  
    return k;  
}  
  
int getp(int k,int p)
{
    int i=0,count=0; 
    for (i=k-1; i>=0; i--)  
    {  
       if(a[i] == p)
        count++;
    }  
    return count;
}

int main()  
{  
    int n,p=0,num=0;  
    int k=0;  
  
    scanf("%d%d",&n,&p);  
    k = fanc(n);  
    num = getp(k,p);
    printf("%d共有%d个\n",p,num); 
    return 0;  
} 



#include <iostream>
using namespace std;
int fact(int n)
{
    int res = 1;
    for (int i = 1; i <= n; i++)
    {
        res *= i;
    }
    return res;
}
int cal(int n, int k)
{
    int res = 0;
    while (n != 0)
    {
        if (n - n / 10 * 10 == k)
        {
            res++;
        }
        n /= 10;
    }
    return res;
}
int main()
{
    int n, k; cin >> n >> k;
    int f = fact(n);
    int res = cal(f, k);
    cout << res << endl;
}

img

如下，有问题请回复

img

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long fact(long long n)//求n！ 
{
    int fac=1;
    if(n==0)
    return 0;
    while(n>1)
    {
        fac*=n;
        n--;
    }
    return fac;
}
int main()
{
    long long n,m;
    scanf("%lld",&n);
    char t[250];
    m=fact(n);
    itoa(m,t,10);//数字转字符串 
    int p,len=strlen(t),j,count=0;
    scanf("%d",&p);
    for( j=0; j<len ; j++)
    {
        if(t[j]==p+'0')
        {
            count++;
        }
    }
    printf("%d",count);
    return 0;
}


#include<iostream>
using namespace std;

int a[5000+10]={0};
int main()
{
      a[1]=1;
      int n,i,j,k,m;
      int p=1,jw=0;
      cin>>n>>m;
      for(i=2;i<=n;i++)
      {
            jw=0;
            for(j=1;j<=p;j++)
            {
            a[j]=a[j]*i+jw;
            jw=a[j]/10;
            a[j]%=10;
            }
            while(jw>0)
           {
            a[j]=jw%10;
            jw/=10;
            j++;
            }
            p=j-1;
      }
      long long sum=0;
      for(i=p;i>=1;i--)
      {
            if(a[i]==m)
            {
            sum++;
            }
      }
        cout<<sum<<endl;
   
    return 0;
}

完善了查找功能，可搜索大于1位数的指定数据

#include <string>
#include<stdlib.h>
#include <sstream>
using namespace std;

/// 求一次的乘积
int getSingleFactorialByNum(int num, int result[], int index, int remainderNum, int lastindex)
{
    int tmp = result[index] * num + remainderNum;
    result[index] = tmp % 10;
    remainderNum = tmp / 10;
    if (index >= lastindex && remainderNum == 0 && result[index] == 0)
        return index - 1;
    return getSingleFactorialByNum(num, result, index + 1, remainderNum, lastindex);
}


/// 求num的阶乘
int getFactorialByNum(int num, int result[], int& lastindex)
{
    if (num > 10000 || num < 1)
    {
        result[0] = -1;
        return -1;
    }
    if (num == 1)
    {
        return lastindex;
    }
    lastindex = getSingleFactorialByNum(num, result, 0, 0, lastindex);
    return     getFactorialByNum(num - 1, result, lastindex);
}

/// <summary>
///  获取数据长度
/// </summary>
int getLen(int num)
{
    if (num / 10 == 0)
        return 1;
    return getLen(num / 10) + 1;
}

/// <summary>
///  判断指定位置是否有匹配的码数
/// </summary>
int isFindNum(int specialNum, int result[],int index, int len)
{
    if (len < 1)
        return 1;
    if (result[index - len + 1] != specialNum % 10)
        return 0;
    return isFindNum(specialNum/10, result,index,len-1);
}

/// <summary>
///  查找指定码数个数，包括大于1位的数据
/// </summary>
int searchCount(int result[], int num, int len, int count, int lastindex)
{
    if (lastindex - len + 1 < 0)
    {
        return count;
    }
    count = count + isFindNum(num, result, lastindex, len);
    return searchCount(result, num, len, count, lastindex-1);
}

/// sourceNum 阶乘
/// specialNum要查找的码数，可大于1位数
int findCodeRecord(int sourceNum, int specialNum)
{
    int result[4000] = { 0 };
    result[0] = 1;
    int lastIndex = 0;
    int record = getFactorialByNum(sourceNum, result, lastIndex);
    if (record < 0)
        return 0;
    return searchCount(result, specialNum, getLen(specialNum), 0, lastIndex);
}


int main()
{
    int count = findCodeRecord(1000, 33);
    string record = to_string(count);
    return 0;
}

层主问的问题，应该是递归里出现了几个4吧？ 你可以定义一个全局变量count
在递归的代码里写上
if（n == 4）
count++；
因为递归有很多层，所以四会重复计算非常多的次数，有需要可以去玩博客看看写的递归，有这个问题的详细解答

楼上说的对，提高效率的角度考虑用递归

#include <bits/stdc++.h>
using namespace std;
int c[100000];
int main()
{
  int t,n,a;
    cin>>n>>a;
    memset(c,0,sizeof(c));
    c[0]=1;
    int l=1;
    for(int j=2; j<=n; j++)//开始阶乘计算
    {
      int w=0;
      for(int k=0; k<l; k++)//高精度乘单精度
      {
        c[k]=c[k]*j+w;
        w=c[k]/10;
        c[k]%=10;
      }
      while(w>0)//处理多进位
      {
        c[l]=w%10;
        l++;
        w/=10;
      }
    }
    int sum=0;
    for(int j=0; j<l; j++)
      if(c[j]==a) sum++;//统计个数
    cout<<sum<<endl;
  return 0;
}

这个的话有公式的，可以查看相关推导，最后结论是挺简单的，站内搜索试试