[20分求解答]求解此问题

CU达人

请问如何使用C来解决这样的问题：


1/2= 0.5
1/3= 0.(3)
1/4= 0.25
1/5= 0.2
1/6= 0.1(6)
1/7= 0.(142857)
1/8= 0.125
1/9= 0.(1)
1/10= 0.1


比如1/7=0.(142857)就是说()里面的是个循环体，
分子是1, 分母是1到1000

请教各位达人，谢谢....

nketc

(看6楼OW，这儿和上面的不对，想改改来，OW都贴出来了，俺保留自己错误吧。)
胡乱写的，vim里排版挺好的。 语言学家请直走。（语言学家说用链表。能给链个不？）
俺自爆吧：
1）用goto了
2）变量命名不好
3）没用链表（realloc行不）
4）。。。

下面是改进版：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(int argc, char *argv[]) {
   
5.     int  i  = 0, s = 0, t  = 1, n, r, k;
   
6.     int *d  = NULL;
   
7.     int  c  = 100;
   
8. 
   
9.     n = atoi(argv[1]);
   
10.     d = malloc(c * sizeof(int));
    
11. 
    
12.     do {
    
13.         if (i + 1 >= c) {
    
14.             c += i;
    
15.             d = realloc(d, c * sizeof(int));
    
16.         }
    
17.         while(t < n) {
    
18.             t *= 10;
    
19.             d[++i] = 0;
    
20.         }
    
21.         while (t >= n) {
    
22.             t -= n;
    
23.             d[i] += 1;
    
24.         }
    
25.         if (t == 0) break;
    
26.         if (s == t) {
    
27.             if (d[i] == d[r]) break;
    
28.             else r = i;
    
29.         }
    
30.         if (s == 0) {
    
31.             s = t;
    
32.             r = i;
    
33.         }
    
34.     }while(1);
    
35. 
    
36.     if (t == 0) r = ++i;
    
37.     printf("1/%d=0.", n);
    
38.     for(k=1; k<i; k++) {
    
39.         if (k == r) printf("(");
    
40.         printf("%d", d[k]);
    
41.     }
    
42.     if (t != 0) printf(")");
    
43.     printf("\n");
    
44. 
    
45.     free(d);
    
46.     return 0;
    
47. }
    

复制代码

nketc

1. int main(int argc, char *argv[]) {
   
2. int i;
   
3. int d[100];
   
4. int t;
   
5. int n;
   
6. int k;
   
7. int w[100];
   
8. int wi;
   
9. 
   
10. n = atoi(argv[1]);
    
11. 
    
12. wi= 0;
    
13. i = 0;
    
14. t = 1;
    
15. do {
    
16.     while(t < n) {
    
17.         t *= 10;
    
18.                 d[++i] = 0;
    
19.         }
    
20.     while (t >= n) {
    
21.             t -= n;
    
22.                 d[i] += 1;
    
23.         }
    
24.     for (k=0; k<wi; k++) {
    
25.             if (w[k] == t) goto out;
    
26.         }
    
27.         w[wi++] = t;
    
28. }while(t != 0);
    
29. 
    
30. out:
    
31. if (t == 0) printf("1/%d=0.", n);
    
32. else printf("1/%d=0.(", n);
    
33. for(k=1; k<=i; k++) {
    
34.     printf("%d", d[k]);
    
35. }
    
36. if (t != 0) printf(")");
    
37. printf("\n");
    
38. 
    
39. return 0;
    
40. }
    
41. 
    

复制代码

nketc

楼主给分。我真是闲的d疼。

OwnWaterloo

回复 1# CU达人

1. 循环节一定存在
相同余数会产生相同后续序列，而余数的取值范围是有限的： [0,分母) 。
一位一位取就是了……
直到遇见相同余数，或余数为0。

2. 有尽小数
只要除数的质因子中只有2与5，就能除尽。
可通过这个判断是否需要"()"记号。

