续 [caozhy] 板主的删除蓝莓算法

--------------------编程问答-------------------- 继续：



                // get the no repeat count num in total

                static int GetTotalCountOfETriangles(int[,] arrSource, List<TPoint> lstPoints)

                {

                        int totalCount = 0;

                        foreach (TPoint item in lstPoints)

                        {

                                totalCount += CountInPosition(arrSource, item);

                        }

                        return totalCount;

                }



                // get the count of triangles in one position

                // !! default --- must be const when compiled!!

                static int CountInPosition(int[,] arrSource, TPoint pntApex, string flag = "two")

                {

                        int x = pntApex.TX;

                        int y = pntApex.TY;



                        int step = 1;

                        int count = 0;

                        while (step < Layer)

                        {

                                count += CountAtOneStep(arrSource, pntApex, step, flag);

                                step++;

                        }

                        return count;

                }



                // get the count in this position by special step

                static int CountAtOneStep(int[,] arrSource, TPoint pntOne, int step, string direction = "two")

                {

                        int x = pntOne.TX;

                        int y = pntOne.TY;



                        // there may exist six ETriangles in one point, but can add up the totalCount in a certain order...



                        //at first  want to use 'Tuple<int,int>', but that may be a big trouble in definition



                        // !  can specify the search direction, then ignore the upper and left

                        // todo: to verify whether there exist missing points -- but for ten nums, check the right and bottom is enough, maybe

                        int[,] twoDirections = { 

                                   {0, 2},

                                   {1, 1},

                                   {1, 1}

                                   };

                        // all directions

                        int[,] sixDirections = { 

                            {-1, -1},

                            {-1, 1},

                            {0, 2},

                            {1, 1},

                            {1, -1},

                            {0, -2},

                            {-1, -1}

                            };

                        int[,] apexes = twoDirections;

                        if (direction == "six")

                                apexes = sixDirections;

                        int count = 0;

                        int row = apexes.GetLength(0);

                        for (int i = 0; i < row - 1; i++)

                        {

                                TPoint pntTwo = new TPoint(x + apexes[i, 0] * step, y + apexes[i, 1] * step);

                                TPoint pntThree = new TPoint(x + apexes[i + 1, 0] * step, y + apexes[i + 1, 1] * step);

                                if (IsETriangle(arrSource, pntOne, pntTwo, pntThree))

                                        count++;

                        }

                        return count;

                }



                //  Whether these three points can form an ETriangle

                static bool IsETriangle(int[,] arrSource, params TPoint[] pnts)

                {

                        foreach (TPoint item in pnts)

                        {

                                if (!IsValidNum(arrSource, item))

                                        return false;

                        }

                        return true;

                }



                //Judge whether the position is valid in an array

                static bool IsValidPoint(TPoint pnt)

                {

                        return pnt.TX >= 0 && pnt.TX < Row && pnt.TY >= 0 && pnt.TY < Col;

                }



                // Judge whether the value of current position is a valid num (1-10)

                static bool IsValidNum(int[,] arrSource, TPoint pnt)

                {

                        if (IsValidPoint(pnt))

                                return arrSource[pnt.TX, pnt.TY] > 0;

                        return false;

                }



                // remove the point -- set value: -1

                static void RemovePoint(int[,] arrSource, TPoint pnt)

                {

                        if (IsValidPoint(pnt))

                                arrSource[pnt.TX, pnt.TY] = -1;

                }

        }

        // new type, to save the position

        class TPoint

        {

                public int TX { get; set; }

                public int TY { get; set; }



                public TPoint() { }  // ctor without args to implement the object initializer



                public TPoint(int x, int y)

                {

                        this.TX = x;

                        this.TY = y;

                }



                public override string ToString()

                {

                        return String.Format("{0} - {1} ", this.TX, this.TY);

                }

        }

}

--------------------编程问答-------------------- 10个蓝莓的是：

又用15个蓝莓做下测试，结果：

不知道正确与否，目测无误。。

--------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- 我要是能看懂我都是那个.. --------------------编程问答-------------------- 技术贴要顶，不顶的写代码一堆bug的，楼下继续 --------------------编程问答-------------------- 技术贴要顶，不顶的写代码一堆bug的，楼下继续 --------------------编程问答--------------------

引用 9 楼 blueink_200451 的回复:

技术贴要顶，不顶的写代码一堆bug的，楼下继续

--------------------编程问答--------------------

引用 9 楼 blueink_200451 的回复:

技术贴要顶，不顶的写代码一堆bug的，楼下继续

太欺负人了。 --------------------编程问答--------------------

Quote: 引用 2 楼 Acc2013 的回复:

