地址:http://www.cppblog.com/0and1/ | E-Mail:firenight@163.com | QQ:79688942 |
排座位: 思路是扩大空间,减少碰撞几率,测试了一下,碰撞几率很小。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const long num_total = 3000000; //总人数
const long size_group = 10000; //每组人数
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define MAX 3000000
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long b[MAX];
long i;
long r;
long tmp;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double duration;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
clock_t start,stop;
srand(time(NULL));
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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]);
}
|