posts - 21,  comments - 9,  trackbacks - 0
此题是一个排列组合加递归的题目。具体解释看代码里面的注释:
  1 #include<stdio.h>  
  2 int x,y,k;  
  3 int array[36][36];  
  4 int result[31];  
  5 //初始化杨辉三角  
  6 void init_array()  
  7 {  
  8     array[0][0] = 1;  
  9     for(int i = 1;i < 31;++i)  
 10     {  
 11         for(int j = 0;j <= i;++j)  
 12         {  
 13             if(j == 0 ||j == i)  
 14             {  
 15                 array[i][j] = 1;  
 16             }  
 17             else  
 18             {  
 19                 array[i][j] = array[i - 1][j - 1] + array[i- 1][j];  
 20             }  
 21         }  
 22     }  
 23 }  
 24   
 25 int get_num_count(int num)  
 26 {  
 27     int total = 0;  
 28     while(num > 0)  
 29     {  
 30         ++total;  
 31         num /= 2;  
 32     }  
 33     return total;  
 34 }  
 35   
 36 //去掉首位的1  
 37 int delete_highest(int num)  
 38 {  
 39     int count = get_num_count(num);  
 40     int total = 1<<(count - 1);  
 41     total = ~total;  
 42     return num & total;  
 43 }  
 44   
 45 //计算跟一个数2进制位数相同的最大值  
 46 int getMin(int total_nums,int one_nums)  
 47 {  
 48     int total = 0;  
 49     if(total_nums < one_nums)  
 50         return -1;  
 51     for(int i = 0;i < one_nums;++i)  
 52     {  
 53         total = total * 2 + 1;  
 54     }  
 55     for(int j = one_nums;j < total_nums;++j)  
 56     {  
 57         total *= 2;  
 58     }  
 59     return total;  
 60 }  
 61 //计算跟一个数2进制位数相同的最小值  
 62 int getMax(int total_nums,int one_nums)  
 63 {  
 64     int total = 1;  
 65     if(total_nums < one_nums)  
 66         return 1000000001;  
 67     for(int i = 0;i < total_nums - one_nums;++i)  
 68     {  
 69         total = total * 2;  
 70     }  
 71     for(int j = 1;j < one_nums;++j)  
 72     {  
 73         total = total * 2 + 1;  
 74     }  
 75     return total;  
 76 }  
 77   
 78   
 79 int recursive_deal(int start,int end,int one_nums)  
 80 {  
 81     if(start > end)  
 82         return 0;  
 83     int start_count = get_num_count(start);  
 84     int end_count = get_num_count(end);  
 85     if(one_nums == 0)  
 86     {  
 87         if(start == 0 || end == 0)  
 88             return 1;  
 89         else  
 90             return 0;  
 91     }  
 92     else  
 93     //如果始末两个数的位数相同的话,就去掉最高位  
 94     if(start_count == end_count)  
 95     {  
 96             return recursive_deal(delete_highest(start),delete_highest(end),one_nums - 1);  
 97     }  
 98     else    //如果始末两个数的位数不同的话,分别计算和起始,终止的的数的2进制位数,中间的数的数量可以通过排列组合计算出来  
 99     {  
100         int total = 0;  
101         for(int i = start_count + 1;i < end_count;++i)  
102         {  
103             total += array[i - 1][one_nums - 1];  
104         }  
105         return total + recursive_deal(start,getMin(start_count,one_nums),one_nums) + recursive_deal(getMax(end_count,one_nums),end,one_nums);  
106     }  
107 }  
108   
109 int main()  
110 {  
111     int tests;  
112     init_array();  
113     scanf("%d",&tests);  
114     while(--tests >= 0)  
115     {  
116         scanf("%d%d%d",&x,&y,&k);  
117         printf("%d\n",recursive_deal(x,y,k));  
118     }  
119     return 0;     
120 }  
posted on 2012-04-07 10:21 崔佳星 阅读(162) 评论(0)  编辑 收藏 引用 所属分类: xoj

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


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