试题历届试题带分数（全排列）

柔情只为你懂 2023-07-11 13:59 17阅读 0赞

# 试题 历届试题 带分数 #

--------------------

资源限制
    时间限制：1.0s   内存限制：256.0MB

## 问题描述 ##

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 ##

## 思路： ##

全排列一下1-9，  
之后就是将这个全排列划分成3个数。  
枚举3个数，加上一些剪枝即可。

## 代码： ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    int num[] = {
        1,2,3,4,5,6,7,8,9};
    int main()
    {
        
        int n;
        cin>>n;
        int ans = 0;
        do{
        
           int x = 0;
           for(int i = 0; i < 7; i++)
           {
        
               x = x*10 + num[i];
               if(x > n) break;
               int y = 0;
               for(int j = i+1; j < 8; j++)
               {
        
                   y = y * 10 + num[j];
                   if(y < n) continue;
                   int z = 0;
                   for(int k = j+1; k < 9; k++)
                   {
        
                       z = z*10 + num[k];
                   }
                   if(z > y) continue;
                   if(y % z == 0 && y / z == n - x)
                   {
        
                       ans++;
                   }
               }
           }
        }while(next_permutation(num,num+9));
        cout<<ans<<endl;
        return 0;
    }