|
|
问题描述：
将分数转化为小数，相信很多人都会吧．那么，这里给定一个分数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 <stdio.h>
#include <string.h>
#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;i<temp; i++)
j=j->next;/*找到循环节开始的前一位*/
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;
}
|
|
