『ACM C++』PTA浙大 | 基础题 - Have Fun with Numbers

时间:2023-11-21 17:40:56

连着这两道都是开学前数构老师的“爱心作业”,还没上课开学就给我们布置作业了,这道题有点小坑,也经常遇到类似的问题,特地拿出来记录一下。

------------------------------------------------题目----------------------------------------------------------

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.

Input Specification:

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

Output Specification:

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.

Sample Input:


Sample Output:

Yes

------------------------------------------------题目----------------------------------------------------------

(一) 原题大意:

    123456789是一个9位数的数字,它完全由1到9之间的数字组成,没有重复。加倍,我们将得到246913578,这恰好是另一个9位数字,由1到9的数字组成,也是没有重复,只是排列不同。

    简单来说,就是判断输入的数乘以2之后的结果,且结果的数和输入的书组成数字一致,且出现次数一致,例如1234567899,出现了两次9,翻倍之后2469135798,也出现两次9,则说明该数Yes,符合要求。

(二) 题目分析:

    想法一:使用long long int存储输入的数值,然后翻倍,再用分割位数的方法对比输入数和结果数是否一致来判断。

    注:这个想法是错误的,也就是我刚刚一开始说的坑点,下面贴上一个表

类型名称 字节数 取值范围
signed char 1 -128~+127 (3位)
short int 2 -32768~+32767(5位)
int 4 -2147483648~+2147483647(10位)
long int 4 -2147483648~+2141483647(10位)
long long int 8 -9223372036854775808~+9223372036854775807(19位)

    

    我们可以清楚的发现long long int 最多只能达到19位,而题目输入要求写了  no more than 20 digits. 不会超过20位,也就是说long long int 存在超范围风险,是不成立的,而且翻倍乘以2之后是存在进位风险的呢。

    想法二:既然用整型long long int都不够存的话,这时候就要使用字符串输入处理法了,将输入的每一位数都当成一个字符来处理,通过翻倍和进位来记录。这种方法的难度是在进位处理上,一不小心还是很容易错的。

(三) 代码分块:

  想法一的错误代码我先贴上把,这种做法很简单,应该很多人都能想到:

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
long long int Number;
long long int num,num2,sum = ,sum2 = ,k;
int Oct[];
int Oct2[];
int OK = ;
int main()
{
scanf("%lld",&Number);
num = Number;
num2 = *Number;
while(num>)
{
k = num % ;
Oct[k]++;
sum += k;
num = num / ;
}
while(num2>)
{
k = num2 % ;
Oct2[k]++;
sum2 += k;
num2 = num2 / ;
}
for(int i = ;i<;i++) if(Oct[i] != Oct2[i]) OK = ;
if(OK == )
{
printf("Yes\n");
printf("%lld",*Number);
}
else printf("No\n");
return ;
}

  做法就是一个变量存输入数,另一个变量存翻倍数,然后分别分隔,然后再互相对比个数组成是否相同。

  下面讲讲想法二AC的代码分块:

  首先,先输入数值并获取它的长度:

    scanf("%s", num1);
for (i = ; num1[i] == ; i--);

  然后再通过对每一位进行翻倍进位:

    for ( ; i >= ; i -- )
{
ji = (num1[i] - '') * ;   //ji是翻倍后的结果
ans[num1[i] - ''] ++;     //ans对原数相应位的个数++
di = ji % ;          //*2后的当前位的数字
num2[i] = di + jin + '';
ans[num2[i] - ''] --;    //ans对结果数的相应位的个数--
jin = (ji + jin) / ;
}
  if (jin != 0) ans[jin] ++;

  上面可以形成一个经典的大数计算模板,通过这道题我也开始接触到了一个新的问题的研究中 —— 大数的加减乘除的方法,过几天研究好了贴博客。

  第三步就是判断ans是否全部都为0,若是,则说明原数和结果数是相同的排列:

    for (i = ; i < ; i++)if (ans[i] != )break;//判断ans是否全部都为0,若是,则说明原数和结果数是相同的排列
if (i == ) printf("Yes");
else puts("No");
if (jin != )printf("%d", jin);
put(num2);

  注:这里直接省略了for去输出num2结果数组,而是直接使用puts函数了,这个函数可以直接把数组所有内容直接输出。

(四) AC代码:

#include<stdio.h>
using namespace std;
int ans[];
char num1[];
char num2[];
int i,di = , jin = ,ji = ;
int main()
{
scanf("%s", num1);
for (i = ; num1[i] == ; i--);
for ( ; i >= ; i -- )
{
ji = (num1[i] - '') * ; //ji是翻倍后的结果
ans[num1[i] - ''] ++;//ans对原数相应位的个数++
di = ji % ;//*2后的当前位的数字
num2[i] = di + jin + '';
ans[num2[i] - ''] --;//ans对结果数的相应位的个数--
jin = (ji + jin) / ;
}
if (jin != ) ans[jin] ++;
for (i = ; i < ; i++)if (ans[i] != )break;//判断ans是否全部都为0,若是,则说明原数和结果数是相同的排列
if (i == ) printf("Yes");
else printf("No");
if (jin != )printf("%d", jin);
puts(num2);
return ;
}

(五)AC截图:

『ACM C++』PTA浙大 | 基础题 - Have Fun with Numbers

(六) 解后分析:

  同样是一道练手的基础题,唯一坑点就是对long long int位数认知的模糊,导致一上手就没脑子的long long int,难点在于用char类型去处理数字基础运算,这也为我打开了一个新世界的大门,那就是大数的计算方法,待我整理整理再贴上来。

注:如果有更好的解法,真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~