搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > Cocoa开发者社区 > 用Swift的函数式编程解决硬币问题

用Swift的函数式编程解决硬币问题

Cocoa开发者社区 2017-11-30


在本文里,我将实验用Swift编写两种不同的实现方式来解决一个逻辑谜题。第一个实验使用命令式编程风格,这已经被大多数iOS开发者所熟悉了。然后我们将尝试用函数式编程风格来解决同一个问题,而这将使用到Swift中的一些语言特性。


项目的源代码见这里: https://github.com/ijoshsmith/break-a-dollar

逻辑谜题

不久前,一个朋友和我闲聊时提到,要破开一美元的方法一共有293种之多。也就是说,如果有人给你一美元换零钱,你可以给他293种不同的硬币组合。第二天,我开始思考如何编写代码来破开任意数量的金钱,本文总结了解开这个谜题的两种实现方式。

如果你碰巧也喜欢解谜,可以先将这篇文章放到一边,尝试编写出你自己的解决方案。因为我发现这个谜题是一个非常有趣的挑战。

美式硬币

为了那些还不太熟悉美式硬币的读者,下面是这些硬币的一个快速概览,包括它们的币值。需要注意的是,一美元纸币和一美元硬币的价值相同,都是100美分。

用Swift的函数式编程解决硬币问题

算法概览

在仔细思考过后,我最终找到了解决谜题的一个非常简单的办法。要写一个快速而粗糙的解决方案是很简单的,但为何要满足于此呢?我想要找到一个优雅的解决方案,因此我持续的从不同角度来剖析这个问题,直到最终我终于找到了想要的结果。


算法的关键在于递归式的细分问题的区间,用有限的硬币来破开一美元的不同方法,实际上是更通常问题的一个特殊实例:即用任何子集的硬币来破开任意数量的钱的方法。


比如,假设你想找出所有可能的方式来破开一个quarter(25美分),这意味着找出所有10美分、5美分和1美分的组合,让它们加起来等于25 美分。如果你选定了10美分作为组合的一部分,问题变成了有多少种组合方式来组成15美分,如果你再加上一个10美分,问题变成了5美分有多少种组合方 式,到这里答案已经很明显了,即2种,1个5美分或者5个1美分。


在这里有对算法细节更详细的描述。

表示一个coin

我编写的算法里将操纵coin,一个coin是一个整数,表示它价值多少美分。我编写了一个枚举类型来定义所有可用的coin,同时还包括一个静态方法,用递减顺序返回所有coin。

用Swift的函数式编程解决硬币问题

命令式解决方案

命令式编程风格的一个重要的地方是表示改变状态的变量。一个命令式程序就像一个微管理器,它精确的告诉计算机每一步应该做什么。下面的Swift代码对大部分iOS开发者来说应该很熟悉,因为Objective-C就是一个命令式编程语言。

上面的代码创建了一个数组来保存比当前coin的值要小的coin,它循环添加元素到数组里,使用熟悉的索引循环(loop-with-index)结构,然后,它使用一个变量sum来计算破开某价值的钱的方法数量,sum则使用递归来增加其自身的值。


这样的代码在命令式编程中就像面包和黄油一样随处可见。下面让我们来探险函数式编程的诡异世界,来看看同样的问题是如何用一种新的方法解开的。

函数式解决方案

函数式编程风格包含大量的函数,而只有少量的可变状态。因为无需维护共享变量的改变,从而减少了潜在的错误和同步的需求。有了函数作为第一类实 体,Swift能够支持高阶函数,让函数成为其它函数的组成部分。iOS开发已经朝这个方面努力了很久,包括Objective-C中的blocks,以 及苹果推出的能够接收completion handler block类型参数的API。


下面是我的函数式风格的解决方案:

这个方法的第二个参数是一个切片Slice 而非一个Coin数组,因为它不需要复制coin到新的数组。一个数组的切片能 只让数组的一部分生效,从而无需创建新数组。方法的第一行创建了数组的一个切片,命名为“smallerCoins”,其中包含写函数式代码的程序员常说 的数组的“tail”,数组的第一个元素被称为为head,剩下的部分则称为tail。需要注意的是,如果选定的范围下标越界,对数组做切片将不会触发错 误,在这个例子里,当数组仅包含一个硬币(一个Penny)时,smallerCoins将为空。


在同一行里我还创建了coin,这里使用了元组的语法,因为接受一个数组的head和tail其实是同一项任务。因此这里采取更紧凑的而有语义性的写法,而不是将它们分开多行进行赋值。


然后,我们利用名为reduce(归约)的高阶函数,来取代循环和用于统计数量的内部变量。如果你需要更多了解reduce函数是干什么的,可以阅读我之前写的文章。这里的代码处理一列整数并计算他们的和,比如[0,1,2,3,4],它们的每一个值代表每一种类型硬币的数量,比如3代表有3个Quarter(25美分)。reduce方法的第一个参数为0,它是sum参数的初始值,sum是包含归约逻辑的闭包的参数。

部分想法

我对Swift支持函数编程风格感到非常兴奋。用另一种方式思考可能会有些难度,但在这个案例中它值得这么做。几年前我告诉自己Haskell是危 险的并拒绝去学它,但现在我发现原来我不知不觉中已经学会了函数式思维,能够在我的iOS开发生涯中用它来寻找问题的不同解决办法,这让我十分惊喜。

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《用Swift的函数式编程解决硬币问题》的版权归原作者「Cocoa开发者社区」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注Cocoa开发者社区微信公众号

Cocoa开发者社区微信公众号:cocoachinabbs

Cocoa开发者社区

手机扫描上方二维码即可关注Cocoa开发者社区微信公众号

Cocoa开发者社区最新文章

精品公众号随机推荐