N个乒乓球问题的答案

一直以来, 流行着这么一个问题:

**********************************************************************

有12个乒乓球特征相同，其中只有一个重量异常，现在要求用一部没有砝码的天平称三次，将那个重量异常的球找出来。

**********************************************************************

懒了, 暂时不写过程和如何编程了, 以后补上, 现在只把最终的结果拿出来好了. 把题目中的12变成n时, 公式如下: 

h(n) = _[log₃(2n - 1)_] + 1 

另外

h(3n + 1) = h(3n) = h(3n - 1) = h(n) + 1 

12个球需要称的次数: h(12) = 3
同样
h(13) = 3
h(14) = 4
h(40) = 4
h(121) = 5
h(364) = 6

通用的解法, 正如一般的说法, 就是三分, 不过分得要有技巧, 根据h(3n + 1) = h(n) +1得知, 实际的分法是第一次减1后三分(why呢? 自己想吧), 至于更详细的, 看证明过程自己总结了....

证明的过程, 在左面可以下载到...PDF, 英文版的...

算法之SudokuPlus(数独,又称九宫)系列(完) --- 迷题生成篇(3)

四, 九宫之随机生成篇

提到随机生成, 不由有2种随机算法映入脑海:
(1)固定的随机: 在固定的位置, 随机填入随机生成的数(1-9之间)
(2)随机的随机: 在随机的位置, 随机填入随机生成的数(1-9之间)


>>> 把(1)的思路贯彻下去, 就有了:

在{1,1}的位置填入i(随机数), 在{1,2}的位置填入j(随机数, 受已填入的数限制), 在{1,3}的位置填入..., 在{9,9}的位置填入m(随机数, 但是由于只有一种可能了).
(注: {i, j}表示在第i行, 第j列) 
试着分析一下,这种状况很容易一下子就夭折了...
例如, 如果不幸的随机到


看来, 在这样的情况下, 能存活到最后的随机题目实在少之又少...

>>> 把(2)的思路贯彻下去, 又有了:

在{i0, i1}的位置(随机位置)填入i(随机数), 在{j0,j1}的位置(随机位置, 受已填入位置的限制)填入j(随机数, 受已填入的数限制), ...

唉, 不用分析了, 夭折的可能性肯定不小...虽然不是女生, 在这里还是该说"直觉"了 --- 一个程序员分析问题时该有的直觉....

那么, 怎么办呢? 第一种方法可控性强(易于控制), 第二种方法易于变通... 两种方法结合起来怎么样呢?
先在特定的位置随机一些数, 然后开始有限制的随机...为了降低失败的可能性, 后期的"随机的随机"应用"'有限制随机'的随机"(既在有最少可填入数的位置随机填入)...
那么该先随机哪些特定的位置而效果最好呢?


^_^为了让大家不晕下去, 我还是直接写出算法吧

步骤1: 在第一行, 第一列, 和中心的3X3方格 依次随机填入随机产生的数
   

步骤2: 检查每个未被填入的位置, 看它能填入的数有多少(假设为n个). 选择n最小的位置随机填入可以被填入的数(若最小的n=1, 那么就填入吧; 若>1, 随机填入; 若=0, 恭喜你, 这次随机可以废了) 

步骤3: 重复步骤2直到得到一个完整九宫或者无解为止(也就是"废")了. 若得到完整九宫, 到步骤4; 若无解, 重复步骤1-3直到得到完整九宫为止.
 

步骤4: 简化得到的完整九宫
 

理论上讲, 这样的随机存在永远得不到完整九宫的可能性. 但事实上, 在10000次的实验结果中发现: 平均1.08次重复可以得到一个完整九宫. 大多数情况下1次就能搞定, 最坏的情况为4次搞定. 也就是说: 这种算法, 在编程中, 完全是可以被接受的. PC上行, 手机上也行...

算法之SudokuPlus(数独,又称九宫)系列 --- 迷题生成篇(2)

三, 九宫知多少

看过了形形色色的九宫题目, 一个疑问飘上心头: 九宫的题目, 总共会有多少呢?

^_^, 就这个问题, 我们先不讨论. 让我们先看看九宫的一个特性吧:

(1)数字间的互换不变性
在一个完整九宫中, 1-9之间的数进行任意互换后的结果仍然是一个九宫题目

如图, 1和2互换位置后仍然是完整九宫
  

(2)行列间的互换不变性
在一个完整九宫中, 大行(或大列)间经过互换或者大行(或大列)中的单行(或单列)间经过互换后的结果仍然是一个九宫题目
注: 行1,2,3(或4,5,6, 或7,8,9)合到一起称为"大行", 列1,2,3(或4,5,6, 或7,8,9)合到一起称为"大列"

如下图: "大行"间互换后
  

如下图: "大行"中的单行互换后
  

根据(1),(2)特性, 一个完整九宫经过变换后可以有多达9!*2!*3!*3!*2!=52,254,720种(至少)的完整九宫出现!!!至于这个数字如何来的, ^_^请自己分析分析看了.

提示: 我们在这里引入"标准九宫"的概念
(1)标准九宫的第一行的数字依次为1,2,3,4,5,6,7,8,9
(2)在标准九宫, 第4行第1列的数字([4,1])比第7行第1列([7,1])的数字小(i.e. [4,1] < [7,1]
(3)在每一大行里的第一列数字里, 行数越小, 数字越小(如: [4,1]<[5,1]<[6,1])


明显的, 标准九宫有N多个噢...具体多少, 自己慢慢算...
而且, 一个完整九宫可以生成NN个九宫题目!
不多讲了, 待续吧, 下面说如何生成随机的九宫题目.