3. 进制
虽然最终是按十进制输出，但内部进制不一定必须是十进制或字符。
内部进制大一些可以减少一些计算， 输出时注意 leading 与 tailing 零就行。
只是对本例子来说作用不明显， 还会加大找循环节的难度……
所以代码中只对有尽小数使用……

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. int terminating_decimal(int divisor)
   
6. {
   
7.       while (divisor%2u==0) divisor/=2u;
   
8.       while (divisor%5u==0) divisor/=5u;
   
9.       return divisor==1;
   
10. }
    
11. 
    
12. int main(int argc, char* argv[])
    
13. {
    
14.       int dividend,divisor,remainder;
    
15. 
    
16.       dividend = argc>1? atoi(argv[1]): 1;
    
17.       divisor = argc>2? atoi(argv[2]): 1;
    
18.       if (dividend<0 || divisor<=0) {
    
19.             fprintf(stderr, "for simplification supports positive only\n" );
    
20.             return EXIT_FAILURE;
    
21.       }
    
22. 
    
23.       printf("%d", dividend/divisor);
    
24.       remainder = dividend%divisor;
    
25.       if (!remainder)
    
26.             return 0;
    
27.       printf(".");
    
28. 
    
29.       if (!terminating_decimal(divisor))
    
30.       {
    
31.             char* digits = (char*)malloc(divisor);
    
32.             int i = 0, j;
    
33.             int* met = (int*)calloc(divisor,sizeof(int));
    
34. 
    
35.             do {
    
36.                   int dividend = remainder*10u;
    
37.                   int quotient = dividend/divisor;
    
38.                   digits[i] = quotient+'0';
    
39.                   met[remainder] = ++i;
    
40.                   remainder = dividend % divisor;
    
41.             } while (!met[remainder]);
    
42. 
    
43.             j = met[remainder]-1;
    
44.             printf("%.*s(%.*s)", j, digits, i-j, digits+j);
    
45. 
    
46.             free(met);
    
47.             free(digits);
    
48.       }
    
49.       else
    
50.       {
    
51. #define RADIX 100u
    
52. #define EXPONENT 2
    
53. #define STR(x) STR_(x)
    
54. #define STR_(x) #x
    
55. 
    
56.             int quotient,i;
    
57. 
    
58.             for (; dividend = remainder*RADIX
    
59.                  , quotient = dividend/divisor
    
60.                  , remainder = dividend%divisor
    
61.                  , remainder
    
62.                  ; printf("%0" STR(EXPONENT) "d", quotient) ) ;
    
63. 
    
64.             for (i=RADIX/10; quotient; quotient%=i, i/=10u)
    
65.                   putchar(quotient/i+'0');
    
66.       }
    
67. 
    
68.       printf("\n");
    
69.       return 0;
    
70. }
    

复制代码

最后附加一份测试代码

1. 
   
2. #!/usr/bin/env python
   
3. 
   
4. import sys
   
5. import re
   
6. from fractions import Fraction
   
7. 
   
8. p = re.compile(r'[ ]*([0-9]*)\.?([0-9]*)(\(([0-9]*)\))?')
   
9. for line in sys.stdin :
   
10.     m = p.match(line)
    
11.     i,f,_,r = m.groups()
    
12.     w = 10**len(f)
    
13.     result = (int(i) if i else 0) \
    
14.            + (Fraction(int(f),w) if f else 0) \
    
15.            + (Fraction(int(r),10**len(r)-1)/w if r else 0)
    
16.     expect = line[m.end():].strip()
    
17.     expect = Fraction(expect) if expect else result
    
18.     print line[:m.end()],result
    
19.     if expect!=result : print >>sys.stderr, line[:m.end()],expect,result
    

复制代码

1. 
   
2. for ((i=1;i<=1212;++i)) do echo $(fraction2decimal 1 $i) 1/$i; done | decimal2fraction.py >/dev/null
   

复制代码

CU达人

回复 4# nketc


   谢谢各位的解答

nketc

回复 1# CU达人


    楼主还没测试吧，我这个是有问题的。6楼，OW的才是正确的。
----------------------
ps 怎么把分还给你？