實驗3 分治算法實驗一

OJ練習

1. 素數判定：http://acm.hdu.edu.cn/showproblem.php?pid=2012

2. 蟠桃記：http://acm.hdu.edu.cn/showproblem.php?pid=2013

3. 偶數求和：http://acm.hdu.edu.cn/showproblem.php?pid=2015

4. Can you find it?：http://acm.hdu.edu.cn/showproblem.php?pid=2141

5. 數列有序!：http://acm.hdu.edu.cn/showproblem.php?pid=2019

6. 絕對值排序：http://acm.hdu.edu.cn/showproblem.php?pid=2020

7*. Toxophily：http://acm.hdu.edu.cn/showproblem.php?pid=2298

8*. Turn the corner：http://acm.hdu.edu.cn/showproblem.php?pid=2438

9*. Quoit Design：http://acm.hdu.edu.cn/showproblem.php?pid=1007

10*. Can you solve this equation?：

http://acm.hdu.edu.cn/showproblem.php?pid=2199

11*. Pie：http://acm.hdu.edu.cn/showproblem.php?pid=1969

12*. Cup：http://acm.hdu.edu.cn/showproblem.php?pid=2289

實驗内容

1. 二分搜尋。分别使用非遞歸算法和遞歸算法實作二分搜尋。【輸入：一個一維整型數組和一個待查詢的值；輸出：待查詢值所在的位置，如果沒有找到，則傳回-1。】

源代碼（非遞歸算法）：

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int mod= +;
const int maxn=;
const int maxm=;
int a[maxn],tmp[maxn];
int ans;

int BinarySort(int a[], int n, int l, int r)
{
    while(l <= r)
    {
        int mid = l + (r - l)/;
        if(l > r) return -;
        if(n == a[mid]) return mid;
        if(n > a[mid]) l = mid + ;
        else if(n < a[mid]) r = mid - ;
    }
    return -;
}

int main()
{
    int n, x;
    cin>>n;
    for(int i=; i<=n; i++) cin>>a[i];
    cin>>x;
    printf("%d\n",BinarySort(a,x,,n));
    return ;
}

源代碼（遞歸算法）：
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int mod= +;
const int maxn=;
const int maxm=;
int a[maxn],tmp[maxn];
int ans;

int BinarySort(int a[], int n, int l, int r)
{
    int mid = l + (r - l)/;
    if(l > r) return -;
    if(a[mid] == n) return mid;
    else if(a[mid] < n)
        BinarySort(a, n, mid+, r);
    else if(a[mid] > n)
        BinarySort(a, n, l, mid-);
}

int main()
{
    int n, x;
    cin>>n;
    for(int i=; i<=n; i++) cin>>a[i];
    cin>>x;
    printf("%d\n",BinarySort(a,x,,n));
    return ;
}

數組合并。編寫一個程式，将兩個有序數組合并成一個更大的有序數組，要求時間複雜度為O(n)。

源代碼：

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int mod= +;
const int maxn=;
const int maxm=;
int a[maxn],b[maxn],tmp[maxn];
int ans;
int k;
void Merge(int a[], int b[], int la, int lb)
{
    int i = , j = , k = ;
    while(i <= la && j <= lb)
    {
        if(a[i] < b[j])
        {
            tmp[k++] = a[i++];
        }
        else
        {
            tmp[k++] = b[j++];
        }
    }
    while(i <= la) tmp[k++] = a[i++];
    while(j <= lb) tmp[k++] = b[j++];
    for(int i=; i<k; i++) cout<<tmp[i]<<" ";
}

int main()
{
    int n, m;
    cin>>n;
    for(int i=; i<n; i++) cin>>a[i];
    cin>>m;
    for(int i=; i<m; i++) cin>>b[i];
    Merge(a, b, n-, m-);
    return ;
}

歸并排序。編寫一個程式，使用分治政策實作二路歸并排序。【輸入：一個一維整型數組；輸出：排序之後的一維整型數組】

源代碼：

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int mod= +;
const int maxn=;
const int maxm=;
int a[maxn],tmp[maxn];
int ans;
int k;
void Merge(int l, int m, int r)
{
    int i = l, j = m + , k = l;
    while(i <= m && j <= r)
    {
        if(a[i] < a[j])
        {
            tmp[k++] = a[i++];
        }
        else
        {
            tmp[k++] = a[j++];
        }
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int i=l; i<=r; i++)
        a[i] = tmp[i];
}

void MergeSort(int l ,int r)
{
    if(l < r){
        int m = l + (r - l) / ;
        MergeSort(l, m);
        MergeSort(m+, r);
        Merge(l, m, r);
    }
}

int main()
{
    int n, x;
    cin>>n;
    for(int i=; i<=n; i++) cin>>a[i];
    MergeSort(, n);
    for(int i=; i<=n; i++) cout<<a[i]<<" ";
    return ;
}

棋盤覆寫問題。編寫一個程式，使用分治法實作棋盤覆寫問題，輸入一個包含特殊方格的棋盤矩陣（使用二維整型數組表示），輸出覆寫之後的矩陣。

輸入格式示例如下：

-1 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

輸出格式示例如下：

-1 2 4 4

2 2 1 4

3 1 1 5

3 3 5 5

其中“-1”表示特殊方格。

源代碼：

#include <bits/stdc++.h>

using namespace std;

