常见算法

95 阅读 0 评论 63 点赞

我是靠谱客的博主活力网络，最近开发中收集的这篇文章主要介绍常见算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

游戏服务器存在一些常见的算法，很多功能都能共用，例如用于字符串切割的，用于随机数生成的等等。可以封装成库，例如命名为mylib.h，里面都是定义一些static函数，方便调用，常见算法有:

1. 随机数

static long my_rand(long min_num, long max_num)
{
   if (min_num == max_num)
       return min_num;
   else if (min_num > max_num)
       return max_num + (long)(((double)min_num - (double)max_num + 1.0) * rand() / (RAND_MAX + 1.0));
   else
       return min_num + (long)(((double)max_num - (double)min_num + 1.0) * rand() / (RAND_MAX + 1.0));
}

int main()
{
srand((unsigned)time(NULL));

   while (1) {
       int a = my_rand(10, 100);
       std::cout << a << " ";
   }
   return 0;
}

在多线程环境下还可以使用rand_r函数。

2.根据vector权重选中一个数据

static int select_by_vec(std::vector<int> vec)
{
int tmp = my_rand(1, 100);
int cnt = 0;

   for (int i = 0; i < vec.size(); ++i) {
       if (tmp > cnt && tmp <= vec[i] + cnt) {
           return i;
       }
       cnt += vec[i];
   }

return -1;
}

int main()
{
   srand((unsigned)time(NULL));
   std::vector<int> vec{20,20,60}; //加起来必须为100
   while (1) {
       int a = select_by_vec(vec); //返回vec的下标
       std::cout << a << " ";
   }
   return 0;
}

3.根据map权重选中一个数据

static int select_by_map(std::map<int, int>& tmpmap)
{
   if (tmpmap.size() == 0) {
       return -1;
   }

   int all_weight = 0;
   for (auto& iter : tmpmap) {
       all_weight += iter.second;
   }

   if (!all_weight) {
       return -1;
   }

int tmp = my_rand(1, all_weight);
int cnt = 0;

   for (auto& iter : tmpmap) {
       if (tmp > cnt && tmp <= iter.second + cnt) {
           return iter.first;
       }
       cnt += iter.second;
   }

return -1;
}

int main()
{
srand((unsigned)time(NULL));

   std::map<int, int> map;
   map.insert(std::make_pair(1, 20));
   map.insert(std::make_pair(2, 20));
   map.insert(std::make_pair(3, 60));

   while (1) {
       int a = select_by_map(map); //返回vec的下标
       std::cout << a << " ";
   }
   return 0;
}

4.根据分数概率来选择

static bool select_by_fraction(const unsigned int up_num, const unsigned int down_num)
{
   if (down_num < 1) return false;
   if (up_num < 1) return false;
   if (up_num > down_num - 1) return true;

int tmp = 1 + (unsigned int)((double)down_num * rand() / (RAND_MAX + 1.0));

return tmp <= up_num;
}

int main()
{
srand((unsigned)time(NULL));

   while (1) {
       int a = select_by_fraction(9, 10); //返回vec的下标
       std::cout << a << " ";
   }
   return 0;
}

5.分割字符串

template <typename T>
inline void string_tok(T& ret, std::string const& in_str, const char* const deli = " tn", const int d = 0) //d用来控制分割几次，0表示完全分割
{
   const std::string::size_type len = in_str.length();
   std::string::size_type i = 0;
   int cnt = 0;

   while (i < len) {

       i = in_str.find_first_not_of(deli, i);
       if (i == std::string::npos)
           return;

std::string::size_type j = in_str.find_first_of(deli, i);

++cnt;

       if (j == std::string::npos || (d > 0 && cnt > d)) {
           ret.push_back(in_str.substr(i));
           return;
       }
       else {
           ret.push_back(in_str.substr(i, j-i));
       }

i = j + 1;
}
}

int main()
{
std::vector<std::string> vec;
std::string str = "123:456:789";

string_tok(vec, str, ":");

   for (auto& iter : vec) {
       std::cout << iter << std::endl;
   }

return 0;
}

参考资料:

http://www.voidcn.com/article/p-eeuvfllz-bpz.html