蓝桥杯算法提高VIP-产生数-题解（C语言代码——>详细解答）

解题思路：

  1.本题出现两个大数，超出整型存储范围，so第一个采用string类来定义后期转换成数字即可，第二个是结果输出，若一个数字变换9次则最多需要9^30，需要用高精度乘法计算

  2.输入：

     string str;int k//表示变换次数

  3.利用while循环对flag[][]数组进行初始化，flag[i][j]表示i变换成-->j，将flag[i][j]=1；

  4.1--->2,2-->3故1--->3可以利用佛洛依德算法进行实现

for(int k=1;k<10;k++){
		for(int i=0;i<10;i++){
			for(int j=1;j<10;j++){
				if(flag[i][k]&&flag[k][j]){//k与j对称 
					flag[i][j]=1;
				}
			}
		}
	}

     计数每个数字的变换次数

for(int i=0;i<10;i++){
		flag[i][i]=1;
		for(int k=0;k<10;k++){
			if(flag[i][k]){
				j[i]++;//j[i]  表示数字i变换的次数是j[i]
			}
		}
	}

    5. 乘法分析

len-->str.length();

for循环遍历i =0 to len{

首先获取字符将其变为数字，look此时该数字的变换次数x;

x=j[str[i]-'0']//紫色表示数字，j[...]表示此数字的变换次数进行相乘

c=0//进位数

for(int k=0 to 100)//100表示a[]数组的100个位置都要进行相乘

{

d-->a[k]*x+c;

a[k]=d%10;

c=d/10;

}

}

#include<bits/stdc++.h>
using namespace std;
int flag[10][10];
int a[100];//用于记录高精度乘法后的结果
int j[10]; 
void chengfa(string str,int a[],int j[]){
	int len=str.length();
	a[0]=1; 
	int d=0,c,x;
	for(int i=0;i<len;i++){
		 x=j[str[i]-'0'];
		 c=0;//进位数 
		for(int k=0;k<100;k++){
			d=a[k]*x+c;
			a[k]=d%10;
			c=d/10;
		}
	}
	for(int i=100;i>=0;i--){
		if(a[i]!=0){
			for(int k=i;k>=0;k--){
				printf("%d",a[k]);
			}
			break;
		}
	}
	printf("\n");
}
int main(){
	string str;
	int k;
	cin>>str>>k;
	int x,y;
	while(k--){
		cin>>x>>y;
		flag[x][y]=1;
	}
	//floyd佛洛依德算法
	/*
	0->1,1->1    1->1,1->1;
	0->1,1->2;   1->1,1->2;
	0->1,1->3;   1->1,1->3;
	0->1,1->4;   1->1,1->4;
	;;
	;;
	*/
	for(int k=1;k<10;k++){
		for(int i=0;i<10;i++){
			for(int j=1;j<10;j++){
				if(flag[i][k]&&flag[k][j]){//k与j对称 
					flag[i][j]=1;
				}
			}
		}
	} 
	for(int i=0;i<10;i++){
		flag[i][i]=1;
		for(int k=0;k<10;k++){
			if(flag[i][k]){
				j[i]++;
			}
		}
	}
	chengfa(str,a,j);
	return 0;
}

PS:欢迎多多交流！！