基础算法题——带分数（全排列，工具库）

拼搏现实的明天。 2023-07-18 03:19 35阅读 0赞

前言  
这道题理解起来不难，但是要找到一个合适的方法对题目进行优化，就会相对麻烦些。  
蓝桥杯的题，真的到处都是坑的感觉。。。

### 带分数题目 ###

资源限制  
时间限制：1.0s 内存限制：256.0MB  
问题描述  
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。  
还可以表示为：100 = 82 + 3546 / 197。  
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。  
类似这样的带分数，100 有 11 种表示法。  
输入格式  
从标准输入读入一个正整数N (N<1000\*1000)  
输出格式  
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。  
注意：不要求输出每个表示，只统计有多少表示法！  
样例输入1  
100  
样例输出1  
11  
样例输入2  
105  
样例输出2  
6

--------------------

#### 题目分析 ####

①、带分数中，数字1~9分别出现且只出现一次（不包含0）。  
②、100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

#### 解题思路 ####

①：如何实现在带分数中，数字1~9分别出现且只出现一次。我们可以考虑全排列，将每种排列都来一遍（感觉挺麻烦的，如果有更好的方法欢迎留言讨论）。  
②：在例子中 100 = 3 + 69258 / 714，“3 + 69258 / 714”部分要符合数字1~9分别出现且只出现一次，这时可以用到我们字符串截取。拿上面的例子说，排列为369258714，我们截取了字符串3、字符串69258、字符串714，然后将三个字符串转换为int类型变量，看看是否符合条件（100 = 3 + 69258 / 714）符合则记录下来。

#### 实用工具功能及使用 ####

##### 实现全排列：next\_permutation(s.begin(), s.end())； #####

在C++中，在字符串要**有序**的前提下，我们能使用现成的函数完成字符串的全排列。例如：**string s=“123456789”;**，字符串s已经有序。通过 *while(next\_permutation(s.begin(), s.end()));* 不断将s进行全排序，当s的全排序全部排完后，跳出循环。可能你会觉得这个有什么用？让我们带着这个问题看看代码设计吧！

string s="123456789";
    do
    { 
    	....
    }
    while(next_permutation(s.begin(), s.end()));

我们这里用do-while的循环体，保证s每进行一次全排列就会先进行do包含的语句。

###### 实现字符串截取：string a = s.substr(i,len); ######

在s字符串中，从下标为i的位置，向右截取len长度的字符串，得到a字符串。

###### 实现字符串转换为int类型变量：int a = atoi(s.c\_str); ######

将字符串s转换为int类型变量a。

--------------------

#### 代码实现 ####

##### 代码一 #####

通过我们的解题思路和工具结合，我们可以得到以下代码一。

//全排列 next_permutation(s.begin(),s.end())
    #include<bits/stdc++.h>
    #include<time.h>
    using namespace std;
    #define ll long long
    ll ans=0;
    
    int main()
    { 
    // clock_t start, finish;
    // start = clock();
    	int n;
    	string s="123456789";
    // sort(s,s+9);
    	cin>>n;
    	
    	do
    	{ 
    		for(int i=1; i<=7; i++)
    		{ 
    			string a=s.substr(0,i);
    			int inta=atoi(a.c_str());
    			if(inta>=n) break;
    			
    			for(int j=1; j<=8-i; j++)
    			{ 
    				string b=s.substr(i, j);
    				int intb=atoi(b.c_str());
    				string c=s.substr(j+i);
    				int intc=atoi(c.c_str());
    				if(intb%intc==0&&inta+intb/intc==n)
    				ans++;
    			}
    		}
    	}
    	//使用next_permutation前要先排序 
    	while(next_permutation(s.begin(), s.end()));
    	cout<<ans;
    // finish = clock();
    // double _time = (double)(finish - start) / CLOCKS_PER_SEC;
    // printf("\ntime:%llf", _time);
    	return 0;
    }

好啦，恭喜你答对了题目一半，为什么是一半呢？因为如果你拿去评测的话， 你会发现：运行超时！  
下面是代码二在**N=100**条件下的运行时间time （单位秒）  
![代码一运行时间][20200426100749755.png]  
原因：**substr函数返回的是值(而不是引用或指针) 在多次调用中传递了大量对象(而不是引用或指针) 导致了耗时多**。  
在代码里，substr函数被放在内层循环中，被调用的次数很多，这样的对程序运行总时间的影响就增大了，拖慢了程序运行速度。

