被一个算法卡住了，请教

Question

从1-9这九个数字中任意取三个数，这三个数之和必须为15,共有多少种方式，分别是什么？自己算了一下好像应该是八种，但不知如何写这个程序，请赐教，谢谢。

Answer 1

for(int i=1; i<9; i++)
{
  for(int j=i+1; j<=9; j++)
  {
     int k = 15 - i - j;
     if( k != i && k != j && k >= 1 && k <= 9 )
     {
         print(i,j,k);
     }
  }
}

Answer 2

new 空结果集FOR(int i=1;i<10;i++)
{
  int subCount = 15-i;
  for(int j=1;j<subCount&&j<10;j++)
  {
    if(j==i)continue;
    组和方式为 i,j,subCount-j
    判断这个组和在结果集中有没有，没有的话就添加进去
  }
}最后结果集就是你要的东东~~这是我的思路~~

Answer 3

是否可以在循环时先把A<5 B<5 C<5和A>5 B>5 C>5的情况去掉 不过好像也么得必要哈

Answer 4

public  int a()
        {
            int n = 0;
            for (int i = 1; i <= 9; i++)
            {
                for (int j = i + 1; j <= 9; j++)
                {
                    for (int k = j + 1; k <= 9; k++)
                    {
                        if (i + j + k == 15)
                        {
                            n = n + 1;
                        }
                    }
                }
            }
            return n;
        }

Answer 5

自己google：3阶幻方 算法呵呵，lz啊，不看数学书不要紧，作为中国人咋连武侠小说都不看呢？这玩意老外叫3阶幻方，俺们中国人叫“九宫图”

Answer 6

发个linq的,不算是算法
            int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };            var result = from a in array
                         from b in array
                         from c in array
                         where a != b && b != c && (a + b + c) == 15
                         select new
                         {
                             A = a,
                             B = b,
                             C = c
                         };            foreach (var ret in result)
            {
                Console.WriteLine("A={0},B={1},C={2}", ret.A, ret.B, ret.C);
            }

Answer 7

改成where a < b && b < c && (a + b + c) == 15

Answer 8

:)
for(int i=1; i<9; i++)
{
  for(int j=i+1; j<9; j++)  //
  {
     int k = 15 - i - j;
     if( k > j && k <= 9 )  //<--
     {
         print(i,j,k);
     }
  }
}

Answer 9

7 楼 正解，，12 楼的linq 强

Answer 10

不太好理解:) 不是么？for (int i = 1; i < 5; i++)
{
    for (int j = Math.Max(i+1, 15-i-9); j < 9 && 15 - i - j > j; j++)
    {
        Print(i, j, 15-i-j);
    }
}

Answer 11

SELECT top 9 id=identity(int,1,1) into # FROM sysobjects
SELECT A.id,B.id,C.id FROM # A,# B,# C
WHERE A.id<=B.id AND A.id<=C.id AND B.id<=C.id
AND (A.id+B.id+C.id)=15/*
id          id          id          
----------- ----------- ----------- 
1           7           7
1           6           8
1           5           9
2           6           7
2           5           8
2           4           9
3           6           6
3           5           7
3           4           8
3           3           9
4           5           6
4           4           7
5           5           5（所影响的行数为 13 行）
*/

Answer 12

j < 9比较是多余的：
for (int j = Math.Max(i+1, 15-i-9); 15 - i - j > j; j++)

Answer 13

for (int i = 1; i < 5; i++) { for (int j = Math.Max(i+1, 15-i-9); j < 9 && 15 - i - j > j; j++) { Print(i, j, 15-i-j); } }

Answer 14

