地址：http://www.cppblog.com/0and1/ | E-Mail：firenight@163.com | QQ：79688942 |
排座位:
思路是扩大空间，减少碰撞几率，测试了一下，碰撞几率很小。
 #include <stdio.h>
#include <time.h>
#include <stdlib.h>
const long num_total = 3000000; //总人数
const long size_group = 10000; //每组人数
const long num_group = int (num_total / size_group); //分组的个数
const long num_left = num_total % size_group; //剩余人数
const long size_arr = int(size_group*1.618); //存放考号的数组大小
long arr[num_group+1][size_arr] = {0};
long find_place(long now_group,long j)
{
while ((j<size_arr) && (arr[now_group][j]))
j++;
if (j==size_arr)
find_place(now_group,0);
else
return j;
}
void assign_group(long begin,long end,long now_group)
{
long j,k;
for (int i=begin;i<=end;i++)
{
j = rand() % size_arr; // 产生 0～size_arr之间的随机数
k = find_place(now_group,j);
arr[now_group][k]=i;
}
}
void assign_seat(void)
{
long begin,end;
for (long i=0;i<num_group;i++)
{
begin = i*size_group+1;
end = (i+1)*size_group;
assign_group(begin,end,i);
}
if (num_left)
{
begin = num_group*size_group+1;
end = num_group*size_group+num_left;
assign_group(begin,end,num_group);
}
}
void main()
{
double duration;
clock_t start,stop;
srand((unsigned)time(NULL));
start = clock();
assign_seat();
stop = clock();
duration = ((double)(stop-start))/CLK_TCK;
printf("Time cost %lfs\nPress Enter to print ",duration);
getchar();
for (long i=0;i<size_arr;i++)
for (long j=0;j<num_group+1;j++)
if (arr[j][i])
printf("%ld\n",arr[j][i]);
getchar();
}目前最快的方法，用的是交换……
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define MAX 3000000
long b[MAX];
long i;
long r;
long tmp;
void fun()
{
for(i=0;i<MAX;i++)
*(b+i)=i;
for(i=MAX;i>0;i--)
{
r=(3000000+rand())%i;
tmp=*(b+r);
*(b+r)=*(b+i);
*(b+i)=tmp;
}
}
void main()
{
double duration;
clock_t start,stop;
srand(time(NULL));
start = clock();
fun();
stop = clock();
duration = ((double)(stop-start))/CLK_TCK;
printf("%lf ",duration);
printf("按任意键打印\n");
getch();
for(i=0;i<MAX;i++)
printf("%d\n",b[i]);
}
|