2^k进制数——基于C排序解决

解题思路:

1:对于要考虑到的从高位开始一直往低位走，右边严格大于左边要如何去处理

   解：实际上，这个地方有一个坑，去诱惑你处理这个数位之间的大小关系排序，可实际上并不需要处理，因为每个数位上的数必然时不重复的，那么我就默认者一组数它就是严格排序的，比如说原来的一组数时321（不符合要求），但我就可以认为它是123（符合要求），发现了吗，就是说，重点是放入的那一组数，它的顺序顺序并不重要。

2：要从k和w 中分析出怎样的信息？（k<w）

     解：2^k表示的是进制，自然K就是将此进制数化为二进制数时的位数，那么我们就可以通过w/k,得到最小的r的位数；通过w%k得到最高位的取值范围（当w可以除尽k时，最高位的取值范围自然就是1~pow(2,k)-1）了。

3：下一步如何去分析？（敲黑板）

A:以题中的k=3,w=7为例子分析：

B:其他例子：w%k==0的情况 和 位数更多的情况（此时心里默认最高位为0）

注意事项:    要考虑到一个细节问题：当给出的位数限制w/k甚至大于 “最大的进制数-1” 时，要将w缩小至与其等值 ，例如

参考代码:

#include

#include

long woc(int m,int n)//进行无序排序 

{

long sum=1;

for(int i=0;i<n;i++)

{

sum*=(m-i);

}

for(int i=2;i<=n;i++)

{

sum/=i;

}

return sum;

}

int main()

{

int k,w,mi,ma,index,x;//注意index用于确定最高位的取值范围

long sum=0;

scanf("%d%d",&k,&w);

mi=w/k;

ma=w%k;

x=pow(2,k);

if((x-1)<mi)//当给出的位数限制w/k甚至大于 最大的进制数-1 时，要将w缩小至与其等值 ,例如

{

mi=x-1;

}

if(ma!=0) //除不尽 

{

if(ma==1)

{

index=1;

}

else

{

index=1;

for(int i=1;i<ma;i++)

{

index*=2;

}

index+=1;

}

sum=woc(x-1,mi+1)-woc(x-1-index,mi+1);

}

for(int i=2;i<=mi;i++)//除得尽时或者是处理高位以外排列 

{

sum+=woc(x-1,i);

}

    printf("%ld\n",sum);

return 0;

}