首页 > 安全资讯 >

【编程珠玑】第四章:编写正确的程序

12-05-14

1、对下标限定界限:加条件 0<=l u<=n-12、这个函数可以写成如下形式:[cpp]#include <iostream>using namespace std;int bs(int *a, int begin, int end, int v){ int *b = a + begin; //开...

1、对下标限定界限:加条件 0<=l u<=n-1
2、这个函数可以写成如下形式:
[cpp]
#include <iostream> 
using namespace std; 
 
int bs(int *a, int begin, int end, int v)   
{   
    int *b = a + begin; //开始  
    int *e = a + end;   //结束  
    int *mid = NULL;    //中间  
      
   
    while (b < e)  //直到等于第一个出现的值  
    {   
        mid = b + ((e - b)>>1);  //得到中间位置的地址  
         
        if (*mid >= v)  
            e = mid;   
        else  
            b = mid + 1;   
    }   
    if ((e-a) < end && (*e == v))  
        return e-a;   
         
    return -1;   
}   
int main() 

    int a[5]={1,2,2,2,4}; 
    cout<<bs(a, 0, 4, 2)<<endl; 
    return 0; 

再给一段测试代码
[cpp]
#include <stdio.h>   
#include <stdlib.h>   
int cmp(const void *a, const void *b)     
{     
    return (*(int*)a) - (*(int*)b);     
}   
   
int bs(int *a, int begin, int end, int v)   
{   
    int *b = a + begin, *e = a + end, *mid = NULL;   
    if (!a) return NULL;   
   
    while (b < e)   
    {   
        mid = b + ((e - b)>>1);   
        if (*mid >= v) e = mid;   
        else if(*mid < v) b = mid + 1;   
    }   
    if ((e-a) < end && (*e == v)) return e-a;   
    return -1;   
}   
   
int find(int *a, int begin, int end, int v)   
{   
    int i = 0;   
    for (i = begin; i < end; ++i)   
        if (a[i] == v) return i;   
    return -1;   
}   
   
int main(void)   
{   
    int a[10000];   
    int n = 10000, i = 0;   
    int f, e;   
    for (i = 0; i < n; ++i)   
        a[i] = random()%100;   
    qsort(a, n, sizeof(int), cmp);   
    for (i = 0; i < n; ++i){   
        f = find(a, 0, n, a[i]);   
        e = bs(a, 0, n, a[i]);   
        if (f != e)   
            printf("Error find of %d %d %d\n", a[i], f, e);   
    }   
    return 0;   
}   
6、程序终止性证明:即每一步都至少会扔出一个豆子,所以总会结束的。此外,白色的豆子要么拿两个,要么不扔,所以白色的豆子如果是奇数,则会留下一个白豆子,否则是黑豆子。
7、题目里面如果要采用二分搜索,那么需要找的是一个数的刚好下界。
采用题目2中的方法,可以找到刚好上界,由于,线段是顺序排列的,所以就可以找刚好的下界了。

 


摘自 小田的专栏

相关文章
最新文章
热点推荐