Utopian

用户名：uq_43094079788

访问量：4670

签　名：

吃得苦中苦，方为人上人

等　　级
排　　名	1550
经　　验	2788
参赛次数	0
文章发表	10
年　　龄	0
在职情况	学生
学　　校	华中科技大学
专　　业

　　自我简介：

TA的其他文章

采药-题解（C++代码——20行以内解决动态规划解法）
浏览：736

你可能喜欢

2^k进制数-题解(C++代码)——深搜版本

　　作者: Utopian　　　　发表时间：2020-04-29 16:23:40 浏览：411　|　评论：0　

原题链接：2^k进制数

# 思路
这个题是排列组合的问题，所以考虑使用排列组合；
这个的思路可以参考我的[CSDN博客](https://blog.csdn.net/qq_43270828/article/details/105274495 "CSDN博客")
基本就是通过一步一步的递归，不断在字符串尾部添加数字。最后在对记录总数total时，需要判断以下：如果这个数字长度等于可能的最大长度，则该数的最高位应该小于根据k分隔的最高位的最大值，比如最高位在二进制中只有1位，那么最高位最大值就是1，除了1以外的数字都不能算在内
# 代码
    #include<iostream>
    #include<cmath>
    using namespace std;
    /*
	*total：记录合法数字总和
	*part：最大可能长度
	*highMax：最高位最大值
	*otherMax：除了最高位之外的最大值
	*/
	int total=0,part,highMax,otherMax;
    void dfs(string s){
        //当数字是最大可能长度时，必须第一位小于等于最高位的最大值才合法
		if(s.length()==part&&(s[0]-'0')<=highMax)   total++;
        //当数字是非最大可能长度时，只要该数字大于两位就是合法的
		if(s.length()<part&&s.length()>=2)          total++;
        if(s.length()<part){
            int last=s[s.length()-1]-'0';
            //可以添加的数字必须严格大于当前数字的最后一位
			for(int i=last+1;i<=otherMax;i++)
                dfs(s+to_string(i));						//递归
        }
		//当该数字达到最大可能长度时，就不再递归
        else    return;
    }
    int main(){
        int k,w;
        cin>>k>>w;
        part=w/k+1;
        highMax=pow(2,w%k)-1;	//最高位的最大值
        otherMax=pow(2,k)-1;	//除了最高位的最大值
        for(int i=1;i<=otherMax;i++) dfs(to_string(i));
        cout<<total<<endl;
        return 0;;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Utopian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

人见人爱A+B （C语言代码）

Tom数（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

点我有惊喜！你懂得！

2^k进制数-题解(C++代码)——深搜版本

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

数列排序（C语言代码）

C语言训练-素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

简单的a+b （C语言代码）

买不到的数目（C语言代码）

C二级辅导-等差数列（C语言代码）

Utopian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

人见人爱A+B （C语言代码）

Tom数 （C语言代码）

【偶数求和】 （C语言代码）记得sum的归零时机

点我有惊喜！你懂得！

2^k进制数-题解(C++代码)——深搜版本

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

数列排序 （C语言代码）

C语言训练-素数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

简单的a+b （C语言代码）

买不到的数目 （C语言代码）

C二级辅导-等差数列 （C语言代码）

Tom数（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

　　评论区

C语言训练-斐波纳契数列（C语言代码）

数列排序（C语言代码）

C语言训练-素数问题（C语言代码）

C语言训练-大、小写问题（C语言代码）

买不到的数目（C语言代码）

C二级辅导-等差数列（C语言代码）