证明在循环偶数n= n/2和奇数n=n+1后任意n等于1
提问于 2015-02-17 00:15:25
假设我们有一个整数n≥1。在一个循环中，当n大于1时，如果n是偶数，则n=n/ 2。如果n是奇数，则n=n+ 1。否则，算法将退出循环并返回“≥”。
我该如何从归纳法证明这个问题。我想使用归纳来假设k≥1。但是，在归纳步骤中我不能假设的条件是什么？
回答 1
Stack Overflow用户
发布于 2015-02-24 11:02:01
分裂问题3例。
1)如果n= 1，我们就完成了。
2)若n>1且n为偶数。那么下一个数字将是n / 2，如果n大于1，那么它肯定小于n。
3)若n>1且n为奇数。然后我们可以写成n= 2 *k+ 1。在下一次迭代后，我们将得到n=2*k+2。在两次迭代之后，我们将得到n=k+ 1。我们知道k+ 1 <2*k+1。
对于情况1)我们完成了，而对于情况2)和3)我们将我们的问题简化为更小的问题。
你可以从这里学习归纳法。
如果需要，我可以编写完整的归纳法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28552621
复制相关文章
![crane：字典项与关联数据处理的新思路[通俗易懂]](https://ask.qcloudimg.com/http-save/yehe-8223537/aedbc11d8e28c2a2ebec7775eda5e9f7.jpg)
【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则简介 | 数据集 与 事物 Transaction 概念 | 项 Item 概念 | 项集 Item Set | 频繁项集 | 示例解析 )
腾讯云开发者
