1209. 带分数刷题笔记

本文主要是介绍1209. 带分数刷题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路暴力匹配

读入目标数 n

看n是否与a+b/c相等

因为c++里面的除法是整除

我们将 n==a+b/c

转换为 c*n==a*c+b

那么如何获得a,b，c

依题意 a，b，c三个数由1-9九个数字组成

且每个数字只能出现一次

由此我们可以搜出123456789的全部排列方式

然后每次将这个九位数分成三部分

例如 a=12,b=4567,c=89

又假如当前排列为 985476321

获得a=985,b=476,c=321;

或者

a=98,b=5476,c=321;

枚举出所有的分法

同时与目标值匹配即可

若相等则计数++

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring >
using namespace std;
int n,cnt;
const int N=10;
bool used[N];
int st[N];
int num[10]={1,2,3,4,5,6,7,8,9};
int cal(int i,int j);
void dfss()
   {
       //双循环枚举出所有的分法
           for(int i=1;i<=6;i++){
               for(int j=i+1;j<=8;j++){
                   int a=cal(1,i);
                   int b=cal(i+1,j);
                   int c=cal(j+1,9);
                   //cout<<a<<endl<<b<<endl<<c<<endl;
                   if(c*n==a*c+b){

                       cnt++;
                   }
               }
           }

       //cout<<dsf(1);
   }
void dfs(int u){
   if(u>9){
       //当u>9说明已经搜索出了一个排列
       //修改num内存的值与当前排列相同
       int ans=0;
       for(int i=1;i<=9;i++){
           num[i]=st[i] ;

       //   cout<<num[i]<<' ';
       }

       dfss();//计算当前排列是否匹配目标值
       return ;
   }
   for(int i=1;i<=9;i++){
       if(!used[i]){
           used[i]=true;
           st[u]=i;
           dfs(u+1);
           used[i]=false;
           st[u]=0;
       }

   }


}
int cal(int i,int j){

   int res=0;
   for( ;   i<=j;i++){
       res=res*10+num[i];
   }
   //将num的值转化为a,b，c的值
   return res;
}