进位&&大数字符串处理

Have Fun with Numbers

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:

1234567899

Sample Output:

Yes

2469135798

通过分析题目可知数的最大位为20位，就连最大的long long类型此时也会爆掉，因此要采用字符串来处理。
上代码：

#include<stdio.h>

#include<string.h>

int main(void){

    char num1[21],num2[21];

    scanf("%s",num1);

    char doublenum[21];

    char tmp;

    strcpy(num2,num1);

    int len=strlen(num2);

    //每位数字乘2后存储在数组num2中

    int carrybit=0;//储存每位数运算后的进位


    char midch;

　　　　//字符串处理的关键

    for(int i=len-1;i>=1;i--){
　　　　　　//根据人工列式计算的步骤给出算法

        midch=num2[i];

        num2[i]=((num2[i]-'0')*2+carrybit)%10+'0'; //先乘2再加上次运算产生的进位

        carrybit=((midch-'0')*2+carrybit)/10; //计算这一次的进位，注意不能再用num2[i],因为num2[i]已经改变  错误：carrybit=((num2[i]-'0')*2+carrybit)/10

　　} 
　　num2[0]=(num2[0]-'0')*2+carrybit+'0'; //最高位不用再进位，若最高位大于9，下面会给出处理


    if(num2[0]>'9'){//如果乘2后的数和原来的数位数不匹配，直接判定No

        printf("No\n");

        printf("%d%d",(num2[0]-'0')/10,(num2[0]-'0')%10);

        printf("%s",&num2[1]);

    }else{

        strcpy(doublenum,num2);

        
　　　　//冒泡排序num1 num2

        for(int i=0;i<len-1;i++){

            for(int j=0;j<len-i-1;j++)

             if(num2[j]>num2[j+1]){

                tmp=num2[j];

                num2[j]=num2[j+1];

                num2[j+1]=tmp;

            }

        }

        for(int i=0;i<len-1;i++){

            for(int j=0;j<len-i-1;j++)

            if(num1[j]>num1[j+1]){

                tmp=num1[j];

                num1[j]=num1[j+1];

                num1[j+1]=tmp;

            }

        }


        if(strcmp(num1,num2)==0){

            printf("Yes\n");

            printf("%s",doublenum);

        }else{

            printf("No\n");

            printf("%s",doublenum);

        }

    }

    return 0;

}

题目来源：

https://pintia.cn/problem-sets/17/problems/263

巴特西

进位&&大数字符串处理

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章