[蓝桥省题](C2013_9) 带分数
9、带分数
100可以表示为带分数的形式:100-3+69258/714
还可以表示为:100=82+3546/197
注意特征:带分数中,数字1-9分别出现且只出现依次(不包含0)
类似这样的带分数,100有11中表示法
题目要求:
- 从标准输入读入一个正整数N(N<1000*1000)
- 程序输出该数字用数码1-9不重复不遗漏的组成带分数表示全部种数
- 注意:不要求输出每个表示,只统计有多少表示法!
例如,用户输入:100
程序输出:11
样例2:用户输入105
程序输出:6
题意:这一题就是1-9个数字中的任意几个数字组成的加数加上剩余的数的商。例如题目上的例子:369258714,将加号添加到第一个数后面3+69258714,将/号添加到第六个数后面:3+69258/714,即ans++
思路:我们可以将1到9的每个全排列取出来,然后进行加号和除号位置的枚举,最维护一个全局计数变量,若该数满足条件,则计数变量+1
测试代码如下:
#include<stdio.h>
#include<stdlib.h>
int ans = 0;
void check(int* nums,int len,int n)
{
int h1=0, h2, h3;
for (int i = 0; i < len-2; i++)//枚举加号前的数
{
h1 = h1 * 10 + nums[i];
if (h1 >= n) break;
h2 = 0;
for (int j = i + 1; j < len - 1; j++)//枚举除号前的数
{
h2 = h2 * 10 + nums[j];
h3 = 0;
for (int k = j + 1; k < len; k++)//枚举除号后的数
{
h3 = h3 * 10 + nums[k];
if (h2 / h3 <= 0)break;
}
if (h1 + h2 / h3 == n && h2 % h3 == 0)//判断是否等于n
{
//printf("%d,%d,%d", h1, h2, h3);//检查代码
ans++;
//system("pause");
}
}
}
}
void swap(int* nums, int a, int b)
{
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
void prem(int* nums,int p,int q)
{
if (p == q)
{
/*for (int i = 0; i < q; i++)
{
printf("%d", nums[i]);
}
printf("\n");
*/
check(nums, q, 100);//一个序列全排列进行检查
}
else
{
for (int i = p; i < q; i++)
{
swap(nums, i, p);
prem(nums, p + 1, q);
swap(nums, i, p);
}
}
}
int main()
{
int nums[9] = { 1,2,3,4,5,6,7,8,9 };
prem(nums, 0, 9);
printf("%d", ans);
system("pause");
return 0;
}
教学视频如下所示: