蓝桥杯历届试题带分数（搜索）

历届试题带分数

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

　　一道搜索题，用递归遍历所有情况。符合条件的累加计数。

　　一开始没思路，借鉴了网上的解答。给出链接：http://bbs.csdn.net/topics/390448276 。借鉴了12楼 nono_lonely 的代码。

　　我选择的做法是将N分成两部分，左边的是整数部分，右边的根据一定的规则化成分数形式。只要这个过程符合规则，则计数+1。

　　下面是第一次代码，与原作者代码大相径庭，但好歹AC了，调了2个小时，主要是细节问题，代码有些臃肿，后面我会再优化。

  1 #include <iostream>
  2 #include <string.h>
  3 using namespace std;
  4 int N;
  5 int _count;
  6 int le,ri; //左边的数，右边的数
  7 int left_digits,right_digits;   //左边数的位数，右边数的位数
  8 
  9 struct CB{
 10     char c;     //存储字符
 11     bool isu;   //有没有被使用
 12 }cb[10];
 13 
 14 void flags(int n)   //对该数进行标记
 15 {
 16     while(n){
 17         int t;
 18         t=n%10;
 19         cb[t].isu = true;
 20         n/=10;
 21     }
 22 }
 23 void unflags(int n) //取消标记
 24 {
 25     while(n){
 26         int t;
 27         t=n%10;
 28         if(t==0)
 29             cb[t].isu = true;
 30         else
 31             cb[t].isu = false;
 32         n/=10;
 33     }
 34 }
 35 int check(int n)
 36 {
 37     CB cb2[10];
 38     memcpy(cb2,cb,sizeof(cb));
 39     while(n){
 40         int t;
 41         t=n%10;
 42         if(cb2[t].isu || t==0){
 43             return 0;
 44         }
 45         cb2[t].isu=true;
 46         n/=10;
 47     }
 48     return 1;
 49 }
 50 int use(int n)  //返回使用的位数
 51 {
 52     int length=0;
 53     while(n){
 54         length++;
 55         n/=10;
 56     }
 57     return length;
 58 }
 59 bool all_use()
 60 {
 61     for(int i=1;i<=9;i++){
 62         if(!cb[i].isu)
 63             return false;
 64     }
 65     return true;
 66 }
 67 void ConstructFraction(int depth,int mol) //构造分数。depth为分子的位数，不能超过剩余位数的一半。mol为本次的分子数，如果本次能构造成功，则计数+1。
 68 {
 69     if(depth <= right_digits/2){
 70         for(int i=mol;i<=mol*10-1;i++){
 71             if(check(i)){
 72                 flags(i);
 73                 int deno = ri*i;   //确定分母
 74                 if(check(deno)){
 75                     flags(deno);
 76                     //分母通过验证，在判断9个数字是否都用上了
 77                     if(all_use()){   //都用上了，计数+1
 78                         _count++;
 79                         //cout<<N<<'='<<le<<'+'<<deno<<'/'<<i<<endl;
 80                     }
 81                     unflags(deno);
 82                 }
 83                 unflags(i);
 84             }
 85         }
 86         ConstructFraction(depth+1,mol*10);
 87     }
 88 }
 89 int main()
 90 {
 91     while(cin>>N){
 92         _count=0;
 93         for(int i=1;i<=N-1;i++){
 94             le=i;
 95             ri = N-le;
 96             cb[0].isu = true;
 97             for(int j=1;j<=9;j++){  //初始化
 98                 cb[j].c = '0'+j;
 99                 cb[j].isu = false;  //初始化时每个字符都定义为没使用
100             }
101             if(check(le)){    //核对左边的数是否符合规则
102                 flags(le);    //对左边的数使用过的位进行标记
103                 left_digits = use(le);    //返回使用的位数
104                 right_digits = 9-left_digits;   //剩余的位数
105                 ConstructFraction(1,1);
106                 unflags(le);
107             }
108         }
109         cout<<_count<<endl;
110     }
111     return 0;
112 }

Freecode : www.cnblogs.com/yym2013

蓝桥杯 历届试题 带分数（搜索）

蓝桥杯历届试题带分数（搜索）