昴樂樂

用户名：2486205137

访问量：3122

签　名：

等　　级
排　　名	11884
经　　验	1003
参赛次数	0
文章发表	4
年　　龄	20
在职情况	学生
学　　校	huse
专　　业	软件工程

　　自我简介：

TA的其他文章

回文数字（枚举，数的分解）
浏览：157

蓝桥杯2015年第六届真题-穿越雷区(BFS, 代码易懂)
浏览：137

蓝桥杯2013年第四届真题-带分数（递归、全排列、C++代码）
浏览：720

你可能喜欢

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

蓝桥杯2013年第四届真题-带分数（递归、全排列、C++代码）

　　作者: 昴樂樂　　　　发表时间：2022-04-05 12:50:49 浏览：720　|　评论：1　

原题链接：蓝桥杯2013年第四届真题-带分数

### 步骤：
1. 对1~9数字进行全排列。
2. 对每个全排列依次划分。
3. 每次划分将当前全排列分成三段，划分后从左到右各个段分别表示整数、分子、分母。因为只要划分成三段，所以要进行两次分割，即对每个全排列的分割需要两次嵌套循环。
4. 判断zs+fz/fm==num 和 fz%fm==0是否成立，即整数+分数是否为输入的值，该分数是否可化成整数。
### 递归求全排列：
![分治法求全排列](/image_editor_upload/20220405124748_47929.png "分治法求全排列")
### 代码：

```cpp
#include<iostream>
using namespace std;

int num, ans;

int toNum(int a[], int l, int r){ // [l,r] 
	int result = 0, temp = 1;
	while(l<=r){
		result = result+a[r]*temp;
		temp *= 10;
		--r;
	}
	return result;
}

void swap(int& a, int &b){
	int temp = a;
	a = b;
	b = temp;
}

void judge(int a[]){
	for(int i=1; i<=9-2; i++){ // [1,7]
		for(int j=i+1; j<=9-1; j++){
			int zs = toNum(a, 1, i);
			int fz = toNum(a, i+1, j);
			int fm = toNum(a, j+1, 9);
				if(zs+fz/fm==num && fz%fm==0){ // fz&&fm==0是因为整数+小数不可能为整数 
					//cout << zs << '+' << fz << '/' << fm << endl;
					++ans;
				}
		}
	}
}

void perm(int a[], int k, int m){
	if(k==m){
		judge(a);
		/*
		for(int i=0; i<=m; i++){
			cout << a[i];
		}cout << endl;
		*/
	}
	else{
		for(int i=k; i<=m; i++){
			swap(a[k], a[i]);
			perm(a, k+1, m);
			swap(a[k], a[i]);
		}
	}	
}

int main(){
	int a[10] = {0,1,2,3,4,5,6,7,8,9};// 第一个0是为了使数组表示方便 
	cin >> num;
	perm(a, 1, 9);
	cout << ans << endl;
	
	return 0;
} 
```

0.0分

4 人评分

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

　　评论区

安河桥北i

太强了

2022-04-18 20:11:51

昴樂樂

TA的其他文章

你可能喜欢

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

C二级辅导-进制转换（C语言代码）

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

C语言训练-字符串正反连接（C语言代码）

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

蓝桥杯2013年第四届真题-带分数（递归、全排列、C++代码）

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

大小写转换（C语言代码）

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

本人酷爱递归实现很多问题，这里也是

DNA （C语言描述，数据结构）

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

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

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

昴樂樂

TA的其他文章

你可能喜欢

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

C二级辅导-进制转换 （C语言代码）

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

C语言训练-字符串正反连接 （C语言代码）

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

蓝桥杯2013年第四届真题-带分数（递归、全排列、C++代码）

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

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

大小写转换 （C语言代码）

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

本人酷爱递归实现很多问题，这里也是

DNA （C语言描述，数据结构）

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

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

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

C二级辅导-进制转换（C语言代码）

C语言训练-字符串正反连接（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

大小写转换（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long