正在刷新

一个十位数

Posted at 2020-11-24

题目

请将0123456789十个数字以特定的顺序排列，组成一个10位数abcdefghij（每个数字只能使用一次），使得：
1.第一位数字组成的整数可以被1整除
2.第一、二位数字组成的整数可以被2整除
3.第一、二、三位数字组成的整数可以被3整除
4.第一、二、三、四位数字组成的整数可以被4整除
……
10.第一、二、三…十位数字组成的整数可以被10整除

分析

1. 奇偶必须间隔

2. 被3，6整除的特点是每位相加是3的倍数，被9整除是每位相加是9的倍数，所以倒数第二个条件等于没有，1~9任何组合都可以是9的倍数

3. 被4，8整除的特点是最后2位数是4的倍数，最后3位数是8的倍数。

4. 5的倍数结尾是5或0，因为最后一位j是0，所以e只能是5

5. 由1）3）推出d=2或6

6. 由1）2）3）可以推出 def相加也是3的倍数，所以def = 654 或 258

7. 根据被8整除的特点，如果f=4，则根据5）推出 fgh 可能是

   • 432，则b=8
   • 472，则b=8

   如果f=8，则fgh可能是

   • 816，则b=4
   • 896，则b=4

8. 截止到目前所有条件，bcdefgh 可能为：

   • 8165432
   • 8165472
   • 8365472
   • 8765432
   • 8965432
   • 8965472
   • 4125896
   • 4725896

9. 再根据前三位相加是3的倍数，abcdefgh可能为：

   • 38165472

   • 98165432

   • 98165472

   • 18365472

   • 98765432

   • 18965432

   • 18965472
   • 78965432
   • 74125896
   • 14725896

10. 根据7的倍数排除后，上面10个数字只有38165472满足要求，最后答案是：3816547290

编程解法

#include <stdio.h>

unsigned int solve( int length, int index, unsigned int numExists, unsigned int value ){

    if ( index > length ) return value;

    for ( unsigned int i = 1; i <= length; ++i ) {
        if ( numExists & ( 0x01u << i )) continue;
        if (( value * 10 + i ) % index ) continue;
        unsigned int result = solve( length, index + 1, numExists | 0x01u << i, value * 10 + i );
        if ( result > 0 ) return result;
    }

    return 0;
}

int main(){

    int          resultLength = 9;
    unsigned int result       = solve( resultLength, 1, 0, 0 );
    printf( "%d0\n", result );

    return 0;
}