ZHRMoe Studio

iOS Developing | NBA/NFL Analyses | Anime Life

分类

iPhone 16 拍照按钮适配

10/14/2024

拍照按钮功能简述

  1. 按钮的按下与抬起,在系统原生相机中的响应事件为开始录像或拍摄照片;
  2. 按钮的轻按和手势滑动:
    • 轻按分为单击和双击,单击时可以唤起侧边栏或选中功能菜单的功能,双击时侧边栏退回到上一层级;
    • 滑动时可以切换菜单中的功能或变更滑杆数值。

适配的条件和准备工作

  1. 以下所有适配在目前 iOS 18.0 SDK 下只能在摄像头启动的场景下有效,文档中特别提到 This API is for media capture use cases only.
  2. 按钮的按下与抬起需要通过 AVCaptureEventInteraction 监听,interaction 需要添加在一个与采集相关的 view 上,个人认为添加在管理拍摄的 viewController.view 上即可;
  3. 按钮的轻按和手势滑动需要根据功能设置对应的 Slider 或 Picker,这些组件都继承自 AVCaptureControl,初始化时需要指定使用的 AVCaptureDevice,并绑定在当前正在采集的 AVCaptureSession 上。
  4. 为了接收 AVCaptureControl 的回调事件,需要指定一个接收代理的对象和队列,并在对象内实现 AVCaptureSessionControlsDelegate 中的方法。

Demo 代码和说明

  1. 如前文第 4 条,在相机采集类中添加代理:
class CustomCameraCapture: NSObject {
    // 其他属性声明...
    lazy var captureSession: AVCaptureSession = AVCaptureSession()
    private lazy var interactionQueue: DispatchQueue = DispatchQueue(label: "MyInteractionQueue")
    
    // 其他方法...
    func startCapture() {
        // 处理其他开始录制的逻辑...
        if #available(iOS 18.0, *) {
            captureSession.setControlsDelegate(self, queue: interactionQueue)
        }
    }
    
}

// 实现 AVCaptureSessionControlsDelegate 中的方法,这些方法的目的是通知 AVCaptureControl 的生命周期
extension CustomCameraCapture: AVCaptureSessionControlsDelegate {
    
    func sessionControlsDidBecomeActive(_ session: AVCaptureSession) {
        debugPrint("[AVCaptureSessionControlsDelegate] sessionControlsDidBecomeActive")
    }
    
    func sessionControlsWillEnterFullscreenAppearance(_ session: AVCaptureSession) {
        debugPrint("[AVCaptureSessionControlsDelegate] sessionControlsWillEnterFullscreenAppearance")
    }
    
    func sessionControlsWillExitFullscreenAppearance(_ session: AVCaptureSession) {
        debugPrint("[AVCaptureSessionControlsDelegate] sessionControlsWillExitFullscreenAppearance")
    }
    
    func sessionControlsDidBecomeInactive(_ session: AVCaptureSession) {
        debugPrint("[AVCaptureSessionControlsDelegate] sessionControlsDidBecomeInactive")
    }
    
}
  1. 在相机采集类中提供一个给 viewController 设置 AVCaptureControl 的方法:
