[CareerCup] 6.6 Toggle Lockers 切换锁的状态

简介:

6.6 There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?

这道题说一个走廊上有100个闭合的锁,首先一个人走过去打开所有的锁,第二次他切换2的倍数的锁的状态,第三次他切换3的倍数的锁的状态,第n次他切换n的倍数的锁的状态,以此类推直到100次遍历后,问我们有多少个锁的状态是打开的。

看到这类的应用题,我不禁想起来了国内的被骂的很惨的数学题,比如有个蓄水池,以啥啥啥速度往里进水,又以啥啥啥速度排水,问多长时间能蓄满或是排空,要么就是有两个人相向而行,中间有条狗,以匀速往返跑,求两人相遇后狗跑了几个来回等等之类的题,很多实用主义者痛批此类题毫无实际意义,其实也不必那么较真,就是练练脑子而已,看人家国外不也用此类的题目来面试嘛。

那么我们来看这道题吧,还是先枚举个小例子来分析下,比如只有5个锁的情况,'X'表示关闭,‘√’表示打开,如下所示:

初始状态:    X    X    X    X    X

第一次:      √    √    √    √    √

第二次:      √     X    √    X    √

第三次:      √     X    X    X    √

第四次:      √     X    X    √    √

第五次:      √     X    X    √    X

那么最后我们发现五次遍历后,只有1号和4号锁是打开的,而且很巧的是它们都是平方数,是巧合吗,还是其中有什么玄机。我们仔细想想,对于第n个锁,只有当次数是n的因子的之后,才能改变锁的状态,即n能被当前次数整除,比如当n为36时,它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同,括号中前面的数改变了锁状态,后面的数又变回去了,等于锁的状态没有发生变化,只有最后那个(6,6),在次数6的时候改变了一次状态,没有对应其它的状态能将其变回去了,所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对,即所有平方数的锁都将会是打开的状态。

本文转自博客园Grandyang的博客,原文链接:切换锁的状态[CareerCup] 6.6 Toggle Lockers ,如需转载请自行联系原博主。

相关文章
|
9月前
|
设计模式 缓存 Java
「全网最细 + 实战源码案例」设计模式——代理模式
代理模式(Proxy Pattern)是一种结构型设计模式,通过代理对象控制对目标对象的访问并添加额外功能。它分为静态代理和动态代理,后者包括JDK动态代理和CGLIB动态代理。JDK动态代理基于接口反射生成代理类,而CGLIB通过继承目标类生成子类。代理模式适用于延迟初始化、访问控制、远程服务、日志记录和缓存等场景,优点是职责分离、符合开闭原则和提高安全性,缺点是增加系统复杂性。
222 25
|
11月前
|
人工智能 知识图谱
轻松搭建AI版“谁是卧底”游戏,muAgent框架让知识图谱秒变编排引擎,支持复杂推理+在线协同
蚂蚁集团推出muAgent,兼容现有市面各类Agent框架,同时可实现复杂推理、在线协同、人工交互、知识即用四大核心差异技术功能。
251 2
|
Web App开发 IDE 测试技术
自动化测试的利器:Selenium 框架深度解析
【10月更文挑战第2天】在软件开发的海洋中,自动化测试犹如一艘救生艇,让质量保证的过程更加高效与精准。本文将深入探索Selenium这一强大的自动化测试框架,从其架构到实际应用,带领读者领略自动化测试的魅力和力量。通过直观的示例和清晰的步骤,我们将一起学习如何利用Selenium来提升软件测试的效率和覆盖率。
|
数据可视化 数据挖掘 数据处理
ChatGPT数据分析应用——热力图分析
ChatGPT数据分析应用——热力图分析
484 1
|
XML 安全 JavaScript
goctl 技术系列 - text/template 深入讲解
goctl 技术系列 - text/template 深入讲解
|
算法
《黑神话:悟空》中的环境渲染技术
【8月更文第26天】 随着游戏行业的不断发展,玩家对于游戏画面质量的要求也越来越高。《黑神话:悟空》作为一款备受期待的游戏大作,其精美的画质和细腻的环境渲染效果无疑给玩家带来了前所未有的视觉体验。本文将重点探讨《黑神话:悟空》中所采用的一些高级渲染技术及其背后的实现原理。
371 0
|
存储 网络协议 网络虚拟化
SRv6 基本结构
【5月更文挑战第4天】SRv6是一种网络功能指令化技术,将128位IPv6地址用于表达网络操作。它将业务需求转化为有序指令列表,由网络设备执行,实现灵活的网络业务编排和定制。
|
机器学习/深度学习 人工智能 中间件
解读顺网算力与AI,破局AIGC落地“最后一公里”
解读顺网算力与AI,破局AIGC落地“最后一公里”
|
人工智能 搜索推荐
AI助理小课堂01期
钉钉AI助理 汇集钉钉多项 AI 产品功能 以智能化方式辅助企业日常的工作
|
测试技术 Nacos 开发工具
灰度发布:揭秘背后的原理与实践浅见
揭秘灰度发布背后的原理与实践浅见
753 2