10个蓝莓的是：

不对呀！去掉1、2、6、8还有3、4、9可以组成等边三角形啊！！
同理，去掉1、3、4、9还有2、6、8
     去掉1、5、7、10还有3、4、9和2、6、8
     去掉2、6、7、8还有3、4、9
     去掉2、6、8、10还有3、4、9
     去掉3、4、7、9还有2、6、8
     去掉3、4、9、10还有2、6、8 --------------------编程问答--------------------
引用 8 楼 Joyhen 的回复:
技术贴要顶，不顶的写代码一堆bug的，楼下继续

求bug   跪求   否则到客户那就不是bug   出的就是money了 --------------------编程问答-------------------- 这个不是杨辉三角演变出来的嘛？ --------------------编程问答-------------------- 技术贴要顶，不顶的写代码一堆bug的，楼下继续   --------------------编程问答-------------------- 来学习一下，支持。。。。
€ --------------------编程问答-------------------- 目测结果已出来删除四个  只能是这几种

1,5,8,9
7,5,3,6
10,5,2,4

--------------------编程问答-------------------- 除 --------------------编程问答-------------------- 技术贴要顶，不顶的写代码一堆bug的，楼下继续

我要是能看懂，我就是那个~ --------------------编程问答-------------------- 除 --------------------编程问答--------------------
引用 8 楼 Joyhen 的回复:
技术贴要顶，不顶的写代码一堆bug的，楼下继续

--------------------编程问答-------------------- 除 --------------------编程问答--------------------
引用 22 楼 line_us 的回复:
Quote: 引用 8 楼 Joyhen 的回复:

技术贴要顶，不顶的写代码一堆bug的，楼下继续

--------------------编程问答-------------------- --------------------编程问答-------------------- 看不懂。 --------------------编程问答-------------------- 来个简单点的，但是同样没有考虑2,6,8和3,4,9.
using System;

using System.Collections.Generic;

using System.Linq;



namespace Triangle

{

    //                  0.0

    //               1.0   1.1

    //            2.0   2.1   2.2 

    //         3.0   3.1   3.2   3.3

    class Program

    {

        const int RowNumber = 4;



        static void Main()

        {

            var points = InitPoints();

            var equilateralTriangles = FindEquilateralTriangle(points);

            KickHighPriPoint(equilateralTriangles);

        }



        //初始化所有的节点

        private static IEnumerable<Point> InitPoints()

        {

            var points = new List<Point>();

            for (int i = 0; i < RowNumber; i++)

            {

                for (int j = 0; j <= i; j++)

                {

                    points.Add(new Point(i,j));

                }

            }



            return points;

        }



        private static IEnumerable<EquilateralTriangle> FindEquilateralTriangle(IEnumerable<Point> points)

        {

            var equilateralTriangles = new List<EquilateralTriangle>();

            foreach (var pointA in points)

            {

                //根据三个点之间的x,y间距相同作为判断等边三角形的依据,我们可以从一个点去找出能和它组成等边三角形的另外两个点。



                //以x间距为基准 找出所有的正三角

                for (int iSpace = 1; iSpace < RowNumber - pointA.X; iSpace++)

                {

                    var pointB = new Point(pointA.X + iSpace, pointA.Y);

                    var pointC = new Point(pointB.X, pointB.Y + iSpace);

                    equilateralTriangles.Add(new EquilateralTriangle(pointA, pointB, pointC));

                }



                //找出所有的倒立三角

                if (pointA.X != pointA.Y && pointA.Y < RowNumber - 1)

                {

                    for (int iSpace = 1; iSpace <= pointA.X - pointA.Y; iSpace++)

                    {

                        //最下方的节点不能超出RowNumber

                        if (pointA.X + iSpace < RowNumber)

                        {

                            var pointB = new Point(pointA.X, pointA.Y + iSpace);

                            var pointC = new Point(pointB.X + iSpace, pointB.Y);

                            equilateralTriangles.Add(new EquilateralTriangle(pointA, pointB, pointC));

                        }

                    }

                }

            }



            return equilateralTriangles;

        }



        private static void KickHighPriPoint(IEnumerable<EquilateralTriangle> equilateralTriangles)