func handleInteractionsAndControls(on view: UIView) {
    // 虽然 AVCaptureEventInteraction 是 iOS 17.2 SDK 引入的,为了逻辑统一按照 iOS 18.0 做版本检查
    guard #available(iOS 18.0, *) else { return }
    guard let device = self.currentDevice else { return }
    self.clearInteractionsAndControls(on: view)

    // 设置 AVCaptureEventInteraction,根据 event.phase 确定按钮按下/抬起状态
    let interaction = AVCaptureEventInteraction { event in
        debugPrint("[AVCaptureEventInteraction] Event Phase: \(event.phase)")
    }
    view.addInteraction(interaction)

    // 设置系统原生的相机缩放值滑杆,回调 zoomFactor 为放大倍率,这个返回值可能有一些问题,将在后文中讨论
    let systemZoomSlider = AVCaptureSystemZoomSlider(device: device) { zoomFactor in
        debugPrint("[AVCaptureSystemZoomSlider] Zoom Factor: \(zoomFactor)")
    }

    // 设置系统原生的相机曝光值滑杆,回调 zoomFactor 为曝光度
    let systemBiasSlider = AVCaptureSystemExposureBiasSlider(device: device) { val in
        debugPrint("[AVCaptureSystemExposureBiasSlider] Value: \(val)")
    }

    // 设置自定义的滑杆,回调 val 为滑杆数值,初始化时的参数 symbolName 对应 SF Symbols 中的图标名称,in 后的参数为可调节的数值范围
    // 滑杆一般用于连续的数值选择,在原生相机中的使用场景是缩放、曝光、景深等
    let customSlider = AVCaptureSlider("Focus", symbolName: "scope", in: 0...2)
    customSlider.setActionQueue(self.interactionQueue) { val in
        debugPrint("[AVCaptureSlider] Value: \(val)")
    }

    // 设置自定义的选取框,回调 index 为选中的元素下标,初始化时的参数 symbolName 对应 SF Symbols 中的图标名称,localizedIndexTitles 为可选择的选项
    // 选取框一般用于离散的元素选择,在原生相机中的使用场景是选择滤镜或切换摄像头等
    let customPicker = AVCaptureIndexPicker("Filters", symbolName: "camera.filters", localizedIndexTitles: ["Filter 1", "Filter 2", "Filter 3", "Filter 4"])
    customPicker.setActionQueue(self.interactionQueue) { index in
        debugPrint("[AVCaptureIndexPicker] Index: \(index)")
    }

    // 开启 session 配置self.captureSession.beginConfiguration()
    let controls = [systemZoomSlider, systemBiasSlider, customSlider, customPicker]
    for control in controls {
        // 添加 control 前务必检查当前是否可以添加,直接添加可能存在个数溢出或报 NSInvalidArgumentException 异常
        if self.captureSession.canAddControl(control) {
            self.captureSession.addControl(control)
        }
    }
    // 提交 session 配置
    self.captureSession.commitConfiguration()
}

private func clearInteractionsAndControls(on view: UIView) {
    guard #available(iOS 18.0, *) else { return }
    view.interactions.forEach({ view.removeInteraction($0) })
    self.captureSession.controls.forEach({ self.captureSession.removeControl($0) })
}
  1. 在使用相机采集的 viewController 上调用方法:
self.customCamera?.handleInteractionsAndControls(on: self.view)

一些讨论

  1. AVCaptureControl 目前是黑盒的,我们只能按要求初始化并获取回调,无法自定义内部行为。特别说明这个问题是因为我个人体验下来,拍照按钮的滑动手感可能由于按钮的触控采样率相对屏幕较低,导致体感上并不非常跟手,但开发者没有办法优化内部的数据采集;
  2. AVCaptureSystemZoomSlider 回调的缩放值和滑杆上显示的数值不同,测试发现滑杆上显示的范围是1.0~5.0,但实际返回的数值是1.0~6.0,且两者之间符合线性关系 y=1.25x-0.25。这个问题在苹果开发者论坛上也有帖子讨论但目前没有官方回复。

参考文档

Enhancing your app experience with the Camera Control

Human Interface Guidelines / Camera Control

AVCaptureEventInteraction

AVCaptureControl

简单讨论 SwiftUI 中 ForEach 引起的越界问题

06/22/2021

问题的发生

某日检查公司产品在 Firebase 上的崩溃日志时,检查到一条这样的错误:

[__NSSingleObjectArrayI objectAtIndex:]: index 1 beyond bounds [0 .. 0]

简而言之,在一个 [0 … 0] 的 range 中,数组访问到了 index = 1。这简直匪夷所思,一个被限定好的合法的 range,是如何产生越界的 index 呢?我们定义到相关代码:

let events: [EKEvents] = getEvents()
let count = min(2, events.count)
ForEach(0 ..< count) { index in
    EventView(event: events[index])
}

代码功能是,获取用户日程表展示在列表中,其中如果日程个数多于两个时,只显示前两个。联系到报错,我初步认为 events 的变化导致了这次崩溃。

Events 列表发生了什么

