今天数据结构实验课，老师给了一道题，说100分能用多少个1分，2分，5分组成，列出所有可能
原本3个for就可以强搜索完， 最近由于搜索题做多了，上来直接想到用dfs做，后来写好了发现问题了
dfs用于储存数据的数组，大小至少要把所有数据都能存进去，这题大小为100+50+20，但是仔细想会发现，答案最多不过为100个，开始我就把数组设为100个，运行起来爆了，调试，发现数组越界，就发现这个原因了，
还有一个办法，在dfs再次操作时，判断len是否超了100，小于100继续，否则不继续，这样递归次数少了，这种方法更好，更快捷
以后要注意这个问题
代码
1 #include<iostream>
2 #include<fstream>
3 using namespace std;
4
5 int usetimes[3] = {20, 50, 100};
6 int num[3] = {5, 2, 1};
7 int a[100];
8 int n = 0;
9
10 void dfs(int, int);
11
12 int main()
13 {
14
15 dfs(0, 0);
16 cout << n;
17
18 return 0;
19 }
20 int sum;
21
22 void dfs(int len, int current)
23 {
24 sum = 0;
25
26 for (int i = 0; i < len; i++)
27 sum += a[i];
28 if (sum == 100)
29 {
30 int b[3] = {0, 0, 0};
31
32 for (int i = 0; i < len; i++)
33 {
34 switch (a[i])
35 {
36 case 5: b[0]++; break;
37 case 2: b[1]++; break;
38 case 1: b[2]++; break;
39 }
40
41 }
42 printf("5*%d + 2*%d + 1*%d = 100\n", b[0], b[1], b[2]);
43 n++;
44 return ;
45 }
46
47 //注意这里，要判断len是否小于100，不然数组会越界
48 //dfs的时候，当不满足100的时候，大于100时也会继续，直到所有数值都用过，
49 //这里len最大去到20+50+100这么多
50 if (len < 100)
51 for (int i = current; i < 3; i++)
52 {
53 if (usetimes[i])
54 {
55 usetimes[i]--;
56 a[len] = num[i];
57 dfs(len+1, i);
58 usetimes[i]++;
59 }
60 }
61 }
62
3个for循环
代码
1 #include<iostream>
2 using namespace std;
3
4 int main()
5 {
6 int count = 0;
7 for (int i = 0; i <= 20; i++)
8 {
9 for (int j = 0; j <= 50; j++)
10 for (int k = 0; k <= 100; k++)
11 {
12 if (i*5 + j*2 + k*1 == 100)
13 {
14 printf("%d*5 + %d*2 + %d*1 = 100\n", i, j, k);
15 count++;
16 }
17 }
18 }
19 cout << count;
20 return 0;
21 }