　题目

　　分数化小数（fracdec.cpp,128MB,1s）

【问题描述】:

　　写一个程序，输入一个形如 N/D 的分数（N 是分子，D 是分母），输出它的

小数形式。如果小数有循环节的话，把循环节放在一对括号中。例如：

1/3=0.33333… 写成 0.(3)；41/333=0.123123123… 写成 0.(123)。

用*.0 表示整数，如 2/2=1.0

【输入文件】:

　　单独的一行包括被空格隔开的 N 和 D。（1≤N、D≤100000）

【输出文件】:

　　输出一行，即分数 N/D 的小数形式。

【输入输出样例】：

　　样例 1：

　　　　fracdec.in

　　　　　　45 46

　　　　fracdec.out

　　　　　　0.803(571428)

　　样例 2：

　　　　fracdec.in

　　　　　　3 8

　　　　fracdec.out

　　　　　　0.375

　　样例 3：

　　　　fracdec.in

　　　　　　8 4

　　　　fracdec.out

　　　　　　4.0

【数据规模】:

　　如上

考试得分：　　60

主要算法：　　除法（循环节性质）

题干：

　　　　分数化为小数

应试策略：

　　1.现将小数点前的lead求出，特殊处理没有小数点后的情况

　　2.再将整除的特殊处理

　　3.剩下的用KMP进行枚举

　　代码

#include
      
       #include
       
        #include
        
         #define FORa(i,s,e) for(int i=s;i<=e;i++)#define FORs(i,s,e) for(int i=s;i>=e;i--)#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)using namespace std;const int N=100;int a,b,lead,cnt;string s="";bool Check(string ss,int sp){    int len=ss.size();    FORa(k,1,6)    {        FORa(i,1,len) if(ss[i-1]!=s[sp+len+i-1]) return 0;            sp=sp+len;    }    }void Init(){    scanf("%d%d",&a,&b);    lead=a/b,a=a%b,a*=10;    if(!a) {printf("%d.0",lead);return;}    while(a&&cnt<=500) s=s+char(a/b+'0'),a=(a%b)*10,cnt++;    if(!a) {printf("%d.",lead),cout<

非完美算法：　　

　　　　照搬应试策略

正解：

　　　　初等数学（循环节的基本性质），知道循环节的出现为除数再次出现

　　代码

#include#include
       
        #include
        
         #include
         
          #define FORa(i,s,e) for(int i=s;i<=e;i++)#define FORs(i,s,e) for(int i=s;i>=e;i--)#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)using namespace std;const int N=100;int a,b,lead,cnt;string s="";map
          
            mp;void Init(){    scanf("%d%d",&a,&b);    lead=a/b,a=a%b,a*=10,mp[a]=++cnt;    if(!a) {printf("%d.0",lead);return;}    while(a)     {        s=s+char(a/b+'0'),a=(a%b)*10,++cnt;        if(mp[a])        {            printf("%d.",lead);            for(int i=0;i