我定位到获取用户日历的相关接口,找到了一处文档中的疑点。在方法 events(matching:) 的文档中有这样一处表述:

@result     An array of EKEvent objects, or nil. There is no guaranteed order to the events.

虽然文档中提到返回值可能包含 nil,但是返回值类型却是 [EKEvent],无论是数组还是数组中的元素都不是 Optional 类型,又怎么会返回 nil 呢?

分析到这,我怀疑这个接口可能会返回类似 [nil, …] 的结构(实际上是说不通的),于是我暂时性地丰富了健壮性:

let events = self.eventStore.events(matching: predicate)
if let _ = events.first {
    return events
} else {
    return []
}

成功复现

之后的某天因为需求改动,获取 events 的方法添加了一组默认值。在调试这个改动时,我们终于稳定复现了上面出现的崩溃。当 events 数组从两个或以上个元素变动为只有一个元素后刷新对应 UI,就会稳定触发崩溃。与此同时,log 中出现如下警告:

ForEach<range<int>, Int, Optional<eventview>> count (1) != its initial count (2). `ForEach(_:content:)` should only be used for *constant* data.

由此终于确定,这是 SwiftUI 中的 ForEach 在缓存时依然保存了上次的 range [0 … 1] 并应用到新的遍历中,所以在 [0 … 0] 中也得到了 index = 1 的结果。

奇妙的 id

我们阅读 ForEach 的文档发现,它总是用初始化的 range 进行遍历:

/// The instance only reads the initial value of the provided `data` and
/// doesn't need to identify views across updates. To compute views on
/// demand over a dynamic range, use ``ForEach/init(_:id:content:)``.

文档提到,如果 range 是动态的,则需要使用含有参数 id 的初始化方法。其中,id 是针对被遍历对象进行哈希的标志。这样一来,ForEach 的每次遍历都会经过一次哈希,而不是使用初始值。因此,我们得到了修复这个问题的代码:

/// F**k foreach, id is needed!
ForEach(0 ..< count, id: \.self) { index in
    EventView(event: events[index])
}

其中的 self 表示使用 range 中的每个 Int 本身作为哈希的标志。这里如果遍历的是 events, 也可以指定 events 中某个 hashable 的属性作为哈希的标志。

#EOF

支持 Xcode 10.1 或以下版本在 iOS 12.3 上进行真机测试的解决方案

05/17/2019

问题的发生​

Apple 在北京时间 5 月 14 日凌晨发布了 iOS 12.3 等系统更新。

一方面,iOS 12.3 更新优化了系统整体流畅性,进行了一系列功能改进[1],最重要的——带回了体验更流畅、观感更舒适的后台任务动画。这些原因让我对这次更新非常期待,阶段性结束了一系列产品需求后,我就把自己的主力机 iPhone XS 升级到了 iOS 12.3。

另一方面,Xcode 在上一个更新周期 (即 Xcode 10.2) 中就不再支持 Swift 3.x。目前我工作中接触的工程绝大多数采用 Swift 3.2 和 Objective-C 混编,少部分升级到了 Swift 4.0,还有极少部分是纯 Objective-C 工程。上一个更新周期,我提取了 Xcode 10.2 中关于 iOS 12.2 的 device support 文件放入老版本的 Xcode 中,算是解决了 IDE 和设备系统不兼容的问题。

这次,在 Xcode 版本没有更新的情况下,为了能够在 iOS 12.3 系统的设备上做真机测试,Xcode 的做法是在 10.2.1 版本上在 IDE 层级上与 iOS 12.2 共用同一套 device support 文件,但是这种方法在 Xcode 10.1 上是失效的。​

问题的解决​

错误的尝试:

将 iOS 12.2 的 device support 复制一份并重命名为”12.3(16F156)”,真机测试后发现并没有生效。

有效的方案:

修改 device support 中的数字签名,重命名文件夹为”12.3(16F156)”。

修改后的文件的下载链接: https://zhr.moe/wp-content/uploads/2019/05/12.3-16F156.zip

使用方法:解压后将文件夹放入 /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/DeviceSupport ,并重新启动 Xcode。

 

