作者sunneo (艾斯寇德)
站内Programming
标题Re: [问题] 面试遇到的题目
时间Wed Aug 13 10:25:23 2008
这是我在ANSI C下写的版本。
刚刚的back保留0是在unsigned的情况，拿来当作error code。
不过java没有unsigned，所以就大概如下吧。
假设以下式子已经写好，且放在utilities.c，并且有utilities.h的话。
-----------------------------------------------------------------------------
float uniform01(){
union{
float m_float;
int m_int;
}f_union;
f_union.m_float = 1.0f;
f_union.m_int|= (rand()<<7)|(rand()&0xef);
return f_union.m_float-1.0f;
}
float uniform(float a,float b){
return a < b ? (a + (b-a)*uniform01()): b + (a-b)*uniform01();
}
void swap(int* a,int* b){
int t = *a;
*a = *b;
*b = t;
}
-----------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "utilities.h"
void take_seat(int cnt){
int back;
int *a = (int*)malloc(sizeof(int)*(cnt));
for(back = 0; back<cnt; ++back) a[ back ] = back+1;
back = cnt-1;
while(back >= 0){
int r = (int)uniform(0,back);
printf("%-11d:back = %-11d \n",a[ r ],back);
swap(&a[ r ],&a[ back ]);
--back;
}
free(a);
}
下面是把token跟back包装的版本
#include <stdio.h>
#include <stdlib.h>
#include "utilities.h"
typedef struct{
int *a;
int back;
}Token;
Token* token_create(int cnt){
Token* t = (Token*)malloc(sizeof(Token));
t->a = (int*)malloc(sizeof(int)* cnt);
for(t->back = 0; t->back< cnt; ++t->back)
t->a[ t->back ] = t->back+1;
t->back = cnt-1;
return t;
}
int token_take(Token* t){
int r;
int ret;
if(t->back < 0) return 0;
r = uniform(0,t->back);
ret = t->a[ r ];
swap(&t->a[ r ],&t->a[ t->back ]);
--t->back;
return ret;
}
void token_delete(Token* t){
free(t->a);
free(t);
}
int main(n){
int i;
Token *token = token_create(15);
while(i = token_take(token))
printf("%d \n",i);
token_delete(token);
system("pause");
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.225.9
※ 编辑: sunneo 来自: 61.227.225.9 (08/13 13:21)
1F：推 joetsai:谢谢 好久没看C的程式了 要先复习 =.="122.125.234.171 08/19 10:55