一个九位数由1-9数目字组成并前N 位被N整除

一个九位数由1-9数字组成并前N 位被N整除

题目：

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

?

?

分析：

通常想法是遍历9！=362280种排列。

其实第5位E一定是5，这样可缩减到8!=40320种排列

进一步分析，偶数位一定是偶数（BDFH={2，4，6，8}），奇数位一定是奇数（ACGI={1，3，7，9}），因而只需分析P(4,4)*P(4,4)=576种排列。

继续分析，4能整除 10*C+D，故D=2? 或 6, 加之8能整除 10*G+H，故D,H={2，6}，所以B，F={4，8}，故需分析P(4,4)*P(2,2)*P(2,2)=48种排列

接着分析，3?能整除 100* D+ 10 * 5+ F，所以DEF={258 ，654}，ABC，GHI能被3整除

如果DEF=258，则，ABC={147，741}，GHI={369，963}，但1472589，7412589均不能被7整除，不符合条件，故DEF=654，

B=8，H=2.此时只有P(4,4)=24种排列

又7能整除A8C654G，故7整除（A+4C+G）,而G={3，7}，如果G=3，ABC为{189，789，981，987}均不满足条件，故G=7，此时ABC={183，189，381，981}中只有381符合条件，故ABCDEFGHI=381654729

?

此时如果需要写代码，一句就够了：

?

Debug.print 381654729

?

附几种解法：

?

由yier_fang?提供

Sub?cnft()
1. ????'定义一个数组
2. ????Dim?a????'定义字符串
3. ????Dim?strNums?As?String????strNums?=?"1,2,3,4,5,6,7,8,9"
4. ????'开始循环 ????Dim?i,?j,?k?As?Integer
5. ????For?i?=?2?To?9????????a?=?Split(strNums,?",")
6. ????????strNums?=?""????????For?k?=?0?To?UBound(a)
7. ????????????For?j?=?1?To?9????????????????If?(a(k)?&?j)?Mod?i?=?0?Then
8. ????????????????????If?InStr(a(k),?j)?=?0?Then????????????????????????strNums?=?strNums?&?","?&?a(k)?&?j
9. ????????????????????End?If????????????????End?If
10. ????????????Next?j????????Next?k
11. ????????strNums?=?Right(strNums,?Len(strNums)?-?1)????Next?i
12. ????Erase?a????
13. ????MsgBox?("运行结果为:"?&?strNums)End?Sub

代码2：

?

（IP zhang5382 提供）

Sub?Getit()
1. Dim?a,?b,?c,?d,?e,?f,?g,?h,?i?As?Integer,?num1,?num2?As?String,?x?As?Doublee?=?5:?num1?=?"123456789":?num2?=?"此数为：":?t?=?Timer
2. For?a?=?1?To?9?Step?2????If?a?=?e?Then?GoTo?10
3. ????For?b?=?2?To?8?Step?2????????For?c?=?1?To?9?Step?2
4. ????????????x?=?a?+?b?+?c????????????If?c?=?a?Or?c?=?e?Or?Int(x?/?3)?<>?x?/?3?Then?GoTo?30
5. ????????????For?d?=?2?To?8?Step?2????????????????x?=?10?*?c?+?d
6. ????????????????If?d?=?b?Or?Int(x?/?4)?<>?x?/?4?Then?GoTo?40????????????????For?f?=?2?To?8?Step?2
7. ????????????????????x?=?d?+?e?+?f????????????????????If?f?=?b?Or?f?=?d?Or?Int(x?/?3)?<>?x?/?3?Then?GoTo?60
8. ????????????????????For?g?=?1?To?9?Step?2????????????????????????x?=?a?*?1000000?+?b?*?100000?+?c?*?10000?+?d?*?1000?+?e?*?100?+?f?*?10?+?g
9. ????????????????????????If?g?=?a?Or?g?=?c?Or?g?=?e?Or?Int(x?/?7)?<>?x?/?7?Then?GoTo?70????????????????????????For?h?=?2?To?8?Step?2
10. ????????????????????????????x?=?10?*?g?+?h????????????????????????????If?h?=?b?Or?h?=?d?Or?h?=?f?Or?Int(x?/?8)?<>?x?/?8?Then?GoTo?80
11. ????????????????????????????For?i?=?1?To?9?Step?2????????????????????????????????If?i?=?a?Or?i?=?c?Or?i?=?e?Or?i?=?g?Then?GoTo?90
12. ????????????????????????????????num2?=?num2?+?Mid(num1,?a,?1)?+?Mid(num1,?b,?1)?+?Mid(num1,?c,?1)????????????????????????????????num2?=?num2?+?Mid(num1,?d,?1)?+?Mid(num1,?e,?1)?+?Mid(num1,?f,?1)
13. ????????????????????????????????num2?=?num2?+?Mid(num1,?g,?1)?+?Mid(num1,?h,?1)?+?Mid(num1,?i,?1)????????????????????????????????num2?=?num2?+??Chr(13)?+?Chr(10)?+?"计算时间："?+?Str(Timer?-?t)?+?"秒"
14. ????????????????????????????????MsgBox?(num2)90:
15. ????????????????????????????Next?i80:
16. ????????????????????????Next?h70:
17. ????????????????????Next?g60:
18. ????????????????Next?f40:
19. ????????????Next?d30:
20. ????????Next?c20:
21. ????Next?b10:
22. Next?aEnd?Sub