[1] 关于 iOS 12.3 的功能改进参考: https://applech2.com/archives/20190514-apple-ios-12-3-now-available.html ; 关于 iOS 12.3 的安全性内容参考: https://support.apple.com/zh-cn/HT210118

聊聊 App Transport Security 和 HTTPS

07/12/2016

App Transport Security

苹果总是成为引领行业的企业,即使很多产品和功能别人早就做出来了,苹果也能靠自己惊人的庞大体量和宣传效果让它火起来。去年,苹果在 iOS 9 和 OS X El Capitan 中引入了 ATS,顾名思义,这项功能屏蔽了所有 HTTP 访问,并保护用户的 HTTPS 访问。

由于这只是 app 中一项起到保护作用的功能,多数开发者一般选择关闭这项功能(下文中会提到)。可能是苹果的责任心爆发,他们要求开发者在 2017 年 1 月 1 日后提交的APP中必须启用 ATS,换句话说,以后的 iOS 应用必须采用 HTTPS 访问,不仅是数据抓取,即使是 web view 访问也必须是 HTTPS 的。

HTTPS

请写出专业名词全称(2 分):

HTTP: Hypertext Transfer Protocol

HTTPS: Hypertext Transfer Protocol Secure

SSL: Secure Sockets Layer

TLS: Transport Layer Security

CA: Certificate Authority

把上面的这些名词串在一起就可以解释 HTTPS 了。它是在 HTTP 的基础上进行加密的协议,而 SSL/TLS (在这里就不解释这二者了,它们可以简单地看做同一个东西在不同阶段的名字)在传输层上完成的就是加密的任务。

HTTPS 的工作原理广义上类似于人的社交关系。用火车站检票举例,火车站信任检票员可以胜任自己的工作,他们负责检查你的票和身份证是否和本人相符。如果你提供的信息是正确的,那么你将借由检票员获得火车站的信任,并允许你乘车。

回到 HTTPS,你信任你的浏览器通过可信的证书提供商 CA 进行验证,浏览器检查网站证书与网站内容是否相符,通过这层验证表示你通过你的浏览器信任了这个 HTTPS 网站。

在这之前可以耍的小聪明

ATS 强制使用 HTTPS,对于遍地 HTTP 的中国互联网环境来说,是个坏消息。虽然 HTTP 和 HTTPS 在迁移上并不复杂,但是一个好用的且可用于商业用途的HTTPS 证书价格不菲,这导致开发者一般都选择屏蔽这个功能。

在 info.plist 文件中,新建一个键为 NSAppTransportSecurity,在其中新建 Boolean 型的键 NSAllowsArbitraryLoads 设置为 YES。

访问 HTTP 网页报错

为了模拟这种情况,创建一个新工程,并添加了一个 webView,加入如下代码:

[self.webView loadRequest:[[NSURLRequest alloc] initWithURL:[NSURL URLWithString:@"http://www.qq.com/"]]];

运行后,不会加载 QQ 的主页,同时会收到访问被禁止的 log,这表示 ATS 完全屏蔽了 HTTP 的访问。

访问 HTTPS 网页报错(-9802)

将上述的代码域名改为 https://www.baidu.com/ 后,得到了报错。

为什么我们访问了HTTPS协议的网站却依然报错呢?这里我们必须参考 NSAppTransportSecurity 的官方文档查找答案。

根据文档,ATS 不仅要求请求必须是 HTTPS 协议的,还有其他的 3 点要求:

1.TLS 协议的版本必须在 TLS1.2 以上

2.要求支持完全正向保密(Perfect Forward Privacy)的加密方式,列举如下:

  • TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
  • TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256
  • TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384
  • TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA
  • TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256
  • TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA
  • TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
  • TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
  • TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384
  • TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256
  • TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA

3.签名算法至少使用一个 SHA256 指纹和一个高于 2048 位的 RSA(Rivest-Shamir-Adleman) 或高于 256 位的 ECC(Elliptic-Curve Cryptography) 秘钥

检查百度的证书,发现它没有符合上述的第二个条件,引起了 ATS 的报错。

AFNetWorking + HTTPS(-1012)