分别写了一个面积计算与循环累加
Console.WriteLine(sumCount3(9, 15).ToString());        private static int sumCount3(int maxValue, int sum)
        {
            int value = 0;
            if ((sum - 3 < maxValue ? maxValue = sum - 3 : maxValue) >= 3 && sum <= maxValue + (maxValue << 1) - 3)
            {
                #region 计算梯形面积
                int nextSum = sum - maxValue, count = (sum >> 1) - nextSum + 1, sumLess = sum - 1, minCount = (sumLess - maxValue) >> 1;
                int maxCount = minCount + (((nextSum & 1) == 0 ? count : (count - 2)) >> 1);
                if (count > 0)
                {
                    if (maxCount >= minCount) value += ((minCount + maxCount) * (count & 0x7ffffffe)) >> 1;
                    if ((count & 1) != 0)
                    {
                        value += maxCount;
                        if ((nextSum & 1) != 0) value++;
                    }
                }
                #endregion
                if ((count = (minCount = sum / 3 + 1) + (minCount << 1)) == sum + 1 || count == sum + 2) minCount++;
                if (minCount <= maxValue)
                {
                    #region 计算左三角面积
                    if ((maxCount = sumLess >> 1) > maxValue) maxCount = maxValue;
                    value += ((count = maxCount - minCount + 1) * (count + 1)) >> 1;
                    #endregion
                    #region 计算右三角面积
                    if ((maxCount -= ((nextSum = sum - maxCount) >> 1) + count + 1) > 0)
                    {
                        value += maxCount * (maxCount + 1);
                        if ((nextSum & 1) != 0)
                        {
                            value -= maxCount;
                            count++;
                        }
                        if (maxCount << 1 > count) value--;
                    }
                    #endregion
                }
            }
            return value;
        }
        private static int _sumCount3(int maxValue, int sum)
        {
            int value = 0;
            if ((sum - 3 < maxValue ? maxValue = sum - 3 : maxValue) >= 3 && sum <= maxValue + (maxValue << 1) - 3)
            {
                for (int nextSum, minValue = Math.Max(sum / 3, 2); maxValue > minValue; maxValue--)
                {
                    if ((nextSum = sum - maxValue) > maxValue)
                    {
                        if ((nextSum = maxValue - (nextSum >> 1) - 1) > 0) value += nextSum;
                    }
                    else value += (nextSum - 1) >> 1;
                }
            }
            return value;
        }

Answer 15

上面是计数的，如果要所有结果怎么也是O(n^3)的复杂度
        private static int[][] sum3(int maxValue, int sum)
        {
            List<int[]> value = new List<int[]>();
            if ((sum - 3 < maxValue ? maxValue = sum - 3 : maxValue) >= 3 && sum <= maxValue + (maxValue << 1) - 3)
            {
                for (int lastVaue, nextValue, nextSum, minValue = Math.Max(sum / 3, 2); maxValue > minValue; maxValue--)
                {
                    if ((nextSum = sum - maxValue) > maxValue)
                    {
                        for (nextValue = maxValue - 1, lastVaue = nextSum >> 1; nextValue > lastVaue; nextValue--) value.Add(new int[] { maxValue, nextValue, nextSum - nextValue });
                    }
                    else
                    {
                        for (nextValue = 1, lastVaue = (nextSum - 1) >> 1; nextValue <= lastVaue; nextValue++) value.Add(new int[] { maxValue, nextSum - nextValue, nextValue });
                    }
                }
            }
            return value.ToArray();
        }

Answer 16

int count = 0;
            for (int i = 1; i <= 9; i++)
            {
                for (int j = 1; j <= 9; j++)
                {
                    if (i != j)
                    {
                        int x = i + j;
                        if (x > 5 && x < 15)
                        {
                            int k = 15 - x;
                            Console.WriteLine("{0}  {1}  {2}", i, j, k);
                            Console.WriteLine("---------------");
                            count++;
                        }
                    }
                }
            }
            Console.WriteLine("总共输出: {0}个组合", count);
            Console.ReadKey();

Answer 17

