1到9着9个数字组成，九位数的前两位能被2整除.....

来源：百度知道 编辑：UC知道 时间：2024/07/04 02:06:08
有一个9位数由1~9共9个阿拉伯数字组成，每个数字用且只能用一次。同时这个数的前2位能被2整除，前3位能被3整除......整个9位数能被9整除。求这个9位数？

结果是 381654729

我是用C语言计算出来的，并且就这一种.
思想是：
除了第5能取5，别的都不能。
2整除末位是偶数
3整除，加起来可以被3除(加法速度快)
4整除，只看最后2位
5整除，末位为5
6整除，末位位偶数，但也要被3整除
7整除，硬算的
8整除，末3位正处就可以了
9整除，只要前面的8位可以，最后一个还没用的数就是第9位的。
（1---9）之和是45，任何顺序都能整除9

复杂度分析： 8*4*6*5*1*4*3*2*1 == 23040, 大概23040种选法里挑正确答案，计算机可以很快完成。 下面是c++代码。

#include <iostream>
#include <queue>

using namespace std;

int num[10];
int Ans;
bool over;
struct Node
{
int data[10];
int p;
};
typedef queue<Node> MyQ;

void Work()
{
int i;
Node tmp;
MyQ q;
for(i=1;i<=9;i++)
{
if (i != 5 )
{
tmp.data[1] = i;
tmp.p = 1;
q.push(tmp );
}
}
while( !q.empty() )
{
tmp = q.front();
q.pop();
int p = tmp.p + 1;
tmp.p++;