        {

            //找出所有节点的出现频率

            var points = new List<Point>();

            foreach (var equilateralTriangle in equilateralTriangles)

            {

                points.Add(equilateralTriangle.A);

                points.Add(equilateralTriangle.B);

                points.Add(equilateralTriangle.C);

            }



            //找出出现最多的点

            var tempFrequency =

                points.GroupBy(r => r.Value)

                      .Select(r => new {count = r.Count(), key = r.Key})

                      .OrderByDescending(r => r.count);

            var kickedPointValue = tempFrequency.FirstOrDefault();



            //踢出这个点，如果还有等边三角形存在，重新查找并踢出

            if (kickedPointValue != null)

            {

                Console.WriteLine("Kick point is: " + kickedPointValue.key);

                var temp =

                    equilateralTriangles.Where(

                        r => r.A.Value != kickedPointValue.key

                        && r.B.Value != kickedPointValue.key

                        && r.C.Value != kickedPointValue.key).ToList();

                if (temp.Count > 0)

                {

                    KickHighPriPoint(temp);

                }

            }

        }

    }



    internal class EquilateralTriangle

    {

        public Point A { get; set; }

        public Point B { get; set; }

        public Point C { get; set; }



        public EquilateralTriangle(Point a, Point b, Point c)

        {

            A = a;

            B = b;

            C = c;

        }

    }



    internal class Point

    {

        //X表示在第几行 Y表示在第几列

        public int X { get; set; }

        public int Y { get; set; }

        public int Value

        {

            get { return StartIndex(X) + Y; }

        }



        private int StartIndex(int rowIndex)

        {

            var startIndex = 1;

            for (int i = 1; i < rowIndex + 1; i++)

            {

                startIndex += i;

            }

            return startIndex;

        }



        public Point(int x, int y)

        {

            X = x;

            Y = y;

        }

    }

}
--------------------编程问答--------------------
引用 13 楼 caohang1990 的回复:
不对呀！去掉1、2、6、8还有3、4、9可以组成等边三角形啊！！
同理，去掉1、3、4、9还有2、6、8

谢谢提醒，竟然忘记了，斜着的外层，也存在正三角形。。。。
怪不得，得出总的正三角形数是13的时候，总觉得有点问题，原来问题出在这里（不过当时我数的也是13，所以没有察觉），
这也好办，不过是再添加几个逻辑判断条件，容我再想想。。。 --------------------编程问答-------------------- OK，又添加了6个条件，（一个点上最多有12个正三角形呀，我只想到了6个，丢了一半呀。。。），算是出结果了，只有三种情况 == 18L的。
估计又要连三，就一块说说我的思路，这10 个蓝莓是：
0， 0， 0， 1， 0， 0， 0

0， 0， 2， 0， 3， 0， 0

0， 4， 0， 5， 0， 6， 0

7， 0， 8， 0， 9， 0， 10
首先，用数组存放这些数字的好处是，判断是否是等边三角形，不用算边长，只用坐标做个大体的估计，比如，用2点（x, y）做说明吧，
A，（2， 4， 5）是构成等边的：  则 4：（x+1, y-1）|  5：（x+1, y+1）

B，或者是倒过来的（2， 3， 5）   则 3：（x, y+2） |  5：（x+1, y+1）  --- 5是一样的，这一点很有用。。

C，然后就是那个我忽略掉的（2， 8， 6）  ----  则 8：（x+2, y） |  6：（x+3, y+1）

这是三个主要的正三角，再从一个一般的示例分析如图：

比如， 8点所生成的坐标为：（x + -1*step,  y+ -1 *step） -- step 为可控制三角形大小的递增变量，此时值为1，而当 step = 2 时，映射为 4点，依次类推
  另这些三角形（8， 9， 13），（9， 13， 14）。。都存在共用的点，可将他们放在首尾相接的数组中循环遍历，如
// all directions

 int[,] sixDirections = { 

     {-1, -1},  //inner

     {-1, 1},

   // 。。。。

     {0, -2},

     {-1, -1},   // end to end , but independent to the next

     {-2, 0},   // outer

     {-1, 3},

     // 。。。。

     {-1, -3},

     {-2, 0}

     };

//只需要在循环的时候，区分开内外两层即可：

for (int i = 0; i < row - 1; i++)

 {

         if (i == row / 2 - 1)   // to separate from the inner and the outer

                 i++;

         TPoint pntTwo = new TPoint(x + apexes[i, 0] * step, y + apexes[i, 1] * step);

         TPoint pntThree = new TPoint(x + apexes[i + 1, 0] * step, y + apexes[i + 1, 1] * step);

         if (IsETriangle(arrSource, pntOne, pntTwo, pntThree))

                 count++;

 }
第一部分，这算是对程序的补充吧，说的有点多，后面的也就简单了，因为对于要查找的点来说，与他相关的等边三角形的点的位置已经确定，下面就是要三个三个地判断这些位置是否合法 --- 不超界，值 > 0 (默认空白用0填充，删除当前点用 -1 替换) -- 就这么简单。。

