＋设为首页 ＋添加到收藏夹
RT,哪位有简单点的算法?
当然,不一定要数字,字符串也可以.
具体要求是什么？这么说太笼统了，说得详细点吧
比如说要生成多少个数字，数字在哪个范围内
hash
选出来后，存入hash 等或stl的 set，map等
先定义一个数组，然后对数组进行赋值，不会重复的值，比如自然数
然后对数组进行乱序排列，这样生成的数字就不会重复
随机生成，然后与存下来的数据比较
#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
bool InNumList(int n, int* srcNumList, int nNums);
int main(int argc, char* argv[])
{
const int n = 5;//要生成的数字串的数目，如生成20个数字，那么n=20;
int i = 0,j = 0;
int randnum = 0;
bool flag = false;//如果为真，则表明这次生成的数已经生成了;
int numlist[n];//存放符合条件的数字
srand((unsigned)time(NULL));
while (i < n)
{
randnum = rand()%n; //生成一个随机数
while (InNumList(randnum,numlist,i))//判断是否有重复，
randnum = rand()%n;//如果有重复，则返回TRUE，继续生成，并判断,直到返回FALSE
numlist[i] = randnum; //程序经过上面的循环，已经生成了一个不重复的数，可以写入buf
i++;//i++，继续生成
}
for (j = 0; j < n; j++) //输入生成的数字
cout << numlist[j] << endl;
return 0;
}
/*
n为刚生成的数字
srcNumList为存放数字的地方
nNums为当前共有多少个数字在srcNumList中
*/
bool InNumList(int n, int* srcNumList, int nNums)
{
for (int j = 0; j < nNums; j++)
if (n == srcNumList[j])
return true;
return false;
}
上面代码基本实现了生成不重复数字，
不会是"猜数字"中生成数字的算法吧.......
随即生成再比较每次生成的时间不同
生成数组乱排序的生成时间是一样的
1，2，3，4，5，...自然数么，肯定不会重复，算法：
int nNetuel[1000];
for (int i = 1; i <= 1000; i++)
nNetuel[i-1] = i;
得到1000个自然数序列。
//找到了 里面是有计算过程的
打造最快的Hash表(暴雪用的MPQ文件)
最近在网上看到篇文章，一起拜一拜暴雪
先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。
最合适的算法自然是使用HashTable，先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法
unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
while(*key != 0)
{
ch = toupper(*key++);
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
Blizzard的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}
看到此，我想大家都在想一个很严重的问题："如果两个字符串在哈希表中对应的位置相同怎么办？",毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。
事情到此似乎有了完美的结局，如果是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。
中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。
现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法：
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos + 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
return -1; //Error value
}
1. 计算出字符串的三个哈希值(一个用来确定位置，另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗？如果为空，则肯定该字符串不存在，返回
4. 如果存在，则检查其他两个哈希值是否也匹配，如果匹配，则表示找到了该字符串，返回
5. 移到下一个位置，如果已经越界，则表示没有找到，返回
6. 看看是不是又回到了原来的位置，如果是，则返回没找到
7. 回到3
怎么样，很简单的算法吧，但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法.
