| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1086 人关注过本帖
标题:[原创]绝对挑战
只看楼主 加入收藏
zefil415
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-6-4
收藏
 问题点数:0 回复次数:10 
[原创]绝对挑战
#include "stdio.h"
long a=10000,b,c=2800,d,e,f[2801],g;
main()
{
for(;b-c;)
f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)
for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);
getchar();
}


这个是算PI值的程序段.

由于本人的能力有限,所以在此,请大侠们能给予详细说明一下!
如果可以的话,还希望说一下这个是用了什么算法和数据结构???

有兴趣的朋友们,大家都来试一试,期待大家的赐教!!!


在此先谢过了!!!
搜索更多相关主题的帖子: 绝对挑战 
2005-06-08 21:47
zefil415
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-6-4
收藏
得分:0 
如果大家还有兴趣的话,本人还可以再提供一段关于"算素数"的程序段!

还希望大家以给予帮助!!!!

2005-06-08 21:50
seeker
Rank: 1
等 级:新手上路
帖 子:172
专家分:0
注 册:2005-6-5
收藏
得分:0 

分析一下上面的程序(转) 一、数学公式 数学家们研究了数不清的方法来计算PI,这个程序所用的公式如下: 1 2 3 k pi = 2 + --- * (2 + --- * (2 + --- * (2 + ... (2 + ---- * (2 + ... ))...)))

3 5 7 2k+1 3 5 7 2k+1 至于这个公式为什么能够计算出PI,已经超出了本文的能力范围。 下面要做的事情就是要分析清楚程序是如何实现这个公式的。 我们先来验证一下这个公式: 程序一:Pi公式验证程序 #include "stdio.h" void main() { float pi=2; int i; for(i=100;i>=1;i--) pi=pi*(float)i/(2*i+1)+2; printf("%f\n",pi); getchar(); } 上面这个程序的结果是3.141593。 二、程序展开 在正式分析程序之前,我们需要对程序一进行一下展开。我们可以看出程序一都是使用 for循环来完成计算的,这样做虽然可以使得程序短小,但是却很难读懂。根据for循环 的运行顺序,我们可以把它展开为如下while循环的程序: 程序二:for转换为while之后的程序 int a=10000,b,c=2800,d,e,f[2801],g; main() { int i; for(i=0;i<c;i++) f[i]=a/5; while(c!=0) { d=0; g=c*2; b=c; while(1) { d=d+f[b]*a; g--; f[b]=d%g; d=d/g; g--; b--; if(b==0) break; d=d*b; } c=c-14; printf("%.4d",e+d/a); e=d%a; } } 注: for([1];[2];[3]) {[4];} 的运行顺序是[1],[2],[4],[3]。如果有逗号操作符,例如:d=0,g=c*2,则先运行d=0, 然后运行g=c*2,并且最终的结果是最后一个表达式的值,也就是这里的c*2。 下面我们就针对展开后的程序来分析。 三、程序分析 要想计算出无限精度的PI,我们需要上述的迭代公式运行无数次,并且其中每个分数也 是完全精确的,这在计算机中自然是无法实现的。那么基本实现思想就是迭代足够多次 ,并且每个分数也足够精确,这样就能够计算出PI的前n位来。上面这个程序计算800位 ,迭代公式一共迭代2800次。 int a=10000,b,c=2800,d,e,f[2801],g; 这句话中的2800就是迭代次数。 由于float或者double的精度远远不够,因此程序中使用整数类型(实际是长整型),分 段运算(每次计算4位)。我们可以看到输出语句 printf("%.4d",e+d/a); 其中%.4就是 把计算出来的4位输出,我们看到c每次减少14( c=c-14;),而c的初始大小为2800,因 此一共就分了200段运算,并且每次输出4位,所以一共输出了800位。 由于使用整型数运算,因此有必要乘上一个系数,在这个程序中系数为1000,也就是说 ,公式如下: 1 2 3 k 1000*pi = 2k+ --- * (2k+ --- * (2k+ --- * (2k+ ... (2k+ ---- * (2k+ ... )). ..))) 3 5 7 2k+1 这里的2k表示2000,也就是f[2801]数组初始化以后的数据,a=10000,a/5=2000,所以下面 的程序把f中的每个元素都赋值为2000: for(i=0;i<c;i++) f[i]=a/5; 你可能会觉得奇怪,为什么这里要把一个常数储存到数组中去,请继续往下看。 我们先来跟踪一下程序的运行: while(c!=0) 假设这是第一次运行,c=2800,为迭代次数 { d=0; g=c*2; 这里的g是用来做k/(2k+1)中的分子 b=c; 这里的b是用来做k/(2k+1)中的分子 while(1) while(1) { d=d+f[b]*a;// f中的所有的值都为2000,这里在计算时又把系数扩大了 a=10000倍。这样做的目的稍候介绍,你可以看到输出的时候是d/a,所以这不影响计算 g--; f[b]=d%g; 先不管这一行 d=d/g; 第一次运行的g为2*2799+1,你可以看到g做了分母 g--; b--; if(b==0) break; d=d*b; 这里的b为2799,可以看到d做了分子。 } c=c-14; printf("%.4d",e+d/a); e=d%a; } 只需要粗略的看看上面的程序,我们就大概知道它的确是使用的那个迭代公式来计算Pi 的了,不过不知道到现在为止你是否明白了f数组的用处。如果没有明白,请继续阅读。 d=d/g,这一行的目的是除以2k+1,我们知道之所以程序无法精确计算的原因就是这个除 法。即使用浮点数,答案也是不够精确的,因此直接用来计算800位的Pi是不可能的。那 么不精确的成分在哪里?很明显:就是那个余数d%g。程序用f数组把这个误差储存起来 ,再下次计算的时候使用。现在你也应该知道为什么d=d+f[b]*a;中间需要乘上a了吧。 把分子扩大之后,才好把误差精确的算出来。 d如果不乘10000这个系数,则其值为2000,那么运行d=d/g;则是2000/(2*2799+1),这 种整数的除法答案为0,根本无法迭代下去了。 现在我们知道程序就是把余数储存起来,作为下次迭代的时候的参数,那么为什么这么 做就可以使得下次迭代出来的结果为 接下来的4位数呢? 这实际上和我们在纸上作除法很类似: 0142 /——------ 7 / 1 10 7 7 --------------- 30 28 --------------- 20 14 --------------- 60 ..... 我们可以发现,在做除法的时候,我们通常把余数扩大之后再来计算,f中既然储存的是 余数,而f[b]*a;则正好把这个余数扩大了a倍,然后如此循环下去,可以计算到任意精 度。 这里要说明的是,事实上每次计算出来的d并不一定只有4位数,例如第一次计算的时候 ,d的值为31415926,输出4位时候,把低四位的值储存在e中间,e=d%a,也就是5926。