作为 iOS/OS X 平台上最好的网络访问库,AFNetWorking 本身是支持 HTTPS 访问的,而且对于 HTTPS 的要求在某些方面甚至高于 ATS 本身。

由于私人开发者一般不愿意购买权威 CA 颁发的证书,所以 AFNetWorking 会判断我们的证书是非法的,这时我们有两种方法选择。

1. 让 AFNetWorking 完全不检测证书

早期的 AFNetWorking 中,我们可以通过引用的 pch(Precompile prefix header),设置一下 AFNetWorking 的配置:

#import <SystemConfiguration/SystemConfiguration.h>
#import <MobileCoreServices/MobileCoreServices.h>
#define AFNETWORKING_ALLOW_INVALID_SSL_CERTIFICATES

后来,这种宏的设定失效了,于是我们可以修改库的安全政策:

AFSecurityPolicy *securityPolicy = [AFSecurityPolicy defaultPolicy];
securityPolicy.allowInvalidCertificates = YES;

另外,由于域名审核也是一个非常麻烦的过程,有的开发者还没有自己的域名,这时还需要设置不匹配域名:

securityPolicy.validatesDomainName = NO;

2. 让 AFNetworking 检测本地提供的个人证书

这种方法则是把自己当做一个 CA,自己一定是信任自己的,由此检查访问的域名是否匹配。

由于库要求检查 cer 文件,如果你手中的证书是 pem 文件则可以进行转换:

openssl x509 -in <servercertification>.pem -outform der -out server.cer

然后设置安全策略:

AFSecurityPolicy *securityPolicy = [AFSecurityPolicy AFSSLPinningModeCertificate];

AFNetworking 自动检查 bundle 当中的证书,这种方式的安全性相比第一种高了一些。

定制 ATS

这里列举的一些方式可能会在未来必须采用ATS后失效,但在目前是可用的。

1. 设置不使用 ATS 的域

在 info.plist 的 ATS 部分中的 NSExceptionDomains 中添加域名,并在其中将 NSIncludesSubdomains 和 NSExceptionsAllowsInsecureHTTPLoads 均设为 YES。

2. 设置使用 ATS 的域

首先按照上面的方法将 NSAllowsArbitraryLoads 设为 YES,并在 NSExceptionDomains 中添加域名,把 NSExceptionsAllowsInsecureHTTPLoads 置为 NO。

3. 降低 ATS 要求

同样在 NSExceptionDomains 中添加域名。如果需要降低 TLS 版本则修改 NSExceptionMinimumTLSVersion 为 TLSv1.1 或 TLSv1.0。如果不支持正向保密,则设置NSExceptionRequiresForwardSecrecy 为 NO。

小结

ATS 作为苹果保证用户安全地访问提供的一项功能,填补了在移动端用户不能了解自己是否访问了加密的站点的盲区。对这一功能的强行要求,可能会加强开发者甚至是用户对网络安全的重视。但即使如此,开发者也不能对安全问题掉以轻心,反而在关键服务上应该更加小心。

iOS 9.3 以上系统版本的迷之卡顿

06/09/2016

作为一名SIF玩家,在不适当的时候弹出一条推送或者收到一个电话绝对有让人摔手机的冲动。但是自从升级到 iOS 9.3 以后,SIF 又出了个新的毛病——迷之卡顿。

不仅仅是日服客户端,盛大版、美服都遇到了这个问题。在不同版本出现了同一问题,我把问题归结为iOS在相关接口和实现上的改动。但是,这种情况的出现没有任何规律可循,不知道什么时候就会卡顿,而不是一直都在卡。(事实上,查阅 iOS 9.3 的 API Differences ,并没有发现 API 实现上的更新,苹果一般也不会在这样的版本里大幅度调整 API)

直到我在城际上玩 SIF,出站的时候突然发生了卡顿,随后屏幕跟着周围光线变得更亮,我开始怀疑这种卡顿的出现和屏幕亮度的自动调节相关。单一变量测试,关闭自动调节屏幕亮度之后,很长一段时间内没有出现卡顿。另外,即使是在不是游戏这种大量消耗资源的应用里,亮度的自动调节也会带来掉帧,这样一来几乎可以确认这个问题的源头了。

