iOS中排列组合算法的使用小结

前言

最近在项目中用到了排列组合计算，虽然比较简单，但是整个学习过程还是要记录下来的，以便以后可以吸取经验。

一般来说，排列组合就等于搜索。

注意点：

1.去重复：规定子集顺序必须升序；

2.候选数组的结果处理。必须深拷贝，否则最后的结果集里全是空的（加了一堆指针）。

3.在写递归的时候（DFS:深度优先搜索），思路是先把以 1 开头的都找出来，再把 2 开头的都找出来 …… 所有在递归之前做过的事情，之后都要把它抹回来。递归做的事情能一句话描述清楚。递归就是不断地把规模变小，但是都做的一件事情。

方法如下：

最开始的思路是用阶乘去解决排列组合的问题，所以就想到了递归。

long arithmetic(int n)
{
 if (n>1) {
 return n*arithmetic(n-1);
 }else if (n == 1){
 return 1;
 }else{
 return 1;
 }
}

但是递归的话，有一个弊端，数字达到一定程度的时候，它会出现值越界的情况，就算是用long long类型，也还是会出现越界的情况。所以用阶乘的这种方式，被暂时搁置。

想到的第二种思路是用for循环去解决问题。仅仅只用到排列这种算法，阶乘还是非用不可得，但是就组合而言，完全可以换另一种方式去解决。

解决的思路就是为了不让数字值越界，可以让分子和分母约分后，再乘下一个分子，再和分母约分。以此类推。话不多说，直接上代码：

/**
 双色球 普通选注
 */
- (long)lotterySSQPTRecursiveWithRedBalls:(NSUInteger)redBalls blueBalls:(NSUInteger)blueBalls{
 if (redBalls > 5 && blueBalls > 0) {
 if (redBalls == 6) {
  return blueBalls;
 }else{
  NSUInteger count = (redBalls-6 > 6) ? 6 : redBalls-6;
  long number = 1;
  long molecular = 1;
  long denominator = 1;
  for (int i = 0; i < count; i++) {
  molecular = molecular*(redBalls-i);
  denominator = denominator * (i+1);
  number = (molecular*number)/denominator;
  molecular = 1;
  denominator = 1;
  }
  number = number*blueBalls;

  return number;
 }
 }else{
 return 0;
 }
}

相比于直接用阶乘，个人觉得还是for循环更好一些。如果有什么更好的解决思路，欢迎各位留言！

