数字转换机

[编程题]数字转换机

热度指数：7195 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：

当按下了红色按钮，两个数字同时加1。

当按下了蓝色按钮，两个数字同时乘2。

小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

输入描述:

输入包括一行，一行中有四个正整数a，b，A，B，（1≤a，b，A，B≤10^9）。

输出描述:

如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

示例1

输入

100 1000 202 2002

输出

算法知识视频讲解

Python

fengqh

a, b, A, B = [int(x) for x in input().split()]
res = 0
while a != A and b != B and a <= A and b <= B:
    if a*2 <= A and b*2 <= B:
        if A % 2 == 0 and B % 2 == 0:
            A = A // 2
            B = B // 2
            res = res + 1
        else:
            a = a * 2
            b = b * 2
            res = res + 1
    else:
        a = a + 1
        b = b + 1
        res = res + 1

if a == A and b == B:
    print(res)
else:
    print(-1)

发表于 2021-04-03 12:25:43 回复(0)

Python

白色纯度

看了好多人的伪代码，能通过样例不代表思路正确。这里我从数学的角度，给出我认为很完美的一种解法。

a *2^n +k = A;

b *2^n +k = B;

判断 A-B == (a-b)*2^n，前提是A>a 且 B>b

本题目要求输出的必须是转换次数res，那么res首先包含了幂次n，其次包含了 ‘k’ 中的次数。而k的计算是基于贪心模式，k为奇数必定要先减1，是偶数就直接整除2。最后的res= n+mi_count(k)。这里我对于k的计算仍存有顾虑，贪心的想法不错。但毕竟和前面的幂次不是完全独立的。校招在即，不想花时间琢磨了，请后面的大神来指点迷津。

import math
def mi_count(k):
    ans = 0
    while k:
        if k&1==1:
            ans += 1
            k -= 1
        else:
            k = k>>1
    return ans
if __name__=='__main__':
    a,b,A,B = list(map(int,input().split()))
    res = 0
    if a<=A and b<=B:
        if (B-A)*(b-a)>=0:
            temp = int(math.log((B-A)/(b-a),2))
            if 2**temp == int((B-A)/(b-a)):
                res = temp
                k = A-a*2**temp
                res += mi_count(k)
                print(res)
            else:
                print(-1)
        else:
            print(-1)
    else:
        print(-1)

发表于 2019-09-03 21:37:49 回复(0)

Python

丶昕楚

Python Solution:

看了挺多伪算法，都是刚好只能通过试例。想了一下，这个问题没有那么简单。代码如下，没考虑到的麻烦指出。

a,b,A,B = map(int,input().split())
p,q,bp=0,0,0  for i in range(30):#30是 大致2^30次在10^9附近，反正取不到也会break，就大概就行了
    if a*2**i>A:#在除了小的数字以外，数字越大用倍数来操作操作数越少
        p=i-1#求得倍数的最大的操作次数
        break
if A-a==B-b:#避免了小的数的时候的关于倍数的判断，例如[1 2 4 5]，同样的A==a*2**p的情况也可以处理
    print(A-a)
elif A-a*2**p==B-b*2**p and A!=a*2**p:
    bp=(A-a*2**p)#计算在进行完倍数的操作数之后剩余的大小 for i in range(p):#将剩余的分配到每次倍数的操作
        if bp%(2**(p-i))>2:
            q+=bp//(2**(p-i))
            bp=bp%(2**(p-i))
        else:
            q+=bp//(2**(p-i))
            bp=bp%(2**(p-i))
            break
    print(p+q+bp)#在进行完所有的倍数操作之后多的数只能用加法解决所以直接+bp就可以了
else:
    print('-1')

编辑于 2019-03-17 10:39:56 回复(0)