只不过,我们并不了解 iOS 9.3 后对屏幕亮度的调节具体做了哪些改变,我只能猜测是它使用了不该使用的资源,如果你对手机的帧率有非常高的要求并可以牺牲亮度调节功能的话(比如玩游戏),可以选择暂时关闭这个功能。

P.S. 关于自动调节亮度和 Night Shift 的一点解释

iOS 9.3 引入了 Night Shift 功能,即在夜间开启防蓝光模式,也就是俗话说的暖屏模式。理论上,降低蓝光有两种解决方案:

  1. 降低亮度
  2. 减弱蓝光

苹果用户应该比较了解,苹果的设备在最低亮度下依然保持着相当高的亮度,这是由屏幕的特性导致的。由此,苹果决定采用第二种方式,让屏幕变暖来解决问题。

你可能会问,是不是屏幕同时要照顾到亮度调节以及变暖才导致了卡顿呢?我认为理论上不是这样的。亮度调节是由屏幕背光板来完成的,而减弱蓝光则是完全让屏幕显示的颜色在 RGB 分布上向 R 倾斜,是由两个机制操作完成的,理论上不会出现互相占用资源的情况。

后续情况

非常不幸的是,6 月 6 日发布的最新测试版 iOS 9.3.3 beta2 中,自动调节亮度依然有掉帧的问题。好在 iOS 10 的预览版就要更新了,我们也只能期待这个问题尽快被解决了。

无法识别的 Selector 发送给实例的快速排错法

01/25/2016

How to solve

Unrecognized selector sent to instance… 应该是 iOS 开发中比较常见的一种问题,但是一般这种错误的报错会指向 main.m,一时间很难找到是哪个对象发生了问题。这时,我们可以下一个 Debug 断点。

在 Xcode 的菜单栏中选择 Debug -> Breakpoints -> Create Symbolic Breakpoint… ,在弹出的标签的 Symbol 栏填入

-[NSObject(NSObject) doesNotRecognizeSelector:]

这时再次运行就会发现真正出现问题的地方了。

Example

今天在给 WebView 的一个属性赋值的时候一直报错。如果初始化 WebView 时不涉及这个属性的话,则不会出现问题。虽然我已经定位了问题的所在,但是如何解决依然没有头绪。添加断点后立刻发现,给这个属性传入的对象的某个属性出现了循环引用,改成 weak 后解决了问题。

约瑟夫环问题的模拟和递归方法

01/09/2016

Description

成都信息工程学院又要发年终大奖了!这次获大奖的人从n名会员中按以下规则选出:首先,让会员们围成一个大圈,按 0, 1, 2, …, n – 1编号.然后,随机抽取一个数 m,让编号为 0 的会员开始报数.每次喊到 m 的那个会员出列,不再回到圈中,从他的下一个人开始,继续 1, …, m 报数.这样下去,直到剩下最后一个会员为止.这名会员就能获得大奖了.输入格式输入有多组数据.每组数据一行,包含 2 个整数 n(1 <= n <= 100,000), m(1 <= m <= 100,000). n, m 分别表示会员的人数(编号 0, 1, 2, …, n – 1)和数 m(如上文所述).输出对应每组数据,输出最后拿到大奖的会员编号.

1. Linked List(Simulation)

使用链表进行模拟,空间复杂度 O(n),时间复杂度 O(mn),代码如下:

int josephRingLinkedList(int n, int m) {
    int i = 0;
    list<int> integers;
    for(i = 0; i < n; ++i) {
        integers.push_back(i);
    }
    list<int>::iterator currentInteger = integers.begin();
    while (integers.size() > 1) {
        for (int i = 1; i < m; ++i) {
            currentInteger++;
            if (currentInteger == integers.end()) {
                currentInteger = integers.begin();
            }
        }
        currentInteger++;   
        list<int>::iterator nextInteger = currentInteger;
        if (nextInteger == integers.end()) {
            nextInteger = integers.begin();
        }
        currentInteger--;
        integers.erase(currentInteger);
        currentInteger = nextInteger;
    }   
    return *(currentInteger);
}

