[算法]怎么用1-9构造出前N位可以被N整除的9位数

conwood

结果是381654729
9!也不大吧，用程序遍历也能出来了

cpperl

太久没有上来了，感谢大家指点。：）不过我和别人打赌输了。

lucifer

Post by conwood
总结一下吧
1. 第5位数字是5，这个不废话了。

2. 偶数位数字是偶数，奇数位是奇数也不废话了。

3. 第123位、456位、789位组成的三个三位数都可以被3整除。

4. 考虑前4位，表示成abcd的样子，c是奇数，而ab00必然可以被4整除，那么d只能是2或者6。

5. 结合3,4，得知中间3位只能是258或者654。

6. 考虑第7,8位，由于前8位可以表示成abcd5fgh的形式，abcd5000必然可以被8整除，由5得知，f是4或者8，而400和800都可以被8整除，因此关键在7、8位，结合5的结果，知道4-8位只能是25816,25896,65432,65472

7. 789位组成的三位数可以被3整除，因此4-9位只能是258963,654327,654729,654321,654723

8. 偶数都快用光了，考虑第二位，所有可能的数字是
_4_258963
_8_654327
_8_654729
_8_654321
_8_654723

9. 下面只验证前7位对7的整除情况即可，只有10种组合了，对7整除的规律我了解不多，手工尝试也不是太大工作量。

7,11,13都一样
看末三位和除了它们以外前面的数字的差能不能整除就行了。而且这个可以一直重复用。

conwood

后来想到这个规律了
1001=7*11*13

11可以用另一个规律：奇数位数字之和等于偶数位数字之和

Post by lucifer
7,11,13都一样
看末三位和除了它们以外前面的数字的差能不能整除就行了。而且这个可以一直重复用。

ggggqqqqihc

Pascal程序来了，不难的，直接用程序描述了一遍问题，没想别的，直接用DFS，结果是381654729。我还纳闷儿咋就一个结果呢？不过程序应该不会有什么问题的。

1. var
   
2.     used:set of 1..9;
   
3.     A:array[1..9] of byte;
   
4. Function divok(k,h:byte):boolean;
   
5. var
   
6.     s:longint;
   
7.     i:byte;
   
8. begin
   
9.     s:=0;
   
10.     for i:=1 to k-1 do s:=s*10+A[i];
    
11.     s:=s*10+h;
    
12.     if s mod k=0 then divok:=True else divok:=False;
    
13. end;
    
14. Procedure outp;
    
15. var
    
16.     i:byte;
    
17. begin
    
18.     for i:=1 to 9 do write(A[i]);
    
19.     writeln;
    
20. end;
    
21. Procedure DFS(k:byte);
    
22. var
    
23.     i:byte;
    
24. begin
    
25.     if k>9 then
    
26.     begin
    
27.         outp;
    
28.         exit;
    
29.     end;
    
30.     for i:=1 to 9 do
    
31.         if divok(k,i) and (not (i in used)) then
    
32.         begin
    
33.             used:=used+[i];
    
34.             A[k]:=i;
    
35.             DFS(k+1);
    
36.             used:=used-[i];
    
37.         end;
    
38. end;
    
39. begin
    
40.     used:=[];
    
41.     DFS(1);
    
42. end.

复制代码

herberteuler

Post by ggggqqqqihc
Pascal程序来了，不难的，直接用程序描述了一遍问题，没想别的，直接用DFS，结果是381654729。我还纳闷儿咋就一个结果呢？不过程序应该不会有什么问题的。

1. var
   
2.     used:set of 1..9;
   
3.     A:array[1..9] of byte;
   
4. Function divok(k,h:byte):boolean;
   
5. var
   
6.     s:longint;
   
7.     i:byte;
   
8. begin
   
9.     s:=0;
   
10.     for i:=1 to k-1 do s:=s*10+A[i];
    
11.     s:=s*10+h;
    
12.     if s mod k=0 then divok:=True else divok:=False;
    
13. end;
    
14. Procedure outp;
    
15. var
    
16.     i:byte;
    
17. begin
    
18.     for i:=1 to 9 do write(A[i]);
    
19.     writeln;
    
20. end;
    
21. Procedure DFS(k:byte);
    
22. var
    
23.     i:byte;
    
24. begin
    
25.     if k>9 then
    
26.     begin
    
27.         outp;
    
28.         exit;
    
29.     end;
    
30.     for i:=1 to 9 do
    
31.         if divok(k,i) and (not (i in used)) then
    
32.         begin
    
33.             used:=used+[i];
    
34.             A[k]:=i;
    
35.             DFS(k+1);
    
36.             used:=used-[i];
    
37.         end;
    
38. end;
    
39. begin
    
40.     used:=[];
    
41.     DFS(1);
    
42. end.

复制代码

这个程序执行的时间怎么样？

ggggqqqqihc

一瞬间就算出来了。

F&D

俺们用C语言写了一个深度优先搜索算法程序，仅用了奇数位为奇数，偶数位为偶数这一个条件，就很快算出结果为：381654729