当前位置: 首页 > news >正文

C#,初学琼林(06)——组合数的算法、数据溢出问题的解决方法及相关C#源代码

1 排列permutation

排列,一般地,从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(permutation)。特别地,当m=n时,这个排列被称作全排列(all permutation)。

注:当且仅当两个排列的元素完全相同,且元素的排列顺序也相同,则两个排列相同。例如,abc与abd的元素不完全相同,它们是不同的排列;又如abc与acb,虽然元素完全相同,但元素的排列顺序不同,它们也是不同的排列

排列可分选排列与全排列两种,在从n个不同元素取出m个不同元素的排列种,当m<n时,这个排列称为选排列;当m=n时,这个排列称为全排列。

重复排列(permutationwith repetiton)是一种特殊的排列。从n个不同元素中可重复地选取m个元素。按照一定的顺序排成一列,称作从n个元素中取m个元素的可重复排列。当且仅当所取的元素相同,且元素的排列顺序也相同,则两个排列相同。

2 组合 combination

组合(combination)是一个数学名词。一般地,从n个不同的元素中,任取m(m≤n)个元素为一组,叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。

组合总数(total number of combinations)是一个正整数,指从n个不同元素里每次取出0个,1个,2个,…,n个不同元素的所有组合数的总和。

重复组合(combination with repetiton)是一种特殊的组合。从n个不同元素中可重复地选取m个元素。不管其顺序合成一组,称为从n个元素中取m个元素的可重复组合。当且仅当所取的元素相同,且同一元素所取的次数相同,则两个重复组合相同。

3 组合数(组合总数)的计算方法C#源代码