2. Math Problem(Recursive)

把这个序列的 n 个元素记为 0, 1, 2, 3, …, n – 1。把一个 m 与 n 的组合得到的结果记为 f(n, m)。

假定第一次去掉的元素为 k,k的值为 (m – 1) % n,则去掉之后,序列剩余元素为0, 1, …, k + 1, k + 2, …, n – 1。顺序地,序列事实上变换为了k + 1, k + 2, …, n – 1, 0, 1, …, k – 1。这时候,这个序列的结果还是函数 f 吗?由于排列的顺序发生了变化,同时 n 减掉了 1,我们把这个结果记为 g(n – 1, m)。但是,第二个排列是第一个排列计算中的一个过程,所以结果应该是相同的,即:

f(n, m) = g(n – 1, m)

这时我们只需要寻找 g(n – 1, m) 与 f(n – 1, m) 建立联系,即可得到 f 的递归法则。它们的不同其实是元素的排列起始点不同,由于它们都是连续的,则只要找到两个排列之间的偏移量即可。将两个排列的顺序列举如下:

0 -> k + 1

1 -> k + 2

n – k – 2 -> n – 1

n – k – 1 -> 0

n – 2 -> k – 1

可以看出,右侧的结果是左侧加上 k + 1 再对 n 取余的结果。所以,对于 f 和 g 有:

f(n, m) = g(n – 1, m) = (f(n – 1, m) + k + 1)%n

显然,对于 n = 1 的情况,最后一定剩下的是元素 0。到这里我们可以得到 f(n, m)的递归公式:

对于 n > 1 f(n, m) = (f(n – 1, m) + k + 1) % n

对于 n = 1 f(n, m) = 0

这种递归的空间复杂度为 O(1),时间复杂度为 O(n),代码如下:

int josephRingRecursive(int n, int m) {
    int lastInteger = 0;
    for (int i = 2; i <= n; ++i) {
        lastInteger = (lastInteger + m) % i;
    } 
    return lastInteger;
}

输出流的缓冲区

12/12/2015

Intro

这段时间,不断听到一年级的萌新们在问,fflush是什么函数。为什么有了它就可以正常地输入输出,反而就会少些什么。

首先需要说明的是,在 C 语言中,不应该依赖 fflush 函数解决 I/O 问题。因为它只在某些编译器上有效。很多比较主流的编译器,比如 gcc,就并不支持这个这个函数。它是对C语言标准的扩充,虽然在 C99 中有定义,但不对所有编译器有效。

我们从文档中查到的这个函数的声明方法是 int fflush(FILE *stream); ——这里我们可以认为这个 int 类型的返回值其实是担当了 bool 类型的作用,用来判断这个操作是否成功。

具体的执行情况是:如果参数是输出流(output stream),fflush函数会把还没有输出的数据都传给这个流指向的文件。举例: fflush(stdout); 。否则,fflush 函数的行为即为未定义行为,如果发生了写入相关的错误,返回值是EOF(-1)。

下面,我们从 C++ 的角度研究一些和缓冲区有关的问题。

Output Buffer

尝试用代码向输出流添加一条输出指令,如: os << “Set output to output buffer.”; 。执行的效果可能是立刻就被打印了出来,也有可能没什么反应。这里我们只是给输出流发送指令,而并不是常规意义上的 cout,使得情况可能有所不同。假想以下情况:操作系统需要同时处理一系列输出流的输出到设备操作,而设备的写操作可能非常耗时(比如打印机等输出时需要耗时的操作),操作系统每接到一次输出流的指令就做一次操作显然浪费了系统资源和操作时间。于是,操作系统把这些指令暂时放在输出缓冲区(output buffer)里,接收到缓冲刷新的指令后,统一将多个类似的操作指令组合成单一的系统级写操作。这样,性能得到了极大的提升。

