0%

前言

很久之前就想写一下 RunLoop — iOS里一个很重要的概念;最近一直很忙,一拖再拖,提到拖延 — 有点像下面要说的定时器了,可以无节操的一直拖,无上限了!O(∩_∩)O~~ 终于轮到定时器了,尽管很累,还是要坚持 run 起来!这是 RunLoop 相关文章的第一篇,认真写,开个好头吧!

我第一次听到的应该是消息事件循环,因为使用了autorelease,所以就想知道这个被延迟释放的对象到底什么时候
会释放,被告知这个消息事件循环结束后,这个真不理解…

还有,使用了定时器,定时更新一些UI,结果在滑动scrollview的时候定时器停止了,网上
搜了下,修改下runloop的mode就行了,这个也不知到为啥…

还有对一些现象的观察:我们知道depatch一个子线程之后,这个线程执行的任务完成后,
就被销毁了,如果不想被销毁,而是周期性的做一些事情,那就得写个while循环或者递归了,
然后在加上sleep;就能像timer周期性的循环做一件事;

反思主线程:怎么感觉主线程就是一直存活的呀,app可以随时响应我们的操作,你可以
停一会,也可以持续操作,主线程和分线程怎么就不一样了呢,为什么主线程能一直存活?
查看代码之后,也没有发现哪里有while循环啊,甚至于递归,
此事必有蹊跷,元芳你怎么看?

我的假设:假如系统隐式地创建了一个循环,那么主线程就能一直跑了,而不会运行之后就停止了。当初学java的时候,曾经写过一个猜大小的小游戏,程序运行后,会随机生成一个1-1000的整数,然后一直猜,如果猜的不对就输出你猜大了或者猜小了,并且继续等待输入,猜对时提示恭喜猜对了,是否继续玩游戏?编写这个小游戏,主要是用两个while循环(嵌套),外部的while循环一次,表示游戏玩了一局,内部的while循环一次,表示猜了一次;不过玩游戏的时候只能一直等待输入,线程阻塞到这了!所以我们app的主线程不可能是一个简单的while循环就能搞定的,要做到不阻塞就需要一种机制,让app有事要做的时候就干活,没事了就睡觉…

NSRunLoop 的简单介绍

这个类在 Foundation framework 里,十分简单,这是他的所有方法了,这个类提供了部分 runloop 的接口,可以方便的获取到她,或者添加定时器或者端口等;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//获取所在线程的 runloop
+ (NSRunLoop *)currentRunLoop;
//获取主线程的 runloop
+ (NSRunLoop *)mainRunLoop NS_AVAILABLE(10_5, 2_0);
//当前输入类型
@property (nullable, readonly, copy) NSString *currentMode;
//获取core foundation 对象,实现更多的功能,比如添加监听;
- (CFRunLoopRef)getCFRunLoop CF_RETURNS_NOT_RETAINED;
//把定时器加入到runloop
- (void)addTimer:(NSTimer *)timer forMode:(NSString *)mode;

- (void)addPort:(NSPort *)aPort forMode:(NSString *)mode;
- (void)removePort:(NSPort *)aPort forMode:(NSString *)mode;

- (nullable NSDate *)limitDateForMode:(NSString *)mode;
- (void)acceptInputForMode:(NSString *)mode beforeDate:(NSDate *)limitDate;

@end

@interface NSRunLoop (NSRunLoopConveniences)

- (void)run;
- (void)runUntilDate:(NSDate *)limitDate;
- (BOOL)runMode:(NSString *)mode beforeDate:(NSDate *)limitDate;

@end

@interface NSRunLoop (NSOrderedPerform)

- (void)performSelector:(SEL)aSelector target:(id)target argument:(nullable id)arg order:(NSUInteger)order modes:(NSArray<NSString *> *)modes;
- (void)cancelPerformSelector:(SEL)aSelector target:(id)target argument:(nullable id)arg;
- (void)cancelPerformSelectorsWithTarget:(id)target;

@end

WARNING

