历届试题 带分数

  历届试题 带分数  

时间限制：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

11

样例输入2

105

样例输出2

6

 

解题思路：首先需要了解一下全排列，以及全排列的算法，我是直接搜的算法，在写这个博客之前表示没还没仔细研究过，但是感觉很好理解，然后就是将每一个数都尝试一边看是不是带分数，也就是循环确定a和b的位置，剩下就是c，判断一下就好了

#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
int sum;
int n;
int x,y,z;

//交换
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
//全排列递归算法
void perm(int list[], int k,int m)
{
    //list 数组存放排列的数，k表示层 代表第几个数，m表示数组的长度
    if(k==m)
    {
        //k==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
        x=0;y=0;z=0;
        for(int i=0;i<7;i++){
                x= x*10+list[i];
                y=0;
            for(int j=i+1;j<8;j++){
                y=y*10+list[j];
                z=0;
                for(int k1=j+1;k1<=8;k1++){
                       z=z*10+list[k1];
                       if(k1==8&&y>z&&y%z==0&&x+y/z==n){
                        sum++;
                       // cout<<x<<" "<<y<<" "<<z<<" "<<y/z<<" "<<y%z<<endl;
                      }




                }
            }

        }

    }
    else
    {
        for(int i=k; i<=m; i++)
        {
            swap(list[i],list[k]);
            perm(list,k+1,m);
            swap(list[i], list[k]);
        }
    }


}

int main()
{

    int a[]= {1,2,3,4,5,6,7,8,9 };
    sum=0;
    cin>>n;
    perm(a,0,8);
    cout<<sum;
    return 0;

}