切棍子
假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段,但是 1 根木棒只能由 1 人切分,当木棒被切分为 3 段后,可以同时由 3 个人分别切分木棒( 图2 )。
求最多有 m 个人时,最少要切分几次。譬如 n = 8,m = 3 时如下图所示,切分 4 次就可以了。
创新互联公司长期为上千多家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为鸡泽企业提供专业的成都网站设计、网站建设,鸡泽网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。
问题1
求当 n = 20,m = 3 时的最少切分次数。
问题2
求当 n = 100,m = 5 时的最少切分次数。
package main
import "fmt"
func cutbar(n,m,current int)int{
if current >= n{
return 0
}else if current <= m{
return 1 + cutbar(n,m,current*2)
}else {
return 1 + cutbar(n,m,current+m)
}
}
func main(){
times := cutbar(20,3,1)
fmt.Println(times)
times2 := cutbar(100,5,1)
fmt.Println(times2)
}
这里使用递归函数较为方便,n是棍子厘米数,m是人数,current是当前棍子的段数。
- 每次运算查看当前棍子段数量少于等于人数,则棍子数量翻倍,返回切分棍子的次数加1;
- 棍子段数且少于厘米数,则棍子不能全被切翻倍,只能增加m个,返回切分棍子的次数加1;
- 当棍子段数大于等于厘米数时,表示已切完,不用再切了,返回次数为0。
结果是8和22.
分享名称:切棍子
标题链接:http://scyanting.com/article/pccccp.html