一个无限等边三角形网格(数字表示网点的序号)，如下面图所示：
1
/ \
2---3
/ \ / \
4---5---6
/ \ / \ / \
7---8---9--10
/ \ / \ / \ / \
11--12--13--14--15
/ \ / \ / \ / \ / \
16--17--18--19--20--21
...........................
例如：
{1，2，3}、{3，8，10}、{1，11，15}是等边三角形的顶点集合
{1，2，3，4}和{3，8，10，14}是平行四边形的顶点集合
{2，3，4，6，8，9}是六边形的顶点集合写一个算法，判断输入的集合属于可以接受的图形
一个图形要成为可接受的图形，必须满足如下两个条件：
1、图形每条边必须和网格中的某条边重合(如：{2，9}是重合的，而{2，13}则不是)；
2、图形每条边必须相等。输入
元素个数为3、4、6的元素列表输出
是否可接受输入出范例
1,2,3=true
1,2,3,4=false
2,3,4,6,8,9=true调试代码
private bool Calc(int[] APoints)
{
//TODO
}
private void button1_Click(object sender, EventArgs ce)
{
textBox1.AppendText(string.Format("1,2,3={0}",
Calc(1, 2, 3)));
textBox1.AppendText(string.Format("1,2,3,4={0}",
Calc(1, 2, 3, 4)));
textBox1.AppendText(string.Format("2,3,4,6,8,9={0}",
Calc(2, 3, 4, 6, 8, 9)));
//...
}
1
/ \
2---3
/ \ / \
4---5---6
/ \ / \ / \
7---8---9--10
/ \ / \ / \ / \
11--12--13--14--15
/ \ / \ / \ / \ / \
16--17--18--19--20--21
...........................
例如：
{1，2，3}、{3，8，10}、{1，11，15}是等边三角形的顶点集合
{1，2，3，4}和{3，8，10，14}是平行四边形的顶点集合
{2，3，4，6，8，9}是六边形的顶点集合写一个算法，判断输入的集合属于可以接受的图形
一个图形要成为可接受的图形，必须满足如下两个条件：
1、图形每条边必须和网格中的某条边重合(如：{2，9}是重合的，而{2，13}则不是)；
2、图形每条边必须相等。输入
元素个数为3、4、6的元素列表输出
是否可接受输入出范例
1,2,3=true
1,2,3,4=false
2,3,4,6,8,9=true调试代码
private bool Calc(int[] APoints)
{
//TODO
}
private void button1_Click(object sender, EventArgs ce)
{
textBox1.AppendText(string.Format("1,2,3={0}",
Calc(1, 2, 3)));
textBox1.AppendText(string.Format("1,2,3,4={0}",
Calc(1, 2, 3, 4)));
textBox1.AppendText(string.Format("2,3,4,6,8,9={0}",
Calc(2, 3, 4, 6, 8, 9)));
//...
}
我做 类似的 用来另外 一种 数据结构
THole = record
X: integer;
Y: integer;
UserIdx: integer;
GroundBmpIdx: integer;
nextIdx: array[0..5] of integer; //0。。5 表示六个方向
end;
THole = record
X: integer;
Y: integer;
UserIdx: integer;
GroundBmpIdx: integer;
nextIdx: array[0..5] of integer; //0。。5 表示六个方向
end;
因为 跳棋 是六角的
用起来 很方便
1、将输入的数从小到大排序
2、确定每个数所在的层（找出使得n*(n+1)/2最接近该数的n）
3、判断是否存在同一层的数，若存在，记下它们的差，该值即边长。
4、对于不同层之间的两数（层数分别是N1，N2，值分别是n1,n2）是否构成边的判断：n2-1n1是否等于N1*(N2-N1)或(N1+1)*(N2-N1)
5、两两判断后，对于所构成边的长统计是否有输入数的个数个边相等，若有则存在。
完毕
private bool Calc(params int[] APoints)
{
//TODO
return true;
}
using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
class Program
{
static private bool Calc(int[] APoints)
{
//TODO
List<MyPoint> list = new List<MyPoint>();
for (int i = 0; i < APoints.Length; i++)
{
list.Add(GetPoint(APoints[i]));
}
List<int> length = new List<int>();
for (int i = 0; i < list.Count; i++)
{
int XCount = 1;
int YCount = 1;
for (int j = i + 1; j < list.Count; j++)
{
if (list[i].x == list[j].x)
XCount++;
if (list[i].y == list[j].y)
YCount++;
length.Add(GetLength(list[i], list[j]));
}
if (XCount >= 3 || YCount >= 3)
return false;
}
while (length.Remove(-1)) { }; int len1 = length.Count;
int val = length[0];
while (length.Remove(val)) { };
int len2 = length.Count; if (len1 - len2 >= APoints.Length)
return true;
else
return false;
}
static void Main(string[] args)
{
Console.WriteLine(Calc(new int[] { 3, 8, 10,19 }));
Console.Read();
} static int GenNum(int i)
{
if (i == 1)
return 1;
else
{
return GenNum(i-1) + i-1;
}
} static MyPoint GetPoint(int Num)
{
for (int i = 1; i < 1000; i++)
{
int num = GenNum(i);
if (num <= Num && num + i -1 >= Num)
{
MyPoint point = new MyPoint();
point.x = i;
point.y = Num - num;
return point;
}
}
//灭找到 不可能吧?
return new MyPoint();
} static bool CheckLine(MyPoint a, MyPoint b)
{
if(a.x == b.x || a.y == b.y || (a.x != b.x && a.y !=b.y && a.x - b.x == a.y - b.y) )
return true;
else
return false;
} static int GetLength(MyPoint a, MyPoint b)
{
if (!CheckLine(a, b))
return -1;
if (a.x == b.x)
return Math.Abs(a.y - b.y);
else
return Math.Abs(a.x - b.x);
} struct MyPoint
{
public int x;
public int y;
}
}
}
while (length.Remove(val)) { };
这个计算不是很好,因该取概率最多的数来移除,我偷懒了.
Console.WriteLine(Calc(new int[] { 3, 8, 10, 19 }));
Console.WriteLine(Calc(new int[] { 1, 2, 3 }));
Console.WriteLine(Calc(new int[] { 1, 2, 3, 4 }));
Console.WriteLine(Calc(new int[] { 8, 9, 13, 14 }));
Console.WriteLine(Calc(new int[] { 4, 6, 11, 24, 26, 15 }));
Console.WriteLine(Calc(new int[] { 12, 14, 25, 27 }));
static int GenNum(int i)
static MyPoint GetPoint(int Num)
似乎可以再优化，让效率再高点．或者算到１０００层以上；
X = Index - Y * (Y + 1) / 2;
X = Index - Y * (Y + 1) / 2;
----------------------------------------
看不懂-_-#我坐标是乱定的,X是Y轴,1起,Y是X轴,0起...
如果按照标准坐标来做的话,是否有什么几何规律或者矢量什么的来快速确定这些东西?
{
MyPoint point = new MyPoint();
point.x = (int)((Math.Sqrt(8 * (Num - 1) + 1) + 1) / 2) - 1;
point.y = (Num - 1) - point.x * (point.x + 1) / 2;
point.x++;
return new MyPoint();
}
static MyPoint GetPoint(int Num)
{
MyPoint point = new MyPoint();
point.x = (int)((Math.Sqrt(8 * (Num - 1) + 1) + 1) / 2) - 1;
point.y = (Num - 1) - point.x * (point.x + 1) / 2;
point.x++;
return point; //<<<
}
namespace WindowsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private bool Calc(params int[] APoints)
{
List<Point> list = new List<Point>();
for (int i = 0; i < APoints.Length; i++)
list.Add(GetPoint(APoints[i]));
List<int> length = new List<int>();
for (int i = 0; i < list.Count; i++)
{
int XCount = 1;
int YCount = 1;
for (int j = i + 1; j < list.Count; j++)
{
if (list[i].X == list[j].X)
XCount++;
if (list[i].Y == list[j].Y)
YCount++;
length.Add(GetLength(list[i], list[j]));
}
if (XCount >= 3 || YCount >= 3)
return false;
}
while (length.Remove(-1)) { }; int len1 = length.Count;
int val = length[0];
while (length.Remove(val)) { };
int len2 = length.Count;
return len1 - len2 >= APoints.Length;
}
private Point GetPoint(int Num)
{
Point point = new Point();
point.Y = (int)((Math.Sqrt(8 * (Num - 1) + 1) + 1) / 2) - 1;
point.X = (Num - 1) - point.Y * (point.Y + 1) / 2;
return point;
}
private bool CheckLine(Point a, Point b)
{
return (a.X == b.X || a.Y == b.Y ||
(a.X != b.X && a.Y != b.Y && a.X - b.X == a.Y - b.Y));
} private int GetLength(Point a, Point b)
{
if (!CheckLine(a, b)) return -1;
if (a.X == b.X)
return Math.Abs(a.Y - b.Y);
else return Math.Abs(a.X - b.X);
} private void button1_Click(object sender, EventArgs e)
{
Console.WriteLine(Calc(3, 8, 10, 19));
Console.WriteLine(Calc(1, 2, 3));
Console.WriteLine(Calc(1, 2, 3, 4));
Console.WriteLine(Calc(8, 9, 13, 14));
Console.WriteLine(Calc(4, 6, 11, 24, 26, 15));
Console.WriteLine(Calc(12, 14, 25, 27));
}
}
}
if (len1 - len2 >= APoints.Length)
return true;
else
return false;这样更爽一些
return len1 - len2 >= APoints.Length;
呵呵 习惯问题
那个韦达定理你怎么找到的-_-#!
>那个韦达定理你怎么找到的-_-#!做过四年的游戏程序，其中有跳棋，那个坐标换算这个差不多
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
SZSJ s1 = new SZSJ(new int[] { 1, 2, 3, 4 });
SZSJ s2 = new SZSJ(new int[] { 2, 3, 4, 6, 8, 9 });
SZSJ s3 = new SZSJ(new int[] { 7, 9, 18, 20 });
SZSJ s4 = new SZSJ(new int[] { 11, 12, 13, 16 });
Console.WriteLine(s1);
Console.WriteLine(s2);
Console.WriteLine(s3);
Console.WriteLine(s4);
Console.Read();
} }
class NumberPoint
{
public int Number;
public int Level;
public override string ToString()
{
return Number.ToString();
}
}
class Line {
public NumberPoint X;
public NumberPoint Y;
public Line(NumberPoint x, NumberPoint y)
{
X = x;
Y = y;
}
//该点是否为该线段上的2点之一
public bool IndexOf(NumberPoint n) {
if (n.Number == X.Number || n.Number == Y.Number) return true;
return false;
}
//2点间距离
public int Distance
{
get
{
if (X.Level == Y.Level)
{
return Math.Abs(X.Number - Y.Number);
}
else
{
return Math.Abs(X.Level - Y.Level);
}
}
}
//判断是否在同一直线上,+3重载
public static bool IsOneLine(NumberPoint a, NumberPoint b)
{
if (a.Level == b.Level) return true;
NumberPoint Big = a.Level > b.Level ? a : b;
NumberPoint Small = a.Level > b.Level ? b : a;
int left = 0;
int right = 0;
for (int i = Small.Level; i < Big.Level; i++)
{
left += i;
right += i + 1;
}
int h = Big.Number - Small.Number;
if (h == left || h == right)
{
return true;
}
else
{
return false;
}
} public static bool IsOneLine(Line line, NumberPoint point)
{
if (line.X.Level == line.Y.Level)
{
if (point.Level != line.X.Level)
{
return false;
}
else
{
return true;
}
}
else if (point.Level == line.X.Level || point.Level == line.Y.Level)
{
return false;
}
else {
return IsOneLine(line.X, point) && IsOneLine(line.Y, point);
}
} public bool IsOneLine(NumberPoint point) {
return IsOneLine(this,point);
}
}
class SZSJ {
private List<NumberPoint> Points = new List<NumberPoint>();
private List<Line> Lines = new List<Line>();
private StringBuilder Log=new StringBuilder("日志:\r\n");//调试用的,日志
public SZSJ(int[] numbers) {
for (int i = 0; i < numbers.Length; i++) {
NumberPoint ln = new NumberPoint();
ln.Number = numbers[i];
ln.Level = GetLevel(ln.Number);
Points.Add(ln);
} //添加日志,可不用理解
Log.Append("顶点:{ ");
for (int i = 0; i < numbers.Length; i++) {
Log.Append(numbers[i]);
Log.Append(" ");
}
Log.Append("}\r\n");
} //获得一个点在该数字三角的深度
private static int GetLevel(int num)
{
int top = 1;
int level = 1;
while (true)
{
if (num < top) return level - 1;
top += level;
level++;
}
}
//分析所有点,组合边,对角线
private bool Execute()
{
for(int i=0;i<Points.Count;i++)
{
foreach (Line line in Lines)
{
if (line.IndexOf(Points[i])==false&&line.IsOneLine(Points[i]))
{
Log.AppendFormat
("出现有3个点处在同一直线上,出错位置:\r\n{0}--{1}--{2}",
line.X,line.Y, Points[i]);
return false;
}
}
for (int j = i; j < Points.Count; j++)
{
if (i == j) continue;
if (Line.IsOneLine(Points[i], Points[j]))
{
Log.AppendFormat("{0}和{1}创建一条直线\r\n", Points[i], Points[j]);
Lines.Add(new Line(Points[i], Points[j]));
}
}
} //检查有没有点没和其它点配对
int right = 0;
foreach (NumberPoint p in Points) {
foreach (Line line in Lines)
{
if (line.IndexOf(p))
{
right++;
break;
}
}
}
if (right < Points.Count)
{
Log.Append("\r\n有一个点无法跟其它点配对!");
return false;
} //为所有点配对了.接下来检查所有线段的长度
//由于对角线也连上了,所以要做出排除
//由于该数字三角的特点,菱形的对角线跟其它边是相等的
//所以只剩下等边六边形了
int theDistance = Lines[0].Distance;
int theDistance2=0;
foreach (Line line in Lines) {
int D = line.Distance;
Log.AppendFormat("{0},{1}边的边距为{2}\r\n", line.X, line.Y, D);
if (D != theDistance && D != theDistance2)
{
if (theDistance2 == 0&&Points.Count==6)
{
theDistance2 = D;
}
else
{
Log.Append("\r\n有一条边边距与其它边不一样");
return false;
}
}
}
return true;
}
public override string ToString()
{
return Execute().ToString()+"\r\n"+Log.ToString();
}
}}
#include <list>
#include <iostream>
#include "stdio.h"
using namespace std; bool CalAngle(int *num, int *lines, int agrc);
int GetLine(int exp);int _tmain(int argc, _TCHAR* argv[])
{
if (argc <= 1)
{
return 0;
} int *num = new int[argc - 1];
int *lines = new int[argc - 1];
if (num == NULL || lines == NULL)
{
cout << "分配内存失败！" << endl;
return 0;
} memset(num, 0, argc - 1);
memset(lines, 0, argc - 1); for(int i = 1; i < argc; i++)
{
sscanf((char*)argv[i], "%d", num + i - 1);
}
if (CalAngle(num, lines, argc - 1))
{
cout << "true" << endl;
}
else
{
cout << "false" << endl;
}
delete[] num;
delete[] lines;
return 0;
}//求两点之间距离
int GetDistance(int m, int n, int l1, int l2)
{
int temp = n;
if (m < n)
{
temp = m;
m = n;
n = temp;
} if (l1 < l2)
{
temp = l1;
l1 = l2;
l2 = temp;
} //判断是否在同一层上
int ilen = 0;
if (l1 == l2 )
{
//ic++;
ilen = m - n; //abs(m - n);
return ilen;
}
//左边
int imax = m;
int icurvalue = n;
for(int k = l2; k < l1; k++)
{
icurvalue += k;
if ( icurvalue > imax)
{
break;
}
else if (icurvalue == imax)
{
ilen = abs(l1 - l2);
return ilen;
}
} //右边
icurvalue = n;
for(int i = l2; ilen == 0 && i < l1; i++)
{
icurvalue += (i + 1);
if ( icurvalue > imax)
{
break;
}
else if (icurvalue == imax)
{
ilen = l1 - l2;
return ilen;
}
}
return 0;
}bool CalAngle(int *num, int *lines, int points)
{
int ilen = 0;
int ioldlen = 99999;
int *pd = new int[points * points]; //各个点之间距离
memset(pd, 0, points * points);
for(int i = 0; i < points; i++)
{
*(lines + i) = GetLine(*(num + i));
} //求出两点之间的最小距离
for(int i = 0; i < points; i++)
{
for( int j = 0; j < points; j++)
{
if (i == j)
continue;
ilen = GetDistance(num[i], num[j], lines[i], lines[j]);
pd[i * points + j] = ilen;
if (ilen > 0 && ilen < ioldlen)
{
ioldlen = ilen;
}
}
}
//某一点到相邻的点的距离等于最小距离的个数不为2就不符合条件
for(int i = 0; i < points; i++)
{
int ic = 0;
for( int j = 0; j < points; j++)
{
if (i == j)
{
continue;
}
//int ilen = GetDistance(num[i], num[j], lines[i], lines[j]);
if ( pd[i * points + j] == ioldlen )
{
ic++;
}
} if (ic != 2)
{
delete[] pd;
return false;
}
} delete[] pd;
return true;
}//获取某个数字所在的行数
int GetLine(int exp)
{
long sum = 0;
for(int i = 1; i < 10000; i++)
{
sum += i;
if ( exp <= sum )
{
return i;
}
}
}
int GetLine(int exp)
{
long sum = 0;
for(int i = 1; i < 10000; i++)
{
sum += i;
if ( exp <= sum )
{
return i;
}
}
}上面的代码已经对这样有优化