蓝桥杯带分数 DFS应用

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

问题描述

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

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

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

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

输入格式

从标准输入读入一个正整数N (N<1000*1000)

输出格式

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

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

样例输入1

100

样例输出1

样例输入2

105

样例输出2

//法一

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

int num[] = {, , , , , , , , },

    N, ans;

int getSum(int lh, int rh)

{

    int sum = ;

    for (int i = lh; i <= rh; i++)

    {

        sum = sum *  + num[i];

    }

    return sum;

}

void check()

{

    for (int i = ; i < ; i++)

    {

        int a = getSum(, i);

        if (a > N) continue;

        for (int j = i + ; j < ; j++)

        {

            int b = getSum(i + , j);

            int c = getSum(j + , );

            if (b >= c && b % c ==  && (a + b/c == N)) {

                ans++;

            }

        }

    }

}

void solve()

{

    cin >> N;

    do {

        check();

    } while(next_permutation(num, num + ));

    printf("%d\n", ans);

}

int main()

{

    solve();

    return ;

}

//法二

 #include <algorithm>

 #include <cstring>

 #include <queue>

 #define INF 0x3f3f3f3f

 #define MAXN 100005

 #define Mod 10001

 using namespace std;

 int vis[], n , ans;

 int num[];

 int getSum(int lh, int rh)

 {

     int sum = ;

     for (int i = lh; i <= rh; i++) {

         sum = sum *  + num[i];

     }

     return sum;

 }

 void check()

 {

     for (int i = ; i <= ; i++) {

         int a = getSum(, i);

         if (a > n) continue;

         for (int j = i + ; j < ; j++) {

             int b = getSum(i + , j);  //[i+1, j]

             int c = getSum(j + , );  //[j+1, 9]

             if (b >= c && b % c ==  && a + b/c == n) {

                 ans++;

             }

         }

     }

 }

 void dfs(int step)

 {

     if (step == ) {

         check();

     }

     else {

         for (int i = ; i <= ; i++) {

             if (!vis[i]) {

                 num[step] = i;

                 vis[i] = ;

                 dfs(step + );

                 vis[i] = ;

             }

         }

     }

 }

 int main()

 {

     scanf("%d", &n);

     ans = ;

     memset(vis, , sizeof(vis));

     dfs();

     printf("%d\n", ans);

     return ;

 }

//这里补充一个next_permutation()的用法

//蓝桥杯 2015省赛第3题三羊献瑞

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int a[] = {, , , , , , , , , };

int b, c;

int d;

void solve()

{

    do {

        b = a[]* + a[]* + a[]* + a[];

        c = a[]* + a[]* + a[]* + a[];

        d = a[]* + a[]* + a[]* + a[]* + a[];

//        if (b + c == d) {

//            cout << b << " + " << c << " = " << d << endl;

//        }

    } while (next_permutation(a, a + ));

}

int main()

{

    solve();

    return ;

}