1
The NSRunLoop class is generally not considered to be thread-safe and its methods should only be called within the context of the current thread. You should never try to call the methods of an NSRunLoop object running in a different thread, as doing so might cause unexpected results.
  • 其中 currentRunLoop ,current 指代的线程!我们可以把 runloop 当做线程的基础组件来对待;因为没有她的话,线程运行就会遇到一些问题,或者要费事些,比如有些线程可以让操作系统唤醒睡眠的线程以管理到来的事情,而 runloop 就是这些线程的基础;

  • runloop 是一种可以在一个周期内调度任务并处理到来的事件的循环;也就是说循环是有周期的(这不是废话么),具备调度和处理事件的能力,这是了不起的;

RunLoop 和线程的关系

  • 每个线程最多只有一个 runloop,创建一个线程时,默认没有;当调用获取方法的时候懒加载创建;主线程系统默认创建了,具体何时创建的不知道,或许系统在某个时候(当然是app启动完毕之前)调用了获取方法,这样就创建好了,换句话说在 applicationDidFinishLaunching 之后你就可以访问了!

  • 分线程开始运行 runloop 之前,要添加输入源或者定时器,要不然 runloop 会立刻退出!

  • runloop 为我们提供了与线程交互的能力,视情况而定,也许根本就用不到她;最常用的可能就是牵涉到网络交互的时候,这个最好的教程当然是 matt 大神写的 AFNetWorking 啦;有兴趣的看下源码吧,日后有时间我也会分享下阅读第三方框架的心得;

  • runloop 的作用在于当有事情(事情来自于下文的输入源,与 Mode 也有关系)要做的时侯他就去唤醒当前的线程开始工作,没事情可做就让线程去休眠;

RunLoop 的输入源

runloop 从输入源和定时器这两类源中接收事件;输入源(通常是基于端口或者自定义的)会异步向应用发送事件,主要差别在于内核会自动发出基于端口的源信号,而自定义源就需要从不同的线程中手动发出。可以通过实现与 CFRunLoopSourceRef 相关的几个回调函数来创建自定义输入源。

  • 定时器,这个是 iOS 开发中经常用到的;你对他了解多少?定时器是基于时间的通知,他为线程提供了一种可以在未来某个时间执行某个任务的机制;他是同步发出的,并且与特定的 mode (就是把定时器添加进 runloop 的那个 mode)有关,如果没有监控特定的 mode ,那么事件就会被会略掉,当然线程也不会收到通知的,直到 runloop 运行在相应的 mode 下为止;

    定时器的触发有必要解释下,我们可能知道定时器的定时间隔不是那么严格的,也就说可能会有偏差!定时器调度是基于设定的开始时间的而不是实际触发时间的!这句话可能不好理解,慢慢讲给你听吧,如果到达定时器触发时间之前有别的任务没有完成,那么就会向后拖延定时器的触发时间,如果一直拖延,加入0.5s应当执行的,拖延到了1.1s的时候可以执行了,那么上次的那个就被忽略了,如果是刷新 UI,那么效果上就是卡顿下;紧接着下一次循环触发时间不是 1.1s + 0.5s, 而是0.5s *3 = 1.5s;这下明白了吧,是基于你设定开始的那个时间的,如果中间拖延了,就会被忽略过去!并且这个延迟是没有上限的!

注:使用定时器是否需要手动添加到 runloop 取决于创建的方式,通过阅读 NSTimer Class Reference 得到的结论:

  • 1.使用 initWithFireDate 或者 timerWithTimeInterval 这些方式创建的定时器必须手动加入到runloop ;
  • 2.使用 scheduledTimerWithTimeInterval 创建的则是默认加入到当前runloop的;
  • 也可以为 runloop 添加监听者,可以在 runloop 执行过程中的某个时候收到回掉,比如进入或者退出、睡眠、唤醒、处理输入源或者定时器之前等;这个就需要使用 core Fundation 里的 api 了(CFRunLoopObserverRef 等);Fundation 提供的 api 是对 core Fundation 的封装,因此你也能找到添加定时器和 source 的方法: CFRunLoopAddTimer / CFRunLoopAddSource ;

总的来说就是:如果你有事情想让 runloop 为你管理线程去完成,那么你选取一种输入源添加进 runloop,runloop就回去监测这些输入源有没有事情要做

RunLoop 和 Mode

  • mode 有几种?阅读过 NSRunLoop Class Reference 文档之后见到了两种,NSDefaultRunLoopMode,NSRunLoopCommonModes;

