馄饨阿威

用户名：13837252486

访问量：1948

签　名：

等　　级
排　　名	37848
经　　验	402
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	河南科技大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-产生数-题解(C++代码)
浏览：795

蓝桥杯基础练习-十进制转十六进制-题解(C++代码)
浏览：429

蓝桥杯算法提高VIP-最长公共子序列-题解(C++代码)
浏览：162

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

蓝桥杯算法提高VIP-产生数-题解(C++代码)

　　作者: 馄饨阿威　　　　发表时间：2020-02-24 00:23:11 浏览：795　|　评论：1　

原题链接：蓝桥杯算法提高VIP-产生数

**问题描述：**
给出一个整数  n（n< 10^30)  和  k  个变换规则（k< =15）。

规则：

一位数可变换成另一个一位数：

规则的右部不能为零。

例如：n=234。有规则（k＝2）：

2－>   5

3－>   6

上面的整数  234  经过变换后可能产生出的整数为（包括原数）:

234

534

264

564

共  4  种不同的产生数

**问题：**

给出一个整数  n  和  k  个规则。

**求出：**

经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。
[![](/image_editor_upload/20200224121441_48965.png)](文档：产生数.note 链接：http://note.youdao.com/noteshare?id=ac5a0f6a3deef223116fc411176b35f4&sub=FE4343190F6A4109ACF056816276D682)

**分析：**
本问题里出现两个地方出现特别大的数，不能直接使用整形变量进行存储，第一处，输入的整数N，范围到10的30次方，超过C++ 里long long int 存储量（long long占用8个字节，数据表示范围也从int的[−2^31,2^31−1][−2^31,2^31−1]，升级到[−2^63,2^63−1][−2^63,2^63−1]）,第二处是一个三十位的整数，每一位最多有9种变换可能（1——9），那么结果的数量是9^30也超出变量的存储范围。
把第一个输入的整数使用字符串进行接收，每一位相当于一个字符（每一位的数字大小相当于该字符与字符‘0’的ASCII差值）。
**代码：**
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int tag[10][10];//tag[i][j]=1表示存在i->j的变换 
int d[10];
int p[1000];
int main()
{
    string a;//存储输入的整数 
    int n;//输入的变换规则的个数 
    while(cin>>a>>n)
    {
        int x,y;
        for(int i=0;i<n;i++)
        {
            cin>>x>>y;
            tag[x][y]=1;
        }
        
    /**
    *推导出所有的变换规则 
	*如果存在i->k,和k->j 那么通过递推 从i->j 的变换也存在 
	*/ 
    for(int k=1;k<=9;k++)
        for(int i=0;i<=9;i++)
            for(int j=1;j<=9;j++)
                if(tag[i][k]&&tag[k][j]) tag[i][j]=1;
    
    /** 
	*求出每个数字可以变换成几种数字形态包括数字本身 
	*/ 
        for(int i=0;i<10;i++)
        {
            tag[i][i]=1;
            for(int j=0;j<10;j++)
                if(tag[i][j])
                d[i]++;
        }
        
        int z=0;
        p[0]=1;//每个数字至少有一种形态，就是他本身 
        for(int i=0;a[i];i++)
        {
            z=0;
            int x=d[a[i]-'0'];//数字字符与字符‘0’的ASCII差值等于数字的值 d[i]表示数字i存在的变换数量
			//输入整数的每一位的形态个数的乘积就是这个整数的形态个数（参考数学排列组合Ann） 
            for(int i=0;i<500;i++)
            {
                p[i]=(p[i]*x+z);//乘法运算,z是进位数 
                z=p[i]/10;
                p[i]%=10;
            }
        }
        int i=500;
        while(p[i]==0) i--;//计算出p数组有多长有效位，即，结果的整数值有多少位 
        for(;i>=0;i--)//将结果从高位到低位，输出每一位的数字，组成结果这个整数 
        {
            cout<<p[i];
        }
        cout<<endl;
    }
}
```

0.0分

41 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

早起床

niua

2022-10-10 18:31:49

馄饨阿威

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

统计字符（C语言描述运用ctype.h）

Tom数（C语言代码）

蓝桥杯算法提高VIP-产生数-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Hello, world! （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

计算质因子（C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1113题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

馄饨阿威

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

统计字符 （C语言描述运用ctype.h）

Tom数 （C语言代码）

蓝桥杯算法提高VIP-产生数-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Hello, world! （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

计算质因子 （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1113题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

统计字符（C语言描述运用ctype.h）

Tom数（C语言代码）

　　评论区

母牛的故事（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

计算质因子（C++代码）