- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 38556
- 在线时间
- 小时
|
楼主 |
发表于 2018-3-23 15:11:20
|
显示全部楼层
最新的代码
- #include <vector>
- #include <set>
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <rdrand.h>
- #include <time.h>
- typedef unsigned int dtype;
- typedef std::vector<dtype> DataState;
- typedef std::set<dtype> UnionState;
- #ifndef K
- #define K 10
- #endif
- #define COUNT 100000
- #if K==10
- #define HK 5
- #define UPBOUND 30
- #define REPLACE_NUMS 5
- #define LARGE_REPLACE_NUMS 8
- #endif
- #if K==11
- #define HK 5
- #define UPBOUND 60
- #define REPLACE_NUMS 5
- #define LARGE_REPLACE_NUMS 10
- #endif
- #if K==12
- #define HK 6
- #define UPBOUND 70
- #define REPLACE_NUMS 5
- #define LARGE_REPLACE_NUMS 11
- #endif
- #if K==13
- #define HK 6
- #define UPBOUND 100
- #define REPLACE_NUMS 4
- #define LARGE_REPLACE_NUMS 12
- #endif
- #if K==14
- #define HK 7
- #define UPBOUND 200
- #define REPLACE_NUMS 6
- #define LARGE_REPLACE_NUMS 13
- #endif
- #if K==15
- #define HK 7
- #define UPBOUND 350
- #define REPLACE_NUMS 7
- #define LARGE_REPLACE_NUMS 15
- #endif
- #if K==16
- #define HK 7
- #define UPBOUND 400
- #define REPLACE_NUMS 7
- #define LARGE_REPLACE_NUMS 15
- #endif
- #if K==17
- #define HK 8
- #define UPBOUND 400
- #define REPLACE_NUMS 7
- #define LARGE_REPLACE_NUMS 15
- #endif
- #if K==28
- #define HK 13
- #define UPBOUND 2000
- #define REPLACE_NUMS 7
- #define LARGE_REPLACE_NUMS 9
- #endif
- #if K==29
- #define HK 13
- #define UPBOUND 2000
- #define REPLACE_NUMS 7
- #define LARGE_REPLACE_NUMS 9
- #endif
- #if K==30
- #define HK 13
- #define UPBOUND 2000
- #define REPLACE_NUMS 8
- #define LARGE_REPLACE_NUMS 16
- #endif
- #if K==31
- #define HK 13
- #define UPBOUND 2000
- #define REPLACE_NUMS 8
- #define LARGE_REPLACE_NUMS 16
- #endif
- #if K==32
- #define HK 14
- #define UPBOUND 2000
- #define REPLACE_NUMS 8
- #define LARGE_REPLACE_NUMS 16
- #endif
- #define UB UPBOUND
- #define MIN_EDGES (REPLACE_NUMS+LARGE_REPLACE_NUMS)
- unsigned gen_rand_edge()
- {
- unsigned d = 0;
- unsigned rd[K];
- int i;
- rdrand_get_n_32(K,rd);
- for(i=0;i<K;i++){
- if(rd[i]<1288490189){
- d|=1<<i;
- }
- }
- return d;
- }
- long update_bits(long v, long bits)
- {
- int i;
- unsigned rd[K];
- rdrand_get_n_32(K,rd);
- for(i=bits+1;i<K;i++){
- if(rd[i]<1288490189){
- v|=1<<i;
- }
- }
- return v;
- }
- int should_we_change()
- {
- unsigned d=0;
- rdrand_get_n_32(1,&d);
- d%=10;
- if(d==0)return 1;
- return 0;
- }
- UnionState tus;
- DataState ds;
- DataState best_result;
- #define WORD_OF(x) ((x)>>5)
- #define INDEX_IN_WORD(x) ((x)&31)
- #define IS_SET(mask,x) (mask[WORD_OF(x)]&(1<<INDEX_IN_WORD(x)))
- #define SET(mask,x) (mask[WORD_OF(x)]|=1<<INDEX_IN_WORD(x))
- #define CLEAR(mask,x) (mask[WORD_OF(x)]&=~(1<<INDEX_IN_WORD(x)))
- void init()
- {
- ds.clear();
- }
- int bitcount(dtype d);
- int test_add(dtype d)
- {
- UnionState ls;
- if(bitcount(d)>HK)return -1;
- #ifdef STRICT
- if(tus.find(d)!=tus.end()){
- return -1;
- }
- ls.insert(d);
- #endif
- int i;
- for(i=0;i<ds.size();++i){
- if(ds[i]==d)return -1;
- dtype u=d|ds[i];
- if(tus.find(u)!=tus.end()){
- return -1;
- }
- if(ls.find(u)!=ls.end()){
- return -1;
- }
- ls.insert(u);
- }
- return 0;
- }
- int bitcount(dtype d){
- int i,b=0;
- for(i=0;i<K;i++){
- if(d&(1<<i))b++;
- }
- return b;
- }
- void do_add(dtype d){
- int i;
- #ifdef STRICT
- tus.insert(d);
- #endif
- for(i=0;i<ds.size();++i){
- dtype u=d|ds[i];
- tus.insert(u);
- }
- ds.push_back(d);
- }
- void pop()
- {
- int i;
- dtype d=ds.back();
- ds.pop_back();
- #ifdef STRICT
- tus.erase(d);
- #endif
- for(i=0;i<ds.size();++i){
- dtype u=d|ds[i];
- tus.erase(u);
- }
- }
- int cds;
- unsigned long long cdc;
- unsigned long long cdi;
- void dumpg(const DataState& data)
- {
- int i;
- printf("[%d]",(int)data.size());
- for(i=0;i<data.size();i++){
- printf("%x ",data[i]);
- }
- printf("\n");
- fflush(stdout);
- }
- unsigned getrande(int e)
- {
- unsigned d=0;
- rdrand_get_n_32(1,&d);
- d%=e;
- return d;
- }
- void rsearch(int s)
- {
- int i;
- while(1){
- for(i=0;i<100;i++){
- unsigned d = gen_rand_edge();
- if(test_add(d)==0){
- do_add(d);
- break;
- }
- }
- if(i==100){
- return;
- }
- }
- }
- int search(int c, clock_t quit_time)
- {
- int i,j;
- if(ds.size()>best_result.size()){
- best_result = ds;
- dumpg(best_result);
- return 1;
- }
- if(clock()>quit_time)return -1;
-
- for(i=1;i<c;++i){
- unsigned d = gen_rand_edge();
- if(test_add(d)==0){
- do_add(d);
- int r = search(2*c, quit_time);
- if(r!=0){
- pop();
- return r;
- }
- pop();
- }
- }
- return 0;
- }
- int largest_bit(long v)
- {
- int i;
- for(i=31;i>=0;i--){
- if(v&(1<<i))return i;
- }
- return -1;
- }
- int count = 0;
- #if K==28
- #define MIN_TIME (5*CLOCKS_PER_SEC)
- #else
- #define MIN_TIME (30*CLOCKS_PER_SEC)
- #endif
- int cur_time_interval=MIN_TIME;
- int main(int argc, const char *argv[])
- {
- int i;
- int orbits[UPBOUND];
- if(argc>1){
- init();
- int bits=0;
- for(i=1;i<argc;i++){
- char *endp=NULL;
- long v=strtol(argv[i],&endp, 16);
- int lbits=largest_bit(v);
- if(lbits>bits)bits=lbits;
- }
- for(i=1;i<argc;i++){
- char *endp=NULL;
- long v=strtol(argv[i],&endp, 16);
- v=update_bits(v,bits);
- if(test_add(v)==0){
- do_add(v);
- }else{
- printf("invalid input %s\n",argv[i]);
- return -1;
- }
- }
- }else{
- do{
- init();
- rsearch(1);
- }while(ds.size()<MIN_EDGES);
- }
- fprintf(stderr,"Init state:\n");
- dumpg(ds);
- for(i=0;i<ds.size();i++){
- best_result.push_back(ds[i]);
- }
- do{
- int replace_num = REPLACE_NUMS;
- for(i=0;i<best_result.size();i++)orbits[i]=0;
- for(i=0;i<replace_num;i++)orbits[i]=1;
- for(i=0;i<replace_num;i++){
- int j=getrande(best_result.size());
- int t=orbits[i];
- orbits[i]=orbits[j];
- orbits[j]=t;
- }
- init();
- for(i=0;i<best_result.size();i++){
- if(orbits[i]==0){
- do_add(best_result[i]);
- }
- }
- if(search(200, clock()+cur_time_interval)==1){count=0;cur_time_interval = MIN_TIME;}else{cur_time_interval+=MIN_TIME;}
- }while(1);
- return 0;
- }
|
|
楼主: mathe
IP卡
狗仔卡
显身卡
发表于 2018-3-23 15:22:16
发表于 2018-3-23 14:50:43
