2019.4.27

1.数组中，元素的位置称为索引

2.递归，调用栈。

发现还是不会写hanoi。。：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void hanoi(int n,char a,char b,char c){
 4  if(n==1) cout<<n<<":"<<a<<"-->"<<c<<endl;
 5  else {
 6     hanoi(n-1,a,c,b);
 7     cout<<n<<":"<<a<<"-->"<<c<<endl;
 8     hanoi(n-1,b,a,c);
 9  }
10 }
11 int main()
12 {
13     int n;
14     cin>>n;
15    hanoi(n,'a','b','c');
16 
17 }

hanoi

3.分治：

▲步骤：1）找出基线条件（尽可能简单）

2）不断将问题分解（缩小规模），直至符合基线条件。

▲证明欧几里得算法（辗转相除法）：

https://zh.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

【

To prove that GCD(A,B)=GCD(B,R) we first neec GCD(A,B)=GCD(B,A-B).

Proof that the GCD(A,B) evenly dividesC .

Proof that the GCD(B,C) evenly dividesA

GCD(A,B)=GCD(B,A-B)

GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)

GCD(A,B)=GCD(B,R)

】

▲排序（以下都按从小到大）：

1）冒泡排序：从左到右，数组中相邻的两个元素进行比较，将较大的放到后面。 // O(n^2)

2）选择排序：从左到右，一个元素与他下面所有元素比较，找出最小的，和那个元素互换，开始下一轮。 // O(n^2)

3）快排：找基准数，左右两边放小于等于和大于，再递归。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void quicksort(vector<int> &num,int l,int r)
 4 {
 5 
 6  if(l>= r) return;
 7  int i=l,j=r,x=num[l];
 8  while(i<j){
 9     while(i<j&&num[j]>=x)
10         j--;
11     if(i<j)
12         num[i++]=num[j]; //填坑之后再加
13     while(i<j&&num[i]<=x)
14         i++;
15     if(i<j)
16         num[j--]=num[i];
17  }
18  num[i]=x;  //把基准值放到i处
19  quicksort(num,l,i-1);  //以i为中间值，排左右两边
20  quicksort(num,i+1,r);
21 }
22 int main()
23 {
24    int f[]={3,35,2,1,8,5,6,2,0};
25    int len=sizeof(f)/sizeof(int);
26   /*前者是该int数组所占的内存总量（字节数),后者是单个int所占的内存,
27     合起来就是数组中元素的个数*/
28    vector<int> num(f,f+len);
29    for(int k=0;k<num.size();k++)
30     cout<<num[k]<<" ";
31    cout<<endl;
32    quicksort(num,0,len-1);
33    for(int k=0;k<num.size();k++)
34     cout<<num[k]<<" ";
35    cout<<endl;
36    return 0;
37 
38 }

快排--填坑法