100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
参考文献：
KeepThinking_的专栏，http://blog.csdn.net/keepthinking_/article/details/8947014，2014年2月9日
MilkCu的专栏，http://blog.csdn.net/milkcu/article/details/9103191，2014年2月9日
这个题目我想了好久还是不能解决，无奈之下，只好求助google大神，找到了两位大神的博客，参照他们的思路改写了少部分代码，AC通过。
这里分别对MilkCu的暴力枚举法，和KeepThinking_的全排列进行简单的分析。
/*
Name: 蓝桥杯：带分数（暴力枚举法）
Copyright: 本算法由MilkCu提供
Author: Jopus
Date: 09/02/14 00:47
Description: dev-cpp 5.5.3
*/
#include <stdio.h>
#include <string.h>
//思路：暴力枚举法
char flag[10]; //用于标记"#123456789"是否已经被选
char backup[10]; //用于临时保存数据
//检查"#123456789"每个数据是否只有一个
int check(int n)
{
do
{
++flag[n%10]; //统计数字：如n = 123;则++flag[3],++flag[2],++flag[1]
}while(n /= 10);
if(flag[0] != 0) //如果存在0
return 1; //返回冲突
for(int i = 1; i < 10; i++)
if(flag[i] > 1)//如果存在某个数据不只有1个
return 1; //返回冲突
return 0; //返回正确
}
//检查是否每个数据都已经存在
int checkAll(void)
{
for(int i = 1; i < 10; i++)
if(flag[i] != 1)
return 1;//不全部包括
return 0; //全部包括
}
int main(void)
{
int i = 0;
int num = 0; //输入数据
int count = 0; //统计个数
scanf("%d", &num);
int left = 0, up = 0, down = 0; //带分数
for(left = 1; left < num; ++left) //先从带分数的左边开始增加
{
for (i = 0; i < 10; ++i) //将标记数组全部初始化为0
flag[i] = 0;
if(check(left)) //检查左边数据合理性
continue;//不合理
for (i = 0; i < 10; ++i) //缓存flag数据，用于下面for循环重置
backup[i] = flag[i];
for(down = 1; down < 100000; ++down) //再增加带分数底数
{
for (i = 0; i < 10; ++i) //重置flag
flag[i] = backup[i];
up = (num - left) * down; //计算出up值
if(check(down) || check(up)) //检查数据合理性
continue;//不合理
if(!checkAll())
{
// printf("%d = %d + %d / %d\n", num, left, up, down);
++count; //计数+1
}
}
}
printf("%d\n", count);//打印总共个数
}
根据题目的要求，输入一个数字，需要将这个数字化成带分数，且包含（0-9）所有数字（不重复）。
这里我们假设输入的数字为number，划分好的带分数为a+b/c，它将满足条件number == a+b/c且b%c==0，同时abc包含所有（0-9，且不重复）。
请注意最后最句话，abc包含所有（0-9，且不重复），我们再看题目给我们的那个满足条件的数字：
3+69258/714 这里a = 3， b = 69258， c = 714 ；则abc = 369258714（这个数字数list的一种排列方式）。
所以我们想到一种方法：先求出list的一种排列，然后对这个排列进行a，b，c划分处理，如果满足条件
（条件：number == a+b/c且b%c==0，同时abc包含所有（0-9，且不重复））则将记录种数+1 。
在看KeepThinking_的全排列算法之前，我们需要知道如何对数据进行全排列。
下图是对（1,2,3,4）全排列的树状图：
将图示转化为C语言代码（如下）：
#include <stdio.h>
/*
递归(分治法思想):
设(ri)perm(X)表示每一个全排列前加上前缀ri得到的排列.
当n=1时,perm(R)=(r) 其中r是唯一的元素,这个就是出口条件.
当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)构成.
*/
//此处为引用,交换函数.函数调用多,故定义为内联函数.
inline void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void Perm(int list[],int k,int m) //k表示前缀的位置,m是要排列的数目.
{
if(k==m-1) //前缀是最后一个位置,此时打印排列数.
{
for(int i=0;i<m;i++)
printf("%d",list[i]);
printf("\n");
}
else
{
for(int i=k;i<m;i++)
{
//交换前缀,使之产生下一个前缀.
Swap(list[k],list[i]); //Ａ
Perm(list,k+1,m); //Ｂ
//将前缀换回来,继续做上一个的前缀排列.
Swap(list[k],list[i]); //Ｃ
}
}
}
int main()
{
int list[] = {1,2,3,4};
Perm(list,0,4);
return 0;
}
（注：（Ａ）表示执行语句（Ａ），见代码后标记。（Ｂ０）表示第０层递归，相当于上图中的根结点结点｛１，２,３,４｝）
第一步：i = k = 0; 交换list[0]←→list[0]（Ａ），即将list[0]加入到前缀得到如结点（b）所示，然后对{2,3,4}全排列。（Ｂ０）（B0表示第０层递归，下同）
第二步：i = k = 1;交换list[1]←→list[1]（Ａ），即将list[1]加入到前缀得到如结点（c）所示，然后对{3,4}全排列。（Ｂ１）
第三步：i = k = 2;（进入Prim）交换list[2]←→list[2]（Ａ），即将list[2]加入到前缀得到如结点（f）所示，然后对{4}全排列。（Ｂ２）
第四步：i = 2,k = 3,（进入Prim）打印第三步的情况，即打印结点（f）。（Ｂ３）
第五步：i = k = 2,交换list[2]←→list[2]（Ｃ），即还原到交换前状态。（Ｂ２）
第六步：i = 3, k = 2,（for循环）交换list[3]←→list[2]（Ａ），即将list[3]加入前缀得到如结点（g）所示，然后对{3}全排列。（Ｂ２）
第七步：i = 3,k = 3,（进入Prim）打印第六步的情况，即打印结点（g）。（Ｂ３）
第八步：i = 3, k = 2,交换list[3]←→list[2]（Ｃ），即还原到交换前状态。（Ｂ２）
第九步：i = 4, k = 2,跳出for循环，第一个分支打印完毕，准备打印第二个分支。（Ｂ２->Ｂ１）
第十步：i = k = 1,交换list[1]←→list[1]（Ｃ），即还原到交换前状态。（Ｂ１）
第十一步：i = 2, k = 1,交换list[2]←→list[1]（Ａ），即将list[2]加入前缀得到如结点（d）所示，然后对{2,4}全排列。（Ｂ１）
第十二步：i = 2, k = 2,（进入Prim）交换list[2]←→list[2]（Ａ），即将list[2]加入到前缀得到如结点（h）所示，然后对{4}全排列。（Ｂ２）
第十三步：i = 2,k = 3,（进入Prim）打印第十二步的情况，即打印结点（h）。（Ｂ３）
......................
不一一列举了，（ｉ）就相当于交换到第几个了，（ｋ）相当于在第几层。
好了，全排列就讲到这里了。
上面已经分析了，将“123456789”全排列，然后用a,b,c划分，我们这里主要讲要怎么划分：
还是用上面那个排列：abc = 369258714
我们规定a在最前面，b在中间，c在尾部（因为对list进行了全排列每种情况都会出现，所以a,b,c位置无所谓，这么规定只是为了好分析）。
这样我们可以知道a的头部就是list的第一位list[0]，a的尾部就是b的头部（不能确定）
b的尾部则是c的头部（也不能确定），但是我们知道c的尾部一定是list[8]。
然后又有number = a + b / c 等式成立。变形一下：b = (number - a) * c。
好了，注意，根据乘法原理我们可以推出b的尾部数字（设为bLast）。
bLast=((number-a)*list[8])%10; //确定b最后一个数字。
最后为了程序优化，我们剪掉一些不可能的情况。
number = a + b / c
a为带分数的左边，（1<= a <= 1000,000）这个范围没错吧？1000,000为题目规定范围。我们用for循环人为设定a区间的尾部。
b为带分数的上部，这里隐含条件（b % c == 0）必须为整数。所以b>=c这点是必须的，由于我们划分的是区间，
所以区间长度就能近似的表示数值的大小了，区间越长，说明数值位数越多，肯定值越大，所以b的区间长度就必须不小于c的区间长度。
也就是说a后面剩下的list长度b要占一半以上。因为b的最后一位我们已经算出来了，所以我们需要匹配最后一位的位置，就能划分出a,b,c区间。
说了这么一大堆，我自己都搞晕了。放个例子出来溜溜，还是以上面那个排列来说明。
示例：3+69258 / 714 （number = 100）
abc = 369258714
第一步：人为划分a（如：（0,1）），即a = 3
第二步：计算出bLast=((number-a)*list[8])%10 = ((100 - 3) * 4)%10 = 8
第三步：a = （0,1）那么bc则是（2,8），那么b的最后一位我们从(8-2)/2 = 3，也就是从list[3] = 2开始找起（直接跳过前面不可能情况） 369-258714
第四步：判断bLast == list[i]，当找到了b的尾部的时候，我们就开始检查组合的合理性：它将满足条件number == a+b/c且b%c==0（如果合理）
第五步：如果合理则将情况种数+1同时跳出for循环，进入递归找下一组排列。
如果不合理，则将a划分区间长度+1，a = （0,2），即a = 36，然后再确定b的尾部bLast.................
下面是一个简单的图分析：
好了，就分析到这里了，下面放出我改编了的KeepThinking_的全排列算法代码：
/*
Name: 蓝桥杯：带分数（全排列）
Copyright: 本算法由KeepThinking_提供
Author: Jopus
Date: 08/02/14 19:57
Description: dev-cpp 5.5.3
*/
#include <stdio.h>
/*思路：将list[1,2,3,4,5,6,7,8,9]数组进行全排列，然后对于每一种排列进行处理
处理方法：将list数组划分为三部分a,b,c，判断是否满足number == a+b/c && b%c == 0;
具体见分析.........
*/
int x = 0, number = 0, count = 0;
//交换a,b两数
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
//将数组区间转化为数字
int getNum(int list[], int f, int r)
{
int i = 0, num = 0;
for (i = f; i <= r; i++)
num = list[i] + num * 10; //进位
return num;
}
//进行全排列并对每种排列结果进行处理
void Prim(int list[], int k, int m)
{
if(k==m-1) //前缀是最后一个位置,此时出现一种排列数.
{
int a = 0, b = 0, c = 0, bLast = 0; //带分数：a+b/c
for (int i = 0; i < x; i++) //i表示a的末尾位置，不会超过number位数
{
a = getNum(list, 0, i); //将list数组中的[0-i]转化为数字，赋值给a
bLast=((number-a)*list[8])%10; //确定b最后一个数字
for (int j =i+(8-i)/2; j < 8; j++)//从list数组中间位置开始找b末尾位置
{
if(list[j]==bLast) //找到b尾部
{
b = getNum(list, i+1, j); //将list数组中的[i+1-j]转化为数字，赋值给b
c = getNum(list, j+1, 8); //将list数组中的[j+1-8]转化为数字，赋值给c
if (b % c == 0 && a + b / c == number) //判断合理性
{
// printf("%d+%d/%d\n",a,b,c); //打印每种情况
++count;
}
break;
}
}
}
}
else
{
for(int i=k;i<m;i++) //全排列数组list[]
{
//交换前缀,使之产生下一个前缀.
Swap(list[k],list[i]); //>>A
Prim(list,k+1,m); //>>B
//将前缀换回来,继续做上一个的前缀排列.//>>C
Swap(list[k],list[i]);
}
}
}
//主函数
int main()
{
int temp = 0;
int list[] = {1,2,3,4,5,6,7,8,9}; //定义全排列数组
scanf("%d",&number);
temp = number;
while (temp != 0) //统计number总共多少位
{
++x;
temp /= 10;
}
Prim(list,0,9);
printf("%d", count); //打印总共多少种
return 0;
}
| 提交序号 | 姓名 | 试题名称 | 提交时间 | 代码长度 | CPU使用 | 内存使用 | 评测详情 | |||
|---|---|---|---|---|---|---|---|---|---|---|
| 63929 | Jopus | 带分数 | 02-09 00:36 | 2.544KB | C++ | 正确 | 100 | 46ms | 808.0KB | 评测详情 |
转载请保留原文地址：http://blog.csdn.net/jopus/article/details/18998403
原文：http://blog.csdn.net/jopus/article/details/18998403