char str[];
int a[][];
int tile=;
void chess(int tr,int tc,int dr,int dc,int size)
{
    if(size==) return;
    int t=tile++,s=size/;

    if(dr<tr+s && dc<tc+s)//左上角
        chess(tr,tc,dr,dc,s); 
    else
    {
        a[tr+s-][tc+s-]=t;
        chess(tr,tc,tr+s-,tc+s-,s);
    }

    if(dr<tr+s && dc>=tc+s)//右上角
        chess(tr,tc+s,dr,dc,s);
    else
    {
        a[tr+s-][tc+s]=t;
        chess(tr,tc+s,tr+s-,tc+s,s);
    }

    if(dr>=tr+s && dc<tc+s)//左下角
    {
        chess(tr+s,tc,dr,dc,s);
    }
    else
    {
        a[tr+s][tc+s-]=t;
        chess(tr+s,tc,tr+s,tc+s-,s);
    }

    if(dr>=tr+s && dc>=tc+s)//右下角
    {
        chess(tr+s,tc+s,dr,dc,s);
    }
    else
    {
        a[tr+s][tc+s]=t;
        chess(tr+s,tc+s,tr+s,tc+s,s);
    }
}

int main()
{
    int n,sx,sy;
    cin>>n>>sx>>sy;
    for(int i=; i<=n; i++){
    for(int j=; j<=n; j++){
            scanf("%d",&a[i][j]);
        }
    }
    chess(,,sx,sy,n);
    for(int i=;i<=n;i++){
    for(int j=;j<=n;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return ;
}

快速排序。程式設計實作快速排序算法，深入了解快速排序算法的基本思想。【輸入：一個一維整型數組；輸出：快速排序之後的一維整型數組】

源代碼：

#include <bits/stdc++.h>

using namespace std;

int a[];
void QuickSort(int a[], int l, int r)
{
    if(l >= r) return ;
    int k = a[l];
    int i = l, j = r;
    while(i != j){
        while(j > i && a[j] >= k)
            --j;
        swap(a[i], a[j]);
        while(i < j && a[i] <= k)
            ++i;
        swap(a[i], a[j]);
    }
    QuickSort(a, l, i-);
    QuickSort(a, i+, r);
}

int main()
{
    int n;
    cin>>n;
    for(int i=; i<=n; i++){
        cin>>a[i];
    }
    QuickSort(a,,n);
    for(int i=; i<=n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return ;
}

6. 設a[0:n-1]是已排好序的數組。請改寫二分搜尋算法，使得當待搜尋元素x不在數組中時，傳回小于x的最大元素的位置i和大于x的最小元素的位置j；當待搜尋元素x在數組中時，傳回的i和j相同，均為x在數組中的位置。

源代碼：

#include <bits/stdc++.h>

using namespace std;

int a[];
bool BinarySort(int a[], int n, int x,int &i, int &j)
{
    int l = , r = n-;
    while(l <= r)
    {
        int mid = l + (r - l)/;
        if(x == a[mid]) {
            i = j = mid;
            return true;
        }
        if(x > a[mid]) {
            l = mid + ;
        }
        else {
            r = mid - ;
        }
    }
    i = r;
    j = l;
    return false;
}

int main()
{
    int n, x, i = , j = ;
    cin>>n;
    for(int i=; i<n; i++){
        cin>>a[i];
    }
    cin>>x;
    if(BinarySort(a,n,x,i,j))
        cout<<"元素 "<<x<<" 在數組中的位置為 "<<i+<<endl;
    else
    {
        cout<<"數組中小于"<<x<<"的最大元素位置為 "<<i+<<endl;
        cout<<"數組中大于"<<x<<"的最小元素位置為 "<<j+<<endl;
    }
    return ;
}

7*. 設n個不同的整數排好序後存儲在T[0:n-1]中。如果存在下标i，0<=i

#include <bits/stdc++.h>

using namespace std;

int a[];

int BinarySort(int a[], int l, int r)
{
    while(l <= r)
    {
        int mid = (r + l)/;
        if(mid == a[mid])
            return mid;
        if(mid > a[mid])
            l = mid + ;
        else
            r = mid - ;
    }
    return -;
}

int main()
{
    int n;
    cin>>n;
    for(int i=; i<n; i++){
        cin>>a[i];
    }
    printf("%d\n",BinarySort(a,,n-));
    return ;
}



時間複雜度分析：
O(logn)

實驗3 分治算法實驗一

繼續閱讀

基礎練習字母圖形 -藍橋杯-Java

基礎練習楊輝三角形-藍橋杯-Java

EOJ 3264 螞蟻（模拟+棧）題目解題思路AC代碼

藍橋杯 ALGO-112 暗戀 java問題描述解題思路參考代碼

基礎練習字母圖形 java 藍橋杯

Python 入門函數：列印特殊符号

藍橋杯基礎練習 BASIC-04 Fibonacci數列 JAVA

藍橋杯 OJ BASIC-6 楊輝三角形

藍橋杯 VIP 基礎練習 Huffuman樹

Java實作藍橋杯藍橋杯VIP 基礎練習數的讀法

c語言龜兔賽跑

c語言報時助手

Python：回文數的三種實作方法

Shell程式設計---監控伺服器整個系統CPU負載

藍橋杯基礎練習 Huffman樹 Java實作基礎練習 Huffman樹

New Year and Days