PREV-3_蓝桥杯_带分数

问题描述

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
 
 记:
题目的类型是：n = a + b/c，求满足的个数
一开始以为就是简单的两个不同比例的"数字+分数"模式,结果在测试其他数据时错误,
故将注意力放在a,b,c的比例分配(隐藏条件b >= c)
然而并没有发现规律...
上网查阅，有一篇博客讲到了全排序(http://blog.csdn.net/jopus/article/details/18998403)
还没开始精细阅读源码，被其中的分区的概念刺激
于是有了思路：

a的默认比例为1，依次递增(a <= n的长度)
将区间总长度(LEN=9)减去a，并取得中值，从而得到b，c的值(b >= c)
每次dfs后，b ++,c --，再次dfs(当b-c > n的长度时，明显不符条件)

源码如下:

 #include <stdio.h>

 #define LEN 9

 int n;

 int a,b,c;

 int sum =  , len = ;

 int ans[LEN+] = {};

 int num[LEN+] = {,,,,,,,,,,};

 int f[LEN+] = {};

 void dfs(int x)

 {

     int i , j;

     int x1,x2,x3;

     if (x > )

     {

         x = x1 = x2 = x3 = ;

         /*1.确定第一个值x1*/

         for (i =  , j =  ; i < a ; i ++)

         {

             x1 += ans[++x]*j;

             j *= ;

         }        

         /*2.确定分数的分子x2*/

         for (i =  , j =  ; i < b ; i ++)

         {

             x2 += ans[++x]*j;

             j *= ;

         }

         /*3.确定分数的分母x3*/

         for (i =  , j =  ; i < c ; i ++)

         {

             x3 += ans[++x]*j;

             j *= ;

         }

         if (x2%x3 ==  && (x1 + x2/x3) == n)

         {

             sum ++;

             //printf("%d+%d/%d\n",x1,x2,x3);

         }

         return ;

     }

     for (i =  ; i <=  ; i ++)

     {

         if (!f[i])

         {

             ans[x] = num[i];

             f[i] = ;

             dfs(x+);

             f[i] = ;

         }

     }        

     return ;

 }

 int main(void)

 {

     int i;

     scanf("%d",&n);

     i = n;

     while(i)

     {

         i = i/;

         len ++;    /*获取n的长度*/

     }

     for (a =  ; a <= len ; a ++)

     {

         i = LEN-a;

         b = i - i/;

         c = i - b;

         if (b < c)/*b必定为较大区间*/

         {

             b = b^c;

             c = b^c;

             b = b^c;

         }

         /*更改b和c的比例*/

         while (c)

         {

             dfs();

             b ++;

             c --;

         }

     }

     printf("%d",sum);

     return ;

 }

 

PREV-3_蓝桥杯_带分数的相关教程结束。