1110: 2^k进制数(C语言代码) 递归回溯

解题思路:

这道题用回溯思想比较好理解，因为每一位都比右边一位小，所以从左到右逐位确定比较方便

确定每一位数都要递归一次，每一个递归里都有一个循环，从本位的最小值（前一位的值加一）循环到最大值

循环内继续向下递归，直至递归终点（确定最右一位之后），返回 1 即向上回溯

详细的看代码注释吧

参考代码:

#include <stdio.h>
#include <math.h>

int getCount(int min, int max, int t) {     //min是前一位的值，max为最大值，t表示后面还有t位数
    if (t == 0) {            //递归终点，到达最后一位
        return 1;            //返回 1
    }
    int cnt = 0;
    for (int i = min + 1; i < max; i++) {   //这一位的值从前一位的值加一循环到最大（不等于）
        cnt += getCount(i, max, t - 1);     //递归下一位
    }
    return cnt;
}

int main(){
    int k, w;
    scanf("%d %d", &k, &w);     //输入k, w
    int max = pow(2, k);        //每一位最大值为 2 的 k 次方

    int t = (w - 1) / k;        //t表示第一位（最左）后面还有 t 位，t = (w - 1) / k;

    int n = pow(2, w % k);      //n表示第一位的最大值
    if (n == 1)     n = max;    // w % k 可能为 0，此时令 n = max

    int cnt = 0;
    for (int i = 1; i < n; i++) {       //循环第一位从1到n（不等于）
        cnt += getCount(i, max, t);     //递归下一位，本位为 i，最大为 max，后面还有 t 位
    }

    while (t > 1) {                     //循环计算无最左位时的个数，（循环条件：剩余位数大于1）
        cnt += getCount(0, max, t);     //递归，假设本位为0
        t--;                            //t--继续循环
    }

    printf("%d\n", cnt);
}