[蓝桥省题](C2013_9) 带分数

9、带分数

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

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

注意特征：带分数中，数字1-9分别出现且只出现依次(不包含0)

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

题目要求：

• 从标准输入读入一个正整数N(N<1000*1000)
• 程序输出该数字用数码1-9不重复不遗漏的组成带分数表示全部种数
• 注意：不要求输出每个表示，只统计有多少表示法！

例如，用户输入：100

程序输出：11

样例2：用户输入105

程序输出：6

题意：这一题就是1-9个数字中的任意几个数字组成的加数加上剩余的数的商。例如题目上的例子：369258714，将加号添加到第一个数后面3+69258714，将/号添加到第六个数后面：3+69258/714，即ans++

思路：我们可以将1到9的每个全排列取出来，然后进行加号和除号位置的枚举，最维护一个全局计数变量，若该数满足条件，则计数变量+1

测试代码如下：

#include<stdio.h>
#include<stdlib.h>
int ans = 0;
void check(int* nums,int len,int n)
{
    int h1=0, h2, h3;
    for (int i = 0; i < len-2; i++)//枚举加号前的数
    {
        h1 = h1 * 10 + nums[i];
        if (h1 >= n) break;
        h2 = 0;
        for (int j = i + 1; j < len - 1; j++)//枚举除号前的数
        {
            h2 = h2 * 10 + nums[j];
            h3 = 0;
            for (int k = j + 1; k < len; k++)//枚举除号后的数
            {
                h3 = h3 * 10 + nums[k];
                if (h2 / h3 <= 0)break;
            }
            if (h1 + h2 / h3 == n && h2 % h3 == 0)//判断是否等于n
            {
                //printf("%d,%d,%d", h1, h2, h3);//检查代码
                ans++;
                //system("pause");
            }
        }
    }
}
void swap(int* nums, int a, int b)
{
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}
void prem(int* nums,int p,int q)
{
    if (p == q)
    {
        /*for (int i = 0; i < q; i++)
        {
            printf("%d", nums[i]);
        }

        printf("\n");
        */
        check(nums, q, 100);//一个序列全排列进行检查
    }
    else
    {
        for (int i = p; i < q; i++)
        {
            swap(nums, i, p);
            prem(nums, p + 1, q);
            swap(nums, i, p);
        }
    }
}
int main()
{
    int nums[9] = { 1,2,3,4,5,6,7,8,9 };
    prem(nums, 0, 9);

    printf("%d", ans);
    system("pause");
    return 0;
}

教学视频如下所示：

本文链接：