切分木棒(DFS)(BFS)
题目
假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切分木棒（图 2）。
图 2 n ＝ 8，m ＝ 3 的时候
求最多有 m 个人时，最少要切分几次。譬如 n ＝ 8，m＝ 3 时如图所示，切分 4 次就可以了。
作者：图灵教育 链接：https://leetcode-cn.com/leetbook/read/interesting-algorithm-puzzles-for-programmers/90ach5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路
方法1：DFS
#include <iostream>
using namespace std;
int sil(int m, int n, int num) //n要求段数 m人数 num目前段数
{
if (num >= n) { //达到要求结束
return 0;
}
else if (num < m) { //目前段数小于人数，直接段数*2
return 1 + sil(m, n, num * 2);
}
else { //目前段数大于等于人数，增加m段
return 1 + sil(m, n, num + m);
}
}
int main()
{
cout<<sil(3, 20, 1)<<endl<<sil(5, 100, 1);
return 0;
}方法2：BFS
#include <iostream>
using namespace std;
int sil(int m, int n, int num) //n要求段数 m人数 num目前段数
{
int count = 0;
while (num < n) {
num += num < m ? num : m;
/*
if (num < m) {
num += num;
}
else {
num += m;
}
count++;
*/
count++;
}
return count;
}
int main()
{
cout<<sil(3, 20, 1)<<endl<<sil(5, 100, 1);
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021年01月30日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