最后,这个c=c-14不太好理解。事实上没有这条语句,程序计算出来的仍然正确。只是 因为如果迭代2800次,无论分数如何精确,最后Pi的精度只能够达到800。 你可以把程序改为如下形式尝试一下: for(i=0;i<800;i++) { { d=0; g=c*2; b=c; while(1) { d=d+f[b]*a; g--; f[b]=d%g; d=d/g; g--; b--; if(b==0) break; d=d*b; } // c=c-14; 不要这句话。 printf("%.4d",e+d/a); e=d%a; } 最后的答案仍然正确。 不过我们可以看到内循环的次数是c次,也就是说每次迭代计算c次。而每次计算后续位 数的时候,迭代次数减少14,而不影响精度。 补:上面的分析结果是正确的,我用其他方法求出来的结果一样。


我相信总有一片天空属于我!http://myseeker. E-Mail:lwqcny@
2005-06-08 22:56
zefil415
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-6-4
收藏
得分:0 
非常感谢非常感谢!!!
或许是由于本人的水平问题,还有些不太懂,但是我会认真去阅读几遍的.我想这对我会有很大的帮助的.
我在此再一次谢过了!!!

提一个小小的问题:就是能不能通过改变其中的赋值关系来改变计算的精确度???
2005-06-08 23:50
zefil415
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-6-4
收藏
得分:0 
#include&lt;stdlib.h&gt;
#include&lt;stdio.h&gt;
main(I,O,O0,OO,l)
int I,O0,OO,l;
char **O;
{
    return !!I&gt;=I?!I&gt;=I?!!~I&gt;=~I?!~I&gt;=~I?!OO?!I:OO%2?
        OO=main(I,O,O0,OO&gt;&gt;!!OO,l),
        OO=main(I-!I-!!I,O,OO,OO,l),
        OO=main(I-!I-!!I,O,O0,OO,l),
        !(OO-!I||I)?l-1:OO
    :(OO=main(I,O,O0,OO&gt;&gt;!!OO,l),
        !(OO-l+!I||I)?l-1:main(I-!I-!!I,O,OO,OO,l))
    :(O0+OO)%l
    :main(I-I/I-I/I,O,O0,OO+OO/OO,
        main(0,O,O0,OO,I-I-I)+I+1?1:printf("%d ",I-I-I)+fflush(stdout))
    :main(I-I-I-I-I,O,I+I-I+I,I,0),
}


这是一个计算素数个数的程序段,运行的时候好像出现了一点小小的问题,希望大侠能给看一看.小弟将不胜感激~~~~~~


还有问一点:C不是说只能有唯一一个main()作为程序段的入口吗???为什么在这里却有着这么多个的main()???

希望大侠们就抽出一点点的时间给予解答一下!!!


随便提一下,大家有没有学习C的好网站,论坛之类的,希望给提供一二个作为学习之用.

不胜感激!!!

2005-06-08 23:55
seeker
Rank: 1
等 级:新手上路
帖 子:172
专家分:0
注 册:2005-6-5
收藏
得分:0 

/*贴一个求素数个数的程序 */ /*求40亿以内的素数*/

#include <iostream.h> #include <math.h> #include <windows.h>

const unsigned default_n=4000000000; const int maxlen=1000;

int primes[maxlen]; int len; int sum; unsigned int n; int m=7; int Q=1; int phiQ=1; int* v;

bool string2int(unsigned int& n,char* s); void init(void); unsigned int phi(unsigned int x,int a);

void main(void){ char number_string[80]; unsigned int time;

cout<<"calc pi(n)\n"; cout<<"n(default = "<<default_n<<") = ";//默认4000000000 cin.get(number_string,80); if(!string2int(n,number_string))n=default_n; time=GetTickCount(); init(); int num=(int)phi(n,len)-sum+len-1; time=GetTickCount()-time; GlobalFree(v); cout<<"pi(n)="<<num<<"("<<time<<"ms)\n"; cout<<"press any key to continue..."; cin.get(); cin.get(); }

void init(void){ int max; int sqrt_max; bool* mark; int i,j; int len2,len3; int s;

max=(int)(pow(1.0*n,2.0/3.0)+1.5); sqrt_max=(int)(sqrt(max)+0.5); mark=(bool*)GlobalAlloc(GMEM_FIXED|GMEM_ZEROINIT,max); for(i=2;i<sqrt_max;++i){ if(!mark[i]){ j=i*i; while(j<max){ mark[j]=true; j+=i; } } }

for(len=0,i=2;(unsigned)i*i*i<=n;++i){ if(!mark[i])primes[++len]=i; }

for(j=max-1,sum=0,s=0,len2=len;(unsigned)i*i<=n;++i){ if(!mark[i]){ ++len2; while((unsigned)i*j>n){ if(!mark[j])++s; --j; } sum+=s; } }

for(len3=len2;i<max;++i){ if(!mark[i])++len3; }

sum=(len2-len)*len3-sum; sum+=len*(len-1)/2-len2*(len2-1)/2;

if(m>len)m=len; for(i=1;i<=m;++i){ Q*=primes[i]; phiQ*=primes[i]-1; }

v=(int*)GlobalAlloc(GMEM_FIXED,Q*sizeof(int)); for(i=0;i<Q;++i)v[i]=i; for(i=1;i<=m;++i){ for(j=Q-1;j>=0;--j){ v[j]-=v[j/primes[i]]; } } GlobalFree(mark); }

bool string2int(unsigned int& n,char* s){ unsigned int val=0; for(int i=0;s[i];++i){ if(s[i]>'9'||s[i]<'0')return false; val*=10; val+=s[i]-'0'; if(val>default_n)return false; } n=val; return true; }

unsigned int phi(unsigned int x,int a){ if(a==m){ return (x/Q)*phiQ+v[x%Q]; } if(x<(unsigned)primes[a]){ return 1; } return phi(x,a-1)-phi(x/primes[a],a-1); }


我相信总有一片天空属于我!http://myseeker. E-Mail:lwqcny@
2005-06-09 00:11
zefil415
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-6-4
收藏
得分:0 
运行的时候好像有出现小点的错误,不知你运行的时候会不会啊???

你有没有好的学习站点,希望共享???

非常感激你的解答!!!
2005-06-09 00:44
seeker
Rank: 1
等 级:新手上路
帖 子:172
专家分:0
注 册:2005-6-5
收藏
得分:0 
我贴的程序都经过自己的验证,没问题啊,我用VC编译的,很少用TC,用TC编译,我会特别注明的。 http://v1.bbs.zol.com.cn/frmView.php http://www.thysea.com/lb/cgi-bin/forums.cgi?forum=127 http://vcok.com/class/index.asp http://www.cstudyhome.com/wenzhang06/default.asp 看看,我还有一些不能一一贴出来了,有卖广告的嫌疑,呵呵。

我相信总有一片天空属于我!http://myseeker. E-Mail:lwqcny@
2005-06-09 12:21
softwarelan
Rank: 1
等 级:新手上路
帖 子:209
专家分:0
注 册:2005-6-1
收藏
得分:0 
有点难度,让我算算了

Not a hero until you reach The Greatwall!
2005-06-09 16:09
yuanjue
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2005-4-26
收藏
得分:0 
热心啊

++生命如歌,我爱生命更爱生活,我的未来不是梦 ◢◤說過〾█◤☆◥◤☆◥█ 〾愛上◥◣ ◥◣的話⿶█☆ ╭╩╮ ☆█ ⿶的人◢◤ ◢◤不可⿸█◣☆╲╱☆◢█ ⿸不可◥◣ ◥◣不算⿷██◣ ☆ ◢██ ⿷再換◢◤
2005-06-13 14:13
快速回复:[原创]绝对挑战
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018293 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved