无心人
发表于 2013-3-19 14:23:15
立体情况下
(1,1)
(2,36)
(3,372)
(4,2032)
(5,8107)
(6,24986)
(7,66688)
(8,155896)
chyanog
发表于 2013-3-19 15:45:51
31# 无心人
有通项公式就更好了
那是不可能的
wayne
发表于 2013-3-19 15:51:34
31# 无心人
新数列么,貌似在OEIS上搜不到
无心人
发表于 2013-3-19 16:06:56
奉上C++代码
#include <iostream>
using namespace std;
#define MAX 99
struct point3
{
int x, y, z, dp;
};
point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
int dp(int n,int x, int y,int z)
{
return (x + (n+1)*y + (n+1)*(n+1)*z);
}
void init(int n)
{
int x, y, z;
for (z=0;z<=n;z++)
for (y=0;y<=n; y++)
for (x=0;x<=n; x++)
{
int t= x+(n+1)*y+(n+1)*(n+1)*z;
point.x = x;
point.y = y;
point.z = z;
point.dp = dp(n, x, y, z);
}
}
int orth(point3 p0, point3 p1,point3 p2)
{
return ((p1.x-p0.x)*(p2.x-p0.x) + (p1.y-p0.y)*(p2.y-p0.y) + (p1.z-p0.z)*(p2.z-p0.z))==0;
}
void addp2(point3& r, point3 p0, point3 p1, point3 p2)
{
r.x=p1.x+p2.x-p0.x;
r.y=p1.y+p2.y-p0.y;
r.z=p1.z+p2.z-p0.z;
}
void addp3(point3& r, point3 p0, point3 p1, point3 p2, point3 p3)
{
r.x=p1.x+p2.x+p3.x-2*p0.x;
r.y=p1.y+p2.y+p3.y-2*p0.y;
r.z=p1.z+p2.z+p3.z-2*p0.z;
}
int inside(int n, point3 p)
{
return (p.x<=n)&&(p.x>=0)&&(p.y<=n)&&(p.y>=0)&&(p.z<=n)&&(p.z>=0);
}
long long calc(int n)
{
if (n < 1) return 0;
if (n == 1) return 1;
point3 t;
long long c=0;
init(n);
int max=(n+1)*(n+1)*(n+1)-1;
for (int i=0; i<=max-3; i ++)
for (int j=i+1; j<=max-2; j ++)
for (int k=j+1; k<=max-1; k ++)
if (orth(point, point, point))
for (int m=k+1; m<=max; m ++)
{
if (orth(point, point, point))
if (orth(point, point, point))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp3(t, point, point, point, point);
if (inside(n, t)) c++;
}
}
}
}
}
return c;
}
int main( void )
{
int n;
cout << "input: ";
cin >> n;
cout << endl;
if (n > MAX) cout << "input is to BIG" << endl;
cout << "total: " << calc(n);
return 0;
}
这个程序还可以深度优化的
无心人
发表于 2013-3-19 16:08:26
(9,332657)
(10,653708)
(11,1216076)
(12, 2135220)
(13,3604679)
(14,5845214)
(15,9160864)
(16,13947880)
(17,20778029)
(18,30205036)
(19,43114824)
无心人
发表于 2013-3-19 16:14:10
33# wayne
是的,我也搜不到
不过急需有人进行复检。。。
无心人
发表于 2013-3-19 19:29:27
优化了一下
数字较大时候,缩短的时间很可观
#include <iostream>
using namespace std;
#define MAX 99
struct point3
{
int x, y, z, dp;
};
point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
int dp(int n,int x, int y,int z)
{
return (x + (n+1)*y + (n+1)*(n+1)*z);
}
void init(int n)
{
int x, y, z;
for (z=0;z<=n;z++)
for (y=0;y<=n; y++)
for (x=0;x<=n; x++)
{
int t= x+(n+1)*y+(n+1)*(n+1)*z;
point.x = x;
point.y = y;
point.z = z;
point.dp = dp(n, x, y, z);
}
}
int orth(point3 p0, point3 p1,point3 p2)
{
return ((p1.x-p0.x)*(p2.x-p0.x) + (p1.y-p0.y)*(p2.y-p0.y) + (p1.z-p0.z)*(p2.z-p0.z))==0;
}
void addp2(point3& r, point3 p0, point3 p1, point3 p2)
{
r.x=p1.x+p2.x-p0.x;
r.y=p1.y+p2.y-p0.y;
r.z=p1.z+p2.z-p0.z;
}
void addp3(point3& r, point3 p0, point3 p1, point3 p2, point3 p3)
{
r.x=p1.x+p2.x+p3.x-2*p0.x;
r.y=p1.y+p2.y+p3.y-2*p0.y;
r.z=p1.z+p2.z+p3.z-2*p0.z;
}
int inside(int n, point3 p)
{
return (p.x<=n)&&(p.x>=0)&&(p.y<=n)&&(p.y>=0)&&(p.z<=n)&&(p.z>=0);
}
long long calc(int n)
{
if (n < 1) return 0;
if (n == 1) return 1;
point3 t;
long long c=0;
init(n);
int max=(n+1)*(n+1)*(n+1)-1;
for (int i=0; i<=max-(n+1)*(n+1)-3; i ++)
for (int j=i+1; j<=max-(n+1)*(n+1)-2; j ++)
for (int k=j+1; k<=max-(n+1)*(n+1)-1; k ++)
if (orth(point, point, point))
for (int m=k+1; m<=max; m ++)
{
if (orth(point, point, point))
if (orth(point, point, point))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp2(t, point, point, point);
if (inside(n, t))
{
addp3(t, point, point, point, point);
if (inside(n, t)) c++;
}
}
}
}
}
return c;
}
int main( void )
{
int n;
cout << "input: ";
cin >> n;
cout << endl;
if (n > MAX) cout << "input is to BIG" << endl;
cout << "total: " << calc(n);
return 0;
}