数据结构-起步能力自测题 自测-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 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

 

---

 

 

最大位数超过long long范围，用字符串存输入数字。然后，转换成数组，并算出2倍数组。最后，计算数字出现次数，比较得出结论。 

   

#include <stdio.h>
int main()
{
    char p[21];
    int a1[20], a2[21];    /*换算数组，a1原来，a2二倍（考虑进位，多一）*/
    int i, j;

    scanf("%s", p);

    /*调试*/
//    printf("%s\n", p);

    int n = 0;    /*位数*/
    for (i = 0; i < 20; i++)
        if (p[i] != '\0')
        {
            a1[i] = p[i] - '0';    /*字符转数字*/
            a2[i] = a1[i] * 2;    /*乘2*/
            n++;
        }
        else
        {
            break;
        }

    /*调试*/
    //printf("n=%d\n", n);
    //for (i = 0; i < n; i++)
    //    printf("%d", a2[i]);
    //printf("\n");

    for (j = n - 1; j > 0; j--)    /*进位*/
        for (i = j; i > 0; i--)
            if (a2[i] > 9)
            {
                a2[i] -= 10;
                a2[i - 1] += 1;
            }

    /*调试*/
    //for (i = 0; i < n; i++)
    //    printf("%d", a2[i]);
    //printf("\n");

    int t1[10] = { 0,0,0,0,0,0,0,0,0,0 };    /*计算数字出现次数*/
    int t2[10] = { 0,0,0,0,0,0,0,0,0,0 };

    /*调试*/
    //for (i = 0; i <10; i++)
    //    printf("%d ", t1[i]);
    //printf("\n");

    if (a2[0] > 9)    /*多1位，No。位数相同，继续*/
    {
        printf("No\n");
    }
    else
    {
        for (j = 0; j < 10; j++)
            for (i = 0; i < n; i++)
            {
                if (a1[i] == j)
                    t1[j]++;
                if (a2[i] == j)
                    t2[j]++;
            }
        for (i = 0; i < 10; i++)    /*比较*/
            if (t1[i] == t2[i])
                continue;
            else
            {
                printf("No\n");
                break;
            }
        if (i == 10)    /*全相同*/
            printf("Yes\n");
    }

    /*调试*/
    //for (i = 0; i < 10; i++)
    //    printf("%d ", t1[i]);
    //printf("\n");
    //for (i = 0; i < 10; i++)
    //    printf("%d ", t2[i]);
    //printf("\n");

    for (i = 0; i < n; i++)    /*第二行输出*/
        printf("%d", a2[i]);

    return 0;
}