还有一点就是这算是暴力破解，比如要删除三个点，需要三层循环来取出点，然后看这三个点删除后（赋值-1），判断其他点是否可构成等边三角形。。三个要是都不行的话，就用四个，依次递增，所以循环层数不定，可递归来动态确定循环，不解释了。。

然后正确结果为：
--------------------编程问答--------------------
引用 8 楼 Joyhen 的回复:
技术贴要顶，不顶的写代码一堆bug的，楼下继续
不是码农，毫无鸭梨。。。 --------------------编程问答--------------------
引用 27 楼 jack43349489 的回复:

@ jack43349489 ，看了你的代码，才知道什么是下里巴人，什么是阳春白雪，先不论别的，至少你的代码层次多么清晰明了，算法多么精简，而且思路好奇特绝对是我想不到的。。。。

还是分析分析下你的代码：你是直接把数字，用坐标存储，
（0， 0）  -- 1
（1， 0）  -- 2 。。。
然后根据这些坐标的关系，只将合法的顶点存入List中，至少在数据上是很优化的，省去了我那大数组，多循环的麻烦。。。

还有这个检测思路：把能构成等边三角形的点都先存起来，重复叠加，然后从最多的点依次开始删除，再判断。。。
而我这，算是纯粹的暴力算法穷举每一对组合数，而且对于每个点都是先做循环，再判断，（像这点1，哪里会需要12个，估计是12的也没几个）致使程序N多次地空转，做了多少无用功呀。。

再加上LINQ，我等只有膜拜的份。。。。。

唯一的不足就是，你木有写完，，赶紧地，咱再比对下，我这15个蓝莓的结果是：
--------------------编程问答--------------------
引用 16 楼 Mockqi 的回复:
技术贴要顶，不顶的写代码一堆bug的，楼下继续

nnd  码农必须顶啊 --------------------编程问答--------------------
引用 31 楼 Acc2013 的回复:
Quote: 引用 27 楼 jack43349489 的回复:

@ jack43349489 ，看了你的代码，才知道什么是下里巴人，什么是阳春白雪，先不论别的，至少你的代码层次多么清晰明了，算法多么精简，而且思路好奇特绝对是我想不到的。。。。

还是分析分析下你的代码：你是直接把数字，用坐标存储，
（0， 0）  -- 1
（1， 0）  -- 2 。。。
然后根据这些坐标的关系，只将合法的顶点存入List中，至少在数据上是很优化的，省去了我那大数组，多循环的麻烦。。。

还有这个检测思路：把能构成等边三角形的点都先存起来，重复叠加，然后从最多的点依次开始删除，再判断。。。
而我这，算是纯粹的暴力算法穷举每一对组合数，而且对于每个点都是先做循环，再判断，（像这点1，哪里会需要12个，估计是12的也没几个）致使程序N多次地空转，做了多少无用功呀。。

再加上LINQ，我等只有膜拜的份。。。。。

唯一的不足就是，你木有写完，，赶紧地，咱再比对下，我这15个蓝莓的结果是：

谢谢你的夸奖，其实如果把这个问题放大了看，我还真的不知道怎么处理2,6,8这种三角形，因为这个所谓的等边三角形只是看起来是具体是挺难用代码来判断他的。

你看这个图，4.10.17 和 4.10.18是不是等边三角形呢？如果是又应该怎么处理呢？呵呵一起讨论一下吧。 --------------------编程问答-------------------- Acc2013：坐标的思路是挺好的但是我现在真的不知道如果用坐标来找出斜三角的规律。当然了如果是用hardcode来完成这个问题那就真的没有什么价值了。 --------------------编程问答-------------------- 所以如果根据等边三角形的规律并且所有的点都占一个单位的话 2,6,8并不是等边三角形。
  

    //                    0.0



    //                1.-1   1.+1



    //            2.-1    2.0    2.+1 



    //        3.-2    3.-1   3.+1    3.+2



    //    4.-2    4.-1    4.0    4.+1    4.+2



    //5.-3    5.-2    5.-1   5.+1    5.+2    5.+3
--------------------编程问答--------------------
    //                   0.0



    //               1.-1   1.+1



    //           2.-2    2.0    2.+2 



    //        3.-3   3.-1   3.+1    3.+3



    //    4.-4   4.-2    4.0    4.+2    4.+4



    //5.-5    5.-3   5.-1   5.+1    5.+3    5.+5
上边的发错了这个是对的其实就是从这个里边找出你认为是等边三角形的规律就行.
PS: 一个账号只能连续发三次只好换一个。 --------------------编程问答-------------------- 来学习一下，支持。。。。... --------------------编程问答-------------------- 技术贴要顶，不顶的写代码一堆bug的，楼下继续

