20151208讲义

diggersun

1. 最大公约数
   
2. #include <iostream>
   
3. using namespace std;
   
4. int gcd1(int m,int n)
   
5. {
   
6.     if (n==0) return m;
   
7.     else return gcd1(n,m%n);
   
8. }
   
9. int gcd2(int m,int n)
   
10. {
    
11.     int x=m%n;
    
12.     while (x!=0) {m=n;n=x;x=m%n;}
    
13.     return n;
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.     int x,y;
    
19.     cin >>x>>y;
    
20.     cout <<gcd1(x,y) <<' '<<gcd2(x,y);
    
21.     return 0;
    
22. }
    
23. 
    
24. 阶乘问题
    
25. #include <iostream>
    
26. using namespace std;
    
27. int fac(int n)
    
28. {
    
29.     if (n==0) return 1;
    
30.     else return fac(n-1)*n;
    
31. }
    
32. 
    
33. int main()
    
34. {
    
35.     cout <<fac(10);
    
36.     return 0;
    
37. }
    
38. 
    
39. Fibo
    
40. #include <iostream>
    
41. using namespace std;
    
42. int fibo(int n)
    
43. {
    
44.     if (n==1) return 1;
    
45.     else if (n==2) return 2;
    
46.     else return fibo(n-1)+fibo(n-2);
    
47. }
    
48. 
    
49. int main()
    
50. {
    
51.     cout <<fibo(10);
    
52.     return 0;
    
53. }
    
54. 
    
55. 汉诺塔问题
    
56. #include <iostream>
    
57. using namespace std;
    
58. void ha(int n,char a,char b,char c)
    
59. {
    
60.     if (n==1) cout<<a<<"->"<<c<<endl;
    
61.     else
    
62.     {
    
63.         ha(n-1,a,c,b);  // n-1个盘子由A通过C挪到B上
    
64.         cout<<a<<"->"<<c<<endl;// 最后一个盘子直接由A到C
    
65.         ha(n-1,b,a,c);// n-1个盘子由B通过A挪到C
    
66.     }
    
67. }
    
68. 
    
69. int main()
    
70. {
    
71.     ha(3,'A','B','C');
    
72.     return 0;
    
73. }
    
74. 
    
75. 错排问题
    
76. #include <iostream>
    
77. using namespace std;
    
78. int cp(int n)
    
79. {
    
80.     if (n==1) return 0;
    
81.     else if (n==2) return 1;
    
82.     else return (n-1)*(cp(n-1)+cp(n-2));
    
83. }
    
84. 
    
85. int main()
    
86. {
    
87.     for (int i=1;i<=10;i++)cout <<cp(i)<<' ';
    
88.     return 0;
    
89. }
    
90. 
    
91. A^B的计算
    
92. #include <iostream>
    
93. using namespace std;
    
94. int a,b;
    
95. long long way1(int n)
    
96. {
    
97.    if (n==0) return 1;   //0次方等于1
    
98.    else if (n%2==1) return way1(n/2)*way1(n/2)*a; //奇数次
    
99.         else return way1(n/2)*way1(n/2);//偶数次
    
100. }
     
101. long long way2(int n)
     
102. {
     
103.         long long s=1,t=a;
     
104.         while (n>0)
     
105.         {
     
106.                 if (n%2==1) s=(s*t);
     
107.                 n=n/2;t=t*t;
     
108.         }
     
109.         return s;
     
110. }
     
111. int main()
     
112. {
     
113.     a=2;b=10;cout<<way1(b)<<' '<<way2(b);
     
114.         return 0;
     
115. }
     
116. 
     
117. PMN
     
118. 
     
119. #include <iostream>
     
120. using namespace std;
     
121. int a[10];
     
122. bool b[10];
     
123. void mysearch(int i)
     
124. {
     
125.     int j,k;
     
126.     if (i>=3) {for (j=0; j<=2; j++) cout<<a[j];cout<<endl;}
     
127.     else for (k=0; k<=4; k++)
     
128.             if (b[k])
     
129.             {
     
130.                 a[i]=k;
     
131.                 b[k]=false;
     
132.                 mysearch(i+1);
     
133.                 b[k]=true;
     
134.             }
     
135. }
     
136. 
     
137. int main()
     
138. {
     
139.     for (int i=0;i<=4;i++) b[i]=true;
     
140.     mysearch(0);
     
141. }
     
142. 
     
143. CMN
     
144. #include <iostream>
     
145. using namespace std;
     
146. int a[10];
     
147. void mysearch(int i)
     
148. {
     
149.     int j,k;
     
150.     if (i>=3) {for (j=0; j<=2; j++) cout<<a[j];cout<<endl;}
     
151.     else for (k=((i==0)?0:a[i-1]+1); k<=5; k++)
     
152.           { a[i]=k;  mysearch(i+1);  }
     
153. }
     
154. 
     
155. int main()
     
156. {
     
157.     mysearch(0);
     
158. }
     
159. 
     

复制代码