发信人: sino (茶水先生), 信区: Algorithm
标 题: ZSUCPC 2000中山同志们的题解--第一试第一题
发信站: 哈工大紫丁香 (2001年08月27日10:09:54 星期一), 站内信件
发信人: splutter (呆子), 信区: ACMICPC
标 题: [合集]第一试第一题 forgetful
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 19 05:25:58 2001), 站内信件
------------------------------------------------------
monster@argo (不再堕落，不再�) 于Fri May 11 20:25:13 2001)
提到：
转信站: argo
【 在 mk (逐风) 的大作中提到: 】
: 第一题：循环节（repeating cycle）（30分）
: 问题描述：
: 求一个分数对应的十进制小数的循环节。我们定义一个小数的循环节是它的第一个最
短
: 的向右无限循环的数字串。
: 下面是一些分数的循环节，循环节部分用括号括住，例如：
: 分数 十进制小数 循环节 循环节长度（位数）
: 1／6 0.1(6) 6 1
: 5／7 0.(714285) 714285 6
: 1／250 0.004(0) 0 1
^^^^^^^^^^^^^^^^^^^^^^^^^
这里0是不应作为无限循环节的，
除非，题意为0.004=0.0040000000000000000000000000000000000000...
: 输入：输入文件的每行包含两个正整数，第一个为分子，第二个为分母，它们之间用
一
: …………
------------------------------------------------------
mysunshine (雨一直下) 于Fri May 11 20:32:44 2001提到：
我想题意就是这样。
------------------------------------------------------
forgetful (准备梨树中) 于Fri May 11 20:33:46 2001提到：
搞掂一题，sigh~，做得好慢～～
#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <conio.h>
void main()
{
clrscr();
fstream in_file("in.txt",ios::in);
fstream out_file("out.txt",ios::out); //打开读和写的文件
int a,b,i,j,k,temp1[100],temp2[100];
a=0;b=-1; //定义循环结束符
in_file>>a>>b;
while(!(a==0&&b==-1))
{
cout<<a<<"\t"<<b;
if(a>=b) a%=b;
temp1[0]=a;
for(i=0;i<50;i++)
{
temp2[i]=temp1[i]/b;
temp1[i+1]=temp1[i]%b*10;
for(j=0;j<=(i+1);j++)
if(temp1[i+1]==temp1[j]) break; //判断是否
已经
�
if(j!=i+1) break; //如果j=j+1,则没有产生循环
}
for(k=0;k<(i-j+1);k++) cout<<temp2[j+k];
cout<<"\t"<<(i-j+1)<<endl;
a=0;b=-1;
in_file>>a>>b;
}
}
------------------------------------------------------
forgetful (准备梨树中) 于Fri May 11 20:34:22 2001提到：
既然题目这样给的测试数据，要求应该就是这样吧？
------------------------------------------------------
menway (我没有钱) 于Fri May 11 20:38:28 2001提到：
我也贴一个，bp7的，总共31行
var
ok:boolean;
a,b,i,j,k:integer;
m,r:array[1..50] of integer;
begin
readln(a,b);write(a div b,'.');
i:=0;a:=a mod b;ok:=false;
while not ok do begin
a:=a*10;
inc(i);
m[i]:=a div b;
r[i]:=a mod b;
a:=r[i];
for j:=1 to i-1 do
if r[j]=r[i] then begin ok:=true;break;end;
if i=50 then break;
end;
if ok then begin
if r[i]=0 then begin inc(i);inc(j);end;
for k:=1 to j-1 do write(m[k]);
write('(');
for k:=j to i-1 do write(m[k]);
writeln(')');
writeln(i-j)
end
else begin
for i:=1 to 50 do write(m[i]);
writeln;
writeln(0);
end;
end.
------------------------------------------------------
Holmaming (更加风采动朝端) 于Fri May 11 23:16:28 2001提到：
错了。
【 在 menway (我没有钱) 的大作中提到: 】
: 我也贴一个，bp7的，总共31行
: var
: ok:boolean;
: a,b,i,j,k:integer;
: m,r:array[1..50] of integer;
: begin
: readln(a,b);write(a div b,'.');
: i:=0;a:=a mod b;ok:=false;
: while not ok do begin
: a:=a*10;
: …………
------------------------------------------------------
menway@argo (我没有钱) 于Sat May 12 00:35:09 2001)
给个数据啊，看看错在那里
【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: 错了。
------------------------------------------------------
forgetful (继续健忘) 于Sat May 12 00:39:47 2001提到：
呵呵，不好意思，一时疏忽，贴错了，输出写错了
应该是这样的
#include <string.h>
#include <fstream.h>
void main()
{
fstream in_file("in.txt",ios::in);
fstream out_file("out.txt",ios::out); //打开读和写的文件
int a,b,i,j,k,temp1[100],temp2[100];
a=0;b=-1; //定义循环结束符
in_file>>a>>b;
while(!(a==0&&b==-1))
{
temp1[0]=a%b;
for(i=0;i<50;i++)
{
temp2[i]=temp1[i]/b;
temp1[i+1]=temp1[i]%b*10;
for(j=0;j<=(i+1);j++)
if(temp1[i+1]==temp1[j]) break; //判断是否
已经
�
if(j!=i+1) break; //如果j=j+1,则没有产生循环
}
out_file<<a<<"/"<<b<<"="<<a/b<<".";
for(k=0;k<j;k++) out_file<<temp2[k];
out_file<<"(";
for(k=0;k<(i-j+1);k++) out_file<<temp2[j+k];
out_file<<")";
out_file<<"\t"<<(i-j+1)<<endl;
a=0;b=-1;
in_file>>a>>b;
}
}
------------------------------------------------------
menway@argo (我没有钱) 于Sat May 12 00:49:14 2001)
提到：
转信站: argo
我也打个补丁，呵呵，原来的程序输入12 3或者4 2等可以整除的数的时候输出不对，把
源程序的第19行加一个and(a[j]<>0)就行了
更新后的源程序如下：(thx to Holm)
var
ok:boolean;
a,b,i,j,k:integer;
m,r:array[1..50] of integer;
begin
readln(a,b);write(a div b,'.');
i:=0;a:=a mod b;ok:=false;
while not ok do begin
a:=a*10;
inc(i);
m[i]:=a div b;
r[i]:=a mod b;
a:=r[i];
for j:=1 to i-1 do
if r[j]=r[i] then begin ok:=true;break;end;
if i=50 then break;
end;
if ok then begin
if (r[i]=0)and(m[j]<>0) then begin inc(i);inc(j);end;
for k:=1 to j-1 do write(m[k]);
write('(');
for k:=j to i-1 do write(m[k]);
writeln(')');
writeln(i-j)
end
else begin
for i:=1 to 50 do write(m[i]);
writeln;
writeln(0);
end;
end.
------------------------------------------------------
menway (我没有钱) 于Sat May 12 00:55:09 2001提到：
try 11 33,好像不对哦。你的程序输出0.03(3)
【 在 forgetful (继续健忘) 的大作中提到: 】
: 呵呵，不好意思，一时疏忽，贴错了，输出写错了
: 应该是这样的
: #include <string.h>
: #include <fstream.h>
: void main()
: {
: fstream in_file("in.txt",ios::in);
: fstream out_file("out.txt",ios::out); //打开读和写的文件
: int a,b,i,j,k,temp1[100],temp2[100];
: a=0;b=-1; //定义循环结束符
: …………
------------------------------------------------------
forgetful (继续健忘) 于Sat May 12 01:09:08 2001提到：
sigh~,太粗心了，忘了去掉前面的0,谢谢menway提醒
再打了一个50位都出不了循环数的补丁
大家可以用2/1237试试
#include <string.h>
#include <fstream.h>
void main()
{
fstream in_file("in.txt",ios::in);
fstream out_file("out.txt",ios::out); //打开读和写的文件
int a,b,i,j,k,temp1[100],temp2[100];
a=0;b=-1; //定义循环结束符
in_file>>a>>b;
while(!(a==0&&b==-1))
{
temp1[0]=a%b;
for(i=0;i<50;i++)
{
temp2[i]=temp1[i]/b;
temp1[i+1]=temp1[i]%b*10;
for(j=0;j<=(i+1);j++)
if(temp1[i+1]==temp1[j]) break; //判断是否已经产生循环
if(j!=(i+1)) break; //如果j=i+1,则没有产生循环
}
out_file<<a<<"/"<<b<<"="<<a/b<<".";
for(k=1;k<j;k++) out_file<<temp2[k];
if(i!=50)
{
out_file<<"(";
for(k=0;k<(i-j+1);k++) out_file<<temp2[j+k];
out_file<<")";
out_file<<"\t"<<(i-j+1)<<endl;
}
else out_file<<"\t0\n";
a=0;b=-1;
in_file>>a>>b;
}
}
------------------------------------------------------
Holmaming (更加风采动朝端) 于Sat May 12 10:58:23 2001提到：
这样找循环节，漏洞多多的说。
【 在 menway@argo (我没有钱) 的大作中提到: 】
: 给个数据啊，看看错在那里
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 错了。
------------------------------------------------------
simontwo (John Active) 于Sat May 12 11:22:27 2001)提到：
我来具体点说明吧：0.110110……
你去试下吧：110/999=0.110110……（其实反例有很多）
你输出的结果：0.（1）
你是用最近相似原则，有重复不代表是循环节的！
所以不够全面嘛！
------------------------------------------------------
menway (我没有钱) 于Sat May 12 11:27:20 2001提到：
可是我查找的是余数啊，并不是在商中查找，就是说，当发现当前位的余数以前出现
过，就认为出现了一个循环结，应该是正确的吧。
源程序和编译后的exe可以到ftp://172.16.16.118下载
【 在 simontwo (John Active) 的大作中提到: 】
: 我来具体点说明吧：0.110110……
:
: 你去试下吧：110/999=0.110110……（其实反例有很多）
: 你输出的结果：0.（1）
:
: 你是用最近相似原则，有重复不代表是循环节的！
:
: 所以不够全面嘛！
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 这样找循环节，漏洞多多的说。
: …………
------------------------------------------------------
Holmaming (更加风采动朝端) 于Sat May 12 11:33:58 2001提到：
嘻嘻，看错了，//sorry。这样应该是可以的。
再给你出一道题吧，已知循环节，求其分数最简式，也很简单的说。
【 在 menway (我没有钱) 的大作中提到: 】
: 可是我查找的是余数啊，并不是在商中查找，就是说，当发现当前位的余数以前出现
: 过，就认为出现了一个循环结，应该是正确的吧。
: 源程序和编译后的exe可以到ftp://172.16.16.118下载
: 【 在 simontwo (John Active) 的大作中提到: 】
: : 我来具体点说明吧：0.110110……
: : 你去试下吧：110/999=0.110110……（其实反例有很多）
------------------------------------------------------
simontwo (John Active) 于Sat May 12 11:35:25 2001)提到：
查余数这是个很好的办法！应该是对的吧，我想？
不肯定！
【 在 menway (我没有钱) 的大作中提到: 】
: 可是我查找的是余数啊，并不是在商中查找，就是说，当发现当前位的余数以前出现
: 过，就认为出现了一个循环结，应该是正确的吧。
:
: 源程序和编译后的exe可以到ftp://172.16.16.118下载
:
: 【 在 simontwo (John Active) 的大作中提到: 】
: : 我来具体点说明吧：0.110110……
: :
: : 你去试下吧：110/999=0.110110……（其实反例有很多）
: : 你输出的结果：0.（1）
: :
: : 你是用最近相似原则，有重复不代表是循环节的！
: :
: : 所以不够全面嘛！
: : 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : : 这样找循环节，漏洞多多的说。
: : …………
:
------------------------------------------------------
simontwo (John Active) 于Sat May 12 11:39:46 2001)提到：
喂，这题很简单的啊，
设：A为无限循环小数，它的循环节为（abc……）有n个位，
那么你把A=(A*10^n-A)/(10^n-1) 然后循环节给减掉了，以后……
这样就可以算出来了！
【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: 嘻嘻，看错了，//sorry。这样应该是可以的。
:
: 再给你出一道题吧，已知循环节，求其分数最简式，也很简单的说。
:
: 【 在 menway (我没有钱) 的大作中提到: 】
: : 可是我查找的是余数啊，并不是在商中查找，就是说，当发现当前位的余数以前出
现
: : 过，就认为出现了一个循环结，应该是正确的吧。
: : 源程序和编译后的exe可以到ftp://172.16.16.118下载
: : 【 在 simontwo (John Active) 的大作中提到: 】
: : : 我来具体点说明吧：0.110110……
: : : 你去试下吧：110/999=0.110110……（其实反例有很多）
:
:
------------------------------------------------------
Holmaming (更加风采动朝端) 于Sat May 12 11:41:53 2001提到：
考虑问题不完整。
【 在 simontwo (John Active) 的大作中提到: 】
: 喂，这题很简单的啊，
: 设：A为无限循环小数，它的循环节为（abc……）有n个位，
: 那么你把A=(A*10^n-A)/(10^n-1) 然后循环节给减掉了，以后……
: 这样就可以算出来了！
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 嘻嘻，看错了，//sorry。这样应该是可以的。
: :
------------------------------------------------------
Holmaming (更加风采动朝端) 于Sat May 12 11:42:29 2001提到：
【 在 simontwo (John Active) 的大作中提到: 】
: 喂，这题很简单的啊，
~~还有，对师兄应该尊重一点哦
: 设：A为无限循环小数，它的循环节为（abc……）有n个位，
: 那么你把A=(A*10^n-A)/(10^n-1) 然后循环节给减掉了，以后……
: 这样就可以算出来了！
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 嘻嘻，看错了，//sorry。这样应该是可以的。
: :
------------------------------------------------------
menway (我没有钱) 于Sat May 12 11:43:37 2001提到：
可是不一定小数点后面就一定开始循环阿。
0.A1A2A3...An(An+1An+2...Am)=
A1A2A3...Am - A1A2A3...An
------------------------------------------------------
simontwo (John Active) 于Sat May 12 11:48:33 2001)提到：
你是不是说，循环节不是在第一位开始啊？其实这个，要靠自己拉，
不需要多讲了吧？我记得小学的时候，老师就是这么跟我讲的
其实如果不是第一位的话，可以再成多个别的10的次方啊？
这个应该不用多讲啦！其他的特例我就没有想到，如果有，请告诉我！
【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: 考虑问题不完整。
:
: 【 在 simontwo (John Active) 的大作中提到: 】
: : 喂，这题很简单的啊，
: : 设：A为无限循环小数，它的循环节为（abc……）有n个位，
: : 那么你把A=(A*10^n-A)/(10^n-1) 然后循环节给减掉了，以后……
: : 这样就可以算出来了！
: : 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : : 嘻嘻，看错了，//sorry。这样应该是可以的。
: : :
:
:
------------------------------------------------------
CSLeeman@argo (CS99+如月影) 于Sat May 12 11:50:56 2001)
提到：
转信站: argo
象这个 1/250==0.004(0);
你那个不行了哦。
【 在 menway (我没有钱) 的大作中提到: 】
: 可是不一定小数点后面就一定开始循环阿。
: 0.A1A2A3...An(An+1An+2...Am)=
: A1A2A3...Am - A1A2A3...An
: -------------------------------
: 999...9000...0 (m-n个9，n个0)
: 用这个公式吧。然后约分一下就行了
: 【 在 Holmaming (更加风采动朝端) 的大作中提到: 】
: : 嘻嘻，看错了，//sorry。这样应该是可以的。
: : 再给你出一道题吧，已知循环节，求其分数最简式，也很简单的说。
------------------------------------------------------
menway (我没有钱) 于Sat May 12 12:26:59 2001提到：
ft,实际上0是不可以作循环结的，违背了循环小数的定义。
+-有限小数（即所谓的以0为循环结的小数）
|
小数-+ +无限循环小数（可化为分数）
| |
+无限小数+
|
+无限不循环小数（如pi，sqrt(3)等无理数）
如果实在要0作循环结，就多加一条判断好了。
if (An+1+...+Am==0)
分数为A1A2...An/10^n，然后再约分
【 在 CSLeeman@argo (CS99+如月影) 的大作中提到: 】
: 象这个 1/250==0.004(0);
: 你那个不行了哦。
: 【 在 menway (我没有钱) 的大作中提到: 】
: : 可是不一定小数点后面就一定开始循环阿。
: : 0.A1A2A3...An(An+1An+2...Am)=
--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]