[蓝桥省题](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;
}

教学视频如下所示:

本文链接:

https://nullcode.fun/97.html
1 + 6 =
快来做第一个评论的人吧~