【开发者笔记】回溯法

八皇后问题

1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace 算法
 8 {
 9     class 回溯_八皇后问题
10     {
11         int[] arr;
12         int max;
13         int solutionCount = 0;
14         public void Run(int n)
15         {
16             max = n;
17             arr = new int[n];
18             Solution(0);
19             Console.WriteLine("解的个数有：{0}",solutionCount);
20             Console.ReadKey();
21         }
22         
23         public void Solution(int rank)
24         {
25             if (rank == max)
26             {
27                 solutionCount++;
28                 print();
29                 return;
30             }
31             for (int i = 0; i < max;i++ )
32             {
33                 arr[rank] = i;
34                 if (Check(rank))
35                 {
36                     Solution(rank+1);
37                 }
38             }
39         }
40         public bool Check(int n)
41         {
42             for (int i = 0; i < n; i++)
43             {
44                 /*检测同列和对角是否有皇后*/
45                 if (arr[i] == arr[n] || Math.Abs(n - i) == Math.Abs(arr[i] - arr[n]))
46                     return false;
47             }
48             return true;
49         }
50         public void print()
51         {
52             Console.WriteLine("------------------------------------------------");
53             for (int i = 0; i < arr.Length; i++)
54             {
55                 for (int j = 0; j < arr.Length; j++)
56                 {
57                     if (j == arr[i])
58                     {
59                         Console.Write("  *  |");
60                     }
61                     else
62                     {
63                         Console.Write("     |");
64                     }
65                 }
66                 Console.WriteLine();
67                 Console.WriteLine("------------------------------------------------");
68             }
69 
70             for (int i = 0; i < arr.Length; i++)
71                 Console.Write(arr[i]);
72             Console.WriteLine();
73             Console.WriteLine("==================================================");
74         
75         }
76 
77     }
78   
79 }      

View Code

单位分数问题

1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace 算法
  8 {
  9     /// <summary>
 10     /// /*  形如：1/a 的分数称为单位分数。   可以把1分解为若干个互不相同的单位分数之和。 
 11     /// 例如：
 12     ///     1 = 1/2 + 1/3 + 1/9 + 1/18 1 = 1/2 + 1/3 + 1/10 + 1/15 
 13     ///     1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231 等等，类似这样的分解无穷无尽。   
 14     /// 我们增加一个约束条件：最大的分母必须不超过30   
 15     /// 请你求出分解为n项时的所有不同分解法。   
 16     /// 数据格式要求：   
 17     /// 输入一个整数n，表示要分解为n项（n<12） 
 18     /// 输出分解后的单位分数项，中间用一个空格分开。 
 19     /// 每种分解法占用一行，行间的顺序按照分母从小到大排序。   
 20     /// 例如， 
 21     ///     输入： 4  
 22     ///     程序应该输出：  1/2 1/3 1/8 1/24
 23     ///                     1/2 1/3 1/9 1/18
 24     ///                     1/2 1/3 1/10 1/15
 25     ///                     1/2 1/4 1/5 1/20 
 26     ///                     1/2 1/4 1/6 1/12 
 27     /// </summary>
 28     class 回溯_单位分数
 29     {
 30 
 31         int max;
 32         int maxNumber = 30;
 33         int[] arr;
 34         HashSet<string> hs = new HashSet<string>();
 35         public void Run(int max)
 36         {
 37             this.max = max;
 38             arr = new int[max];
 39             Solution(0);
 40             Console.ReadKey();
 41         }
 42         public void Solution(int n)
 43         {
 44             double sum = 0;
 45             for (int j = 0; j < n; j++)
 46             {
 47                 double t = arr[j];
 48                 if (t != 0)
 49                     sum += 1 / t;
 50 
 51             }
 52             if (n >= max && sum != 1)
 53             {
 54                 return;
 55             }
 56             if (n == max && sum == 1)
 57             {
 58                 print();
 59                 return;
 60             }
 61 
 62             for (int i = n > 1 ? n : 2; i <= maxNumber; i++)
 63             {
 64                 arr[n] = i;
 65 
 66                 if (n <= max && Check(n))
 67                 {
 68                     Solution(n + 1);
 69                 }
 70             }
 71         }
 72         public bool Check(int n)
 73         {
 74             for (int i = 0; i < n; i++)
 75             {
 76                 double sum = 0;
 77                 for (int j = 0; j < n; j++)
 78                 {
 79                     double t = arr[j];
 80                     if (t != 0)
 81                         sum += 1 / t;
 82 
 83                 }
 84                 if (sum > 1 || n > max)
 85                 {
 86                     return false;
 87                 }
 88             }
 89             return true;
 90         }
 91         public void print()
 92         {
 93             string re = "";
 94             int[] arrr = arr.ToArray<int>();
 95             Array.Sort(arrr);
 96             for (int i = 0; i < arrr.Length; i++)
 97             {
 98                 re += (arrr[i] + "==");
 99             }
100             if (hs.Contains(re))
101                 return;
102             hs.Add(re);
103             /*判断是否有相同的数*/
104             for (int i = 0; i < arr.Length; i++)
105                 for (int j = 0; j < arr.Length; j++)
106                     if (arr[i] == arr[j]&&i!=j)
107                         return;
108             Console.WriteLine(re);
109         }
110     }
111 }      

黑夜给了我黑色的眼睛，我却用它寻找光明