在开始今天的算法题之前,先介绍一个概念:循环不变式
这个概念主要用来检验算法的正确性。原文如下:
We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant:
Initialization: It is true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
翻译如下(笑哭.jpg)
在循环的第一轮迭代开始之前,应该是正确的。
=>初始化(循环第一次迭代之前)的时候,A[1 ‥ j -1]的“有序性”是成立的;如果在循环的某一次迭代开始之前它是正确的,那么在下一次迭代开始之前,它也应该保持正确;
=>在循环的每次迭代过程中,A[1 ‥ j -1]的“有序性”仍然保持;当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。
=>循环结束的时候,A[1 ‥ j -1]的“有序性”仍然成立。
apparently,这和我们数学里面的数学归纳法看起来就很像了。
相似之处在于数学归纳法中,要证明某一个性质是成立的,必须首先证明其基本情况和某一个归纳步骤是成立的。
这儿证明循环不变式在第一次迭代开始之前是成立的,就有点类似于对基本情况的证明;证明不变式在各次迭代之间保持成立,就有点类似于归纳法中对归纳步骤的证明。
不过需要注意的是:有关循环不变式的三个性质最重要的可能是第三个性质,因为我们用循环不变式的目的就是证明算法的正确性。数学归纳法中的归纳步骤是无穷使用的,而在证明循环不变式时当循环结束就会停止归纳。
OK,那么现在开始解决今天的算法题了。
题目贴出来先:
输入:n个数的一个序列A=<a1,a2,……,an>和一个值v。
输出:下标i,使得v=A[i];或者当v不在A中出现时,v为特殊值NIL。
这个题目其实和之前的那个插入的题也差不多,就是一个扫描配对查找。听easy的。
附上代码:
#include <iostream>
using namespace std;
int search(int arr[],int v,int len);
int main(){
int Arr[5],v;//此处假设数组长度为5
cout<<"please input 5 number"<<endl;
for(int i=0;i<5;i++)
cin>>Arr[i];
int length=sizeof (Arr)/sizeof (Arr[0]);//int length=5;
cout<<"please input the value of v"<<endl;
cin>>v;
int k;//接收返回值
k=search(Arr,v,length);//调用search方法
cout << "back index:"<<k<<endl;//数不存在则输出404
return 0;
}
int search(int arr[],int v,int len){
int i;
for(i=0;i<len;i++){
if(arr[i]==v){
return i;
break;
}
}
if(i=len-1)//无此数,则循环完
return 404;
}
今天贴代码的方式和昨天是不是感觉不一样了,昨天百度了一波简书贴代码的方式,原来简书支持部分markdown编辑,在个人设置里面设置就可以了。至于markdown的语法规则,百度一下就出来啦。https://www.appinn.com/markdown/
运行结果展示:
明天的算法:用分治法解决DAY1的排序题,设计更高效的算法。
输入:n个数的一个序列<a1,a2,……,an>
输出:输入序列的一个排列< a1',a2',……,an '>,满足 a1'≤a2 '≤ …… ≤ an'
回顾:[DAY1]//www.greatytc.com/p/b4e20b4a7a62
继续:[DAY3]//www.greatytc.com/p/01d17607b719