首页 > 代码库 > 蓝桥杯 带分数

蓝桥杯 带分数

2024-07-03 15:30:57   232人阅读

                 历届试题 带分数  
时间限制：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
11
样例输入2
105
样例输出2

6




#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int vis[10],a[10];
int counter;
int sum(int start,int end)
{
    int total=0;
    int i;
    for(i=start;i<end;i++)  total=total*10+a[i+1];
    return total;
}
void check(int a[],int n,int num)
{   
    int begin=1,temp=num;
    while((temp=temp/10)!=0)  begin++;//先判断目标数据的位数n，那么num1的位数小于等于n。 
    int i,j;
    int num1,num2,num3;
    for(i=1;i<begin+1;i++)
        {
        num1=sum(0,i);
        if(num1>num) return ;
        for(j=i+(n-i)/2;j<n-1;j++)
            {
                                   num2=sum(i,j);
                                   num3=sum(j,n-1);
                                   if(num2>num3&&num2%num3==0&&(num==num1+num2/num3))
                                   {
                                    counter++;
                                   // printf("%d=%d+%d/%d\n",num,num1,num2,num3);                                               
                                   }
            }
                          
        }
}
void dfs(int start,int n,int num)//全排列 
{
     if(start==n)
     {
                 check(a,n,num);
     }
     else
     {
         int i;
         for(i=1;i<n;i++)
         {
         if(vis[i]) continue;
         vis[i]=1;
         a[start]=i;
         dfs(start+1,n,num);
         vis[i]=0;
         }
     }
}
int main()
{
    int num;
    scanf("%d",&num);
    counter=0;
    memset(vis,0,sizeof(vis));
    dfs(1,10,num);
    printf("%d\n",counter);
    system("pause");
    return 0;
}
/*100
100=3+69258/714
100=81+5643/297
100=81+7524/396
100=82+3546/197
100=91+5742/638
100=91+5823/647
100=91+7524/836
100=94+1578/263
100=96+1428/357
100=96+1752/438
100=96+2148/537
11
*/


联系
我们