00-自测4. Have Fun with Numbers (20)

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 file 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:

1234567899

Sample Output:

Yes

2469135798

这道题的意思呢，就是给一个不超过20位的数，然后乘以2，如果之后得到的数的组成与之前一样，顺序不同，那么就输出“Yes”，否则就“No”咯。要声明一下，这道题如果用长整形之类的话，那么大数的乘法是会有误差的，可以自己先试试，你会发现得到的数会让你大吃一惊。所以我们需要以另外一种方式来解决，我将每一位作为一个字符输入，然后再转化为整形数，存到一个整形数组中，接着通过两个存储了乘2前后数组成的数组比较，来判断是否相同，由此来输出答案，当然这种方法需要你自己写代码来进行乘法运算。只是乘2，应该都会得。

代码一：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ( void )
{
int appear [10] ;
char num1[25], num2[25] ;
int more = 0 ,len , temp , counter = 0 ;
/**
more 用来表示进位的数值，在后面当做 bool 类型来使用，用来表示计算出来的数列是否满足题意
len 用来存放接收到的字符串的长度， temp 用来存放每次将数列上的数值乘以 2 之后的数值
counter 用来存放计算出来的数列的长度
*/
memset (appear , 0 , sizeof(appear)) ;
scanf("%s", num1) ;
len = strlen(num1) ;
for ( int i = len -1 ; i >= 0 ; i-- )
{
appear[num1[i] -'0']++ ;
temp = (int)(num1[i]-'0')*2 + more ; // temp 数值 = 数列当前位置 i 上的数值 *2 + 进位
num2[counter++] = (temp % 10)+'0' ;
// 将 temp 数值与 10 取余，并将 int 数值修改为 char 类型
more = temp / 10 ;
// more 变量用来存放每次的进位值
}
if ( more != 0) // 最后需要检查一下最后的进位是否为 0 ，如果不为零，将其置于 num2 数列的最高位
num2[counter++] = more + '0';
more = 0 ; // means that all elements appears in the appear array
for ( int i = 0 ; i < counter ; i++ )
{
appear[num2[i]-'0']-- ; // if num2[i] -'0' not appear , appear[..] will < 0
if ( appear[num2[i]-'0'] < 0 )
more = 1 ;
}
if ( more == 1 )
printf("No\n") ;
else
printf ("Yes\n") ;
for ( int j = counter-1 ; j >= 0 ; j-- )
printf("%c" , num2[j]) ;
return 0 ;
}

代码二：

#include <stdio.h> #include <string.h> int oriDigit[20], resDigit[20]; void ToDigit(char *s, int n) { for(int i = 0; i < n; ++i) oriDigit[i] = s[i] - '0'; return; } void Double(int n) { for(int i = 0; i < n; ++i) resDigit[i] = 2 * oriDigit[i]; for(int i = n - 1; i > 0; --i) { resDigit[i - 1] += resDigit[i] / 10; resDigit[i] %= 10; } return; } int Check(char *s, int n) { //检查数字是否满足要求 ToDigit(s, n); //将字符串数字转化为整数 Double(n); //将整数加倍 for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(oriDigit[i] == resDigit[j]) { //将已经相等的数字做标记：减去10变成负数 resDigit[j] -= 10; break; } for(int i = 0; i < n; ++i) if(resDigit[i] >= 0) return 0; return 1; } int main() { char s[20]; gets(s); int len = strlen(s); if(Check(s, len)) { printf("Yes\n"); for(int i = 0; i < len; ++i) { if(resDigit[i] < 0) resDigit[i] += 10; printf("%d", resDigit[i]); } } else { printf("No\n"); for(int i = 0; i < len; ++i) { if(resDigit[i] < 0) resDigit[i] += 10; printf("%d", resDigit[i]); } } return 0; }

代码三：

#include <stdio.h>

#include <stdlib.h> int main() { char c; int cnt=0; //计数器 //输入数字 int num[20]; int a[10]={0}; int b[10]={0}; //用于比较的数组a,b，其中元素为含有这个数的个数 while(1) { scanf("%c",&c); if((int)c-48>=0 && (int)c-48<=9) { num[cnt] = (int)c-48; //将数存到数组中 a[num[cnt]]++; //个数+1 cnt++; } else break; } //对数进行*2处理 int i; int flag =0; //进位 for(i=cnt-1;i>=0;i--) //从最低位开始 { num[i] = num[i]*2+flag; //*2后的数 if(num[i]>9 && i!=0) { flag =1; //进位为1 num[i] = num[i]%10; //只留个位 } else flag =0; if(num[0]<=9) b[num[i]]++; //个数+1 } //判断a，b数组是否相同 int sign = 0; for(i=0;i<10;i++) { if(a[i]!=b[i]) { sign = 1; break; } } //输出 if(sign == 0) printf("Yes\n"); else printf("No\n"); for(i=0;i<cnt;i++) { printf("%d",num[i]); } return 0; }

代码四：

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int cmp(const void *a,const void*b)
{
    int *m = (int *)a;
    int *n = (int *)b;
    return *m - *n;
}
int main()
{
    char str[30];
    scanf("%s",str);
    int lenth = strlen(str);
    int a[30],b[30],c[30];
    int i,j,k;
    for (i=0;i<lenth;i++)
        a[i] = str[i] - '0';
    int enter = 0;
    for (i=lenth-1;i>=0;i--)
       {
           b[i] = a[i]*2 + enter;
           enter = b[i]/10;
           b[i] = b[i]%10;
           c[i] = b[i];
       }
    qsort(a,lenth,sizeof(int),cmp);
    qsort(b,lenth,sizeof(int),cmp);
    for (i=0;i<lenth&&a[i]==b[i];i++);
    if (i==lenth)
        printf("Yes\n");
    else
        printf("No\n");
    if (enter!=0)
         printf("%d",enter);
    for (i=0;i<lenth;i++)
        printf("%d",c[i]);
    printf("\n");
    return 0;
}

秒客网

00-自测4. Have Fun with Numbers (20)

相关文章