JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
【练习】
2.3-2 MERGE的改进
void MERGE(int *A, int p,int q, int r) {
    int B[maxn] , i = p , j = q+1 , k = 0;
    while(k < r - p + 1) {
        if(i > q || j <= r && A[i] > A[j]) B[k++] = A[j++];
        else B[k++] = A[i++];
    }
    for(i=0;i<r-p+1;i++) A[p+i] = B[i];
}

2.3-5 二分查找的C++代码
int find(int *a, int l, int r, int value) {
    if(l == r) return l;
    int mid = (l+r) >> 1;
    if(a[mid] >= value) return find(a, l, mid, value);
    else return find(a , mid+1, r , value);
}

*2.3-7 (这道题其实有O(n)的算法,而且写起来更方便些)这里是O(nlogn)的算法
O(nlogn)算法思想:1.首先进行排序;2.然后枚举每一个小于等于x/2的数S[i],二分查找对应的x-S[i]是否存在
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
bool findx(int *S,int n, int x,int l,int r) {
    if(l > r) return false;
    if(l ==r) return S[l] == x;
    int mid = (l+r) >> 1;
    if(S[mid] >= x) return findx(S, n, x, l, mid);
    else return findx(S, n, x, mid+1, r);
}
bool check(int *S,int n,int x) {
    for(int i=0;S[i]<=x/2 && i < n;i++) {
        if(findx(S, n, x-S[i], i+1, n-1)) return true;
    }
    return false;
}
int main() {
    int S[1010] , x , n;
    while(~scanf("%d%d" , &n , &x)) {
        for(int i=0;i<n;i++) cin >> S[i];
        if(check(S, n, x)) puts("yes");
        else puts("no");
    }
    return 0;
}

O(n)的方法是在数的范围不是特别大的时候(或者数的范围比较大,此时采用hash的方法)标记的方法,这里假设数的范围<=10000,并且假设数没有重复的情况下,其他情况稍许改变一下就行:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;

bool check(int *S,int n,int x) {
    bool vis[10001] = {0};
    for(int i=0;i<n;i++) vis[x-S[i]] = true;
    for(int i=0;i<n;i++) if(vis[S[i]]) return true;
    return false;
}
int n ,x , S[maxn];
int main() {
    while(~scanf("%d%d" , &n , &x)) {
        for(int i=0;i<n;i++) cin >> S[i];
        if(check(S, n, x)) puts("yes");
        else puts("no");
    }
    return 0;
}

2-4(逆序对):这道题就是在归并排序中得到逆序对,具体见代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int ans;
void merge_sort(int *A, int l,int r) {
    if(l >= r) return;
    int mid = (l+r) >> 1;
    merge_sort(A, l, mid);
    merge_sort(A, mid+1, r);
    int i = l , j = mid+1 ,B[maxn] , k = l;
    while(i <= mid || j <= r) {
        if(i > mid || j <= r && A[j] < A[i]) B[k++] = A[j++] , ans += mid-i+1;
        else B[k++] = A[i++];
    }
    for(i=l;i<=r;i++) A[i] = B[i];
}
int main() {
    int A[maxn] , n;
    while(~scanf("%d" , &n)) {
        for(int i=0;i<n;i++) cin >> A[i];
        ans = 0;
        merge_sort(A, 0, n-1);
        cout << ans << endl;
        //for(int i=0;i<n;i++) cout << A[i] << " "; cout << endl;
    }
    return 0;
}
posted on 2015-03-07 15:19 JulyRina 阅读(283) 评论(0)  编辑 收藏 引用 所属分类: 算法专题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理