- 注册时间
- 2010-4-21
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 7299
- 在线时间
- 小时
|
发表于 2019-12-2 18:43:43
|
显示全部楼层
本帖最后由 chyanog 于 2019-12-2 19:35 编辑
更新到第8项
(1), 0, 20, 0
(2), 140, 216, 44
(3), 4456, 1224, 2320
(4), 97232, 7968, 54800
(5), 1999432, 54456, 1146112
(6), 40353584, 367944, 23278472
(7), 809527216, 2444520, 468028264
(8), 16206910376, 16284576, 9376805048
代码没有根据对称性作优化,时间复杂度O(20^n),还有很大优化空间,计算到第8项需要十五六分钟。
- #include <stdio.h>
- #include <math.h>
- #include <time.h>
- #define MAX(x, y) (((x) > (y)) ? (x) : (y))
- #define MIN(x, y) (((x) < (y)) ? (x) : (y))
- unsigned __int64 in_count, out_count;
- void f(double x, double y, double z, int m, int n)
- {
- double d = 2 * pow(3, -n);
- if (n == 0)
- {
- double r = pow(3, -m);
- double d1, d2, d3, d4, d5, d6, d7, d8;
- d1 = pow(x + r, 2) + pow(y + r, 2) + pow(z + r, 2);
- d2 = pow(x + r, 2) + pow(y + r, 2) + pow(z - r, 2);
- d3 = pow(x + r, 2) + pow(y - r, 2) + pow(z + r, 2);
- d4 = pow(x + r, 2) + pow(y - r, 2) + pow(z - r, 2);
- d5 = pow(x - r, 2) + pow(y + r, 2) + pow(z + r, 2);
- d6 = pow(x - r, 2) + pow(y + r, 2) + pow(z - r, 2);
- d7 = pow(x - r, 2) + pow(y - r, 2) + pow(z + r, 2);
- d8 = pow(x - r, 2) + pow(y - r, 2) + pow(z - r, 2);
- if (MAX(MAX(MAX(MAX(MAX(MAX(MAX(d1, d2), d3), d4), d5), d6), d7), d8) < 1)
- {
- in_count++;
- }
- if (MIN(MIN(MIN(MIN(MIN(MIN(MIN(d1, d2), d3), d4), d5), d6), d7), d8) > 1)
- {
- out_count++;
- }
- }
- else
- {
- f(x - d, y - d, z - d, m, n - 1);
- f(x - d, y - d, z, m, n - 1);
- f(x - d, y - d, z + d, m, n - 1);
- f(x - d, y, z - d, m, n - 1);
- f(x - d, y, z + d, m, n - 1);
- f(x - d, y + d, z - d, m, n - 1);
- f(x - d, y + d, z, m, n - 1);
- f(x - d, y + d, z + d, m, n - 1);
- f(x, y - d, z - d, m, n - 1);
- f(x, y - d, z + d, m, n - 1);
- f(x, y + d, z - d, m, n - 1);
- f(x, y + d, z + d, m, n - 1);
- f(x + d, y - d, z - d, m, n - 1);
- f(x + d, y - d, z, m, n - 1);
- f(x + d, y - d, z + d, m, n - 1);
- f(x + d, y, z - d, m, n - 1);
- f(x + d, y, z + d, m, n - 1);
- f(x + d, y + d, z - d, m, n - 1);
- f(x + d, y + d, z, m, n - 1);
- f(x + d, y + d, z + d, m, n - 1);
- }
- }
- int main()
- {
- clock_t t0 = clock();
- for (int i = 1; i <= 6; i++)
- {
- in_count = 0;
- out_count = 0;
- f(0, 0, 0, i, i);
- printf("(%d), %llu, %llu, %llu\n", i, out_count, (__int64)pow(20, i) - out_count - in_count, in_count);
- }
- printf("Elapsed time %0.4fs\n", (clock() - t0) / 1000.0);
- return 0;
- }
复制代码 |
|