代码3

?

（彭希仁 提供）<!-- -->

Dim?x,?s?As?String
1. Sub?cai()????Call?caii("",?0)
2. ????MsgBox?sEnd?Sub
3. Sub?caii(a,?i)????For?j?=?1?To?9
4. ????????If?Not?(a?Like?"*"?&?j?&?"*")?And?(a?&?j)?Mod?(i?+?1)?=?0?Then????????????If?i?+?1?=?9?Then
5. ????????????????s?=?s?&?a?&?j?&?vbCrLf????????????Else
6. ????????????????Call?caii(a?&?j,?i?+?1)????????????End?If
7. ????????End?If????Next?j
8. End?Sub

代码4：

Sub?cnft()
1. getNumEnd?Sub
2. Sub?getNum(Optional?ByRef?strNums?As?String?=?"",?Optional?ByRef?iTurn?As?Integer?=?1)
3. ????Dim?i?As?Integer,?tm?As?Single????tm?=?Timer
4. ????For?i?=?1?To?9????????If?InStr(strNums,?i)?=?0?Then
5. ????????????If?(strNums?&?i)?Mod?iTurn?=?0?Then????????????????If?iTurn?=?9?Then
6. ????????????????????MsgBox?strNums?&?i?&?vbCrLf?&?"用时:"?&?Timer?-?tm?&?"秒"????????????????Else
7. ????????????????????Call?getNum(strNums?&?i,?iTurn?+?1)????????????????End?If
8. ????????????End?If????????End?If
9. ????Next?iEnd?Sub

代码5

?

Sub?macro1()
1. Dim?d,?s,?x,?i?As?Long,?j?As?Long,?n?As?Currency,?k?As?Long,?befit?As?Booleand?=?Array(1,?3,?7,?9)
2. s?=?Array(2,?4,?6,?8)x?=?Split("0123?0132?0213?0231?0312?0321?1023?1032?1203?1230?1302?1320?2013?2031?2103?2130?2301?2310?3012?3021?3102?3120?3201?3210")
3. For?i?=?0?To?23For?j?=?0?To?23
4. n?=?Val(d(Mid(x(i),?1,?1))?&?s(Mid(x(j),?1,?1))?&?d(Mid(x(i),?2,?1))?&?s(Mid(x(j),?2,?1))?&?5?&?s(Mid(x(j),?3,?1))?&?d(Mid(x(i),?3,?1))?&?s(Mid(x(j),?4,?1))?&?d(Mid(x(i),?4,?1)))befit?=?True
5. For?k?=?2?To?8If?Not?Left(n,?k)?Mod?k?=?0?Then?befit?=?False:?Exit?For
6. NextIf?befit?=?True?Then?Debug.Print?n
7. NextNext
8. End?Sub