@chawuciren
2018-11-27T03:34:12.000000Z
字数 2201
阅读 664
7-解决问题和算法
rCSI
这一部分先说了简单变量,他是不可分的。接着开始分析一个选择算法,今天穿什么。
首先写出一个大致的过程,再看该过程是否需要细化。
循环可以分为两种,一种是通过循环变量的计数来控制,一种通过循环体中的事件来控制。
先说第一种
循环可以分为三个部分,首先初始化循环不变量,然后检查该值是否到达了预定值,最后将这个变量加1。(是不是和for很像?)书上举了一个读取值10次并计算总和的例子。
然后是第二种
还是分成三步,先初始化事件,检查该事件,然后更新该事件。举计算平方根为例。
这个算法大致如下,先猜测结果是什么,然后将这个猜测值平方,如果误差比较小,就将猜测值作为结果。
用这种方法更新guess的值,guess+(square/guess)/2.0
注意:gusee的初始值设为square/4更接近答案
将所有元素分为已排序与未排序,在未排序的元素中找到最小的一个元素,将其放入到已排序中
void SelectionSort(int a[],int len){
int i,j;
for(i = 0 ; i < len-1 ; i++){
int min_index = i; //存储最小值
for(j = i + 1 ; j < len; j++)
if(a[ min_index ] > a[j])//选出最小值
min_index = j;
if(min_index != i){
int temp = a[i]; //若当前比较的a[i]>最小值,进行交换
a[i] = a[min_index];
a[min_index] = temp;
}
}
}
//插入排序
从第一个元素开始,如果它比下一个元素大,就交换两个元素的位置,然后再比较下一个元素,一直到不能交换为止。
到最后得到一个已排序的数组。
void BubbleSort(int a[], int len)
{
int i=0;
int j=0;
int key=1;//用于替换
for(i = 0 ; i < len - 1 ; i++)
{
for(j = 0 ; j < len - i - 1 ; j++)
if(a[j] > a[j+1])//比较a[j]和a[j+1],大的向上交换,直到这一次全部比完。然后i+1,比较下一次
{
key = a[j];
a[j] = a[j+1];
a[j+1] = key;
}
}
return;
}
将所有元素分为已排序与未排序,将未排序的元素的第一个元素插入到已排序的元素中
int InsertionSort(int a[],int len){
int key=0;//用于交换
for(int i=0;i<len-1;i++){
int j=i;
do{
if(a[j]>a[j+1]){ //假设a[j]已排好,a[j]与a[j+1],若a[j+1]大于前一位,交换,否则不交换。若还有更前一位,再比较。
key=a[j];
a[j]=a[j+1];
a[j+1]=key;
}
j-=1; //j=j-1,若前一位存在,比较前一位
} while(j>=0);
}
return ;
}
使用分治的思想,将最后一个元素作为比对值,比这个元素小的放在他的左边,比这个元素大的放在他的右边,然后递归,最后得到排好序的数组。
int partition(int array[],int len){
int x=array[len-1];
int i=-1;
for(int j=0;j<len-1;j++){//最后一个数内定了
if(array[j]<=x){
exchange(&array[i],&array[j]);
i+=1;
}
}
exchange(&array[i+1],&array[len-1]);
i++;
return i;
}
上面那个程序,第一没有考虑i=-1时访问了非法空间,第二交换的时候交换错了,应该是i+1以后再交换
int partition(int array[],int len){
int x=array[len-1];
int i=-1;
for(int j=0;j<len-1;j++){//最后一个数内定了
if(array[j]<=x){
if(i==-1){
i+=1;
}+=1;
else{
exchange(&array[i],&array[j]);
}
}
}
i+=1;
exchange(&array[i],&array[len-1]);
return i;
}
一个元素一个元素去找
int search(int array[],int len,int x){
int find=0;
for(int i=0;i<len;i++){
if(array[i]==x)
find=1;
if(find==1)
break;
}
return find;
}
使用了分治的思想,将一个数组分成两半(只能针对排好序的数组)
还可以分为递归与非递归
int BinSearch(int sorted_arr[],int Len,int key)
{
int low=0;
int high=Len-1;
int mid=-1;
while (low<=high)
{
mid=(low+high)/2;
if (sorted_arr[mid]>key)
{
high=mid-1;
}
if(sorted_arr[mid]<key)
{
low=mid+1;
}
if(sorted_arr[mid]==key)
{
return mid;
}
}
return -1;
}
在不同的人眼中一条狗是不同的