其实不止两种呢,在别的地方也能找到:UIApplication Class Reference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Run Loop Mode for Tracking
Mode while tracking in controls is taking place.

Declaration
SWIFT
let UITrackingRunLoopMode: String
OBJECTIVE-C
UIKIT_EXTERN NSString *UITrackingRunLoopMode;

Constants
UITrackingRunLoopMode

The mode set while tracking in controls takes place. You can use this mode to add timers that fire during tracking.

Available in iOS 2.0 and later.

这种模式发生在 tracking 时,现在学习的 UIKit 中的控件貌似只有 scrollview 有tracking;

  • mode 有什么用途?我们通过阅读上文已经知道了,runloop 可以调度线程去完成我们要做的事情,先看两个场景吧:

    • 1.微信客户端中的聊天界面而言,当滑动聊天页面的时候,你发的动画就会暂停,手松开后就会动起来,这样做的好处就是使得滑动列表更加流畅;

    • 2.还有一些相反的场景,就是在滑动列表的时候我们也想让我们的倒计时在一直跑秒而不是停下来;

    这些都是可以通过 mode 来配置的,在不同的场景下 runloop 运行在不同的 mode 下;可以因此添加 timer ,port 时都要指定 这个源的 mode;这样 runloop 才能知道当前所处的 mode 是不是要处理输入源的事情!相当于对输入源分组,这个分组比较特殊,输入源可以同时属于不同的 mode;比如场景1设置为 DefaultRunLoopMode 就行了;对于场景2设置为DefaultRunLoopMode还不行,这会导致在滑动列表的时候停止更新UI,因为 滑动的时候 runloop 处于 UITrackingRunLoopMode ,不同于 DefaultRunLoopMode!因此到了定时器触发的时间了,却没有调用 target 的方法,所以要把 定时器加入到 UITrackingRunLoopMode 才行,这样滑动的时候也能触发定时器了!

说了半天还未提及 NSRunLoopCommonModes 这个 mode ;有人把她称之为伪模式,因为他代表了所以模式,可以说不是一种真正的模式!这些模式名称都是字符串,如果你对于 mode 不理解的话,你大可把他们都当做 枚举 而 commonModes = (default + uitacking + other…);并且每个 mode 都映射一个数组,数组里放的是添加的输入源,当然可以把输入源放到多个数组里啦;这样 runloop 运行在不同的 mode 下时就去找不同的数组,去完成任务,相信我这样通俗的说你会明白的!


这是 RunLoop 学习的第一篇博客,随着我学习的加深也会继续分享,我本人也很期待自己能耐心写作,毕竟写作的过程是枯燥的😢O(∩_∩)O~~

背景

昨天发布的博客 港版苹果充电器DIY全过程 里使用了太多的图片,看了下好几十兆大,这怎么能行呢,作死的节奏啊!所以找了一款 mac 无损图片压缩工具 – ImageOptim ,压缩比特别高,支持 PNG/JPEG/GIF 等主流格式,并且是免费的!

  • 可以直接拖入文件夹批量处理,也可以直接拖入图片,默认自动开始处理;亲身感受如下, 这是我昨天博客的图片:


  • 技巧:这里可以调节压缩比,默认的压缩比小些,博客图片质量不用很高,可以压缩定得更小些:

  • 这是今天的截图,先压缩吧:

有了这个工具就可以大大减小图片的体积了,并且是无损的,图片质量不受影响!

中秋节到了,先说声:“中秋接快乐” !
昨天晚上手机没电了,怎么办?这还用问!?脑瘫么?哦,不是啦;木有充电器啊,那就用电脑充吧,土豪么,吊!之前是用我的pro充,这次用公司发的电脑吧,两年不用忘记了windows睡眠了,结果第二天手机还是不到百分之三十的电量!这就是没有充电器的不便啊!我有港版的充电器啊,可是大陆的插排不能用啊,我有个插排,可以插上,可是不通电啊,仔细观察了下是因为港版的只有金属头是导电的,这个待会看图就明白啦!作为一个geek当然不甘寂寞!

注意事项:需要给电容放电,虽然电容存储的电量不多,但是电压不低呢,我亲身感受过,你会被电的跳起来。。。

