断金链问题
只要将63化成二进制表示:等于”111111″即63=1 2 4 8 16 32只要将从第二节开始的两节割开,再将从第八节开始的八节割下来,和从第32节开始的32节割下来即可,这样就有了从1,2,3,4,5,6,直到63的所有节数.一般地,若有 n 节金链, n 是形如 2k-1 类型的数,将 n 化成二进制表示,再将所有”1″的位置所代表的2的幂的数相间隔地割开即可达到目的.但是对于其他任意类型的数,却不能奏效,比如对于格罗丽亚的79节金项链,79的二进制记数法表示为”1001111″.即79=1 2 4 8 0 0 64,这样从1到15都能表示,可是从16到63都没法表示. 咱们可以这样:你不是要求节数最少吗?假设 n=a b 其中 a 是已经找到的最大的那一节数,b 是比 n 小的已经解决了的金链问题,由于 b 已经解决,因此 b 的拆分能够表示从1,2,3,…b-1,b 的所有金链节数,而再大一些的数就不能够表示了,比如 b 1,所以必须要 a 参加进来,如果 n 是奇数,可令 a=b 1,这样 n=2b 1,所以 b=(n-1)/2,a=(n 1)/2,这样就找到了最大的一节的节数 a ,然后对 b=(n-1)/2继续应用如上的办法,即可解决问题.如果 n 是偶数,可令 a=b ,这样虽然 a 本身不能表示出 b 1,但是可以从 b 的拆分中拿出一个1来(这个1是必须存在的,因为要表示从1,2,3,…b-1,b的所有数)与 a 组成 a 1 也就是 b 1.所以 n=a b=2a=2b,a=b=n/2.这样也找到了 n 为偶数时最大的一节金链的节数.对于 b 继续如上的过程,就可以找到全部应该断开的金链节数. 从上面所列出的拆分法可以看出,如果,那么 n 一定要用 k 1个数来表示,即: . [...]
