【递归】带分数
题目来源
带分数
，这道题目比较有意思
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
自己也尝试去实现，但是自己写的代码时间复杂度太高，因此这里黏贴了自己的代码 和 别人的代码，以供对比理解和学习。
一、自己写的代码（相当相当耗时~~）
想法：
-
从小于
num
的整数集合中选一个数作为整数
k
，并判断是否出现重复数字。 -
将9位数字中未出现的数字拼接成一个字符串，利用全排列和字符串截断，校验分数是否等于
num - k
实现代码：
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include<string>
#define N 9
using namespace std;
//查找带分数（不包含0）
int found(int num){
int i;
int count = 0; //满足条件的带分数个数
for(i = 0; i < num; ++i){
if(i % 10 == 0){ //整数部分含0，去除
continue;
}
int visited[10] = {0};
int flag = 1;
int temp = i;
do{
if(visited[temp % 10] == 1){ //整数部分含重复数字，去除
flag = 0;
break;
}
visited[temp % 10] = 1;
}while(temp / 10);
//整数部分i满足要求
if(flag){
string str;
int j;
for(j = 1; j < 10; ++j){
if(visited[j] == 0){
str += (j + '0');
}
}
int left = num -i; //num - 整数
//全排列 + 分数校验
do {
// cout << str << endl;
int k;
for(k = str.length() / 2 - 1; k < str.length(); ++k){
long p1 = atol(str.substr(0,k).c_str());
long p2 = atol(str.substr(k, str.length()).c_str());
cout << p1 << " / " << p2 << endl;
if(p1 / p2 == left){
count++;
}
}
} while (next_permutation(str.begin(), str.end()));
cout << endl;
}
}
return count;
}
int main(int argc, char const *argv[])
{
int num = 100;
int count = found(num); // 分数校验
cout << count << endl;
}
无奈时间复杂度太高：
-
如果
num=100
，需要遍历100次查找整数部分； - 分数部分最好情况下则需要每次对7位字符进行全排列；
-
全排列后每次得到的字符串又需要通过截断来计算分子和分母，再进行
100-k
的数值校验。
所以整趟下来，遍历次数为
100 * 7! * (7 - 2) = 2520000
。对于
n=100
，
10
0
3
∼
2520000
100^3 \sim 2520000
1
0
0
3
∼
2
5
2
0
0
0
0
，因此时间复杂度为
O
(
n
3
)
O(n^3)
O
(
n
3
)
。
接下来看看别人写的代码，自行分析解题思路，理解是怎样毫秒级求得解的。
二、别人的代码1
#include<iostream>
#include <cstring>
using namespace std;
int a[10] = {0};
int Division(int m)
{
int t;
while (m)
{
t = m % 10;
if (t == 0)
{
return 0;
}
a[t]++;
m = m / 10;
}
return 1;
}
int main()
{
int i, k, j;
int number, ans = 0, flag;
cin >> number;
for (i = 1; i < number; i++)
{
for (j = 1; j <= 4938; j++)
{
memset(a, 0, sizeof(a));
k = (number - i) * j;
if (Division(i) && Division(j) && Division(k))
{
flag = 1;
for (int x = 1; x < 10; x++)
{
if (a[x] != 1)
{
flag = 0;
break;
}
}
if (flag == 1)
ans++;
}
}
}
cout << ans;
return 0;
}
三、别人的代码2
#include<iostream>
#include <cstring>
using namespace std;
int visit[10] = {0};
int s[10];
int ans = 0;
int N;
void found(int s[])
{
int x, y, z;
for (int i = 1; i < 9; i++)
{
for (int j = i + 1; j < 9; j++)
{
x = y = z = 0;
for (int k = 0; k < 9; k++)
{
if (k < i)
x = x * 10 + s[k + 1];
else if (k < j)
y = y * 10 + s[k + 1];
else
z = z * 10 + s[k + 1];
}
if (y % z == 0 && x + y / z == N)
{
ans++;
}
}
}
}
void dfs(int pos, int n)
{
if (pos == n)
found(s);
else
{
for (int i = 1; i <= 9; i++)
{
if (!visit[i])
{
s[pos] = i;
visit[i] = 1;
dfs(pos + 1, n);
visit[i] = 0;
}
}
}
}
int main()
{
cin >> N;
dfs(1, 10);
cout << ans << endl;
return 0;
}
四、别人的代码3
#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
int parse(const char *arr, int pos, int len)
{
int ans = 0;
int t = 1;
for (int i = pos + len - 1; i >= pos; i--)
{
ans += (arr[i] - '0') * t;
t *= 10;
}
return ans;
}
int main()
{
int N;
cin >> N;
int ans = 0;
string s = "123456789";
do
{
const char *str = s.c_str();
for (int i = 0; i <= 7; i++)
{
int inta = parse(str, 0, i);
if (inta >= N)
break;
for (int j = 1; j <= 9 - 1 - i; j++)
{
int intb = parse(str, i, j);
int intc = parse(str, i + j, 9 - i - j);
if (intb % intc == 0 && inta + intb / intc == N)
{
ans++;
}
}
}
} while (next_permutation(s.begin(), s.end()));
cout << ans;
return 0;
}