// chp2.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
//数据结构
//数组(Array)、堆栈(Stack)、队列(queue)、链表(Linked List)、树(Tree)、图(Grahp)、堆(Heap)、散列表(Hash)
//
// 判断是否为2的n次幂
bool PowofTwo(int n)
{
return !(n & (n-1));
}
//
// 利用割圆术求pi的近似值， 假设有一个半径是1的圆，第一次切割在其内部内接正六边形。
// 正六边形的变长为y1, 根据几何知识，y1=1, 圆周长近似为L1=6*y1
// 第二次切割，在正六边形的基础上，扩展为12边形时，边长为y2, y2^2=2-sqrt(4-y1^2)
// pi≈3*2^n*yn
double cyclotomic(int n)
{
double k, yy;
int i;
long s;
double pi = 0.0f;
i = 1; //第一次切割
s = 6; //初始为6边形
yy = 1.0f;
k = 3.0f;
while (i<=n)
{
pi = k*sqrt(yy);
printf("第%d次切割，为正%ld多边形，PI近似为%.24f\n", i, s, pi);
s *= 2; //边数加倍
yy = 2-sqrt(4-yy); //内接多边形的变长的平方值
k *= 2.0f; //累积前面的系数3*2^n
i++;
}
return pi;
}
//
// 蒙特卡罗算法（Monte Carlo）
// 一个半径为1的圆，他在第一象限的1/4圆面积为pi/4
// 在上面接一个正方形，面积为1，两者相比pi/4, 概率算法
// 随即产生一个点，判断是不是在圆形区域，比上总点数，即为pi/4
double MontePI(int n)
{
int sum;
double pi;
double x, y;
sum = 0;
srand((unsigned)time(NULL));
for (int i=0; i<n; i++)
{
x = (double)rand()/RAND_MAX; //产生0~1的随机数
y= (double)rand()/RAND_MAX;
if ((x*x + y*y) <= 1)
sum++;
}
pi = 4.0*sum/n;
return pi;
}
int _tmain(int argc, _TCHAR* argv[])
{
int *pnums = new int[100];
memset(pnums, 0, 100);
srand((unsigned)time(NULL));
int num8;
int temp;
for (int i = 0; i<100; i++)
{
pnums[i] = rand()%500;
num8 = (pnums[i] + 0x7)&~0x7; //两种方法将数字提升到8的倍数
temp = (pnums[i] + 0x7)/8*8;
printf("%d->%d, %d", pnums[i], num8, temp);
if (PowofTwo(pnums[i]))
{
printf("--->pow of two");
}
printf("\n"); //换行
}
printf("\n\n");
//clean:
delete[] pnums;
//
//计算pi的近似值
printf("计算pi的近似值\n");
cyclotomic(12);
printf("\n\n");
for (int i=1; i<10; i++)
{
printf("Monte Carlo pi = %.24f\n", MontePI(i*1000) );
}
return 0;
}
392->392, 392
35->40, 40
51->56, 56
72->72, 72
245->248, 248
15->16, 16
158->160, 160
252->256, 256
158->160, 160
122->128, 128
154->160, 160
334->336, 336
82->88, 88
96->96, 96
192->192, 192
101->104, 104
116->120, 120
52->56, 56
94->96, 96
257->264, 264
58->64, 64
70->72, 72
337->344, 344
67->72, 72
382->384, 384
142->144, 144
25->32, 32
492->496, 496
14->16, 16
469->472, 472
217->224, 224
363->368, 368
387->392, 392
317->320, 320
233->240, 240
415->416, 416
199->200, 200
422->424, 424
217->224, 224
472->472, 472
184->184, 184
498->504, 504
92->96, 96
244->248, 248
172->176, 176
44->48, 48
133->136, 136
390->392, 392
440->440, 440
373->376, 376
341->344, 344
246->248, 248
214->216, 216
183->184, 184
465->472, 472
103->104, 104
83->88, 88
123->128, 128
141->144, 144
37->40, 40
71->72, 72
152->152, 152
333->336, 336
257->264, 264
62->64, 64
240->240, 240
170->176, 176
292->296, 296
490->496, 496
139->144, 144
32->32, 32--->pow of two
55->56, 56
190->192, 192
54->56, 56
376->376, 376
163->168, 168
35->40, 40
273->280, 280
233->240, 240
79->80, 80
21->24, 24
436->440, 440
59->64, 64
485->488, 488
4->8, 8--->pow of two
118->120, 120
97->104, 104
123->128, 128
383->384, 384
215->216, 216
482->488, 488
315->320, 320
369->376, 376
433->440, 440
102->104, 104
305->312, 312
290->296, 296
417->424, 424
451->456, 456
363->368, 368
计算pi的近似值
第1次切割，为正6多边形，PI近似为3.000000000000000000000000
第2次切割，为正12多边形，PI近似为3.105828541230249800000000
第3次切割，为正24多边形，PI近似为3.132628613281236900000000
第4次切割，为正48多边形，PI近似为3.139350203046872100000000
第5次切割，为正96多边形，PI近似为3.141031950890529800000000
第6次切割，为正192多边形，PI近似为3.141452472285344300000000
第7次切割，为正384多边形，PI近似为3.141557607911622100000000
第8次切割，为正768多边形，PI近似为3.141583892148935900000000
第9次切割，为正1536多边形，PI近似为3.141590463236761700000000
第10次切割，为正3072多边形，PI近似为3.141592106043048300000000
第11次切割，为正6144多边形，PI近似为3.141592516588154600000000
第12次切割，为正12288多边形，PI近似为3.141592618640789400000000
Monte Carlo pi = 3.192000000000000200000000
Monte Carlo pi = 3.206000000000000000000000
Monte Carlo pi = 3.173333333333333300000000
Monte Carlo pi = 3.141000000000000000000000
Monte Carlo pi = 3.138399999999999900000000
Monte Carlo pi = 3.133999999999999900000000
Monte Carlo pi = 3.129142857142857000000000
Monte Carlo pi = 3.123499999999999900000000
Monte Carlo pi = 3.125777777777778000000000
请按任意键继续. . .