PTA：有趣的数

雨点打透心脏的1/2处 2021-09-26 15:26 386阅读 0赞

# 有趣的数 （20 分） #

--------------------

### 文章目录 ###

*  有趣的数 （20 分）
 *   *  1. 题目描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 输入样例
     *  5. 输出样例
     *  6. 解题思路
     *  7. 代码实现
     *  8. 题目来源

--------------------

## 1. 题目描述 ##

> Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication.  
> Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!  
> Now you are suppose to check if there are more numbers with this property.  
> That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.

## 2. 输入格式 ##

> Each input contains one test case. Each case contains one positive integer with no more than 20 digits.

## 3. 输出格式 ##

> For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.

## 4. 输入样例 ##

> 1234567899

## 5. 输出样例 ##

> Yes  
> 2469135798

## 6. 解题思路 ##

>  *  1、输入的数 “123456789” 非常大，如果输入的数足够大，就会超出了 int 、long、long long 表示整数的范围；
>  *  2、基于第一点的理由，所以需要自定义类型来存储“大数”；
>  *  3、需要进行大数的运算。题目中要求将这个大数乘以 2，所以需要自己编写大数的加法（自身相加即是自身乘以 2）或者编写大数的乘法，都可以实现大数乘以 2 的要求，然后将新的大数存储取来；
>  *  4、题目中要用到大数的每一位出现的次数，所以需要将统计大数的每一位数字出现的次数，这里可以使用一个数组来存储每一位数字出现的次数，数组大小为 10，因为十进制整数数字只有 \[0，9\] 共计 10 个；
>  *  5、将原大数乘以 2 之后得到的新大数也需要用到每一位出现的次数，操作和上面一步一摸一样；
>  *  6、比较两个数组，其中一个存储的是原来输入的大数的每一位数字出现的次数，另外一个存储的是 2 倍之后得到的新大数的每一位数字出现的次数。如果有任何一项（共 10 项）不同，那么这个原大数就不是满足题意的数字，应该输出 “No”，否则就输出 “Yes”。然后在最后一行都要输出 2 倍后的新大数。

## 7. 代码实现 ##

C语言代码如下：

