image.png image.png

2015 CAT Junior 最后一道题，但不难

考察二进制的原理

image.png

策略：

首先考虑power：2**n运算符合即 *2，因为增长的更快！

容易记住的几个2的幂：

4，8，16，32，64，128，256，512，1024

例如：最接近10的2的幂数，且小于10的是 8，
2**3 + 2 = 10

共有 2 次乘法，1 次加法， 一共是 3 次按下按钮

• 或者python代码bin(10)转换为2进制表达,取最高位！

例如：100和2的幂关系

print(bin(100),bin(100//2 -2),bin((100//2 -2)//8))
Output：
0b1100100  0b110000  0b110

print("以上逆运算过程: ")
print((int('0b110',2) * 8 + 2) * 2)
100

((((2+2+2)22*2 + 2) * 2)) = 100

共有 4 次乘法，3 次加法， 一共是 7 次按下按钮

例如：1000和10的幂关系

#1000 == 0b1111101000
print("1000 分解运算过程: ")
#1 // 2**2, 确保结果末尾数是0，而不是 1
print(bin(1000//2**2))   # 0b11111010
print(bin(1000//2**2 - 2))  # 0b11111000

#2  // 2**2, 确保结果末尾数是0，而不是 1
print(bin((1000//2**2 - 2) // 2**2 ))  #0b111110

#3 无法做 //2 运算，否则商的结果奇数，而通过对 2 加法或者乘法无法获得奇数
#  但可以做减法后
print(bin((1000//2**2 - 2) // 2**2 - 2))
#0b111100

#4 末尾有'00'。继续 //2 运算
print(bin(((1000//2**2 - 2) // 2**2 - 2)//2))
# 0b11110

#5 可做减法
print(bin(((1000//2**2 - 2) // 2**2 - 2)//2 - 2))
# 0b11100

#6 '00' 可以 //2，
print(bin((((1000//2**2 - 2) // 2**2 - 2)//2 - 2) // 2))
# 0b1110

#7 '0' 减去 2
print(bin((((1000//2**2 - 2) // 2**2 - 2)//2 - 2) // 2 - 2))
# 0b1100

#8 '00' // 2
print(bin(((((1000//2**2 - 2) // 2**2 - 2)//2 - 2) // 2 - 2) // 2))
# 0b110

#9 '0' - 2
print(bin(((((1000//2**2 - 2) // 2**2 - 2)//2 - 2) // 2 - 2) // 2 - 2))
# 0b100

#10 '00' // 2
print(bin((((((1000//2**2 - 2) // 2**2 - 2)//2 - 2) // 2 - 2) // 2 - 2) // 2))
# 0b10

#11 '0' - 2
print(bin((((((1000//2*2 - 2) // 2*2 - 2)//2 - 2) // 2 - 2) // 2 - 2) // 2 - 2))
# 0b0 == 0
final = "((((((1000//2*2 - 2) // 2*2 - 2)//2 - 2) // 2 - 2) // 2 - 2) // 2 - 2)"

print(final.count('*')+final.count('//')+final.count('-'))

14

再进一步，可否总结为算法实现？

再进一步，可否总结为算法实现？

十进制整数求最少次数的2 * +组合

1 整除2并且商为偶数，则 //, 数组首尾添加"(",")"

2 否则，减去 2 即二进制的'10'

from collections import deque
def shortcut(num): 

    s = str(num)
    n = num
    s = deque(s)
    while n != 0:
        if (n//2) % 2 == 0:

            s.append('//2')
            n //= 2
        else:
            n -= 2
            s.appendleft('(')
            s.append('-2'+')')
    s = ''.join(s)
    total = s.count('*')+s.count('//')+s.count('-')
    return s,eval(''.join(s)),total

num = 10
print('short:',shortcut(num))

4

num = 100
print('short:',shortcut(num))
('(((100//2-2)//2//2//2-2)//2-2)', 0, 8)

8

num = 1000
print('short:',shortcut(num))

short: ('((((((1000//2//2-2)//2//2-2)//2-2)//2-2)//2-2)//2-2)', 0, 14)

14

num == 100时，结果是8 而非是 7！这个原因是
(6-2) // 2 -2 == 0 ，共 3 个运算符
6 = 2 + 2 + 2， 只需要 2 个运算符 ’+‘

需要另外做特判处理！