华师一附中OI组

标题: 20151208讲义 [打印本页]
作者: diggersun    时间: 2015-12-13 11:43
标题: 20151208讲义
  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. }

  16. int main()
  17. {
  18.     int x,y;
  19.     cin >>x>>y;
  20.     cout <<gcd1(x,y) <<' '<<gcd2(x,y);
  21.     return 0;
  22. }

  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. }

  33. int main()
  34. {
  35.     cout <<fac(10);
  36.     return 0;
  37. }

  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. }

  49. int main()
  50. {
  51.     cout <<fibo(10);
  52.     return 0;
  53. }

  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. }

  69. int main()
  70. {
  71.     ha(3,'A','B','C');
  72.     return 0;
  73. }

  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. }

  85. int main()
  86. {
  87.     for (int i=1;i<=10;i++)cout <<cp(i)<<' ';
  88.     return 0;
  89. }

  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. }

  117. PMN

  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. }

  137. int main()
  138. {
  139.     for (int i=0;i<=4;i++) b[i]=true;
  140.     mysearch(0);
  141. }

  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. }

  155. int main()
  156. {
  157.     mysearch(0);
  158. }

复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2