当前位置: 首页 > news >正文

卖网站怎样做泉州百度seo公司

卖网站怎样做,泉州百度seo公司,昆明网站建设SEO公司,旅行社建网站目录 ##问题描述 ##问题思考 ##贪心策略确定 ##代码实现 ##时间复杂度 ##正确性验证 ##问题描述 给定一个正整数 𝑛 ,将其切分为至少两个正整数的和,求切分后所有整数的乘积最大是多少 ##问题思考 假设我们将 𝑛 切分为 &…

目录

##问题描述

 ##问题思考

##贪心策略确定

##代码实现

##时间复杂度

 ##正确性验证


##问题描述

给定一个正整数 𝑛 ,将其切分为至少两个正整数的和,求切分后所有整数的乘积最大是多少

 ##问题思考

假设我们将 𝑛 切分为 𝑚 个整数因子,其中第 𝑖 个因子记为 𝑛𝑖 ,即

本题的目标是求得所有整数因子的最大乘积,即

我们需要思考的是:切分数量 𝑚 应该多大,每个 𝑛𝑖 应该是多少?

##贪心策略确定

我们假设从n中分出一个最小的因子2,则它们的乘积为2 * (n - 2),我们将该乘积与n进行比较得到一个重要结论:

当n≥4的时候,切分出来一个2后乘积会变大,这就说明大于等于4的整数都应该被切分出来。

##贪心策略1

如果切分方案中包含≥4因子,那么它就应该被继续切分。最终的切分方案只应出现1,2,3者三种因子。

这是我们就要思考选择什么因子会使结果达到最优解,1可以直接舍弃考虑。

当n = 6时,3*3>2*2*2,说明因子3比因子2更优。

##贪心策略2

在切分方案中,最多出现两个2.因为3个2总可以替换成2个3,获得最优的更大乘积。

综上所述,可推理出以下贪心策略。

  1. 输入整数 𝑛 ,从其不断地切分出因子 3 ,直至余数为 0、1、2 。
  2. 当余数为 0 时,代表 𝑛 是 3 的倍数,因此不做任何处理。
  3. 当余数为 2 时,不继续划分,保留。
  4. 当余数为 1 时,由于 2×2>1×3 ,因此应将最后一个 3 替换为 2 。

##代码实现

#python代码示例
import math
def max_product_cutting(n) :if n <= 3 :return 1 * (n - 1) a = n // 3b = n % 3if b == 1 :return int(math.pow(3,a-1)) * 2 * 2if b == 2 :return int(math.pow(3,a)) * 2return int(math.pow(3,a))
//c++代码示例
int maxProductCutting(int n)
{if (n <= 3){return 1 * (n - 1) ;	}	int a = n / 3 ;int b = n % 3 ;if (b == 1){return (int)pow(3,a-1) * 2 * 2 ;}if (b == 2){return (int)pow(3,a) * 2 ;}return (int)pow(3,a) ;
} 

##时间复杂度

时间复杂度取决于编程语言的幂运算的实现方法。以 Python 为例,常用的幂计算函数有三种。

  • 运算符 ** 和函数 pow() 的时间复杂度均为 𝑂(log⁡⁡𝑎) 。
  • 函数 math.pow() 内部调用 C 语言库的 pow() 函数,其执行浮点取幂,时间复杂度为 𝑂(1) 。

变量 𝑎 和 𝑏 使用常数大小的额外空间,因此空间复杂度为 𝑂(1) 。

 ##正确性验证

使用反证法,只分析 𝑛≥3 的情况。

  1. 所有因子 ≤3 :假设最优切分方案中存在 ≥4 的因子 𝑥 ,那么一定可以将其继续划分为 2(𝑥−2) ,从而获得更大的乘积。这与假设矛盾。
  2. 切分方案不包含 1 :假设最优切分方案中存在一个因子 1 ,那么它一定可以合并入另外一个因子中,以获得更大的乘积。这与假设矛盾。
  3. 切分方案最多包含两个 2 :假设最优切分方案中包含三个 2 ,那么一定可以替换为两个 3 ,乘积更大。这与假设矛盾。
http://www.ds6.com.cn/news/18742.html

相关文章:

  • 新手学做网站推荐软件人民日报最新新闻
  • 工信部企业网站备案吗产品关键词
  • 网站靠什么挣钱seo薪酬
  • 机关门花网站建设产品推广计划书怎么写
  • 政府网站建设管理工作落实情况微信小程序免费制作平台
  • 用超轻粘土做网站武汉seo网站优化排名
  • 成都市自住房建设网站互联网营销师证
  • 网站运营总监关键词优化的建议
  • 莱州网站建设哪家好如何做好网络宣传工作
  • 微网站好制作吗seo的课谁讲的好
  • 南充网站建设服务商建网站需要多少钱和什么条件
  • 一般网站维护要多久一键清理加速
  • wordpress搜索插件慢seo课培训
  • 凡网站建设潍坊网站定制模板建站
  • 做网站字体要求深圳seo推广公司
  • 政府网站集约化建设的调研报告软文是啥意思
  • 国外网站搭建平台seo霸屏软件
  • 公安部备案网站品牌战略
  • 广西建设厅建管处网站网站seo排名优化
  • 做网站是先买域名优化推广排名网站教程
  • 公司做一个网站内容如何设计方案网络营销团队
  • 网站开发的主要技术电商网站建设价格
  • wordpress cnzz 插件seo关键词排名技术
  • 网站制作帐户设置近三天重大新闻摘抄
  • 桂林网站建设找骏程发布软文的平台有哪些
  • 网站前端做报名框软文推广
  • 网站怎么提供下载推广资源seo
  • 自助手机网站建站软件国内可访问的海外网站和应用
  • css 网站根目录今日头条关键词排名优化
  • 企业网站导航菜单和业务多一样的平台