/// <summary>
        /// 获取N位(n>=2)不重复的匹配总值组合结果值
        /// </summary>
        /// <param name="data">当前数据</param>
        /// <param name="minnum">最小起始数值</param>
        /// <param name="maxnum">最大结束数值</param>
        /// <param name="sum">匹配组合总值</param>
        /// <param name="index">当前匹配位置索引</param>
        /// <returns>得到匹配的组合集合</returns>
        private List<int[]> GetData(int[] data, int minnum, int maxnum, int sum, int index)
        {
            List<int[]> result = new List<int[]>();
            int newminnum = sum - (int)((maxnum + maxnum - (data.Length - index - 2)) / 2.0 * ((data.Length - index) - 1));
            minnum = newminnum > minnum ? newminnum : minnum;//计算获取第一个最小起始值
            for (int i = minnum; i <= maxnum; i++)
            {
                if (sum - i > (int)((i + 1 + i + (data.Length - index - 2)) / 2.0 * ((data.Length - index) - 1)))//当前总值减去索引位置值仍大于后一位以后的最小总值，则仍可执行下一步匹配计算。
                {
                    data[index] = i;
                    if (index == data.Length - 2)
                    {
                        if (sum - i <= maxnum)//最后一位时，如果小于最大限制值则成功匹配
                        {
                            data[index + 1] = sum - i;
                            result.Add((int[])data.Clone());
                        }
                        else//否则后面也没有了。可跳出此次循环。
                        {
                            break;
                        }
                    }
                    else
                    {
                        result.AddRange(GetData(data, i + 1, maxnum, sum - i, index + 1).ToArray());//开始计算一下位的数据。
                    }
                }
                else//后最小面值已经无法支持当前索引位置值继续增加。因此跳出此次循环
                {
                    break;
                }
            }
            return result;
        }
调用：
List<int[]> result = GetData(new int[3], 1, 9, 15, 0);

Answer 18

//如果不重复的话，应是13组
            int count = 0;
            for (int i = 1; i <= 9; i++)
            {
                for (int j = 1; j <= i; j++)
                {
                    for (int k = 1; k <= j; k++ )
                    {
                        if ((i + j + k) == 15)
                        {
                            Console.WriteLine("{0}  {1}  {2}", i, j, k);
                            Console.WriteLine("---------------");
                            count++;
                        }
                    }
                    
                }
            }
            Console.WriteLine("总共输出: {0}个组合", count);
            Console.ReadKey();

Answer 19

写了两种方法，LZ有兴趣试试看using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            sum();            Console.WriteLine("_________________________________________________________________");            sum2();
        }
        static void sum()
        {
            Stopwatch stw = new Stopwatch();
            stw.Start();
            int sum = 0;
            for (int n = 0; n < 100000 ;n++)
            {                List<string> listSum = new List<string>();
                for (int i = 1; i < 9; i++)
                {
                    for (int j = i + 1; j <= 9; j++)
                    {
                        int k = 15 - i - j;
                        if (k != i && k != j && k >= 1 && k <= 9)
                        {
                            string print = string.Format("{0},{1},{2}", i, j, k);
                            if (listSum.Count > 0)
                            {
                                bool flag = false;
                                foreach (string s in listSum)
                                {
                                    if ((s.Contains(i.ToString()) && s.Contains(j.ToString()) && s.Contains(k.ToString())))
                                    {
                                        flag = true;
                                        break;
                                    }
                                    else
                                    {
                                        flag = false;
                                    }
                                }
                                if (!flag)
                                {
                                    listSum.Add(print);
                                    Console.WriteLine(print);
                                    sum += 1;
                                }
                            }
                            else
                            {
                                listSum.Add(print);
                                Console.WriteLine(print);
                                sum += 1;
                            }
                        }
                    }
                }
            }
            stw.Stop();
            Console.WriteLine("{0}", sum);
            Console.WriteLine("执行时间：{0}", stw.ElapsedMilliseconds.ToString());
        }        static void sum2()
        {
            Stopwatch stw = new Stopwatch();
            stw.Start();
            int sum = 0;
            for (int n = 0; n < 100000 ;n++)
            {
                List<string> listSum = new List<string>();
                for (int i = 1; i < 9; i++)
                {
                    for (int j = i + 1; j <= 9; j++)
                    {
                        int k = 15 - i - j;
                        if (k != i && k != j && k >= 1 && k <= 9)
                        {
                            string print = order(i, j, k);
                            if (listSum.Count > 0)
                            {
                                if (listSum.Contains(print))
                                {
                                    continue;
                                }
                                else
                                {
                                    listSum.Add(print);
                                    Console.WriteLine(print);
                                    sum += 1;
                                }
                            }
                            else
                            {
                                listSum.Add(print);
                                Console.WriteLine(print);
                                sum += 1;
                            }
                        }
                    }
                }            }
            stw.Stop();
            Console.WriteLine("{0}", sum);
            Console.WriteLine("执行时间：{0}", stw.ElapsedMilliseconds.ToString());
            Console.ReadKey();
        }
        public static string order(int x, int y, int z)
        {
            string order = string.Empty;
            if (x > y)
            {
                if (y > z)
                {
                    //xyz
                    order = string.Format("{0},{1},{2}", x, y, z);
                }
                if (y < z)
                {
                    //xzy
                    order = string.Format("{0},{1},{2}", x, z, y);
                }
                if (x < z)
                {
                    //zxy
                    order = string.Format("{0},{1},{2}", z, x, y);
                }
            }
            else
            {
                if (x > z)
                {
                    //yxz
                    order = string.Format("{0},{1},{2}", y, x, z);
                }
                if (x < z)
                {
                    //yzx
                    order = string.Format("{0},{1},{2}", y, z, x);
                }
                if (y < z)
                {
                    //zyx
                    order = string.Format("{0},{1},{2}", z, y, x);
                }
            }
            return order;
        }
    }}