刷新缓冲的原因可能有:

  1. main 函数的 return 操作让程序正常地结束
  2. 缓冲区满,如果不刷新缓存则其他的指令不能进入缓冲区
  3. 利用操纵符显式刷新缓冲区(比如熟悉的 std::endl)
  4. 利用操纵符设置流的状态并清空缓冲区(比如 unitbuf,如果对这个东西不熟悉,那么更熟悉一些的 cerr 的内容都是默认设置  unitbuf  的)
  5. 一个输出流被关联到另一个流(比如 cin 和 cerr 都关联到 cout,因此这两种操作都会使得 cout 的缓冲区刷新)

下面介绍几个实例:

cout << "Output with a newline, refresh buffer." << endl;
cout << "Output, refresh buffer." << flush;
cout << "Output with a blank, refresh buffer." << ends;

当然,每次输出都和缓冲区打交道是很累的。这时,我们可以借用 unitbuf 指令,告诉系统之后的所有的输出都自带 flush 操作,直到我们给某次输出 nounitbuf,比如:

cout << unitbuf; //After this, every output will refresh buffer.
cout << nounitbuf; //Back to usual status.

Worthy to Say

很多情况下,萌新们辛辛苦苦写了很多代码却见不到输出。一方面可能是确实没有输出内容,还有可能是程序崩溃导致这些输出被滞留在缓冲区里面等待打印了。所以,调试的时候必须保证输出缓冲区的数据确实被刷新了,否则就会一直纠结于为什么没有输出结果这个问题上(我个人建议先写出一份可行的版本,也就是编译和运行都没有问题的,之后添加复杂的功能以满足需求)。

One More Thing

在交互较多的情况下,cin 之前必须有 cout 信息输出到设备,这时我们可以把输入流关联到输出流,让每次输入之前都刷新输出缓冲,示例:

cin >> ival;

HDOJ-2552 三足鼎立——数学不是白学的

04/09/2015

描述

MCA 山中人才辈出,洞悉外界战火纷纷,山中各路豪杰决定出山拯救百姓于水火,曾以题数扫全场的威士忌,曾经高数九十九的天外来客,曾以一剑铸十年的亦纷菲,歃血为盟,盘踞全国各个要塞(简称全国赛)遇敌杀敌,遇佛杀佛,终于击退辽军,暂时平定外患,三人位置也处于稳态。

可惜辽誓不甘心,辽国征南大将军<耶律 javac++>欲找出三人所在逐个击破,现在他发现威士忌的位置 s,天外来客的位置 u,不过很难探查到亦纷菲 v 所在何处,只能知道三人满足关系:

arctan(1 / s) = arctan(1 / u) + arctan(1 / v)

定义 f(s,u,v)=v*u-s*u-s*v 的值为”三足鼎立”

<耶律 javac++>想计算<三足鼎立>的值

输入

首先输入一个 t,表示有 t 组数据,跟着 t 行:

输入 s, u(s <= 12^3; u <= 2^20; s, u, v > 0), s, u, v 均为实数

输出

输出 v * u – s * u – s * v 的值,为了简单起见,如果是小数,直接取整

比如:答案是 1.7,则输出 1。

分析

第一感觉,这题一定是个纯模拟,反正 arctan 是可以算的。

不过,仔细想过之后发现,这个题反而是用 arctan 好好的骗了我们一把——当你看到 f(s,u,v) = v * u – s * u – s * v 的时候是不是反映到了 tan 的运算法则呢?

所以,我觉得这是一道数学题。

运算

中等数学告诉我们

tan(a + b) = (tan(a) + tan(b)) / (1 – tan(a) * tan(b)) (1)

tan(arctan(a)) = a (2)

有了以上两个基本准则,我们针对 arctan(1 / s) = arctan(1 / u) + arctan(1 / v)进行推导:

tan(arctan(1 / s)) = tan(arctan(1 / u) + arctan(1 / v))

1 / s=(1 / u + 1 / v) / (1 – 1 / u * v)

1 / s – 1 / s * u * v = 1 / u + 1 / v

v * u – s * u – s * v = 1

所以,我们居然推导出了这道题的结果直接为1!数感拯救世界!

代码

#include <stdio.h>
int main(int argc, const char * argv[]) {
    int n, a, b;
    scanf("%d", &n);
    while(n--) {
        scanf("%d %d", &a, &b);
        printf("1\n");
    }
    return 0;
}