放电方法很简单,用改锥短路电容两极就行啦,如果你看到了火花,那就说明电容里确实存了电!最后一张图就是印证哦,电容存储的电供LED亮了15s呢!

(有史以来图片最多的一次了,一共41张,wifi下浏览吧,土豪就当我没说吧…)

  • 还没开始动工呢,已经被我深深地伤害了呀…..

  • 再看看吧:

  • 先把这层模揭掉:


  • 接着就用我为数不多的工具开始割肉啦,埋头苦干了好一会,没啥反应啊!这苹果的充电器没螺丝,都是胶粘好的,用刀子划不开啊!怎么办,记得上次查过融化公交卡的办法,有种化学药剂天那水就可以,网上开始查,发现这货好像没用,因为苹果的充电器不是普通的胶水粘的!这尼玛是什么玩意呢?一个术语出来了—超声热和;高大上的技术啊;苹果做工就是好,我这租房这里家伙不全,简单的砟了几下没卵用!网上有人说房冰箱里冻下,好吧,扔冰箱里试试,下午了拿出来,确实有点凉,没锤子,尼玛看见啥用啥,大学时候的硬盘(里面有什么你懂的)拿来用吧,结果试了几下,还是没卵用。。。

  • 睡了一会觉。。。

  • 这是肯定没完啊,想当年在老家时,熬过多少个夜晚,只为我那组装的音响,往事不堪回首啦,一晃几年了!这是你逼我的,用我的电烙铁吧!我查,好使,那就继续吧,没一小会,我就把周围给全部踏平了,然后拿掉了这个盖子,识得庐山真面目:

  • 哈哈,这货是不是面目全非了:

  • 不忍心看了:

  • 接下来就是把电路板取出来了:

  • 还有工作要做,因为边缘需要处理,有的地方烙进去了

  • 不过问题不大,不严重,也不多:其实这材料挺硬的,需要小心,不要划到手,也不要划到电路板了

  • 哈哈,拿出来了:

  • 好好瞅瞅这家伙:

  • 这里是伤到的地方:

  • 这点小伤没啥的:

  • 看看背面吧:

  • 这是电源插头连接处,可以看出苹果也就是做个摆设啊,这地线根本就没连线!

  • 这货是出来了,我去哪里找个何时的外壳呢?卸开一个别的充电器看能不能放下吧,你看这电路板多简单呀,你就看中间这道黄线把,左边是220V的电源,一个整流桥,经过这个黄色的电感,得到低压,整流滤波,加个小灯完事,这比苹果的简单太多了,苹果的电路板上的东西我都看懂是啥,所以一个原装的充电器就是贵,今天就看到了,这是有原因滴!港版的是三角形的啊,放不进去:

  • 那就自己做个壳吧,就地取材,没办法,身在外不由己;上星期买的鼠标,纸壳子还在呢,感觉够硬,拿来用吧,大致比划了下,还行吧:

  • 给他留个盖子:

  • 感觉只有前盖没后盖不得劲啊,算了,画图纸,再来一个:

  • 我从小就喜欢看LED,记得第一次捡到一个绿色的led,用两节5号干电池点亮了一夜,陪着我入睡,陪着我醒来,那感觉很不错呢,所以我得装个指示灯!先看有地方没,刚好母插头旁边有地方,需要先取下她的铠甲才行呢:

  • 不得不再说一次,苹果做的就是精细,一个插头,也给她做个小外壳,这设计的真好,不忍心干掉他了都:

  • 去掉铠甲后,留下一条缝:

  • 这是前面,这条缝刚好可以用来穿过led的导线:

  • 这个LED小灯肯定是有着落啦,先找导线接通电源吧,这里我想灵活些,我可不想让她拖着长长的导线,所以又找来了废弃的光猫,上面有个插孔,刚好拿来用吧,就是这个黑色的啦:

  • 后面的为什么有一堆烟盒呢?烟瘾这么大!?什么啊,哥不抽烟好久了…这是大学时买的,刚才找LED分压电阻时拿出来的,看看里面有啥吧(认识么?):

  • 620欧姆的电阻:

  • 有电烙铁就好办事,取下来,焊接下,通电试试,这是物理老师教的哦,你忘了没?不要什么都做好了才通电,结果发现电路板已经挂了,那不就白费了嘛:

  • 我擦类,什么情况,怎么我的手机没有显示充电啊!我晕,尼玛的,老子很小心了啊,不可能啊,怀疑是光猫插头的事,立马查看电路板,看到了吗,那两个是连着的,再看我的电路,不一样,凭借经验断定我接的那个不是导电的,而是起固定作用的,莫慌,让我调换下导线,记得拔掉电源啊!!!

  • 然后开始接LED吧,测试了下正负极之后就确定了,LED的具体位置了,开搞吧,红色的太普遍啦咱不用,黄色的做指示灯的不多吧,白色是照明才用的,7彩色的我也没了,那就蓝色的吧,看放这里还行吧,也别无他选了呀:

  • 图纸早就剪好了,开始包装吧,是不是很丑啊:

  • 后面包好了,包前面吧,这里需要留孔,可是纸壳子不好搞,最终把留下的前盖给剪掉了,这算是个败笔啦,图纸是白画了!

  • 看到小灯了吗?

  • 好了,盖子都粘好了,通电吧:

  • 配备的是1k的电阻,高亮度的LED,是不是很亮了!

  • 看下后面吧,这个插头,可以拔下,剩下的就是个火柴盒那么大了:

  • 插上线试试充电吧:

  • 完工啦,来个华丽的转身:

  • 看看我这凌乱的工作台吧:

  • 哇,好乱啊!

  • ಥ_ಥ,电源拔了还能亮15s左右呢!电容在放电啦,不稀奇…

