2013年第四届蓝桥杯省赛-I. 带分数

2020-09-24 · 68次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解

I. 带分数

原题链接

题面

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。

类似这样的带分数，100 有 11 种表示法。

输入描述

从标准输入读入一个正整数 N ( $N<1000 \times 1000$ )。

输出描述

程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

输入样例

输出样例

题解

枚举，全排列，剪枝

记该式子为：

$n = b + \frac{x}{y}$

暴力枚举数组 a 中的每个数字的排列位置，再划定两个分割符 i 和j ( i < j )，则 b 由 a[0] ~ a[i] 表示，而 x 由a[i + 1] ~ a[j] 表示，y 由 a[j + 1] ~ a[8] 表示。移动分隔符 i 和 j ，就能产生不同的组合，再判断生产的三个数能否满足上式即可。

代码

#include<iostream>
#include<algorithm>

using namespace std;
int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n, res;

void check() {
    for (int i = 0; i <= 5; ++i) {  //左区间
        int b = 0;
        for (int k = 0; k <= i; k++) b = b * 10 + a[k];
        if (b >= n - 1) return; //剪枝

        for (int j = i + 1; j < 8; ++j) {   //右区间
            if (j - i < 8 - j) continue;    //x的数字位数需要比y等或大
            int x = 0, y = 0;	//分子和分母
            for (int k = i + 1; k <= j; k++) x = x * 10 + a[k];
            for (int k = j + 1; k <= 8; k++) y = y * 10 + a[k];
            if (x < y || x % y != 0) continue;   //不能整除
            int t = x / y;
            if (n == b + t) res++;
        }
    }
}

int main() {
    cin >> n;

    do {
        check();
    } while (next_permutation(a, a + 9));
    cout << res << endl;

    return 0;
}

标题：	2013年第四届蓝桥杯省赛-I. 带分数
链接：	https://www.fightingok.cn/detail/9
更新：	2022-09-18 22:31:35
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可