Re: [問題] 面試遇到的題目
這是我在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)
推
08/19 10:55, , 1F
08/19 10:55, 1F
討論串 (同標題文章)