想要看Demo的小伙伴，点击此处传送 （本地下载）

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • ios使用OC写算法之递归实现八皇后

    八皇后算法介绍 知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后 八皇后算法思路解析 既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行.纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用

  • iOS算法教程之分段截取常数示例

    前言 本文主要给大家介绍了关于iOS算法之分段截取常数的相关内容,分享出来供大家参考学习价值,下面话不多说了,来一起看看详细的介绍吧. 一.错位分段相加,递归合并的过程 #include intHamming_weight_3(intn ) { n = (n&0x55555555) + ((n>>1)&0x55555555); n = (n&0x33333333) + ((n>>2)&0x33333333); n = (n&0x0f0f0f0

  • iOS常用加密算法介绍和代码实践

    iOS系统库中定义了软件开发中常用的加解密算法,接口为C语言形式.具体包括了以下几个大类: #include <CommonCrypto/CommonCryptor.h> //常用加解密算法 #include <CommonCrypto/CommonDigest.h> //摘要算法 #include <CommonCrypto/CommonHMAC.h> #include <CommonCrypto/CommonKeyDerivation.h> #inclu

  • iOS实现高效裁剪图片圆角算法教程

    iOS实现高效裁剪图片圆角算法教程

    前言 项目有个需求:裁剪图片,针对头像,下面是要求: 大家可以看到这张图片的圆角已经去除,下面说说我在项目利用了两种方式实现此裁剪以及查看技术文档发现更高效裁剪方式,下面一一讲解:看下来大约需要15-20分钟. 在公共类中Util类中创建类方法 1.CGContext裁剪 //CGContext裁剪 + (UIImage *)CGContextClip:(UIImage *)img cornerRadius:(CGFloat)c; 实现该方法: // CGContext 裁剪 + (UIImag

  • iOS中MD5加密算法的介绍和使用

    前言 软件开发过程中,对数据进行加密是保证数据安全的重要手段,常见的加密有Base64加密和MD5加密.Base64加密是可逆的,MD5加密目前来说一般是不可逆的. MD5生成的是固定的128bit,即128个0和1的二进制位,而在实际应用开发中,通常是以16进制输出的,所以正好就是32位的16进制,说白了也就是32个16进制的数字. MD5主要特点是 不可逆,相同数据的MD5值肯定一样,不同数据的MD5值不一样(也不是绝对的,但基本是不能一样的). MD5算法还具有以下性质: 1.压缩性:任意

  • IOS面试大全之常见算法

    这篇文字给大家分享了IOS面试中熟悉常见的算法,下面来一起看看吧. 1. 对以下一组数据进行降序排序(冒泡排序)."24,17,85,13,9,54,76,45,5,63" int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int num = sizeof(array)/sizeof(int); for(int i = 0; i < num-1; i

  • iOS中排列组合算法的使用小结

    前言 最近在项目中用到了排列组合计算,虽然比较简单,但是整个学习过程还是要记录下来的,以便以后可以吸取经验. 一般来说,排列组合就等于搜索. 注意点: 1.去重复:规定子集顺序必须升序: 2.候选数组的结果处理.必须深拷贝,否则最后的结果集里全是空的(加了一堆指针). 3.在写递归的时候(DFS:深度优先搜索),思路是先把以 1 开头的都找出来,再把 2 开头的都找出来 -- 所有在递归之前做过的事情,之后都要把它抹回来.递归做的事情能一句话描述清楚.递归就是不断地把规模变小,但是都做的一件事情

  • 浅谈c语言中一种典型的排列组合算法

    浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • Golang排列组合算法问题之全排列实现方法

    本文实例讲述了Golang排列组合算法问题之全排列实现方法.分享给大家供大家参考,具体如下: [排列组合问题] 一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号. 输入: 包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格. 输出: 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行. 样例输入: 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3

  • C#实现排列组合算法完整实例

    排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法.分享给大家供大家参考之用.具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections.Generic; namespace Test { class Prog

  • JS实现的排列组合算法示例

    JS实现的排列组合算法示例

    本文实例讲述了JS实现的排列组合算法.分享给大家供大家参考,具体如下: 在数学中有排列组合,用来计算概率. 比如:从4个数字中,任意选择两个的情况.从5个数字中任意选择3个数字的情况.(这里我们只考虑没有顺序的情况). 公式:C(n,m)=n!/[m!(n-m)!]=n*(n-1)*...*(n-m+1)/[1*2*...*m],如C(5,2)=[5*4]/[1*2]=10. 举例说明:有 1,2,3,4 四个数字,从这四个数字中,任意选择两个数字一共有多少种情况:[1,2], [1,3], [

  • 高效的java版排列组合算法

    本文实例为大家分享了java排列组合算法的具体代码,供大家参考,具体内容如下 package BeanUtil; import java.util.ArrayList; import java.util.List; import com.work.core.exception.OurException; /** * 统计任三出现的最多的几率的组合 * * @author wangmingjie * @date 2009-1-1下午01:22:19 */ public class Copy_2_o

  • PHP实现的简单排列组合算法应用示例

    本文实例讲述了PHP实现的简单排列组合算法应用.分享给大家供大家参考,具体如下: 一.问题: 给你一个40斤的西瓜,给3个人分,有多少种分法? 二.PHP实现代码: <?php $aa = range(1,40); $bb = array(); foreach($aa as $k=>$val){ foreach($aa as $v){ foreach($aa as $vl){ $sum = $val+$v+$vl; if($sum == 40){ $bb[$k][0] = $val; $bb[

  • Java获得一个数组的指定长度排列组合算法示例

    本文实例讲述了Java获得一个数组的指定长度排列组合算法.分享给大家供大家参考,具体如下: package demo; import java.util.Stack; /** * JAVA获得一个数组的指定长度的排列组合.<br> * * @author JAVA世纪网(java2000.net, laozizhu.com) */ public class TestSequenceAll { public static void main(String[] args) { TestSequen

  • Python实现的简单排列组合算法示例

    本文实例讲述了Python实现的简单排列组合算法.分享给大家供大家参考,具体如下: 1.python语言简单.方便,其内部可以快速实现排列组合算法,下面做简单介绍 2.一个列表数据任意组合 主要是利用自带的库: #_*_ coding:utf-8 _*_ #__author__='dragon' import itertools list1 = [1,2,3,4,5] list2 = [] for i in range(1,len(list1)+1): iter = itertools.comb

随机推荐