Done

不管别人怎么看,反正我是很享受这个过程啦,这是我的一个兴趣爱好而已!很遗憾没有学习物理电学,所以我也是个小白啦,仅仅知道一点电路罢了,让你们见笑了,O(∩_∩)O~~

这是别人拆绿点的过程 国外大神拆解苹果绿的充电器+深入解读其设计+绿点的由来

2015 中秋快乐!

  • ViewContrller 管理的 view 的大小是如何确定的?
  • 不同的系统版本 View 的大小一样吗?
  • 用 ViewContrller 管理的 view 的大小如何优雅的控制?

这些问题是我在写项目的时候遇到的,比较有感受;我写的是一个只支持横屏的 iPad 项目,view 比较多,因此按区域划分为好几个控制器分别管理,为了确保使用期间对象的安全存在,所以要把控制器保留住,如果不保留控制器,MRC 就会内存泄露,ARC下控制器就会释放,剩下他的 view 孤军奋战,这肯定不是你想要的结果,所以常规做法是保留控制器,然后把view添加上去,改变frame;这也可能是你现在正在使用的方法吧?!这里隐含了一个条件,在这个控制器里添加子控件的时候,是按一定的大小来写的,比如,A 控制器是一个详情展示,view 大小是(500,768),那么子视图的参考平面就是{(0,0),(500,768)}了,当然也可以超出边界,但这不是讨论的范围。

这种方法有什么问题?

其实这种方法可以,不过我在写某个模块时遇到了这样一个情形:

图 1 点击标签显示为图2

图 2

先看第一张图,很简单的九宫格布局;点击标签会出来一个浮层,样式大致是一样的,就是少了一个标签而已,所以立马想到的应该是重用了!(我可不想写两套布局)先别写哦,想下改怎么写?

按照引言部分的分析,大小已经确定了,不能重用!对于一个固执的人,没办法,就是要重用!因此考虑下怎么把这个 view 的大小变得可操控,然后子视图参考父视图而自动改变不就行了!

  • 查看view创建时的大小吧,因为这个很关键,子视图要参考的:

    1
    2
    在 viewDidLoad 里打印时,不论你模拟器的是什么方向,它默认总是竖屏(Portrait) size,也就是说在横屏模式下 width 和 height 是相反的,不是你想要的;本来猜测着vc的view的宽高会跟window的有关,通过测试把window 的宽高翻转也不行,反而会带来别的问题!经过测试,在viewDidAppear时,已经修改好了,变成横屏的大小了!又测试了下系统版本,发现:
    !!!iOS 8 已经没这个问题了,也就是说iOS 8 之后view的大小就是你的屏幕大小,而且与方向对应,比如横屏就是(1024,768);

