Craze.0&1

软件是计算机的灵魂-而我是灵魂的设计师

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  7 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿(1)

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜


 地址: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]);
}
posted on 2007-04-14 21:26 Craze.0&1 阅读(202) 评论(0)  编辑 收藏 引用 所属分类: 学习笔记

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理