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

时间:2021-01-23 17:03: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,应该都会得。

代码一:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. int main ( void ) 
  5. {
  6.     int appear [10] ; 
  7.     char num1[25], num2[25] ;
  8.     int more = 0 ,len , temp , counter = 0 ;
  9. /**
  10. more 用来表示进位的数值,在后面当做 bool 类型来使用,用来表示计算出来的数列是否满足题意
  11. len 用来存放接收到的字符串的长度, temp 用来存放每次将数列上的数值乘以 2 之后的数值
  12. counter 用来存放计算出来的数列的长度
  13. */
  14.     memset (appear , 0 , sizeof(appear)) ;

  15.     scanf("%s", num1) ;
  16.     len = strlen(num1) ;

  17.     for ( int i = len -; i >= 0 ; i-- )
  18.     {
  19.         appear[num1[i] -'0']++ ;

  20.         temp = (int)(num1[i]-'0')*+ more ; // temp 数值 = 数列当前位置 i 上的数值 *2 + 进位

  21.         num2[counter++] = (temp % 10)+'0' ;  
  22.         // 将 temp 数值与 10 取余,并将 int 数值修改为 char 类型
  23.      
  24.         more = temp / 10 ;
  25.         // more 变量用来存放每次的进位值
  26.           
  27.     }


  28.     if ( more != 0)   // 最后需要检查一下最后的进位是否为 0 , 如果不为零,将其置于 num2 数列的最高位
  29.         num2[counter++] = more + '0';
  30.     
  31.     more = 0 ; // means that all elements appears in the appear array 

  32.     for ( int i = 0 ; i < counter ; i++ )
  33.     {
  34.          appear[num2[i]-'0']-- ; // if num2[i] -'0' not appear , appear[..] will < 0 
  35.                   
  36.          if ( appear[num2[i]-'0'] < 0 )
  37.              more = 1 ;

  38.     }

  39.     if ( more == 1 )
  40.      printf("No\n") ;
  41.     else 
  42.      printf ("Yes\n") ;
  43.           
  44.         for ( int j = counter-; j >= 0 ; j-- )
  45.             printf("%c" , num2[j]) ;
  46.          
  47.     return 0 ;
  48. }

代码二:

#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;
}