问题来了,我们布局子视图的代码都写在 viewDidLoad 里,当我们在外部修改 view 的大小时 viewDidLoad 已经调用过了,因此这个外部指定的大小对于子视图来说然并卵啊!参照个毛线啊!有没有一举两得的办法,外部可以指定 子控制器 view 的大小,并且子控制器 viewDidLoad 里可以获取到指定的大小,而不是没有卵用的屏幕大小?

  • 由果索因 — view 从哪里来?

    当控制器的 view 被访问时就会调用 loadView 方法创建,然后紧接着调用 viewDidLoad ,
    我们创建添加子视图的代码一般也都写在这里面,因此如果 loadView 的时候 size 能正确的指定,
    我们就可以在 viewDidLoad 参照 view 的大小,布局子视图了!先打印看看结果吧,
    结果和 viewDidLoad 里打印的一样;所以可以从这里下手,
    在 loadVeiw 的时候指定一个 view 的 size,
    那么不可避免的就要加一个属性 viewSize 了!然后处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 - (instancetype)initWithViewSize:(CGSize)aSize
{
self = [super init];
if (self) {
self.viewSize = aSize;
}
return self;
}

- (void)loadView
{
[super loadView];
// 这里用了frame;用bound可能会导致origin不是0,0;导致 view 在其父视图上的位置有偏移;
CGRect rect = self.view.frame;
rect.size = self.viewSize;
self.view.frame = rect;
}

- (void)setViewSize:(CGSize)viewSize
{
_viewSize = viewSize;
if (self.isViewLoaded) {
CGRect rect = self.view.frame;
rect.size = self.viewSize;
self.view.frame = rect;
}
}
  • 有了上面的处理我们就可以在 viewDidLoad 以 view 的大小为参照布局子视图了!只需在外部调用的时候赋值就行了,不过需要注意,最好在外部使用到 view 之前给 viewSize 赋值,尽管已经实现了 setViewSize 方法!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 这个 fetch 方法是根据索因找出对应控制器的,如果是刚创建的就需要添加为子控制器
- (UIViewController *)fetchAControllerwidthIndex:(NSUInteger)idx
{
if (idx >= self.btnArr.count) {
return nil;
}

BLBaseViewController *vc = self.controllers[idx];
if ([vc isKindOfClass:[UIViewController class]]) {
return vc;
}else{
//!!!创建控制器
vc = (BLBaseViewController *)[self createViewControllerwidthIndex:idx];
if (vc) {
//!!! 访问 view 属性之前指定 view 的大小
vc.viewSize = _contentView.bounds.size;
//!!! 添加控制器和 view
[self addChildViewController:vc];
[self.contentView addSubview:vc.view];
//!!! 这个显然就没什么用了;vc.view.frame = _contentView.bounds;
[self.controllers replaceObjectAtIndex:idx withObject:vc];
}
return vc;
}
}
  • 这样一来我就可以参考父视图写我的子控制器了,由于页面几乎一样,所以抽取了父类,页面布局都是在父类完成的,逻辑统一处理,两个子类就剩下寥寥数行而已!

加了一个属性,使用方法一样,还是在外部指定大小,最重要的是内部可以参考了!这达到了我预期的要求了!经过在项目中的使用,感觉比较理想!

在我的一个群里,小伙伴发了一道题,考察下算法,自己试着想了想,拿出来一起看下吧,下面是题目:

在漆黑的夜里,N 位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N 个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N 人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这 N 人尽快过桥。( ACM 难度系数 :5)

分析问题

面对毫无头绪的问题只能慢慢分析喽,首先把 N 个人需要的时间放到一个数组 T[n] 里面吧,时间的长短是不定的,因此先排为升序;既然是 N 个人,那就从 N = 1开始分析,找找规律吧:

1
2
3
4
N = 1; 当然需要花费 T[0] 喽(数组下标从 0 开始);
N = 2; 需要花费 T[0] + T[1],也就是两个人一起过去;
N = 3; 需要花费 T[0] + T[1] + T[2]; 很容易想到的是让最快那个人去送最慢的那个花费了 T[2];他返回来花费了 T[0],然后最快的这个和剩下的这个速度不是很快的一起过去花费了 T[1];
N = 4; 这个怎么过?陷入沉思之中...

