2014年北郵計算機上機題目二

Problem A. 中位數

題目描述

給定一個長度為N的非降數列，求數列的中位數。

中位數：當有序數列的項數N為奇數時，處于中間位置的變量即為中位數；當N為偶數時，中位數則為處于中間位置的兩個數的平均數。

輸入格式

輸入資料第一行是一個整數T（1<=T<=100），表示測試資料的組數。

對于每組測試資料：

第一行是一個正整數N（1<=N<=100），表示數列長度。

第二行有N個整數，整數之間用空格隔開，所有的整數都不超過100000，表示這個數列的元素。

輸出格式

對于每組測試資料，輸出數列的中位數，請不要輸出小數點末尾多餘的0。

輸入樣例

2

4

1 1 2 2

5

1 1 2 2 3

輸出樣例

1.5

2

　　說一點：%g用來輸出實數，它根據數值的大小，自動選f格式或e格式（選擇輸出時占寬度較小的一種），且不輸出無意義的0。即%g是根據結果自動選擇科學記數法還是一般的小數記數法。

　　這題的精度用%g可以混過去的，不行的話其實自己寫個函數處理下也是簡單的。比如用sprintf(s,”%lf”,f)把實數變成字元串，再把後面沒用的0去掉就行了。

#include<stdio.h>

int main() {
    int T,a[];
    scanf("%d",&T);
    while(T--) {
        int N;
        scanf("%d",&N);
        for(int i = ;i < N;i++) {
            scanf("%d",&a[i]);
        }
        if(N % ) {
            printf("%d\n",a[N / ]); 
        } else {
            printf("%g\n",(a[N / ] + a[N /  - ]) / );
        }
    }
}
           

Problem B. 記憶體配置設定

題目描述

在作業系統中，記憶體配置設定是非常重要的工作。

已知記憶體空間由N個記憶體塊組成，這些記憶體塊從1到N編号，進行記憶體配置設定時，作業系統将選擇一塊大小足夠的記憶體全部配置設定給請求記憶體的程序。例如，當程序請求10MB的記憶體時，作業系統必須向該程序配置設定一個不小于10MB的記憶體塊。記憶體塊不能被重複配置設定。

作業系統有三種基本的配置設定方式，分别為：

首次适應：從1号到N号記憶體塊依次查找，直到找到第一塊足夠大的且未配置設定出去的記憶體塊，将其配置設定給程序。

最佳适應：找到目前未配置設定出去且大小足夠的記憶體塊中最小的記憶體塊配置設定給程序。

最差适應：找到目前未配置設定出去且大小足夠的記憶體塊中最大的記憶體塊配置設定給程序。

其中，最佳适應是應用最為廣泛的配置設定方式。現在，作業系統要依次處理M個程序的記憶體請求，請按照最佳适應方式配置設定記憶體，并輸出相應配置設定到的記憶體塊的大小。如果沒有大小足夠的記憶體塊可以滿足目前請求，則輸出“NULL”（不包含引号），并跳出該請求。

輸入格式

輸入資料的第一行是測試資料組數T（T<=50）

每組資料由4行構成：

第一行為一個整數N（1<=N<=100），表示有N個記憶體塊。

第二行有N個整數，第i個整數表示第i塊記憶體塊的大小。

第三行為一個整數M（1<=M<=100），表示有M個請求。

第四行有M個整數，表示程序所請求的記憶體空間。

輸出格式

每組資料輸出一行，每行有M個數，表示作業系統采用最佳适應方式，依次配置設定給程序的記憶體塊大小；如果沒有可用的記憶體塊，輸出“NULL”（不包含引号）

請不要輸出多餘的行尾空格，否則會被判為格式錯誤。

輸入樣例

2

4

7 5 10 3

2

4 6

4

3 5 9 10

3

5 12 6

輸出樣例

5 7

5 NULL 9

　　水題。

#include<stdio.h>

int main() {
    int T,a[],b[];
    scanf("%d",&T);
    while(T--) {
        int N,M;
        scanf("%d",&N);
        for(int i = ;i < N;i++) {
            scanf("%d",&a[i]);
            b[i] = ;
        }
        scanf("%d",&M);
        int temp,dx,index,flag = ;
        while(M--) {
            dx = ;
            scanf("%d",&temp);
            for(int i = ;i < N;i++) {
                if(b[i] && a[i] >= temp && a[i] - temp < dx) {
                    dx = a[i] - temp; 
                    index = i;
                } 
            }
            if(dx != ) {
                b[index] = ;
                if(flag) {
                    printf(" %d",a[index]);
                } else {
                    flag = ;
                    printf("%d",a[index]);
                }
            } else {
                if(flag) {
                    printf(" NULL");
                } else {
                    flag = ;
                    printf("NULL");
                }
            }           
        }
        printf("\n");
    }
}
           

Problem C. 圖像識别

題目描述

在圖像識别中，我們經常需要分析特定圖像中的一些特征，而其中很重要的一點就是識别出圖像的多個區域。在這個問題中，我們将給定一幅N x M的圖像，其中每個1 x 1的點都用一個[0,255]的值來表示他的RGB顔色。如果兩個相鄰的像素點顔色差不超過D，我們就認為這兩個像素點屬于同一個區域。對于一個像素點(x,y) ，以下這8個點（如果存在）是與它相鄰的：（x-1, y-1），（x-1,y），（x-1,y+1），（x,y-1），（x,y+1），（x+1,y-1），（x+1,y），（x+1,y+1）。

