此题是一个排列组合加递归的题目。具体解释看代码里面的注释:
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
崔佳星 阅读(160)
评论(0) 编辑 收藏 引用 所属分类:
xoj