练习题链接：http://student.csdn.net/mcs/programming_challenges
给定一个非负整数，问能否重排它的全部数字，使得重排后的数能被8整除。 输入格式： 多组数据，每组数据是一个非负整数。非负整数的位数不超过10000位。 输出格式 每组数据输出一行,YES或者NO，表示能否重排它的全部数字得到能被8整除的数。注意： 重排可以让0开头
今天一个小学弟问我这道题怎么做，我直接回答他将数字全排列，验证是否可被8整除，例如123的全排列：123、231、312、213、132、321 (共3！=6种)
他听我讲后，问怎么做全排列，然后我上网找个了方法复制粘贴给他（这个，呵呵，这种方法网上肯定可以找到），他就屁颠屁颠的不理我了。全排列方法是验证一个开发者能力最简单有效的方法。
以下为提供全排序处理此问题的方法，当然这种方法网上随处可见：
1 class Program 2 { 3 static int Count = 1; 4 static int DivNum = 8; 5 6 /* 7 * 8 * 1,2: {1,2},{2,1} 9 * 1,2,3: 10 * {3,1,2},{1,3,2},{1,2,3} ( {1,2}中随机插入3 ) 11 * {3,2,1},{2,3,1},{2,1,3} ( {2,1}中随机插入3 ) 12 * 13 * 1，2,3，4： 14 * 就是在上面的六组数字中随机插入4 15 * 16 * 依次类推 17 */ 18 19 static void Main(string[] args) 20 { 21 string[] arr = new string[] 22 { 23 "11223344", 24 "23456798", 25 "89289238", 26 "23458203945829345" 27 }; 28 29 foreach (string item in arr) 30 { 31 if (Perm(item.ToCharArray(), 0)) 32 Console.WriteLine(" {0} Yes", item); 33 else 34 Console.WriteLine(" {0} No", item); 35 } 36 } 37 38 static void Swap(ref Char lc,ref Char rc) 39 { 40 Char tmp = lc; 41 lc = rc; 42 rc = tmp; 43 } 44 45 static bool Perm(char[] arrChar, int cur) 46 { 47 if (cur == arrChar.Length - 1) 48 { 49 long val1 = 0; 50 51 if (long.TryParse(new string(arrChar), out val1) && val1 % DivNum == 0) 52 { 53 return true; 54 } 55 else 56 return false; 57 } 58 else 59 { 60 for (int i = cur; i < arrChar.Length; i++) 61 { 62 Swap(ref arrChar[cur], ref arrChar[i]); 63 if (Perm(arrChar, cur + 1)) 64 return true; 65 Swap(ref arrChar[cur], ref arrChar[i]); 66 } 67 } 68 return false; 69 } 70 }C# 完全排序
排序算法结果：
还有一种更简洁的方法，erlang语言，我记得在变位词那个章节里，举例就是全排序。大致如下：
-module(lib_misc). -export([perms/1]). perms([]) -> [[]]; perms(L) -> [ [H|T] || H <- L , T <- perms( L--[H] ) ].二郎 全排序
排序算法结果：
全排序方法在我之后审题中被抛弃了，因为这道题不能够用全排序，里面有个条件很苛刻。
下面我把自己的思路提炼出来，以飨读者。
其实，这道题使用归纳法比较好，为什么？题目有提示 非负整数的位数不超过10000位 ，这意味着什么呢？非负整数的长度可能达到9999位，如果这么大的数使用全排序，估计计算机要死了，更何况我家自用开发机是8年前的老古董，想的出这种馊主意，它肯定受不了了。所以要借助归纳法，为什么可以用归纳法？呵呵，我猜的，别笑，我说得是实话，我猜测它可以使用归纳法，那么就得找出它遵循什么规律了，下面开始做一些假设过程：
怎么样，简单吧，只要判断末三位组成的数字能被8整除，这个数必然能被8整除，这是一道公务员考试题，别问我为什么知道哦，这是秘密。o(∩_∩)o 哈哈
碰到问题，想都不想的去做，结果只有一种，徒劳无功，倒不如什么都不做。这道题我开始也是全排序，因为胸有成竹嘛，但是后来仔细看题后，发现问题不是那么回事，有一个可能很难达到的要求，就是位数达到9999位怎么计算？所以，最后我认真的分析了一下发现它似曾相识。呵呵。
抱歉，兄弟们，还没完，我只做出这个推论，还没写出怎么组合数字的地方法，非常抱歉，稍等。
1 string aaa = "123123213840213849102384192034801923480192381234"; 2 int length = aaa.Length - 3; 3 4 for (int x = 0; x < length; x++)//对应百位 5 { 6 for (int y = 0; y < length; y++)//对应十位 7 { 8 if (y == x) 9 continue; 10 11 for (int z = 0; z < length; z++)//对应个位 12 { 13 if (z == x || z == y) 14 continue; 15 16 if (Convert.ToInt32(new string(new char[] { aaa[x], aaa[y], aaa[z] })) % 8 == 0) 17 { 18 char[] arr = aaa.ToCharArray(); 19 20 Swap(ref arr[x], ref arr[length + 0]); 21 Swap(ref arr[y], ref arr[length + 1]); 22 Swap(ref arr[z], ref arr[length + 2]); 23 24 Console.WriteLine("重排后字符串 ： " + new string(arr)); 25 goto GT_1; 26 } 27 } 28 } 29 } 30 31 GT_1: ;简单写点
好吧，就这么多吧。这个网站的试题还不错，我看了不少，没事可以去练习一下。http://student.csdn.net/mcs/programming_challenges
相关文章
