连着这两道都是开学前数构老师的“爱心作业”,还没上课开学就给我们布置作业了,这道题有点小坑,也经常遇到类似的问题,特地拿出来记录一下。
------------------------------------------------题目----------------------------------------------------------
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截图:
(六) 解后分析:
同样是一道练手的基础题,唯一坑点就是对long long int位数认知的模糊,导致一上手就没脑子的long long int,难点在于用char类型去处理数字基础运算,这也为我打开了一个新世界的大门,那就是大数的计算方法,待我整理整理再贴上来。
注:如果有更好的解法,真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~