15年蓝桥杯第5题

题意：

1,2,3...9 这九个数字组成一个分数，其值恰好为1/3，如何组法？

思路：和15年第3题几乎是一样的dfs。依然不是自己想出来的。太佩服这个机智的深搜了。

如果题意是把用完九个数的话。

附right代码：

 1 /*
 2  1,2,3...9 这九个数字组成一个分数，其值恰好为1/3，如何组法？
 3  */
 4 
 5 #include <stdio.h>
 6 
 7 bool check(int x[]) {
 8     for (int i=0; i<9; ++i) {
 9         for (int j=0; j<9; ++j) {
10             if (x[i] == x[j] && i != j) {
11                 return false;
12             }
13         }
14     }
15     return true;
16 }
17 
18 void test(int x[])
19 {
20     int a = x[0] * 1000 + x[1] * 100 + x[2] * 10 + x[3];
21     int b = x[4] * 10000 + x[5] * 1000 + x[6] * 100 + x[7] * 10 + x[8];
22 
23     if (a * 3 == b && check(x))  {
24       printf("%d / %d
", a, b);
25     }
26 }
27 
28 void f(int x[], int k)
29 {
30     int i, t;
31     if (k >= 9)
32     {
33         test(x);
34         return;
35     }
36 
37     for (i = 1; i<=9; i++)
38     {
39         f(x, k + 1);
40         x[k] = i;  //填空处
41     }
42 }
43 
44 int main()
45 {
46     int x[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
47     f(x, 0);
48     return 0;
49 }

View Code

讲道理！在大腿的指导下，我终于明白源码在干嘛了。

附right代码：

 1 #include <stdio.h>
 2 
 3 void test(int x[])
 4 {
 5     int a = x[0] * 1000 + x[1] * 100 + x[2] * 10 + x[3];
 6     int b = x[4] * 10000 + x[5] * 1000 + x[6] * 100 + x[7] * 10 + x[8];
 7 
 8     if (a * 3 == b) printf("%d / %d
", a, b);
 9 }
10 
11 void f(int x[], int k)
12 {
13     int i, t;
14     if (k >= 9)
15     {
16         test(x);
17         return;
18     }
19 
20     for (i = k; i<9; i++)
21     {
22         {
23             t = x[k];
24             x[k] = x[i];
25             x[i] = t;
26         }
27         f(x, k + 1);
28         //_____________________________________________ // 填空处
29         {
30            t = x[k];
31            x[k] = x[i];
32            x[i] = t;
33         }
34     }
35 }
36 
37 int main()
38 {
39     int x[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
40     f(x, 0);
41     return 0;
42 }

View Code