0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 Output:
The 1 th connection is:ABHG The 2 th connection is:C The 3 th connection is:DEF
[cpp] view plaincopy
1. //当对某一顶点进行深搜时，可以遍历到这个顶点所在连通图的所有节点
[cpp] view plaincopy 1. #include
4. #define MAXV 50 5.
6. int graph[MAXV][MAXV]; //图的矩阵表示 7. bool vis[MAXV]; //是否已访问的标志 8. char s[MAXV]; //顶点的字母表示 9. int nVertices; //顶点的个数 10.
11. void dfs(int v) //深度优先遍历 12. {
13. vis[v] = 1; //修改为已访问 14. printf (\, s[v]); 15. int i;
16. for (i = 0; i < nVertices; ++i)
17. if (!vis[i] && graph[v][i]) //没有访问且有边 18. dfs(i); 19. } 20.
21. int main() 22. {
23. int i, j; 24. while (gets(s)) 25. {
26. memset(vis, 0, sizeof(vis)); //访问标志初始化 27. memset(graph, 0, sizeof(graph)); //图矩阵初始化 28.
29. nVertices = strlen(s);
30. for (i = 0; i < nVertices; ++i) //读入图的矩阵 31. for (j = 0; j < nVertices; ++j) 32. scanf (\, &graph[i][j]); 33.
34. int index = 1;
35. for (i = 0; i < nVertices; ++i) //对所有的节点，看是否已经访问 36. {
37. if (!vis[i]) 38. {
39. printf (\, index++); 40. dfs(i); 41. printf (\); 42. } 43. 44. } 45. }
46. return 0; 47. }
5.给出一个整数分解成连续整数的和.
[cpp] view plaincopy
1. //sum[i] 记录了前i个数的和，从i~j的和用sum[j]-sum[i-1] 计算，若与n相等则输出
[cpp] view plaincopy 1. #include
3. int main() 4. {
5. int n; 6. int i, j, k;
7. int sum[1000]; //sum[i] --- 前i个数的和 8. sum[0] = 0;
9. for (i = 1; i < 1000; ++i) 10. sum[i] = sum[i-1] + i; 11.
12. while (scanf (\, &n) != EOF) 13. {
14. for (i = 1; i <= n/2; ++i) //i为起始位置，j为终止位置，计算i~j的和 15. {
16. int ok = 0;
17. for (j = i; j <= n/2; ++j)
18. {
19. if (sum[j] - sum[i-1] == n) //相等 20. {
21. ok = 1; 22. break; 23. }
24. else if (sum[j] - sum[i-1] > n) //大于，无需将j后移，因为越加
会越大
25. break; 26. } 27. if (ok) 28. {
29. for (k = i; k <= j; k++) //输出 30. printf (\, k); 31. printf (\); 32. } 33. } 34. }
35. return 0; 36. }
6.给出带括号的四则运算表达式,要求给出逆波兰式
[cpp] view plaincopy
1. #include
6. bool compare (char op1, char op2) //比较优先级，op1为当前操作符，op2为栈顶操
作符 7. {
8. // 若op1优先级比op2高，返回1；否则返回0. 9. if (op1 == '+' || op1 == '-') 10. if (op2 == '#' || op2 == '(') 11. return 1; 12. else
13. return 0; 14. else if (op1 == '(') 15. return 1; 16. else
17. if (op2 == '*' || op2 == '/')
18. return 0; 19. else
20. return 1; 21. } 22.
23. int main() 24. {
25. int val; 26. char ch, op; 27. char exp[100]; 28. stack
32. while (gets(exp)) 33. {
34. i = 0;
35. len = strlen(exp); 36. while (i < len) 37. {
38. ch = exp[i];
39. if (isdigit(ch)) //是数字 40. {
41. val = ch - '0';
42. while (isdigit(exp[++i]))
43. val = val * 10 + exp[i] - '0'; 44. i--; //退回 45. printf (\, val); 46. }
47. else if (ch != ')') //不为')‘ 48. {
49. op = opStack.top();
50. if (compare(ch, op)) //ch > op,压入 51. opStack.push(ch); 52. else 53. {
54. while (!compare(ch, op)) //ch < op，弹出直到op比ch优先
级高
55. {
56. printf (\, op); 57. opStack.pop(); 58. op = opStack.top(); 59. }
60. opStack.push(ch);
61. } 62. }
63. else if (ch == ')') //右括号，弹出栈中操作符直道遇到’（‘，并且将
'('弹出 64. {
65. op = opStack.top(); 66. while (op != '(') 67. {
68. printf (\, op); 69. opStack.pop(); 70. op = opStack.top(); 71. }
72. opStack.pop(); 73. } 74. i++; 75. } 76.
77. op = opStack.top(); 78. while (op != '#') 79. {
80. printf (\, op); 81. opStack.pop(); 82. op = opStack.top(); 83. }
84. printf(\); 85. }
86. return 0; 87. }
7.递归列出的所有选择方法.
例如m=3,n=4时（4选3）,结果为 1,2,3 1,2,4 1,3,4 2,3,4
[cpp] view plaincopy
1. //求出1~n长度为m的子集
[cpp] view plaincopy