Answer 20

既然是求最优解。就不能这么遍历吧？？for (int n = 0; n < 100000 ;n++)？？为何 n < 100000？
假如这个需求改变，求的是1~100任意取20个的解。。或者更大，不把机器给遍历当机？

Answer 21

for (int a=1; a <= 9 - 3; a++)
                        {
                            for (int b = a + 1; b <= 9 - 2; b++)
                            {
                                for (int c= b + 1; c <= 9 - 1; c++)
                                {
                                    if(a + b + c  == 15)
                                    {
                                        string sun =a.ToString() + " " +
                                                     b.ToString() + " " + c.ToString() + " "                                        this.listBox1.Items.Add(sun);
                                    }
                                }
                            }
                        }

Answer 22

int i=0;
for (int a=1; a <= 9 - 3; a++)
  {
  for (int b = a + 1; b <= 9 - 2; b++)
  {
  for (int c= b + 1; c <= 9 - 1; c++)
  {
  if(a + b + c == 15)
  {
  i++;  }
  }
  }
  }
 Console.WriteLine("{0}个组合", i);

Answer 23

List<int[]> result = GetData(new int[3], 1, 9, 15, 0);
循环次数：17 
结果
1,5,9
1,6,8
2,4,9
2,5,8
2,6,7
3,4,8
3,5,7
4,5,6

Answer 24

for (int i = 1; i < 10; i++)
            {
                for (int j = i + 1; j < 10; j++)
                {
                    int k = 15 - i - j;
                    if (k > j && k < 10)
                    {
                        Console.WriteLine(i.ToString() + "," + j.ToString() + "," + k.ToString());
                    }
                }
            }

Answer 25

 string tt = "";
        for (int i = 1; i <= 9 ; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                for (int k = 1; k <= 9; k++)
                {
                    if (i + j + k == 15&&i>=j&&j>=k)
                    {
                        tt += i + "," + j + "," + k + " \n";
                    }
                }
            }
        }
       TextBox1.Text = tt;呵呵，试下这招准不准，重复是不存在了，但需要确定下是否列出完全。

Answer 26

 private List<int[]> GetData()
        {
            List<int[]> result = new List<int[]>();
            int k = 9;//设置初始最大值
            for (int i = 1; i < 8 && k > i + 1; i++)
            {
                for (int j = (15 - 9 - i) > (i + 1) ? (15 - 9 - i) : (i + 1); j < 9 && k > j + 1; j++)
                {
                    k = 15 - i - j;
                    //count++;
                    result.Add(new int[] { i, j, k });
                }
            }
            return result;
        }还不结贴.无聊了!!!这次给个最优解你....
