经典算法(13) 随机生成和为S的N个正整数——投影法

随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。

以生成和为20的4个数为例,可以先生成随机生成0到20之间的三个数字再排序,假设得到了4,7,18 。然后在X-Y数轴上画出这三个数,如下图:

然后将这些数值投影到Y轴上 ,可得下图:

由图很容易看出AB,BC,CD, DE这四段的长度和肯定为20。因此AB,BC,CD,DE这四段的长度即和为20的4个数,这4个数分别为4,3,11 ,2。

时间: 2025-01-23 16:45:44

经典算法(13) 随机生成和为S的N个正整数——投影法的相关文章

算法-java 随机生成 两个数 n1 n2

问题描述 java 随机生成 两个数 n1 n2 java 随机生成 两个数 n1 n2 要求: n1,n2 均要 小于 指定 数值 ,比如小于1000 n1 要能整除 n2 最好不用循环.... 大概一次要生成 1万条数据,越高效率越好, 越能装13越好 解决方案 public class Test { public static void main(String[] args) { Test test = new Test(); long start = System.currentTime

C++实现随机生成迷宫地牢_C 语言

可以用这个地图核心做成一个无限迷宫类的游戏 main.cpp // Author: FreeKnight 2014-09-02 #include "stdafx.h" #include <iostream> #include <string> #include <random> #include <cassert> /* 简单逻辑流程描述: 将整个地图填满土 在地图中间挖一个房间出来 选中某一房间(如果有多个的话)的墙壁 确定要修建某种新

算法:随机生成25个元素的数组,再从里面随机取出5个不同的数(50分)

问题描述 算法:随机生成25个元素的数组,再从里面随机取出5个不同的数 解决方案 解决方案二:staticvoidRand(){Randoma=newRandom();List<Int32>lista=newList<Int32>();for(Int32i=0;i<25;i++){lista.Add(a.Next());}List<Int32>listb=newList<Int32>();for(Int32j=0;j<5;j++){Int32iT

微信红包随机生成算法php版_php实例

想了想,自己写写php版的微信红包随机生成算法,能不能实现类似的功能(其实也不敢说是算法).// $bonus_total 红包总金额// $bonus_count 红包个数// $bonus_type 红包类型 1=拼手气红包 0=普通红包 function randBonus($bonus_total=0, $bonus_count=3, $bonus_type=1){ $bonus_items = array(); // 将要瓜分的结果 $bonus_balance = $bonus_to

微信随机生成红包金额算法php版_php实例

最近在研究发红包的功能,于是写了个红包的生成算法. 红包生成算法的需求预先生成所有的红包还是一个请求随机生成一个红包 简单来说,就是把一个大整数m分解(直接以"分为单位,如1元即100)分解成n个小整数的过程,小整数的范围是[min, max]. 最简单的思路,先保底,每个小红包保证有min,然后每个请求都随机生成一个0到(max-min)范围的整数,再加上min就是红包的钱数. 这个算法虽然简单,但是有一个弊端:最后生成的红包可能都是min钱数的.也就是说可能最后的红包都是0.01元的. 另一

微信随机生成红包金额算法java版_java

最近几年玩得最疯狂的应该是发红包了,尤其是过年的时候特别受欢迎,下面写了红包的随机算法,其实挺简单的,仅是提供一种思路,希望可以给大家一些启发.  public class WxAlgorithm{ /** * @param moneySum 输入总金额 * @param redNum 输入红包数量 */ private static void wxAlgorithm(double moneySum, int redNum) { // 设置最小的金额 double moneyMin = 0.01

数据挖掘十大经典算法(详解)

数据挖掘十大经典算法  一. C4.5  C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法.   C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:  1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足:  2) 在树构造过程中进行剪枝:  3) 能够完成对连续属性的离散化处理:  4) 能够对不完整数据进行处理.  C4.5算法有如下优点:产生的分类规则易于理解,准确率较高.其缺点是:在构造树的过程中,需要对数据

PHP经典算法集锦【经典收藏】_php技巧

本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

100元50个人 随机生成 大于1小于20的随机金额 求个代码案例

问题描述 100元50个人随机生成大于1小于20的随机金额求个代码案例 解决方案 解决方案二:这个?http://blog.csdn.net/z69183787/article/details/50674531解决方案三:这个达不到我想要的效果,我想的是比如100元20个人抢,我可以设置最高的人可以抢到30元最低的人可能抢到0.1元解决方案四:你发的这个感觉最高的那么不定额度最低的那个也是不低额度解决方案五:以"平均概率"的思路来分配红包,非常无趣,这类创意乏味极了.要分配红包,就要有