五千年(敝帚自珍)

主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎

共:💬102 🌺203
全看分页树展 · 主题 跟帖
家园 切环问题,须计入实践上的复杂性,2^k 序列未必是最优的

原因在于,当切破的环数(n0)大于一定数值时,那n0个环本身就提供了我们n0个1,因此我们可以不用再切出2个环、4个环……的链条(具体可以省去多少,取决于1的个数)。

例如,63个环的链条,我们须切几刀呢?只需3刀。依此法:

[4]⊙[8]⊙[16]⊙[32],其中[n]表示长度为n的链条;⊙表示切破的一个环。

2047个环的链条,只需切7刀:

[8]⊙[16]⊙[32]⊙[64]⊙[128]⊙[256]⊙[512]⊙[1024]

(七个1,加上8、16、32、……)


本帖一共被 2 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河