2.减去一个常数因子(decrease by a constant factor)
减去常数因子实际上就是把规模除以一个常数。（在多数情况下，这个常数因子是二）
继续以计算f(n)=a^n为栗：
这里的时间复杂度为O (log n)，就比蛮力法优化多了。
对分查找，假币问题都可以用这种思想。我们以假币问题为例：
有n枚银币，其中有1枚是假的，假币重量偏重、偏轻未知，输入银币的重量，求假币的位置。
我们先取出一枚银币作为对照，再将银币分为两半称重，每次称重对比，再从有问题的一堆中继续称重查找。这样，每次我们都减去了常量因子2。
当然，银币总数是奇偶时需要不同的处理方式，在银币数量为偶数时，由于不知道假币偏轻或偏重，我们需要选择一个compare进行对照。
同时，我们还可以把银币分为三堆考虑，进一步优化时间复杂度。（作为代价，代码要考虑总数mode3余1、2、0的情况，同时要比较三堆，会稍稍复杂一些）
Codding time：
//三分法求八枚银币问题 #include <iostream> using namespace std; int coin[105],num; int sum(int left, int right) { int sum = 0; for (int i = left; i <= right; i++) sum += coin[i]; return sum; } int findfake(int left, int right) { int n=right-left+1; int p1=(right+left)/3; int p2=p1*2; int sign = n % 3; if (sign == 0) { int fake = 0; int A, B, C; A = sum(left,p1); B = sum(p1+1,p2); C = sum(p2+1,right); if (n == 3) { if (A == B) { fake = right; } else if (A == C) { fake = right - 1; } else { fake = left; } return fake; } else { if (A == B) { fake = findfake(p2+1,right); return fake; } else if (A == C) { fake = findfake(p1+1,p2); return fake; } else { fake = findfake(left,p1); return fake; } } } if (sign == 1) { int fake = right; int A, B, C; A = sum(left,p1); B = sum(p1+1,p2); C = sum(p2+1,right-1); if (n == 1) { return fake; } else { if (A == B) { if (A == C) return fake; if (A !=C) { fake = findfake(p2+1,right-1); return fake; } } else if (A == C) { fake = findfake(p1+1,p2); return fake; } else { fake = findfake(left,p1); return fake; } } } if (sign == 2) { int fake = 0; int x1 = right - 1; int x2=right; int A, B, C; A = sum(left,p1); B = sum(p1+1,p2); C = sum(p2+1,right-2); if (n == 2) { int campare; //参照物 if (right != num) campare = coin[num]; else campare = coin[1]; if (coin[x2] == campare) fake = x1; else fake = x2; return fake; } else { if (A == B && B == C) { int campare = coin[0]; if (coin[x1] == campare) fake = x2; else fake = x1; return fake; } else if ((A == B) && (A!=C)) { fake=findfake(p2+1,x1-1); return fake; } else if (A == C) { fake=findfake(p1+1,p2); return fake; } else { fake = findfake(left,p1); return fake; } } } return 0; } int main() { cin >> num; for (int i = 1; i <= num; i++) cin >> coin[i]; int fake=findfake(1,num); cout << fake; return 0; }
3.减去的规模是可变的(variable size decrease)
字面理解，就是指每次减去的规模的模式或数值是不同的。
这里我们拿欧几里德算法为栗子。学过数论的盆友们知道（数学害人不浅啊），欧几里得算法是一种求最大公约数的较为简便的方法，也叫辗转相除法。用一个简单的式子来表示：
gcd(a,b) = gcd(b,a mod b) (这里a>b)
（题外话，我记得数论里最大公约数是不需要gcd的。。。）
可以大致想象到，这里每次减去的规模是完全未知、可变的。
我们再举一个栗子：二叉查找树。
百度百科告诉我们，二叉查找树是一颗这样的树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
根据树的性质，我们可以发现对二叉查找树的查找并不困难，只要从顶点开始不断比较就行了。但二叉查找树不一定就是平衡二叉树，如果只有一个分支，那减去的规模就会变化。（为什么我感觉解释的好扯啊。。。）
查找的代码并不困难，我们这里只给出实现插入和查找两种功能的代码。
（就当练习数据结构了= =）
Coding time：
//二叉排序树 #include <iostream> using namespace std; typedef class BiTNode //定义结点类，指针类型名 { public: int data; class BiTNode *leftchild, *rightchild; }*BiTree; // BST查找,查找成功,则p指向该元素节点,返回true bool searchBST(BiTree T,int key,BiTree f,BiTree &p) { if (!T) { p = f; return false; } else if (key == T->data) { p = T; return true; } else if (key < T->data) return searchBST(T->leftchild, key, T, p); else return searchBST(T->rightchild, key, T, p); } //BST插入，用于建立树 bool insertBST(BiTree &T, int key) { BiTree p, s; //因为在searchBST的过程中有进行比较,所以search完T就指向该插入位置的父结点 if (!searchBST(T, key,NULL, p)) { s = new BiTNode; s->data = key; s->leftchild = s->rightchild = NULL; if (!p) T = s; //p是空的说明树是空的,则插入在根节点 else if(key < p->data) p->leftchild = s; else p->rightchild = s; return true; } else return false; } int main() { //二叉树的创建 int n; cout<<"输入点个数"<<endl; cin>>n; BiTree T = NULL; cout<<"输入节点"<<endl; for (int i = 0; i < n; i++) { int a; cin>>a; insertBST(T, a); } //二叉树的查找 BiTree p=NULL; BiTree f=NULL; cout<<"接下来进行二叉排序树的查找,请输入值key"<<endl; int key; cin>>key; if (searchBST(T, key, f, p)) cout<<"在二叉排序树中"<<endl; else cout<<"不在二叉排序树中"<<endl; return 0; }
emmm，这图好像看不出什么。。。
编写的过程中有一点小插曲，我看错了树的定义，所以一开始的版本出现了错误(┬＿┬)，可以放出来给无聊的人看看，找找错。（说明看对题目真的很重要！！！）
wrong code：
//二叉查找树的建立（数组实现） #include <iostream> using namespace std; int size=0; //size为树的规模 int tree[1005]; const int INF=0; void addElement(int element) { int p = 1; //指标p if(size == 0) { tree[p] = element; size++; return; } while(true) { if(element<tree[p]) { int p1 = 2 * p ; //p1指向p的左儿子的位置 if(tree[p1] == INF) { tree[p1] = element; size++; return; } else p = p1; } else { int p2 = 2 * p + 1; //p2指向p的右儿子的位置 if(tree[p2] == INF) { tree[p2] = element; size++; return; } else p = p2; } } } int main() { int i,j=1; for (i=1;i<=size;i++) tree[i]=INF; int temp; while(cin>>temp) { addElement(temp); } for (i=1;j<=size;i++) { if(tree[i]!=INF) { cout<<tree[i]<<" "; j++; } } return 0; }
