找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 703|回复: 0
收起左侧

[资源分享] 50: Count Conversion Operations 证明

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-4-2015 03:54 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
令f(n)表示从0经过(a)和(b)两种操作到达n的最少步骤,则由题意我们可以得出:
(1)如果n是奇数,则显然有f(n) = f(n-1)+1,即最后一步必须是操作(b),这是因为如果最后一步是操作(a),乘2,我们不可能得到一个奇数
(2)如果n是偶数,则有f(n) = min(f(n/2), f(n-1))+1,由于n-1是奇数,由(1)知f(n-1) = f(n-2)+1,所以
f(n) = min(f(n/2), f(n-2)+1)+1

到底是先减2好呢,还是先除以2好呢,贪心的知觉告诉我们先除好,因为除了之后得到的数更小,通过数学归纳法,我们可以证明知觉是对的:
考虑base的情况,我们有
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 3
可以看到f(4) = min(f(2), f(2)+1)+1 = f(2)+1,所以对于4,最后一步是操作(a)更优,也即f(4) = f(4/2)+1

假设对于n=2k,满足f(n) = f(n/2)+1,即f(2k) = f(k)+1,对于n = 2k+2的情况,通过上面的讨论(2)有
f(2k+2) = min(f(k+1), f(2k)+1)+1
将f(2k) = f(k)+1带入,则有
f(2k+2) = min(f(k+1), f(k)+2)+1,
又因为k+1可由k通过操作(b)达到,所以f(k+1) <= f(k)+1 < f(k)+2,从而
f(2k+2) = f(k+1) + 1

所以对于n为偶数的情况,有f(n) = f(n/2)+1,结合上面的讨论(1)就可以写代码了:
  1. class Solution {
  2. public:
  3.     int countOperations(int n) {
  4.     int step = 0;
  5.     for(; n; ++step){
  6.         if(n & 1) --n;
  7.         else n >>= 1;
  8.     }
  9.     return step;
  10.     }
  11. };
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表