一道没作出来的面试题求解

Question

// test.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include <vector>
using namespace  std;bool isIn(int value,const vector<int>& vec)
{
for (int i=0; i<vec.size(); i++)
{
if(value == vec[i])
return true;
}
return false;
}void printdata(const vector<int>& vec)
{

for (int i=0; i<vec.size(); i++)
{
if (i!=0)
{
printf(",");
}
printf("%d",vec[i]); }
printf("\n");
}
void getall(int m,int n,const vector<int>& data,int* ptotalnum)
{
if (data.size() == n)
{
(*ptotalnum) ++ ;
printdata(data);
return;
} vector<int> tmp;
for (int i=0; i<m; i++)
{
if (isIn(i,data) )
{
continue;
}
else
{
tmp = data;
tmp.push_back(i);
getall(m,n,tmp,ptotalnum);
}
}

}int main(int argc, char* argv[])
{
vector<int> data;
int totalnum = 0;
getall(33,6,data,&totalnum);
printf("totoalnum:

Answer 1

// test.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include <vector>
using namespace  std;bool isIn(int value,const vector<int>& vec)
{
for (int i=0; i<vec.size(); i++)
{
if(value == vec[i])
return true;
}
return false;
}void printdata(const vector<int>& vec)
{

for (int i=0; i<vec.size(); i++)
{
if (i!=0)
{
printf(",");
}
printf("%d",vec[i]); }
printf("\n");
}
void getall(int m,int n,const vector<int>& data,int* ptotalnum)
{
if (data.size() == n)
{
(*ptotalnum) ++ ;
printdata(data);
return;
} vector<int> tmp;
for (int i=0; i<m; i++)
{
if (isIn(i,data) )
{
continue;
}
else
{
tmp = data;
tmp.push_back(i);
getall(m,n,tmp,ptotalnum);
}
}

}int main(int argc, char* argv[])
{
vector<int> data;
int totalnum = 0;
getall(33,6,data,&totalnum);
printf("totoalnum:

Answer 2

#include <stdlib.h>
#include <stdio.h>
#include <time.h>//随机数产生类
class clRandom
{
protected:
int mRange;            //随机数的值域
int mIndex;            //取出索引
int *mTable;           //随机数表
bool mAutoGenerate;    //是否自动产生随机数public:
//构建函数
clRandom(unsigned int Range, bool AutoGen = false) : mRange(Range),
mTable(NULL),
mIndex(0),
mAutoGenerate(AutoGen)
{
srand((unsigned)time(NULL));   //使用时间产生随机数字
mRange = Range;
mTable = new int [mRange];
Generate();                    //产生随机数
} //析构函数
virtual ~clRandom()
{
if (mTable != NULL)
{
delete [] mTable;
mTable = NULL;
}
mRange = 0;
} //取出随机数
int GetNumber(void)
{
int Number = -1; if (mRange > 0)
{
Number = mTable[mIndex];  //取出随机数
++mIndex;                 //偏移取出随机数的指针
if (mIndex >= mRange)
{
mIndex = 0;
if (mAutoGenerate)    //是否重新产生随机数
{
Generate();       //产生随机数
}
}
} return Number;
} //随机数重整
void Generate(void)
{
int loop, Offset;
//建立连续数字
for (loop = 0; loop < mRange; loop++)
{
mTable[loop] = loop;
}
//依照随机数改变数字的位置
for (loop = 0; loop < mRange; loop++)
{
int Temp;
//使用随机数选择要变换的数字
Offset = (rand() % mRange) + loop;
if (Offset >= mRange)
{
Offset -= mRange;
} //将数字对调
Temp = mTable[loop];
mTable[loop] = mTable[Offset];
mTable[Offset] = Temp;
} mIndex = 0;
}
};int main(int argc, int argv[])
{
clRandom *RandMaker;
int loop, Range = 33; RandMaker = new clRandom(Range); for (loop = 0; loop < 6; loop++)
{
printf(" %d", RandMaker->GetNumber()+1);
} printf("\n");
return 0;
}

Answer 3

#include <iostream>using namespace std;int ForSelect(int Mseed,int Nseed)
{
    int l_iForResult=1;
    for(int i=Mseed;i>=Mseed-Nseed+1;i--)
    {
        l_iForResult*=i;
    }
    return l_iForResult;
}
int main()
{
    int l_iResult=0;
    l_iResult=ForSelect(33,6)/ForSelect(6,6);
    cout << l_iResult<< endl;
    return 0;
}

Answer 4

如果是这样,那么3楼的方法就比较可取了,不过为了加快速度,还可以进一步优化算法,思路如下:
1.在1~33随机取数,得a1;
2.在{1~33}但排除a1的集合内随机取数a2;
3.类似上面,在缩减空间中随机取数,总循环次数<6.

Answer 5

刚看到LZ说的是全排列貌似已知的算法时间复杂度是θ（nn!）

Answer 6

洗牌算法
http://topic.csdn.net/t/20050720/20/4157548.html