最近关注了CSDN的程序员小灰,前两天发了个红包算法看着还蛮有意思的,自己使用C实现一下!(PS:后来才发现早已烂大街了……o(╥﹏╥)o)
规则:
1. 所有人抢到金额之和等于红包金额,不能超过,也不能少于
2. 每个人至少抢到一分钱
3. 要保证所有人抢到金额的几率相等
先做好准备:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<stdio.h> #include<stdlib.h> #include<time.h> #define random(x) (rand()%x) struct Node { float Money; struct Node *Next; }; typedef struct Node *List; List CreateList(); void Add(float current, List *last); int Find(int money, List L); void Sort(List L); void PrintList(List L); void Algorithm1(float money, int num, List L); void Algorithm2(float money, int num, List L); void Algorithm3(float money, int num, List L); int main() { List L= CreateList(); //Algorithm1(100,10,L); //Algorithm2(100, 10, L); //PrintList(L); Algorithm3(100, 10, L); } List CreateList() { List L; L = (List)malloc(sizeof(List)); L->Next = NULL; return L; } void Add(float current,List *last) { List L = (List)malloc(sizeof(List)); L->Money = current; L->Next = NULL; (*last)->Next = L; (*last) = L; } int Find(int money,List L) { List ptr = L->Next; while (ptr) { if (ptr->Money == money) { return 1; } ptr = ptr->Next; } return 0; } void Sort(List L) { List cur = NULL, tail = NULL; cur= L->Next; while (cur->Next!=tail){ int flag = 1; while (cur->Next != tail){ if (cur->Money > cur->Next->Money) { float tmp = cur->Money; cur->Money = cur->Next->Money; cur->Next->Money = tmp; flag = 0; } cur = cur->Next; } if (flag) break; tail = cur; //下一次遍历的尾结点是当前结点(仔细琢磨一下里面的道道) cur = L->Next; //遍历起始结点重置为头结点 } } void PrintList(List L) { List ptr = L->Next; int i = 0; while (ptr) { printf("第%d人抽中金额:%.2f ", ++i,ptr->Money); ptr = ptr->Next; } }
讲了三个算法
1. 第一个是乱讲的不正确的,也写一下好对比嘛
每次取0.01~剩余金额的一个随机数作为当前抽红包人的金额,当最后一个人抽取时,将剩余金额全部给他
分析一下:
假设10人,红包金额100元
第一人:随机范围(0,100),平均可以抢到50元
第二人:随机范围(0,50),平均可以抢到25元
第三人:随机范围(0,25),平均可以抢到12.5元
以此类推,每一次随机范围越来越小
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
void Algorithm1(float money,int num, List L) { List last = L; srand((int)time(0));//设置随机数种子,不设置每次随机数相同 int currentMoeny = money * 100;//将金额乘以100以获得整数 while (num>1){ int tmp = random(currentMoeny-1)+1;//保证随机数最小为1 Add(tmp/100.0,&last); currentMoeny -= tmp;//更新当前余额 num--; } Add(currentMoeny / 100.0, &last);//最后一个人抽中剩余全部金额 }
结果如下,这第一个抢的人也太多了吧……
2. 二倍均值法
剩余红包金额M,剩余人数N,那么:每次抢到金额=随机(0,M/N*2)
保证了每次随机金额的平均值是公平的
假设10人,红包金额100元
第一人:100/10*2=20,随机范围(0,20),平均可以抢到10元
第二人:90/9*2=20,随机范围(0,20),平均可以抢到10元
第三人:80/8*2=20,随机范围(0,20),平均可以抢到10元
以此类推,每次随机范围的均值是相等的
缺点:除了最后一次,任何一次抢到的金额都不会超过人均金额的两倍,并不是任意的随机
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
void Algorithm2(float money, int num, List L) { List last = L; srand((int)time(0));//设置随机数种子,不设置每次随机数相同 int currentMoeny = money * 100;//将金额乘以100以获得整数 while (num>1) { int mon = (currentMoeny / num) * 2; int tmp = random(mon-1) + 1;//保证随机数最小为1 Add(tmp / 100.0, &last); currentMoeny -= tmp;//更新当前余额 num--; } Add(currentMoeny / 100.0, &last);//最后一个人抽中剩余全部金额 }
结果一看,恩……好多了,但是我很想一个人多抢点好不好……o(* ̄︶ ̄*)o
3. 线段分割法
把红包总金额想象成一条很长的线段,而每个人抢到的金额,则是这条主线段所拆分出的若干子线段。
当N个人一起抢红包的时候,就需要确定N-1个切割点。
因此,当N个人一起抢总金额为M的红包时,我们需要做N-1次随机运算,以此确定N-1个切割点。
随机的范围区间是(1, M)。当所有切割点确定以后,子线段的长度也随之确定。这样每个人来抢红包的时候,只需要顺次领取与子线段长度等价的红包金额即可。
这就是线段切割法的思路。在这里需要注意以下两点:
(1)当随机切割点出现重复,如何处理 --- 重复了就重新切呗
(2)如何尽可能降低时间复杂度和空间复杂度 --- 这里我用链表,牺牲时间换取空间(排了个序),也可以牺牲空间节省时间(大数组)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
void Algorithm3(float money, int num, List L) { List last = L; srand((int)time(0));//设置随机数种子,不设置每次随机数相同 Add(0,&last);//初始点 int currentMoeny = money * 100;//将金额乘以100以获得整数 while (num>1) {//产生N-1个点 int tmp = random(currentMoeny - 1) + 1;//保证随机数最小为1 if (Find(tmp, L)==0) {//该点不存在 Add(tmp, &last); num--; } } Add(currentMoeny,&last);//终结点 Sort(L); int i = 0; List ptr = L->Next; while (ptr->Next) { List tmp = ptr->Next; int money = tmp->Money - ptr->Money; printf("第%d人抽中金额:%.2f ", ++i, money/100.0); ptr = ptr->Next; } }
苦啊,为了节省空间没有大数组,需要冒个泡排个序O(n^2)就没了,ε=(´ο`*)))唉,也可以再优化一点:每次随机数出来后,按顺序插入到链表,这样就节省排序的时间
比如说这样,时间复杂度是O(n^2),之前多了一个排序所以是:O(n^2)+O(n^2):
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
int Insert(float money, List L) { List ptr = L->Next; while (ptr->Next){ if (ptr->Next->Money == money) { return 0; } else if (ptr->Next->Money > money) { List tmp = (List)malloc(sizeof(List)); tmp->Money = money; tmp->Next = ptr->Next; ptr->Next = tmp; return 1; } ptr = ptr->Next; } Add(money,&ptr);//目前链表最大值加到最后 return 1; } void Algorithm3(float money, int num, List L) { List last = L; srand((int)time(0));//设置随机数种子,不设置每次随机数相同 int currentMoeny = money * 100;//将金额乘以100以获得整数 Add(0,&last);//初始点 Add(currentMoeny, &last);//终结点 while (num>1) {//产生N-1个点 int tmp = random(currentMoeny - 1) + 1;//保证随机数最小为1 //if (Find(tmp, L)==0) {//该点不存在 // Add(tmp, &last); // num--; //} if (Insert(tmp, L) == 1) { num--; } } /*Sort(L);*/ int i = 0; List ptr = L->Next; while (ptr->Next) { List tmp = ptr->Next; int money = tmp->Money - ptr->Money; printf("第%d人抽中金额:%.2f ", ++i, money/100.0); ptr = ptr->Next; } }
结果,恩……看着舒服多了,nice……睡觉了~
欢迎来吐槽!(*^▽^*)