問題描述：

將分數轉化為小數，相信很多人都會吧．那么，這里給定一個分數N/D,N為分子，D為分母(N,D均為整數)，試編程求出N/D的小數形式，當然如果這個小數為無限循環小數，則把循環的部分用括號括起來，接著循環的部分則省略不寫。比如：

1/3??? =0.(3)

22/5=4.4

1/7??? =0.(142857)

2/2??? =1.0

3/8??? =0.375

45/56??? =0.803(571428)

輸入為兩個正整數N,D(1 <= N,D <= 100000),輸出為對應的小數(為了對齊格式，請一行最多輸出76個字符)。

樣例輸入：

1 3

22 5

1 7

對應輸出：

0.(3)

4.4

0.(142857)

============

code=================== /** *Copyright (C) aprin at Xiamen University *2005-04-23 */ #include #include #define LEN_SHANG sizeof(struct node_shang) #define LEN_YUSHU sizeof(struct node_yushu) struct node_shang {/*商結點*/ ? char data; ? struct node_shang *next; } *shang_head=0, *shang_tail=0; struct node_yushu {/*余數結點*/ ? long data; ? struct node_yushu *next; } *yushu_head=0, *yushu_tail=0; int shang_empty(void) {/*判斷商串是否空*/ ? return shang_head==0; } int yushu_empty(void) {/*判斷余數串是否空*/ ? return yushu_head==0; } struct node_shang *new_shang_node(char ch) {/*新建商的結點*/ ? struct node_shang *ptr= (struct node_shang *) malloc(LEN_SHANG); ? ptr->data=ch; ? ptr->next=0; ? return ptr; } struct node_yushu *new_yushu_node(long a) {/*新建余數結點*/ ? struct node_yushu *ptr= (struct node_yushu *) malloc(LEN_YUSHU); ? ptr->data= a; ? ptr->next=0; ? return ptr; } void insert_shang(char ch) {/*插入商字符串的結點*/ ? struct node_shang *newptr= new_shang_node(ch); ? if(shang_empty()) ??? shang_head=shang_tail=newptr; ? else { ??? shang_tail->next= newptr; ??? shang_tail= newptr; ? } } void insert_yushu(long a) {/*插入余數結點*/ ? struct node_yushu *newptr= new_yushu_node(a); ? if(yushu_empty()) ??? yushu_head=yushu_tail=newptr; ? else { ??? yushu_tail->next= newptr; ??? yushu_tail= newptr; ? } } char *longinttostr(long a, char *str) {/*將長整型轉化為字符串*/ ? char temp; ? int i, j; ? i=0; ? if(a==0) {/*a=0時特別處理*/ ??? str[0]='0'; ??? i++; ? } else { ??? while(a!=0) { ????? str[i]=(a%10)+'0'; ????? a=a/10; ????? i++; ??? } ? } ? str[i]='/0'; ? for(j=0; j<=(i-1)/2; j++) {/*倒置*/ ??? temp= str[j]; ??? str[j]= str[i-1-j]; ??? str[i-1-j]= temp; ? } ? return str;/*返回長度*/ } long found_xunhuan(void) {/*通過余數是否相等判斷是否出現循環節，若出現返回出現位置的指針ind(相對小數點的偏移量)，若無反回-1*/ ? struct node_yushu *i; ? long ind; ? for(i=yushu_head, ind=0; i->next!=0; i=i->next, ind++) ??? if(yushu_tail->data==i->data) ????? return ind; ? if(i->next==0) ??? return -1; } void div(long d, long n) {/*d是被除數，n是除數*/ ? long yushu, shang_zhenshu, temp, i, len_temp; ? char str[7]; ? struct node_shang *j, *new_node; ? /*計算整數部分*/ ? shang_zhenshu= d/n; ? d=d%n; ? insert_yushu(d);/*余數保存到余數鏈表*/ ? longinttostr(shang_zhenshu, str); ? i=0; ? while(str[i]!='/0') {/*商保存到商鏈表*/ ??? insert_shang(str[i]); ??? i++; ? } ? insert_shang('.'); ? if(d==0) {/*恰好整除的情況*/ ??? insert_shang('0'); ??? return; ? } ? while((d!=0)&&((temp=found_xunhuan())==-1)) {/*當除盡或發現循環節時停止*/ ??? d=d*10;/*進位*/ ??? insert_shang((d/n)+'0'); ??? insert_yushu(d%n); ??? d=d%n; ? } ? /*除法已完成*/ ? if(temp!=-1) {/*發現循環節*/ ??? j=shang_head; ??? while(j->data!='.')/*找到小數點的位置*/ ????? j=j->next; ??? for(i=0;inext;/*找到循環節開始的前一位*/ ??? new_node= new_shang_node('('); ??? new_node->next=j->next; ??? j->next= new_node; ??? new_node= new_shang_node(')'); ??? shang_tail->next= new_node; ??? shang_tail= new_node; ? } } void output(void) { ? struct node_shang *i; ? long temp; ? i=shang_head; ? temp=0; ? while(i->next!=0) { ??? putchar(i->data); ??? i=i->next; ??? temp++; ??? if((temp%76)==0)/*每行輸出76個字符*/ ????? putchar('/n'); ? } ? putchar(shang_tail->data); ? putchar('/n'); } int main(void) { ? long d, n; ? scanf("%ld %ld", &d, &n); ? while((d<1)||(d>100000)||(n<1)||(n>100000)) { ??? printf("Input is wrong! Please inpute again!(1<=d, n<=100000)/n"); ??? scanf("%ld %ld", &d, &n); ? } ? div(d, n); ? output(); ? return 0; }