using System;namespace Legalsoft.Truffer
{public static partial class XMath{/// <summary>/// 计算组合数C(M,N) M>=N/// </summary>/// <param name="M"></param>/// <param name="N"></param>/// <returns></returns>public static int Combine(int M, int N){ulong ret = 1L;for (int i = M - N + 1; i <= M; i++){ret *= (ulong)i;}for (int i = 2; i <= N; i++){ret /= (ulong)i;}return (int)ret;}}
}

4 计算组合数的数据溢出问题

上述的代码,计算 C(12,5) 是没有问题的。但是,如果计算 C(100,50)!

结果 = 0 !!!

这是因为太多的数相乘,超过了 ulong 允许的最大数,这就是数据超界的问题。

5 组合总数递归算法的C#源程序

namespace Legalsoft.Truffer
{public static partial class XMath{/// <summary>/// 计算组合数C(M,N) M>=N/// </summary>/// <param name="M"></param>/// <param name="N"></param>/// <returns></returns>public static int Combine_Recursion(int M, int N){if (M < N) return 0;if (M <= 0 || N <= 0) return 1;return Combine_Recursion(M - 1, N) + Combine_Recursion(M - 1, N - 1);}}
}

递归算法可解决数值溢出问题,但会带来堆栈溢出问题,可谓“按下葫芦浮起瓢”。

6 计算组合数的追溯法(BackTrack,亦称回溯法)C#源代码

using System;namespace Legalsoft.Truffer
{public static partial class XMath{private static int num = 0;private static ulong bestnum = 0L;/// <summary>/// 追溯法计算组合数/// </summary>/// <param name="M"></param>/// <param name="N"></param>/// <returns></returns>public static ulong Combine_Backtrack(int M, int N){num = 0;bestnum = 0L;BackTrack(1, M, N);return bestnum;}/// <summary>/// 内部递归函数/// </summary>/// <param name="k"></param>/// <param name="n"></param>/// <param name="m"></param>private static void BackTrack(int k, int n, int m){if (k > n){if (num == m){bestnum++;}}else{for (int i = 0; i <= 1; i++){if (i == 0){BackTrack(k + 1, n, m);}else{if (num <= m){num = num + 1;BackTrack(k + 1, n, m);num = num - 1;}}}}}}
}

世界上没有十全十美的人,也没有十全十美的事!

回溯算法同样存在大问题,而且是致命问题:

(1)计算效率太低,速度太慢!

(2)另外会导致堆栈溢出问题。

大数的组合 有其他计算方法,以后再介绍。

本文暂且做个了解。

相关文章:

C#,初学琼林(06)——组合数的算法、数据溢出问题的解决方法及相关C#源代码

1 排列permutation 排列&#xff0c;一般地&#xff0c;从n个不同元素中取出m&#xff08;m≤n&#xff09;个元素&#xff0c;按照一定的顺序排成一列&#xff0c;叫做从n个元素中取出m个元素的一个排列(permutation)。特别地&#xff0c;当mn时&#xff0c;这个排列被称作全…...

MySQL数据库——绘制E-R图:数据库概要设计阶段

在MySQL数据库的概要设计阶段&#xff0c;绘制E-R图是非常重要的一步。E-R图&#xff08;实体关系图&#xff09;是一种图形化的工具&#xff0c;用于描述数据库中实体之间的关系。 以下是在MySQL数据库概要设计阶段绘制E-R图的步骤&#xff1a; 确定实体&#xff1a;在MySQL数…...

对类和对象的理解

对象&#xff1a;对象是人们要进行研究的任何事物&#xff0c;它不仅能表示具体的事物&#xff0c;还能表示抽象的规则、计划或事件。对象具有状态&#xff0c;一个对象用数据值来描述它的状态。对象还有操作&#xff0c;用于改变对象的状态&#xff0c;对象及其操作就是对象的…...

edge-tts微软文本转语音库,来听听这些语音是否很熟悉?

上期图文教程,我们分享了Azure机器学习的文本转语音的账号申请与API申请的详细步骤,也介绍了基于python3实现Azure机器学习文本转语音功能的代码实现过程,虽然我们可以使用Azure账号免费提供一年的试用期,但是毕竟是要付费的,我们的API也无法长期使用,好在微软发布了edge…...

MySQL更换存储引擎

要更换 MySQL 5.7 中某个表的存储引擎&#xff0c;可以使用以下的 SQL 命令&#xff1a; sql复制代码 ALTER TABLE table_name ENGINEengine_name; 其中&#xff0c;table_name 是需要更换存储引擎的数据表名称&#xff0c;engine_name 则是需要更换成的新存储引擎名称。 举…...

filebeat收集不规则多行日志

现环境有多行日志输出内容和格式不确定&#xff0c;合并后使用grok默认正则无法收集&#xff0c;需要自己编写正则 日志内容如下&#xff1a; ERROR|2023-04-06 14:27:52|helper|test|http|/api/ad/listBanner|1d60fff861bqwe4b0397be554141eb 127.0.0.1|1b4429-5adb-44d4-acf…...

Token Contrast for Weakly-Supervised Semantic Segmentation

文章来源&#xff1a;[CVPR2023] Keywords&#xff1a;Weakly-Supervised Semantic Segmentation&#xff08;WSSS&#xff09;&#xff1b;over-smoothing; ViT 一、本文提出的问题以及解决方案: 本文解决了over-smoothing问题&#xff0c;该问题其实是在之前的GCN网络中提出…...

Jenkins运行在docker中使用Maven构建Java应用程序

这篇笔记是Jenkins入门教程使用Maven构建Java应用程序的一个补充说明&#xff0c;因为我照着文档操作的过程中遇到不少问题&#xff0c;遂一一做个笔记。 我的主机是Windows 11&#xff0c;安装的docker是Docker Desktop 4.18.0。 第一点&#xff0c;在Windows里执行docker命…...

将excel导入到sqlite的方法代码

Python实现excel转sqlite的方法&#xff0c;具体如下&#xff1a; Python环境的安装配置就不说了&#xff0c;个人喜欢pydev的开发环境。 python解析excel需要使用第三方的库&#xff0c;这里选择使用xlrd 下面是源代码&#xff1a; #!/usr/bin/python # encodingutf-8 Creat…...

Redis主从复制、哨兵和集群部署

文章目录一、主从复制1、主从复制-哨兵-集群2、主从复制的概念3、主从复制的作用4、主从复制流程5、部署Redis 主从复制步骤6、实例操作&#xff1a;部署Redis 主从复制二、哨兵模式1、哨兵模式的原理2、哨兵模式的作用3、哨兵结构由两部分组成&#xff0c;哨兵节点和数据节点4…...

protobuf序列化

文章目录protubufprotobuf序列化protobuf的原理定义message编译message文件应用protobufMessage 基本用法Message 嵌套使用protubuf protobuf序列化 protobuf是一种比json和xml等序列化工具更加轻量和高效的结构化数据存储格式&#xff0c;性能比json和xml真的强很多&#xff…...

更新时无冲突的情况(阁瑞钛伦特软件-九耶实训)

大多数使用“与资源库同步”菜单的目的是想查看本地和远程资源的差异&#xff0c;并不想将本地的内容进行更新。 而“更新”菜单则不然&#xff0c;它的主要作用是将远程仓库中的内容下载到本地&#xff0c;以使本地的版本内容和仓库中的内容一致。 Step01&#xff1a;复用前…...

3.4 函数的单调性和曲线的凹凸性

学习目标&#xff1a; 如果我要学习函数的单调性和曲线的凹凸性&#xff0c;我会采取以下几个步骤&#xff1a; 理解概念和定义&#xff1a;首先&#xff0c;我会学习单调性和凹凸性的定义和概念。单调性是指函数的增减性质&#xff0c;可以分为单调递增和单调递减&#xff1b…...

LeetCode 404. 左叶子之和 | C++语言版

LeetCode 404. 左叶子之和 | C语言版LeetCode 404. 左叶子之和题目描述解题思路思路一&#xff1a;使用递归代码实现运行结果参考文章&#xff1a;思路二&#xff1a;减少遍历节点数代码实现运行结果参考文章&#xff1a;LeetCode 404. 左叶子之和 题目描述 题目地址&#xf…...

arm架构安装Rancher并导入k8s集群解决Error: no objects passed to apply

Rancher介绍 Rancher 2.0-2.4版本 是一个开源的企业级容器管理平台。通过Rancher&#xff0c;企业再也不必自己使用一系列的开源软件去从头搭建容器服务平台。Rancher提供了在生产环境中使用的管理Docker和Kubernetes的全栈化容器部署与管理平台。 Rancher 2.5版本 是为使用容…...

安装PaddleSpeech

github地址https://github.com/PaddlePaddle/PaddleSpeech 创建虚拟环境 conda create -p E:\Python\envs\nlppaddle python3.7 # conda create -p E:\Python\envs\speechstu python3.8激活虚拟环境 conda activate E:\Python\envs\nlppaddle # conda activate E:\Python\…...

UE “体积”的简单介绍

目录 一、阻挡体积 二、摄像机阻挡体积 三、销毁Z体积 四、后期处理体积 一、阻挡体积 你可以在静态网格体上使用阻挡体积替代碰撞表面&#xff0c;比如建筑物墙壁。这可以增强场景的可预测性&#xff0c;因为物理对象不会与地面和墙壁上的凸起细节相互作用。它还能降低物理模…...

微信 JAVA SDK 封装

weixin-popular 微信 JAVA SDK&#xff0c;是微信平台&#xff08;公众平台、开放平台、商户平台、服务商平台&#xff09;接口服务的JAVA 实现&#xff0c;开发 严格按照官方技术文档&#xff0c;合理划分包名、定义字段及方法&#xff0c;能胜任任何微信相关的业务。 使用建…...

上海智慧校园视频智能分析算法 yolov7

上海智慧校园视频智能分析算法通过yolov7python网络模型分析技术&#xff0c;上海智慧校园视频智能分析算法对校园内学生打架、翻墙、倒地、异常聚集、攀高等行为实时监测预警。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#xff0c;研究团队希望它能够同时支持移动 GP…...

【树】你真的会二叉树了嘛? --二叉树LeetCode专题

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...