/* 标准输入输出和标准库头文件 */
    	#include<stdio.h>
    	#include<stdlib.h>
    
    	/* 宏定义 */
    	#define MAX 10
    	#define INCREMENT 10
    	
    	/* 自定义类型，名称为List */
    	/* 使用List类型存储读入的数据，主要是为了大数计算 */
    	typedef struct List
    	{ 
    		/* 存放数据的地方 */
    		int *data;
    
    		/* 存储的数据长度 */
    		int length;
    
    		/* 分配的内存空间大小，没有乘上sizeof(int)得到的内存空间大小 */
    		int size;
    	}List;
    
    	/* 一个自定义函数 */
    	/* 函数功能：交换数组给定下标的两个元素 */
    	/* 参数：toSwapArray见名知意，是待交换元素的数组 */
    	/* firstIndex和secondIndex是两个数组下标 */
    	/* 这里假设传入的参数都是合法的 */
    	void swap(int toSwapArray[], int firstIndex, int secondIndex)
    	{ 
    		/* 当fristIndex和secondIndex相等时，不需要交换 */
    		if (firstIndex == secondIndex)
    		{ 
    			// empty block.
    		}
    		/* 当fristIndex和secondIndex不相等时，需要交换 */
    		else
    		{ 
    			int temp = toSwapArray[firstIndex];
    			toSwapArray[firstIndex] = toSwapArray[secondIndex];
    			toSwapArray[secondIndex] = temp;
    		}
    	}
    
    	/* 一个自定义函数 */
    	/* 函数功能：反转（翻转）数组从第一个下标到第二个下标的所有元素 */
    	/* 参数：toReverseArray见名知意，是待反转元素的数组 */
    	/* toStartIndex和toEndIndex是两个数组下标 */
    	/* toStartIndex是起始下标，toEndIndex是终止下标 */
    	/* 其中反转的元素下标包含toStartIndex和toEndIndex */
    	/* 这里假设传入的参数都是合法的 */
    	void reverseArray(int toReverseArray[], int toStartIndex, int toEndIndex)
    	{ 
    		/* 采用“双指针”--i和j */
    		/* i从toStartIndex开始往后指 */
    		/* j从toEndIndex开始往前指 */
    		int i = toStartIndex;
    		int j = toEndIndex;
    		/* 当i和j没有相遇时，交换toReverseArray[i]和toReverseArray[j] */
    		while (i < j)
    		{ 
    			swap(toReverseArray, i, j);
    			++i;
    			--j;
    		}
    	}
    
    	/* 一个自定义函数 */
    	/* 此函数有一点点超出了题目的要求，不过有这个函数最好，绝对不会出现进位错误，除非内存耗尽 */
    	/* 函数功能：当List中存放数据的空间不足时，增加分配的内存空间 */
    	void increseListSize(List *list)
    	{ 
    		/* 分配的内存一旦确定就无法改变，所以想要增加数组长度，只能重新开辟内存空间 */
    		int *tempArray = (int*)malloc(sizeof(int) *(list->size + INCREMENT));
    	
    		/* 将原数组中已有的数据填入到新数组中 */
    		for (int i = 0; i < list->length; ++i)
    		{ 
    			tempArray[i] = list->data[i];
    		}
    
    		/* 释放掉原来分配的空间，避免内存泄漏 */
    		free(list->data);
    		list->data = NULL;
    	
    		/* 将新数组和list->data连接上 */
    		list->data = tempArray;
    
    		/* 分配的内存空间数目增加 */
    		list->size += INCREMENT;
    	}
    
    	/* 一个自定义函数 */
    	/* 函数功能：判断List的数据是否存满 */
    	/* 参数：一个List指针类型的 list */
    	/* 返回值：数据已存满，返回1 */
    	/* 数据未存满，返回0 */
    	/* 这里假设传入的参数都是合法的 */
    	/* 函数意义：当分配的数据空间满时，可以及时分配新的更大空间 */
    	int fullList(List *list)
    	{ 
    		int isFullList = 0;
    		
    		/* 如果当前数据的长度和当前分配的空间大小相等时，表示满了；否则表示未满 */
    		if (list->length >= list->size)
    		{ 
    			isFullList = 1;
    		}
    		return isFullList;
    	}
    	
    	/* 一个自定义函数 */
    	/* 函数功能：大数计算--大数乘以2 */
    	/* 这里假设传入的参数都是合法的，***并且下标小的地方存储低位，下标大的地方存储高位 */
    	void doubleLargeNumbers(List *list)
    	{ 
    		/* extra表示低位的进位，由于最低位的进位为0，所以初始化为0 */
    		int extra = 0;
    
    		/* 某一位的数据乘以2加上低位进位的结果 */
    		int doubleResultInDigit = 0;
    
    		/* 循环处理每一位 */
    		for (int i = 0; i < list->length; ++i)
    		{ 
    			/* 某一位的数据乘以2加上低位进位的结果 */
    			doubleResultInDigit = (list->data[i]) * 2 + extra;
    
    			/* list->data[i]存放doubleResultInDigit对10求余的结果， 避免list->data[i]的结果大于等于10 */
    			/* 因为数字只有0~9 */
    			list->data[i] = doubleResultInDigit % 10;
    
    			/* extra保存向高位的进位 */
    			extra = doubleResultInDigit / 10;
    		}
    
    		/* 当最高位的进位不为0时，循环执行 */
    		while (extra > 0)
    		{ 
    			if (fullList(list))
    			{ 
    				increseListSize(list);
    			}
    			list->data[list->length] = extra % 10;
    			extra /= 10;
    			++(list->length);
    		}
    	}
    
    
    	/* 本题的主算法函数 */
    	/* 函数功能：接收输入，处理数据，输出结果 */
    	void interestingNumbers()
    	{ 
    		/* 申请一个List指针变量，并分配空间 */
    		List *list = (List*)malloc(sizeof(List));
    
    		/* 给数据存放地点申请空间，初始大小为MAX，并给相应的字段赋值 */
    		list->data = (int*)malloc(sizeof(int)*MAX);
    		list->length = 0;
    		list->size = MAX;
    		
    		// get input.
    		/* 将大数以字符的形式，一个一个读入并存放 */
    		char inputCharacter = 0;
    		while ((inputCharacter = getchar()) != '\n')
    		{ 
    			if (fullList(list))
    			{ 
    				increseListSize(list);
    			}
    	
    			list->data[list->length] = inputCharacter - '0';
    			++(list->length);
    		}
    	
    		// reverse
    		/* 由于最先读入的是大数的最高位，却存放在数组的最低位， 这与处理的方式不符合，应该首先将读入的数据数组进行反转 */
    		reverseArray(list->data, 0, list->length - 1);
    	
    		// statistic data.
    		/* 两个整型数组，大小都为MAX */
    		/* oneNumbersOfDigits 搜集原数的每一位的数字信息 */
    		/* doubleNumbersOfDigits 搜集新数的每一位的数字信息 */		
    		int oneNumbersOfDigits[MAX] = {  0 };
    		int doubleNumbersOfDigits[MAX] = {  0 };
    	
    		/* 搜集原数每一位的数字信息，统计每一个数字出现的次数 */
    		for (int i = 0; i < list->length; ++i)
    		{ 
    			/* list->data[i]的范围是0~9，刚好和oneNumbersOfDigits的范围0~9重合，可以巧妙的利用 */
    			++oneNumbersOfDigits[list->data[i]];
    		}
    	
    		// double list->data.
    		/* 将原数乘以2，得到新结果（新数） */
    		doubleLargeNumbers(list);
    
    		/* 搜集新数每一位的数字信息，统计每一个数字出现的次数 */
    		for (int i = 0; i < list->length; ++i)
    		{ 
    			++doubleNumbersOfDigits[list->data[i]];
    		}
    		
    	
    		// judge
    		/* 判断原数和新数每一个数字出现的次数是否相同 */
    		/* 如果相同，numbersOfDigitsEqual为1 */
    		/* 如果不相同，numbersOfDigitsEqual为0 */
    		int numbersOfDigitsEqual = 1;
    		for (int i = 0; i < MAX; ++i)
    		{ 
    			if (oneNumbersOfDigits[i] != doubleNumbersOfDigits[i])
    			{ 
    				numbersOfDigitsEqual = 0;
    				break;
    			}
    		}
    	
    		//output
    		/* 输出新数的每一位 */
    		printf("%s\n", (numbersOfDigitsEqual ? "Yes" : "No"));
    		for (int i = list->length - 1; i >= 0; --i)
    		{ 
    			printf("%d", list->data[i]);
    		}
    		printf("\n");
    	
    		// finishing processing
    		/* 扫尾处理，释放内存空间，避免内存泄漏 */
    		free(list->data);
    		list->data = NULL;
    		free(list);
    		list = NULL;
    	}
    	
    	/* 主函数 */
    	int main()
    	{ 
    		interestingNumbers();
    	    return 0;
    	}

--------------------

## 8. 题目来源 ##

PTA（Programming Teaching Assistant） [https://pintia.cn/problem-sets/17/problems/263][https_pintia.cn_problem-sets_17_problems_263]  
题目所有权归 PTA 所有。

[https_pintia.cn_problem-sets_17_problems_263]: https://pintia.cn/problem-sets/17/problems/263