这道题目的说白了就是送人,时间由最慢的那个人决定,而且送完一个,还要返回来接着送,所以我们不可能让一个走的慢的人来充当这个‘摆渡’的,既然如此,那么我们就从走的慢的人下手吧,因为他不能充当‘摆渡’的,那么他早晚都要‘坐船’走呀,所以 N = 4 就转化为花最少的时间送走‘坐船’的;(为了简化描述,按照时间升序的顺序将4人命名为a,b,c,d)下面分析下:

  1. 根据 N = 3 的经验,我们很容易想到让 a 去送每一个人,送完一个就返回,接着送最慢的,如此3次;
  2. 可是还有一种送法,a 送 b,a 回来;c 送 d,b 回来;a 送 b,也可以,而且时间不一定哪个短,因此要比较下哪个短;
  3. 4个人不可能就这两种送法啊,还有别的,不过时间都要比这两个长;

当 N > 4 呢?其实根据 N = 4 的情况来看,这就是一个如何先送走最慢的的2个人的问题,因此 N > 4 的时候,先不考虑中间的,把最快的,次快的,最慢的,此慢的拿出来摆渡,然后问题就变成了 N - 2 的问题了!当然可以写个递归了!

下面是主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sumTimeNeed = 0;

while (size > 3) {
int time1 = a[1] + a[0] + a[size-1] + a[1] ;
int time2 = a[size-1] + a[0] + a[size-2] + a[0];
size -= 2;
sumTimeNeed += MIN(time1, time2);
}

if (size == 3) {
sumTimeNeed += a[0] + a[1] + a[2];
}else if (size == 2){
sumTimeNeed += a[1];
}else if (size == 1){
sumTimeNeed += a[0];
}

return sumTimeNeed;

欢迎去我的 GitHub 建议


1.最古老的过河问题

一个农民携带一只狼,一只羊和一棵白菜,要借助一条小船过河。小船上除了农民只能再带狼、羊、白菜中的一样。而农民不在时,狼会吃羊,羊会吃白菜。农民最少需要几趟才能安全过河呢?

2.人鬼殊途

三个鬼与三个人都要过河。河中只有一条小船,可容两人(鬼)。而且无论在船上或在岸上,每边的鬼数量如果多于人,鬼就会把人吃掉。最少需要几趟才能安全过河

3.道士与和尚

四个道士与四个和尚四个老道士与四个和尚分别在一条河的两岸,都要到河的对岸去。河中只有一条小船,可容两人。只有一个道士和一个和尚会划船。而且无论在船上或在岸上,道士的数量都不能超过和尚的数量。最少需要几趟才能安全过河

4.夫妻过河

两对夫妻两对夫妻要过河,河中只有一条小船,可容两人。两个丈夫都不愿让自己的妻子和另一个男人在一起,除非自己也在场。
最少需要几趟才能安全过河?

5.一家人及警察与犯人

现有一条河,共有八个人要过河,分别是爸爸,妈妈,两个儿子,两个女儿,一个警察,一个犯人.现有一条木伐,一次最多载两个人,在这八个人中,有妈妈,爸爸,警察会开船,即这个船上必须有爸爸,妈妈,警察三个中的一个,船才会开动.船过去无法自动回来.并且要避免以下三件事发生,1,警察不在犯人会伤害一家六口.2,爸爸不在,妈妈会伤害儿子.3,妈妈不在,爸爸会伤害女儿.
最少需要几趟才能安全过河

6.虎毒不食子

三只大老虎A、B、C和各自的小老虎a.b.c;其中只有A、B、C和a会划船;如果小老虎不和自己的母亲在一起就会被其他大老虎吃掉;只有一条船;船上可以坐一只大老虎和任意的小老虎;问:最少需要几趟才能安全过河

7.八仙过海

铁拐李 、汉钟离 、 张果老 、蓝采和 、 何仙姑 、 吕洞宾 、 韩湘子 、 曹国舅一同过海。小船只能容下三人,而且只有道铁拐李 、汉钟离、韩湘子会划船。如果韩湘子不在,曹国舅会攻击所有人;如果铁拐李不在,汉钟离会攻击张果老和蓝采和;如果汉钟离不在,铁拐李会攻击何仙姑 、 吕洞宾。请问最少需要几趟才能安全过海?

有兴趣的快去 AC 吧!