黑马程序员技术交流社区

标题: 递归的问题又来了，大神们求解答 [打印本页]

---

作者: guobin_lu    时间: 2013-3-31 17:13
标题: 递归的问题又来了，大神们求解答
有10个球，随机取出2个，请编程列出所有可能的组合。（ab与ba视为同一组合，用递归实现有加分）

1. private static void Main(string[] args)
   
2.         {
   
3.             List<string> strs = new List<string>() {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",};
   
4.             GetResult(strs);
   
5.             Console.ReadKey();
   
6.         }
   
7.         public static void GetResult(List<string> strs)
   
8.         {
   
9.             if (strs.Count > 1)
   
10.             {
    
11.                 for (int i = 1; i < strs.Count; i++)
    
12.                 {
    
13.                     Console.Write(strs[0] + strs[i] + "    ");
    
14.                 }
    
15.                 strs.RemoveAt(0); //这里为什么是0下标呀
    
16.                 Console.WriteLine();
    
17.                 GetResult(strs);
    
18.             }
    
19.         }

复制代码

为什么要removeat（0）

---

作者: DWC_5101    时间: 2013-3-31 18:13
算法思想是：
每次拿List的第一个元素，和其他元素组合，组合完后，就将第一个元素删除（代码 ：strs.RemoveAt(0) ）；
递归执行上面的操作，直到List中只剩一个元素。

如果不删除第一个元素，List中永远有那么多元素，就永远达不到结束条件，陷入循环递归，出现死循环。

---

作者: 张正强    时间: 2013-3-31 19:51
楼上说的很对，其实你可以根据运行结果看出规律，实在不行可以调试，总会找出算法思想的。
PS:这里还有一种方法,很类似九九乘法表

1. static void Main(string[] args)
   
2. {
   
3.     List<string> strs = new List<string>() { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", };
   
4.     GetResult(strs);
   
5.     Console.ReadKey();
   
6. }
   
7. public static void GetResult(List<string> strs)
   
8. {
   
9.     int i = 0;
   
10.     for (; i < strs.Count; i++)
    
11.     {
    
12.         for (int j = i + 1; j < strs.Count; j++)
    
13.         {
    
14.             Console.Write(strs[i] + strs[j] + "    ");
    
15.         }
    
16.         Console.WriteLine();
    
17.     }
    
18.     if (i < strs.Count)
    
19.         GetResult(strs);
    
20. }

复制代码

---

作者: 曾玉锋    时间: 2013-3-31 21:01
其实用递归思路并不如用双循环清晰，但两者执行原理是一样的。建议楼主同学能用循环尽量用循环。
下面给出双循环和递归的解法：
双循环：
int[] arr={0,1,2,3,4,5,6,7,8,9};
           List<string> list = new List<string>();
           for (int i = 0; i < arr.Length; i++)
           {
               for (int j = 0; j < arr.Length; j++)
               {
                   if (list.Contains(arr[i] + "" + arr[j]) || list.Contains(arr[j] + "" + arr[i]))
                   {
                       continue;
                   }
                   else
                   {
                       list.Add(arr[i] + "" + arr[j]);
                   }
               }
           }
            Console.Write(string.Join(",", list));
            Console.ReadKey();


下面是递归解法：
static void Main(string[] args)
        {
           int[] arr={0,1,2,3,4,5,6,7,8,9};
           List<string> list = new List<string>();
           getList(0,0,arr,list);//递归方法
            Console.Write(string.Join(",", list));
            Console.ReadKey();
        }
        public static void getList(int i,int j,int[] arr,List<string> strs) {
            if(i==arr.Length)
            {
                //递归结束条件
                return;
            }
            
            if (j == arr.Length)
            {
                j = 0;
                getList(i+1,j,arr,strs);
            }
            else {
                if (strs.Contains(arr[i] + "" + arr[j]) || strs.Contains(arr[j] + "" + arr[i]))
                {
                    //如果已经有这种组合，则什么都不做
                    
                }
                else
                {   //如果不包含这种组合，则将这种组合加入集合中
                    strs.Add(arr[i] + "" + arr[j]);
                }
                getList(i, j + 1, arr, strs);

            }
           
        }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2