题目
请将0123456789十个数字以特定的顺序排列,组成一个10位数abcdefghij(每个数字只能使用一次),使得:
1.第一位数字组成的整数可以被1整除
2.第一、二位数字组成的整数可以被2整除
3.第一、二、三位数字组成的整数可以被3整除
4.第一、二、三、四位数字组成的整数可以被4整除
……
10.第一、二、三…十位数字组成的整数可以被10整除
分析
奇偶必须间隔
被3,6整除的特点是每位相加是3的倍数,被9整除是每位相加是9的倍数,所以倒数第二个条件等于没有,1~9任何组合都可以是9的倍数
被4,8整除的特点是最后2位数是4的倍数,最后3位数是8的倍数。
5的倍数结尾是5或0,因为最后一位j是0,所以e只能是5
由1)3)推出d=2或6
由1)2)3)可以推出 def相加也是3的倍数,所以def = 654 或 258
根据被8整除的特点,如果f=4,则根据5)推出 fgh 可能是
- 432,则b=8
- 472,则b=8
如果f=8,则fgh可能是
- 816,则b=4
- 896,则b=4
截止到目前所有条件,bcdefgh 可能为:
- 8165432
- 8165472
- 8365472
- 8765432
- 8965432
- 8965472
- 4125896
- 4725896
再根据前三位相加是3的倍数,abcdefgh可能为:
- 38165472
98165432
98165472
18365472
98765432
18965432
- 18965472
- 78965432
- 74125896
- 14725896
根据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;
}