算法题:李嘉诚保险柜密码问题
据说,李嘉诚的保险柜密码是一个 8 位的数字。他经常更换密码,但换密码的规则很简单,每次都把密码的数字 * 3,如果有位数溢出,就把最前面的那个数字挪到整个数字末尾加起来 —— 比如 98765432 就会变成 98765432 * 3 = 296296296, 但是这有 9 位, 把最前面的 2 加到末尾, 变成 96296298, 就是新密码。现在我们偷到了李嘉诚的保险柜,而且我们知道他最初的密码是 00000001, 已经迭代了 n 次,求一个算法,可以在 O(log n) 的时间内算出密码。
迭代分析第n次的密码计算公式:
X0 = 0000 0001
X1 = (3 * X0) % 108 + (3 * X0) / 108,显然,X1< 108
X2 = (3 * X1) % 108 + (3 * X1) / 108
= {3 * [(3 * X0) % 108 + (3 * X0) / 108]} % 108 + {3 * [(3 * X0) % 108 + (3 * X0) / 108]} / 108
= {3 * [(3 * X0) % 108]} % 108 + {3 * [(3 * X0) / 108]}(显然其值<9) % 108
+ {3 * [(3 * X0) % 108 ]} / 108 + {3 * [(3 * X0) / 108]} / 108(显然其值趋于0)
= (32 * X0) % 10(由分配率得) + (32 * X0) / 108 + [(32 * X0) % 108 ] / 108(趋于0忽略) + 0
= (32 * X0) % 10 + (32 * X0) / 108
X3 = (33 * X0) % 10 + (33 * X0) / 108
以此类推可得:
Xn = (3n * X0) % 10 + (3n * X0) / 108
又因:X0 = 1,所以:Xn = 3n % 10 + 3n / 108
关于计算3n:
1、简单处理的话可以n个3联乘,时间复杂度O(n),当n较大时比较耗时,此题暂时不考虑大数问题;
2、当n为偶数时,3n=[3(n/2)]2,当n为奇数时,3n=3*{3[(n-1)/2]}2,时间复杂度O(log n),此为最优解法。
Python实现如下:
def g(x):
return x % 100000000 + x // 100000000
def f(x):
if x == 1:
return 3
elif x % 2 == 0:
return g(f(x / 2) * f(x / 2))
elif x % 2 == 1:
return g(f(1) * f(x - 1))
if __name__ == '__main__':
print(f(50))
参考资料:
相关文章
- 【分布式搜索引擎】Elasticsearch之开启Elasticsearch的用户名密码验证
- Navicat 密码加密算法
- Gitlab修改用户密码
- Linux进阶05:忘记root密码咋办
- js 检验密码强度
- activemq安全设置 设置admin的用户名和密码
- 停止启用了安全性的WAS Server而不手动输入密码之第二种选择
- 习题 5.11 有一行电文,已按下面规律译成密码:A-Z a-z即第一个字母变成第26个字母,第i个字母变成第(26-i+1)个字母。非字母字符不变。要求编程序将密码译回原文,并输出密码和原文。
- linux操作系统中oracle数据库的密码过期问题解决
- kali linux 忘记root密码
- 提高redis cluster集群的安全性,增加密码验证
- 2023·新星计划 - 为什么头部博主们写的内容有那么多人追捧?他们是掌握了什么流量密码?
- win7系统设置进入主板密码的方法分享
- WinServer 2019 组策略 启用本地管理员账号,重置密码