感觉用几何比较实在。。小菜妄言听听就好 --------------------编程问答-------------------- 说实话这个版主很2 --------------------编程问答--------------------
引用 39 楼 jiaoshiyao 的回复:
说实话这个版主很2

着实很桑心， --------------------编程问答--------------------
引用 35 楼 jack43349489 的回复:
所以如果根据等边三角形的规律并且所有的点都占一个单位的话 2,6,8并不是等边三角形。
  

    //                    0.0



    //                1.-1   1.+1



    //            2.-1    2.0    2.+1 



    //        3.-2    3.-1   3.+1    3.+2



    //    4.-2    4.-1    4.0    4.+1    4.+2



    //5.-3    5.-2    5.-1   5.+1    5.+2    5.+3
如果是以等边来考虑的，就不是一个单位了，比如那个正三角形，三线合一，高可以看做是行间距，如果列间距是1 的话，那行距就是，这样（2， 6， 8）仍然可以构成等边。 --------------------编程问答-------------------- 这个办法真好好好 --------------------编程问答--------------------
引用 36 楼 jack280649233 的回复:
    //                   0.0



    //               1.-1   1.+1



    //           2.-2    2.0    2.+2 



    //        3.-3   3.-1   3.+1    3.+3



    //    4.-4   4.-2    4.0    4.+2    4.+4



    //5.-5    5.-3   5.-1   5.+1    5.+3    5.+5
上边的发错了这个是对的其实就是从这个里边找出你认为是等边三角形的规律就行.
PS: 一个账号只能连续发三次只好换一个。
这样找规律不科学，什么是找规律，就是能够穷举到所有可能的点，并由此得粗一般性的结论，注意是所有。。。至少，我承认在这点上，我狭隘了，只看到了一两个特殊的点，就以为是得出了规律，自己就觉得可笑。。。
想到以前做的找规律数： 1， 2， 4 。。。那下个数会是多少呢？----你想到哪里，就是哪里！可以是等比的 8，也可以是的递增加的 7，各种。。。。扯远了，，说实话，真有点小挫败，这样的坐标方法行不通：当我取了更多的数据，看到（25， 50， 30）也能构成等边的时候，我瞬间崩溃了， 12 不是上限，层数越多，可能存在的在三角形的个数也越多，也就出现了在这个‘规律’之外的新点，，，

难道真的是要开始计算边长么？？还是这个思路，从一开始就是错误的？？

现在的我黔驴技穷了，仅有的脑细胞全部死光光了。。。。
--------------------编程问答-------------------- 除 --------------------编程问答-------------------- --------------------编程问答-------------------- 除 --------------------编程问答--------------------
引用 31 楼 Acc2013 的回复:
Quote: 引用 27 楼 jack43349489 的回复:

@ jack43349489 ，看了你的代码，才知道什么是下里巴人，什么是阳春白雪，先不论别的，至少你的代码层次多么清晰明了，算法多么精简，而且思路好奇特绝对是我想不到的。。。。

还是分析分析下你的代码：你是直接把数字，用坐标存储，
（0， 0） -- 1
（1， 0） -- 2 。。。
然后根据这些坐标的关系，只将合法的顶点存入List中，至少在数据上是很优化的，省去了我那大数组，多循环的麻烦。。。

还有这个检测思路：把能构成等边三角形的点都先存起来，重复叠加，然后从最多的点依次开始删除，再判断。。。
而我这，算是纯粹的暴力算法穷举每一对组合数，而且对于每个点都是先做循环，再判断，（像这点1，哪里会需要12个，估计是12的也没几个）致使程序N多次地空转，做了多少无用功呀。。

再加上LINQ，我等只有膜拜的份。。。。。

唯一的不足就是，你木有写完，，赶紧地，咱再比对下，我这15个蓝莓的结果是：

对于第一个结果，2,10,12则可构成一个等边三角形 --------------------编程问答-------------------- 是不是这个样子：
当蓝莓三角形层数=2时，应该拿走的蓝莓为：1；
当蓝莓三角形层数=3时，应该拿走的蓝莓为：1，5；
当蓝莓三角形层数=4时，应该拿走的蓝莓为：1，5，8,9；
当蓝莓三角形层数=5时，应该拿走的蓝莓为：1，5，8,9,12,13,14；
所以....应该拿走三角形的一个顶点，以及该顶点所在的两条三角形边以外的所有蓝莓；
这么看来对于L层的蓝莓三角形，应该拿走的蓝莓个数为：（设L层的蓝莓总数为S）
n = S - 2 * (L - 1)

上面的结果是找规律找出来的。
补充：.NET技术 ,  C#