##### 代码二（手写截取字符串，引用字符串s） #####

#include<bits/stdc++.h>
    #include<time.h>
    using namespace std;
    #define ll long long
    ll ans=0;
    
    int parse(string &s, int a, int b)//字符串转换为int类型 
    { 
    	int temp=0;
    	for(int i=a; i<b; i++)
    	{ 
    		temp+=s[i]-'0';
    		if(i<b-1)
    			temp*=10;
    	}
    	return temp;
    }
    
    int main()
    { 
    // clock_t start, finish;
    // start = clock();
    	int N;
    	string s="123456789";
    // sort(s,s+9);
    	cin>>N; 
    	
    	do
    	{ // 1234567+8/9 
    		for(int i=1; i<=7; i++)			//分割第一个数据长度 
    		{ 
    			int inta = parse(s, 0, i);
    			if(inta>N) break;
    			//1+2345678/9
    			//12+345678/9 
    			//1+2/3456789
    			for(int j=1; j<=8-i; j++)		//分割第二个数据长度
    			{ 
    				int intb=parse(s, i, j+i);
    				int intc=parse(s, j+i, s.length());//分割第三个数据
    				if(intb%intc==0&&inta+intb/intc==N)
    				{ 
    // cout<<inta<<"+"<<intb<<"/"<<intc<<endl;
    					ans++;
    				}
    			}
    		} 
    	}
    	while(next_permutation(s.begin(), s.end()));
    	cout<<ans;
    // finish = clock();
    // double _time = (double)(finish - start) / CLOCKS_PER_SEC;
    // printf("\ntime:%llf", _time);
    	return 0;
    }

优化：截取字符串函数传参采用传指针或引用(即在parse 的string参数右侧加一个&)。  
下面是代码二在**N=100**条件下的运行时间time （单位秒）  
![代码二运行结果][20200426101955382.png]  
时间上满足1s内，可以通过评测。  
下面还能够再通过优化算法的方式，进一步缩短运行时间。

##### 代码三（算法优化） #####

#include<bits/stdc++.h>
    #include<time.h>
    using namespace std;
    #define ll long long
    ll ans=0;
    
    int parse(string& s, int a, int b)//字符串转换为int类型 
    { 
    	int temp=0;
    	for(int i=a; i<b; i++)
    	{ 
    		temp+=s[i]-'0';
    		if(i<b-1)
    			temp*=10;
    	}
    	return temp;
    }
    
    int main()
    { 
    // clock_t start, finish;
    // start = clock();
    	int N;
    	string s="123456789";
    // sort(s,s+9);
    // N=100;
    	cin>>N;
    	
    	do
    	{ 
    		for(int i=1; i<=7; i++)			
    		{ 
    			int inta = parse(s, 0, i);
    			if(inta>N) break;
    			//1+2345678/9
    			//12+345678/9 
    			//1+2/3456789
    			for(int j=1; j<=8-i; j++)	
    			{ 
    				if(j<9-i-j) continue;	//排除多余情况
    				int intb=parse(s, i, j+i);
    				int intc=parse(s, j+i, s.length());
    				if(intb%intc==0&&inta+intb/intc==N)
    				{ 
    // cout<<inta<<"+"<<intb<<"/"<<intc<<endl;
    					ans++;
    				}
    			}
    		} 
    	}
    	while(next_permutation(s.begin(), s.end()));
    	cout<<ans;
    	
    // finish = clock();
    // double _time = (double)(finish - start) / CLOCKS_PER_SEC;
    // printf("\ntime:%llf", _time);
    	return 0;
    }

优化：排除多余判断情况。  
下面是代码三在**N=100**条件下的运行时间time（单位秒）  
![运行时间][2020042609502771.png]

#### 总结 ####

这道题思路固然重要，但是优化也很重要。  
在蓝桥杯的比赛中，都是提交代码，我们不能都提前判断我们的代码是否能够通过所有评测数据，所以要尽量将时间复杂度降到最小。

**感谢评论区的朋友，对我的文章提出指正√**  
希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[20200426100749755.png]: /images/20230528/08a802d368ef4e78b1cf56d52e9f8635.png
[20200426101955382.png]: /images/20230528/f1de2c2ac9e5457fafeccc840cac5797.png
[2020042609502771.png]: /images/20230528/6c8d5af31487442d95b8337226873ec6.png