List<int[]> result = GetData();
循环次数：8 八个数据循环八次.够优解了吧!!!! 
结果
1,5,9
1,6,8
2,4,9
2,5,8
2,6,7
3,4,8
3,5,7
4,5,6

Answer 27

private List<int[]> GetData()
        {
            List<int[]> result = new List<int[]>();
            for (int i = 1; i < 8; i++)
            {
                for (int j = (15 - 9 - i) > (i + 1) ? (15 - 9 - i) : (i + 1); j < 9 && 15 - i - j > j ; j++)
                {
                    result.Add(new int[] { i, j, 15 - i - j });
                }
            }
            return result;
        }再精减一下代码...无语了!!!

Answer 28

 /// <summary>
        /// 获取N位(n>=2)不重复的匹配总值组合结果值
        /// </summary>
        /// <param name="data">当前数据</param>
        /// <param name="minnum">最小起始数值</param>
        /// <param name="maxnum">最大结束数值</param>
        /// <param name="sum">匹配组合总值</param>
        /// <param name="index">当前匹配位置索引</param>
        /// <returns>得到匹配的组合集合</returns>
        private List<int[]> GetData(int[] data, int minnum, int maxnum, int sum, int index)
        {
            List<int[]> result = new List<int[]>();
            int newminnum = sum - (int)((maxnum + maxnum - (data.Length - index - 2)) / 2.0 * ((data.Length - index) - 1));
            minnum = newminnum > minnum ? newminnum : minnum;//计算获取第一个最小起始值
            for (int i = minnum; i <= maxnum && sum - i > (int)((i + 1 + i + (data.Length - index - 2)) / 2.0 * ((data.Length - index) - 1)); i++)
            {
                //count++;
                data[index] = i;
                if (index == data.Length - 2)
                {
                    data[index + 1] = sum - i;
                    result.Add((int[])data.Clone());
                }
                else
                {
                    result.AddRange(GetData(data, i + 1, maxnum, sum - i, index + 1).ToArray());//开始计算一下位的数据。
                }
            }
            return result;
        }再次精减递归的循环次数.去掉break的循环浪费..#56楼的代码也应该是12次.因为前面一个循环没算进去.这次算是优解到无法再优了吧.呵呵!!无突破!
List<int[]> result = GetData(new int[3], 1, 9, 15, 0);
循环次数：12  
结果
1,5,9
1,6,8
2,4,9
2,5,8
2,6,7
3,4,8
3,5,7
4,5,6

Answer 29

 private List<int[]> GetData()
        {
            List<int[]> result = new List<int[]>();
            for (int i = 1; i < 15-i-i-1; i++)
            {
                //count++;
                for (int j = (15 - 9 - i) > (i + 1) ? (15 - 9 - i) : (i + 1); j < 9 && 15 - i - j > j ; j++)
                {
                    //count++;
                    result.Add(new int[] { i, j, 15 - i - j });
                }
            }
            return result;
        }修正一下.这个才是循环12次的最优解

Answer 30

for (int i = 1; i < 5; i++)//1234四个数不可重复，
            {
                for (int j = 6; j <= 9; j++)//6789四个数不可重复，
                {
                    int k= 15 - i - j;
                    if (k>= 1 && k<= 9 && k!= i && k!= j && i != j &&k<j&&k>i)//条件k>= 1 && k<= 9 为在范围内 条件 && k!= i && k!= j && i != j  为三个数相互不重复，k<j&&k>i  小数  大数 小数规则 
                    {
                        count++;
                        listView1.Items.Add(new ListViewItem(i.ToString()));
                        listView1.Items[listView1.Items.Count - 1].SubItems.Add(j.ToString());
                        listView1.Items[listView1.Items.Count - 1].SubItems.Add(k.ToString());
                    }
                    number++;
                }
            }

Answer 31

#21比较好。
for (int i = 1; i < 5; i++)
            {
                for (int j = Math.Max(i + 1, 15 - i - 9);  15 - i - j > j; j++)
                {
                    Console.WriteLine("{0}\t{1}\t{2}", i, j, 15 - i - j);                }
            }