你的任務是寫一個程式，分辨出給定圖像中一共被分為多少個區域。

輸入格式

輸入資料包含多組測試資料。

輸入的第一行是一個整數T（T<=100），表示測試資料的組數。

每組測試資料的第一行是三個整數N,M,D（1<=N,M<=100, 0<=D<=255），意義如上所述。

接下來N行，每行M個整數，表示給定圖像的每個像素點顔色。

輸出格式

對于每組測試資料輸出一行，即圖像中的區域數量。

輸入樣例

2

3 3 0

1 1 1

0 1 0

0 1 0

3 4 1

10 11 12 13

9 8 7 6

2 3 4 5

輸出樣例

3

1

　　很經典的問題，Flood Fill。

#include<stdio.h>
#include<stdlib.h>

int map[][];

void dfs(int i,int j,int m,int n,int d) {
    if(i >=  && i < m && j >=  && j < n && map[i][j] != ) {
        int temp = map[i][j];
        map[i][j] = ; 
        if(abs(map[i + ][j] - temp) <= d) {
            dfs(i + ,j,m,n,d);
        }
        if(abs(map[i - ][j] - temp) <= d) {
            dfs(i - ,j,m,n,d);
        }
        if(abs(map[i][j + ] - temp) <= d) {
            dfs(i,j + ,m,n,d);
        }
        if(abs(map[i][j - ] - temp) <= d) {
            dfs(i,j - ,m,n,d);
        }
        if(abs(map[i + ][j + ] - temp) <= d) {
            dfs(i + ,j + ,m,n,d);
        }
        if(abs(map[i - ][j - ] - temp) <= d) {
            dfs(i - ,j - ,m,n,d);
        }
        if(abs(map[i + ][j - ] - temp) <= d) {
            dfs(i + ,j - ,m,n,d);
        }
        if(abs(map[i - ][j + ] - temp) <= d) {
            dfs(i - ,j + ,m,n,d);
        }
    }
}


int main() {
    int T,N,M,D;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d",&N,&M,&D);
        for(int i = ;i < N;i++) {
            for(int j = ;j < M;j++) {
                scanf("%d",&map[i][j]);
            }
        }
        int num = ;
        for(int i = ;i < N;i++) {
            for(int j = ;j < M;j++) {
                if(map[i][j] != ) {
                    dfs(i,j,N,M,D);
                    num++;
                }
            }
        }
        printf("%d\n",num);     
    }
}
           

Problem D. 彙編

題目描述

彙編語言描述了機器最終所要執行的指令序列，其中，以8086CPU為中央處理器的彙編就是最經典的版本之一。這個題目需要你的程式處理一些簡單的彙編指令，并傳回執行之後各寄存器的結果。

在該CPU中，所有寄存器都是16位，可以存放兩個位元組（即0到65535之間）。為簡單起見，我們隻是用其中AX，BX，CX，DX四個通用寄存器。其中，每個寄存器又可分為兩個獨立使用的8位寄存器：

AX可分為AH和AL

BX可分為BH和BL

CX可分為CH和CL

DX可分為DH和DL

在存儲資料時，低8位構成了L型寄存器（AL，BL，CL，DL），高8位構成了H型寄存器（AH，BH，CH，DH）。例如，當AX=（20000）10 =（0100 1110 0010 0000）2時，我們有

AX AH AL

0100 1110 0010 0000B 0100 1110B 0010 0000B

在彙編中，數值通常表示為2進制（以B結尾），16進制（以H結尾）或者10進制（沒有字尾字元）。如上例出現的20000（10進制）可以表示為0100111000100000B，也可表示為04E20H。為了避免指令的歧義，16進制下的首位一定是0。

本題中所涉及的操作指令有以下兩類：

MOV：資料轉移

ADD：加法

指令的用法如下：

彙編指令 控制CPU完成的操作 用進階語言的文法描述

MOV AX，18 将18送入寄存器AX AX=18

MOV AH，11B 将11B送入寄存器AH AH=11B

MOV AX，BX 将寄存器BX中的資料送入AX AX=BX

ADD AX，08H 将寄存器AX中的數值加上08H AX=AX+08H

ADD AX，BX 将AX和BX中的數值相加， AX=AX+BX

結果存在AX中

注意在MOV和ADD操作中，指令的兩個操作對象的位數應當是一緻的，即不會出現如MOV AX，BL或ADD AL，100H這樣錯誤的指令。

在初始狀态下，四個通用寄存器中的數值均為0.給定一系列的彙編指令，請輸出執行完所有指令後四個通用寄存器中的數值。

輸入格式

輸入的第一行是一個整數T（T<=50），表示輸入的資料組數。

每組測試資料的第一行是一個整數N（1<=N<=100），表示指令的數量。

接下來N行，每行包括一個指令。指令中隻會存在一個空格，出現在指令名和操作對象中間。資料保證不會出現錯誤的語句，每條語句結束之後該寄存器内的數值都不會超過它本身所能存儲的最大值。

輸出格式

對于每組測試資料，輸出一行表示AX，BX，CX，DX最終的值（用十進制表示），數值中間用一個空格隔開。注意行末不要輸出多餘的空格。

樣例輸入

2

3

MOV AX，2

MOV BX，3

ADD AX，BX

5

MOV AX，2

MOV BX，030H

MOV CX，11B

ADD AX，CX

ADD DL，CL

樣例輸出

5 3 0 0

5 48 3 3

暫時沒時間做了，以後做吧，畢竟渣渣又不是要AK，還有四門專業課等着我去背。。。