相较稳定的红包算法实现/c语言实现

红包的分配分布，个人认为能够运用到正态分布是极好，运气好的人少，运气差的人也少，但是本篇算法并不打算利用正态分布的特性来实现分配红包算法（本人太菜），而是一个产生红包相对稳定，一定程度上也算一个是符合正太分布特性的算法（世间很多事物的分布一定程度上都满足正态分布，我的理解：1、总量是固定不变的(具体特性记不得了),；2、分布呈现的是两边少，中间多；)。

下面介绍以下该算法的思路中涉及比较重要的点

    1. 随机二分法（我自己取的名字，大概的意思就是使用一个随机数，将一个较大的值随机分为两个较小的值）。

    2. 每次将集合(分割出来的节点)中值最大的节点进行分割。

 算法涉及的基本数据结构介绍:

    1. Node，红包节点，属性(金额，相邻的前后红包节点指针)

    2. List，链表，属性(红包总数，红包总金额，指向最大金额红包的head指针，和指向金额最小的tail指针)

算法流程:

    1. 首先初始化链表(红包总金额和总数)，并向链表中插入总金额的红包节点; 

    2. 取出最大的红包节点，将其金额进行分割，将分割的金额生成两个红包节点;

    3. 将分割出来的红包节点插入链表中；

    4. 执行2, 3过程，直至分割出预期的红包个数

    ... todo, 可以通过遍历链表获取从大到小排序的红包节点。可以按照规则实现（获取大额红包的人尽可能是比较快的人，等等），将节点有规则或者无规则的打乱然后放入到队列中，抢红包的时候就从队列中取出即可。

以下是算法的源码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>

const float MIN = 0.01;
const float MIN_LIMIT_PERCENT = 0.5;
const float ROUND_FLOAT = 0.005;

/*----------- 涉及到的数据结构的定义*/
/*=======Node */
typedef struct Node{
    float val;          //值
    struct Node * pre;
    struct Node * next;
} nod;

nod * create_node(float value)
{
    nod * node = (nod *)malloc(sizeof(nod));
    node->val = value;
    node->pre = NULL;
    node->next = NULL;
    return node;
}

void rep_node(nod * before, nod * cur)
{
    cur->next = before->next;
    cur->pre = before;
    before->next->pre = cur;
    before->next = cur;
}

/*=======list */
typedef struct List{
    nod * tail;    //链表尾部
    nod * head;    //链表头部
    int number;     //结点数量
    float value;    //链表总值
} LT;

void init_lt(LT * l, float value, int number)
{
    l->tail = NULL;
    l->head = NULL;
    l->number = number;
    l->value = value;
}

nod * get_head(LT * l)
{
    return l->head;
}

nod * pop(LT * l)
{
    nod * node = l->head;
    if(!node)
    {
        return node;
    }
    nod * n_head = node->next;
    node->next = NULL;
    l->head = n_head;
    if(!l->head)
    {
        l->tail = NULL;
    }
    return node;
}

void inst_node(LT * l, nod * node)
{
    nod * head = l->head;
    if(!head)
    {
        l->head = node;
        l->tail = node;
        return;
    }
    nod * before;
    nod * go = head;
    while(go && go->val > node->val)
    {
        before = go;
        go = go->next;
    }
    if(!go)
    {
        before->next = node;
        l->tail = node;
    }
    else
    {
        //链表头节点置换
        if(go == head)
        {
            node->next = head;
            l->head = node;
        }
        else
        {
            rep_node(before, node);
        }
    }
    return;
}


/*----------- 涉及到的算法*/
float random(int mask)
{
    int random = rand();
    //printf("random:%d, mask:%d, div:%d, mid:%0.4f\n", random, mask, (random%mask+1), (float)(random%mask+1)/(mask+2));
    return (float)((int)((((float)(random%mask+1)/(mask+2))+0.0005)*1000))/1000;
}

//分割一个数
float divide(float value, float percent)
{
    //printf("percent:%f\n", percent);
    return (float)((int)((value*percent+ROUND_FLOAT)*100))/100;
}

/*----------- process*/
void work(LT * l, float money, int count)
{
    srand(time(NULL));
    nod * mey = create_node(money);
    inst_node(l, mey);
    int mask = count-1;
    //将money分割count次
    while(count-- > 0)
    {
        //将最大节点弹出
        nod * max_value_node = pop(l);
        //printf("node:%0.2f, count:%d\n", max_value_node->val, count);
        //产生一个随机数, 随机切分最大节点的值c，产生两个数a、b, c = a+b;
        //float div_left = divide(max_value_node->val, random(count+1));    //波动幅度较下面的小
        float div_left = divide(max_value_node->val, random(mask));         //波动幅度较上面的大
        //当数值及其小时，采取对分的方法，将value分割开来
        if(div_left - 0 < MIN || max_value_node->val - div_left < MIN)
        {
            div_left = (float)((int)(((max_value_node->val*MIN_LIMIT_PERCENT)+ROUND_FLOAT)*100))/100;
        }
        float div_right = max_value_node->val - div_left;
        //生成两个节点a, b;
        nod * left_nod = create_node(div_left);
        nod * right_nod = create_node(div_right);
        //printf("left:%0.2f, right:%0.2f\n", div_left, div_right);
        //依次插入链表中
        inst_node(l, left_nod);
        inst_node(l, right_nod);
        free(max_value_node);
    }
    printf("============= result =============\n");
    _print(l);
}


/*----------- test*/
void _print(LT * l)
{
    nod * go = l->head;
    int count = 0;
    float sum = 0.00;
    while(go)
    {
        count++;
        sum += go->val;
        printf("node->value:%0.3f\n", go->val);
        go = go->next;
    }
    printf("sum:%0.2f, count:%d", sum, count);
}

/*----------- main*/
int main()
{
    float money = 100.00;        //红包总金额
    int number = 100;            //红包个数
    if(money/number - MIN < 0) {
        return 0;
    }
    //创建一个链表
    LT * l = (LT *)malloc(sizeof(LT));
    init_lt(l, money, number);
    //printf("number:%d, value:%0.2f\n", l->number, l->value);
    work(l, money, number-1);
    return 0;
}

算法改进：上面算法用到的数据结构是链式的，时间复杂度为O(n^2)，如果将堆作为算法的底层结构，那么时间复杂度会降低为O(nlogn)，之后我会写一篇新的文章来讲解优化后的算法。优化算法链接