这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1099
以前记得做过这题,不过HDOJ上次资料丢失,导致我已经AC的150题也没了,就重新做了遍。
水题吧~~~
就是求n*(1/1 + 1/2 + ... + 1/n)
我AC的:
#include
using namespace std;
typedef struct tt{
__int64 fenmu, fenzi;
}tt;
int gcd(int a, int b)//求最大公约数
{
if(a < b)
return gcd(b, a);
if(a%b == 0)
return b;
return gcd(b, a%b);
}
tt add(tt a, tt b)
{
int temp = gcd(a.fenmu, b.fenmu);
tt c;
c.fenmu = a.fenmu*b.fenmu/temp;
c.fenzi = c.fenmu/a.fenmu*a.fenzi + c.fenmu/b.fenmu*b.fenzi;
int g = gcd(c.fenzi, c.fenmu);
c.fenmu /= g;
c.fenzi /= g;
return c;
}
int bit(int n)
{
int cnt = 0;
while(n)
{
++cnt;
n /= 10;
}
return cnt;
}
int main()
{
bit(1234);
int n;
while(cin >> n)
{
tt res, temp;
res.fenmu = 1;
res.fenzi = 1;
for(int i=2; i<=n; ++i)
{
temp.fenmu = i;
temp.fenzi = 1;
res = add(res, temp);
}
res.fenzi *= n;
//cout << "res: " << res.fenzi << " " << res.fenmu << endl;
if(res.fenzi/res.fenmu*res.fenmu == res.fenzi)
cout << res.fenzi/res.fenmu << endl;
else
{
int num1 = res.fenzi/res.fenmu;
int num2 = res.fenzi - num1*res.fenmu;
int gg = gcd(num2, res.fenmu);
res.fenmu /= gg;
res.fenzi = num2/gg;
int t1 = bit(num1);
int t2 = bit(res.fenzi);
int t3 = bit(res.fenmu);
for(int i=1; i<=t1+1; ++i)
cout << " ";
cout << res.fenzi<< endl;
cout << num1 << " ";
for(int i=1; i<=t3; ++i)
cout << "-";
cout << endl;
for(int i=1; i<=t1+1; ++i)
cout << " ";
cout << res.fenmu << endl;
}
}
}
我写的很乱,下面这个写的比较不错:
#include
using namespace std;
int getBit(int n)
{
int i=0;
while(n!=0){
n/=10;
++i;
}
return i;
}
void print(int s,int n,int d){
int i,len=getBit(s)+1;
for(i=0;id) n=n-d;
else d=d-n;
}
return n;
}
int main()
{
int n,i;
int sum,g;
int numerator;
int denominator;
while(cin>>n){
sum=0;
numerator=0;
denominator=1;
for(i=1;i<=n;i++){
numerator=numerator*i+n*denominator;
denominator*=i;
g=gcd(numerator,denominator);
numerator/=g;
denominator/=g;
sum+=numerator/denominator;
numerator%=denominator;
}
if(numerator==0)
printf("%d\n",sum);
else
print(sum,numerator,denominator);
}
return 0;
}