假设有12个球，其中一个球的重量与其他11个球不同。你有一个天平，三次机会找出这个重量不同的球。请用C++给出你认为最优的数据结构和算法。
有哪位大神能解？（请看清题目再解）
6 个解决方案
#1
说下算法吧，12个球分成4份，每份3个，从中挑出两份来称
如果 平衡，取走一份，再拿一份，再称，如果还平衡，重量不同的一定在最后的那一份中，如果不平衡，重量不同的就在这刚拿来的一份中了。
如果不平衡，取走一份，再拿一份，再称，如果平衡，重量不同的一定在取走的那一份中，如果不平衡，则重量不同的在没有取走的那一份中。
以上称两次即可知道重量不同的球在哪一份中，且知道这个球是重了还是轻了。
从这个含有重量不同的一份中，取出两个球称，如果平衡，重量不同的就是没取的那一个了，如果不平衡，根据之前得到的重量不同的球是重了还是轻了，就能知道谁是重量不同的那个了
如果 平衡，取走一份，再拿一份，再称，如果还平衡，重量不同的一定在最后的那一份中，如果不平衡，重量不同的就在这刚拿来的一份中了。
如果不平衡，取走一份，再拿一份，再称，如果平衡，重量不同的一定在取走的那一份中，如果不平衡，则重量不同的在没有取走的那一份中。
以上称两次即可知道重量不同的球在哪一份中，且知道这个球是重了还是轻了。
从这个含有重量不同的一份中，取出两个球称，如果平衡，重量不同的就是没取的那一个了，如果不平衡，根据之前得到的重量不同的球是重了还是轻了，就能知道谁是重量不同的那个了
#2
问题
12 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13 个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）
分析
初次遇到这种问题，容易分析晕，如果能够找到一种思维工具，解决起来会清晰很多。让我们从“信息”的角度来对这个问题进行分析：将球分成4 种：“黑球”、“白球”、“轻球”、“重球”：
在称之前，所有球都不知道是否有问题，都是“黑球”（用“*”表示）；
排除嫌疑的球是“白球”（用“-”表示）。将“黑球”变白需要获取“信息”，方式为“用天平称”；
天平称了以后，被怀疑偏轻或重的球是“轻球”（用“↑”表示）或“重球”（用“↓”表示），我们要做的事情就是让“轻球”再次被怀疑“偏重”，则它是白球，反之亦然这也很好证明：举例说明，若x≥8 且 x≤8，则x = 8。
用“V”表示天平，例如：** V *- 表示天平左边两黑球，右边一白一黑。
求解
有了思维工具了，求解就方便了：
初始时候我们有12 个黑球，拿出8 个来称：**** V ****
若平，8 个球变白。还剩4 个黑球，则称 ** V *-
若平，则3 个黑球变白，剩下一个黑球，称* V -，即得出结果。
若左轻，即：↑↑ V ↓ - ，那么再称 ↑ V ↑，即得结果。右轻情况以此类推。
若左轻，即：↑↑↑↑ V ↓↓↓↓，那么再称↑↑↓ V↑↓-
若平，剩下↓↓↑，再称 ↓V↓，即得结果。
若左轻，剩下↑↑↓，再称 ↑V↑，即得结果。
若右轻，剩下↑↓，再称 ↑V-，即得结果。
若右轻，以此类推。
讨论
在我高中的时候，同桌非常聪明，做题画的乱七八糟的居然都能算对，很多同学思维能力强，记忆力好，对这种作法引以为荣。
然而在现实生活中，个人英雄是不行的，需要团队的合作。如何找到“思维工具”，将问题清晰的表述出来，比去解决一个具体问题更为重要。有了工具大家都能用，若所有人都提供很多工具，工具之上又可构建更强工具，那么“巨人肩膀上的巨人”就出现了。
12 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13 个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）
分析
初次遇到这种问题，容易分析晕，如果能够找到一种思维工具，解决起来会清晰很多。让我们从“信息”的角度来对这个问题进行分析：将球分成4 种：“黑球”、“白球”、“轻球”、“重球”：
在称之前，所有球都不知道是否有问题，都是“黑球”（用“*”表示）；
排除嫌疑的球是“白球”（用“-”表示）。将“黑球”变白需要获取“信息”，方式为“用天平称”；
天平称了以后，被怀疑偏轻或重的球是“轻球”（用“↑”表示）或“重球”（用“↓”表示），我们要做的事情就是让“轻球”再次被怀疑“偏重”，则它是白球，反之亦然这也很好证明：举例说明，若x≥8 且 x≤8，则x = 8。
用“V”表示天平，例如：** V *- 表示天平左边两黑球，右边一白一黑。
求解
有了思维工具了，求解就方便了：
初始时候我们有12 个黑球，拿出8 个来称：**** V ****
若平，8 个球变白。还剩4 个黑球，则称 ** V *-
若平，则3 个黑球变白，剩下一个黑球，称* V -，即得出结果。
若左轻，即：↑↑ V ↓ - ，那么再称 ↑ V ↑，即得结果。右轻情况以此类推。
若左轻，即：↑↑↑↑ V ↓↓↓↓，那么再称↑↑↓ V↑↓-
若平，剩下↓↓↑，再称 ↓V↓，即得结果。
若左轻，剩下↑↑↓，再称 ↑V↑，即得结果。
若右轻，剩下↑↓，再称 ↑V-，即得结果。
若右轻，以此类推。
讨论
在我高中的时候，同桌非常聪明，做题画的乱七八糟的居然都能算对，很多同学思维能力强，记忆力好，对这种作法引以为荣。
然而在现实生活中，个人英雄是不行的，需要团队的合作。如何找到“思维工具”，将问题清晰的表述出来，比去解决一个具体问题更为重要。有了工具大家都能用，若所有人都提供很多工具，工具之上又可构建更强工具，那么“巨人肩膀上的巨人”就出现了。
#3
这个题应该是4次才行吧
#4
二楼的解法应该是没有问题的。数据结构用数组好呢还是用树呢？
#5
不需要4次，而且不止一种算法。
#6
1 2 3 4 5 6 7 8 A B C D 注：一共有12个球，其中一个的重量与其他11个球不同。现在你有一个天平，并有3次机会（仅有3次），试着找出这个重量不同的球。
1) 1 2 3 4 = 5 6 7 8
1.1) A = B
1.1.1) A = C → D ↑↓
1.1.2) A < C → C ↑
1.1.3) A > C → C ↓
1.2） A < B
1.2.1) A = C → B ↑
1.2.2) A < C → A ↓
1.3) A > B
1.3.1) A = C → B ↓
1.3.2) A > C → A ↑
2) 1 2 3 4 < 5 6 7 8
2.1) 1 5 6 = 2 7 A
2.1.1) 3 = 4 → 8 ↑
2.1.2) 3 < 4 → 3 ↓
2.1.3) 3 > 4 → 4 ↓
2.2) 1 5 6 < 2 7 A
2.2.1) 8 = 7 → 1 ↓
2.2.2) 8 < 7 → 7 ↑
2.2.3) 8 > 7 → 8 ↑
2.3) 1 5 6 > 2 7 A
2.3.1) 5 = 6 → 2 ↓
2.3.2) 5 < 6 → 6 ↑
2.3.3) 5 > 6 → 5 ↑
3) 1 2 3 4 > 5 6 7 8
3.1) 1 5 6 = 2 7 A
3.1.1) 3 = 4 → 8 ↓
3.1.2) 3 < 4 → 3 ↑
3.1.3) 3 > 4 → 4 ↑
3.2) 1 5 6 < 2 7 A
3.2.1) 5 = 6 → 2 ↓
3.2.2) 5 < 6 → 6 ↑
3.2.3) 5 > 6 → 5 ↑
3.3) 1 5 6 > 2 7 A
3.3.1) 8 = 7 → 1 ↓
3.3.2) 8 < 7 → 7 ↑
3.3.3) 8 > 7 → 8 ↑
刚刚闲下来，把自己的算法总结编排了一下，不用解释应该也能看懂。算法和2楼的不同，但一样可以得出答案。
#1
说下算法吧，12个球分成4份，每份3个，从中挑出两份来称
如果 平衡，取走一份，再拿一份，再称，如果还平衡，重量不同的一定在最后的那一份中，如果不平衡，重量不同的就在这刚拿来的一份中了。
如果不平衡，取走一份，再拿一份，再称，如果平衡，重量不同的一定在取走的那一份中，如果不平衡，则重量不同的在没有取走的那一份中。
以上称两次即可知道重量不同的球在哪一份中，且知道这个球是重了还是轻了。
从这个含有重量不同的一份中，取出两个球称，如果平衡，重量不同的就是没取的那一个了，如果不平衡，根据之前得到的重量不同的球是重了还是轻了，就能知道谁是重量不同的那个了
如果 平衡，取走一份，再拿一份，再称，如果还平衡，重量不同的一定在最后的那一份中，如果不平衡，重量不同的就在这刚拿来的一份中了。
如果不平衡，取走一份，再拿一份，再称，如果平衡，重量不同的一定在取走的那一份中，如果不平衡，则重量不同的在没有取走的那一份中。
以上称两次即可知道重量不同的球在哪一份中，且知道这个球是重了还是轻了。
从这个含有重量不同的一份中，取出两个球称，如果平衡，重量不同的就是没取的那一个了，如果不平衡，根据之前得到的重量不同的球是重了还是轻了，就能知道谁是重量不同的那个了
#2
问题
12 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13 个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）
分析
初次遇到这种问题，容易分析晕，如果能够找到一种思维工具，解决起来会清晰很多。让我们从“信息”的角度来对这个问题进行分析：将球分成4 种：“黑球”、“白球”、“轻球”、“重球”：
在称之前，所有球都不知道是否有问题，都是“黑球”（用“*”表示）；
排除嫌疑的球是“白球”（用“-”表示）。将“黑球”变白需要获取“信息”，方式为“用天平称”；
天平称了以后，被怀疑偏轻或重的球是“轻球”（用“↑”表示）或“重球”（用“↓”表示），我们要做的事情就是让“轻球”再次被怀疑“偏重”，则它是白球，反之亦然这也很好证明：举例说明，若x≥8 且 x≤8，则x = 8。
用“V”表示天平，例如：** V *- 表示天平左边两黑球，右边一白一黑。
求解
有了思维工具了，求解就方便了：
初始时候我们有12 个黑球，拿出8 个来称：**** V ****
若平，8 个球变白。还剩4 个黑球，则称 ** V *-
若平，则3 个黑球变白，剩下一个黑球，称* V -，即得出结果。
若左轻，即：↑↑ V ↓ - ，那么再称 ↑ V ↑，即得结果。右轻情况以此类推。
若左轻，即：↑↑↑↑ V ↓↓↓↓，那么再称↑↑↓ V↑↓-
若平，剩下↓↓↑，再称 ↓V↓，即得结果。
若左轻，剩下↑↑↓，再称 ↑V↑，即得结果。
若右轻，剩下↑↓，再称 ↑V-，即得结果。
若右轻，以此类推。
讨论
在我高中的时候，同桌非常聪明，做题画的乱七八糟的居然都能算对，很多同学思维能力强，记忆力好，对这种作法引以为荣。
然而在现实生活中，个人英雄是不行的，需要团队的合作。如何找到“思维工具”，将问题清晰的表述出来，比去解决一个具体问题更为重要。有了工具大家都能用，若所有人都提供很多工具，工具之上又可构建更强工具，那么“巨人肩膀上的巨人”就出现了。
12 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13 个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）
分析
初次遇到这种问题，容易分析晕，如果能够找到一种思维工具，解决起来会清晰很多。让我们从“信息”的角度来对这个问题进行分析：将球分成4 种：“黑球”、“白球”、“轻球”、“重球”：
在称之前，所有球都不知道是否有问题，都是“黑球”（用“*”表示）；
排除嫌疑的球是“白球”（用“-”表示）。将“黑球”变白需要获取“信息”，方式为“用天平称”；
天平称了以后，被怀疑偏轻或重的球是“轻球”（用“↑”表示）或“重球”（用“↓”表示），我们要做的事情就是让“轻球”再次被怀疑“偏重”，则它是白球，反之亦然这也很好证明：举例说明，若x≥8 且 x≤8，则x = 8。
用“V”表示天平，例如：** V *- 表示天平左边两黑球，右边一白一黑。
求解
有了思维工具了，求解就方便了：
初始时候我们有12 个黑球，拿出8 个来称：**** V ****
若平，8 个球变白。还剩4 个黑球，则称 ** V *-
若平，则3 个黑球变白，剩下一个黑球，称* V -，即得出结果。
若左轻，即：↑↑ V ↓ - ，那么再称 ↑ V ↑，即得结果。右轻情况以此类推。
若左轻，即：↑↑↑↑ V ↓↓↓↓，那么再称↑↑↓ V↑↓-
若平，剩下↓↓↑，再称 ↓V↓，即得结果。
若左轻，剩下↑↑↓，再称 ↑V↑，即得结果。
若右轻，剩下↑↓，再称 ↑V-，即得结果。
若右轻，以此类推。
讨论
在我高中的时候，同桌非常聪明，做题画的乱七八糟的居然都能算对，很多同学思维能力强，记忆力好，对这种作法引以为荣。
然而在现实生活中，个人英雄是不行的，需要团队的合作。如何找到“思维工具”，将问题清晰的表述出来，比去解决一个具体问题更为重要。有了工具大家都能用，若所有人都提供很多工具，工具之上又可构建更强工具，那么“巨人肩膀上的巨人”就出现了。
#3
这个题应该是4次才行吧
#4
二楼的解法应该是没有问题的。数据结构用数组好呢还是用树呢？
#5
不需要4次，而且不止一种算法。
#6
1 2 3 4 5 6 7 8 A B C D 注：一共有12个球，其中一个的重量与其他11个球不同。现在你有一个天平，并有3次机会（仅有3次），试着找出这个重量不同的球。
1) 1 2 3 4 = 5 6 7 8
1.1) A = B
1.1.1) A = C → D ↑↓
1.1.2) A < C → C ↑
1.1.3) A > C → C ↓
1.2） A < B
1.2.1) A = C → B ↑
1.2.2) A < C → A ↓
1.3) A > B
1.3.1) A = C → B ↓
1.3.2) A > C → A ↑
2) 1 2 3 4 < 5 6 7 8
2.1) 1 5 6 = 2 7 A
2.1.1) 3 = 4 → 8 ↑
2.1.2) 3 < 4 → 3 ↓
2.1.3) 3 > 4 → 4 ↓
2.2) 1 5 6 < 2 7 A
2.2.1) 8 = 7 → 1 ↓
2.2.2) 8 < 7 → 7 ↑
2.2.3) 8 > 7 → 8 ↑
2.3) 1 5 6 > 2 7 A
2.3.1) 5 = 6 → 2 ↓
2.3.2) 5 < 6 → 6 ↑
2.3.3) 5 > 6 → 5 ↑
3) 1 2 3 4 > 5 6 7 8
3.1) 1 5 6 = 2 7 A
3.1.1) 3 = 4 → 8 ↓
3.1.2) 3 < 4 → 3 ↑
3.1.3) 3 > 4 → 4 ↑
3.2) 1 5 6 < 2 7 A
3.2.1) 5 = 6 → 2 ↓
3.2.2) 5 < 6 → 6 ↑
3.2.3) 5 > 6 → 5 ↑
3.3) 1 5 6 > 2 7 A
3.3.1) 8 = 7 → 1 ↓
3.3.2) 8 < 7 → 7 ↑
3.3.3) 8 > 7 → 8 ↑
刚刚闲下来，把自己的算法总结编排了一下，不用解释应该也能看懂。算法和2楼的不同，但一样可以得出答案。