c/c++ 編程試題

帶*號為選作題，給出代碼截屏和編譯運算結果截屏

1.編程:選取M個最大的數 編程實現從N個無序數中選取M個最大的數(0 < M < N )

思路：通過冒泡排序或者選擇排序對N個數進行遞減排序，然后輸入前M個數即可。這里我想到的是通過數組來存儲這N個數。

#include <iostream>
#include <stdio.h>using namespace std;int main()
{int i,j,t,N,M,a[1000];printf("請輸入N：");scanf("%d",&N);for(i=0;i<N;i++){scanf("%d",&a[i]);}for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}}printf("請輸入M：");scanf("%d",&M);for(j=0;j<M;j++){printf("%d\n",a[j]);}return 0;
}

2.編程:斷開鏈條 給定一個包含N個整數的數組A,假設這個數組表示的是一條鏈條,其中 每個元素表示鏈條上的一環。現在我們想把這條鏈條斷成3小部分。我們需 要做的就是斷開不相連的兩個環,比如,我們需要斷開環P、Q
(0<P<Q<N-1, Q-P > 1),得到三個小鏈條[0,P-1],[P+1,Q-1],[Q+1,N-1]。
上述操作的成本是A[P]+A[Q]。 例如:數組A為 A[0] = 5 A[1] = 2 A[2] = 4 A[3] = 6 A[4] =
3 A[5] = 7 我們可以選擇如下方式斷開鏈條

• (1,3):成本是 2+6 = 8
• (1,4):成本是 2+3 = 5
• (2,4):成本是 4+3 = 7 寫一個函數如int breakchain(參數列表自定義); 對任一個給定的鏈條,返回斷開鏈條的最低成本,比如上面的例子中, 需要返回最低成本5 假設:
• N是整數,范圍[5,100000] A的元素是范圍在[1,1000000000]的整數

3.編程:順時針環繞列印矩陣元素 給定一個整數元素組成的矩陣,寫一個函數,返回一個數組,數組中的元 素是按照順時針遍歷矩陣中的元素而組成。例如如下的3x4矩陣: 2, 3, 4, 8 5, 7, 9, 12 1, 0, 6, 10
得到的數組的元素按照順序是“2, 3, 4, 8, 12, 10, 6, 0, 1, 5, 7, 9”.

我讀完該題的時候腦子里面想到了《算法競賽 入門經典 第2版》里面P40頁的蛇形填數問題。
即：在n * n方陣里填入1，2，…，n*n，要求填成蛇形。例如，n=4時方陣為：

10  11  12  19  16  13  28  15  14  37   6   5  4

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define maxn 20
int a[maxn][maxn];
using namespace std;int main()
{int n,x,y,tot = 0;scanf("%d",&n);memset(a,0,sizeof(a));tot = a[x=0][y=n-1] = 1;while(tot < n*n){while(x+1 < n && !a[x+1][y]) a[++x][y]=++tot;while(y-1 >=0 && !a[x][y-1]) a[x][--y]=++tot;while(x-1 >=0 && !a[x-1][y]) a[--x][y]=++tot;while(y+1 < n && !a[x][y+1]) a[x][++y]=++tot;}for(x = 0;x < n;x++){for(y=0;y<n;y++)printf("%3d",a[x][y]);printf("\n");}return 0;
}

當然這道題可以參考蛇形填數來進行改編

4.編程:最大方形長度 給定一個元素是布爾型大小為NM的矩陣A。大小為L的方形可以放置在A 中的(X,Y)處,如果滿足: 0 < L <= min(N,M) - 1 0 <= X <= N-L 0 <= Y <= M-L A[X+i][Y+j] = true, 0 <= i
< L, 0 <= j < L 如果L能被放置在(X,Y)以及(X+1,Y)或者(X,Y+1),我們說它可以被
從(X,Y)移動到(X+1,Y)或者(X,Y+1)。 我們想找出滿足以下條件的最大的L: L可以被放置在(0,0)(假如此處為true)
它可以被經過一系列的移動,從(0,0)到達(N-L,M-L)
換言之,我們想找到最大的方形,可以從為true的左上移動到為true的右下，該方形覆蓋的區域都是true,移動方式是向下或者向右移動。一個極端情況是如果矩陣A中的元素全部是true,那
么L = min(N,M) - 1。 寫一個函數:比如int moveSquare(參數列表自定義); 返回值為L。 比如:
A[0][0]=true A[0][1]=true A[0][2]=true A[0][3]=false A[1][0]=true
A[1][1]=true A[1][2]=true A[1][3]=false A[2][0]=true A[2][1]=true
A[2][2]=true A[2][3]=false A[3][0]=true A[3][1]=true A[3][2]=true
A[3][3]=true A[4][0]=false A[4][1]=true A[4][2]=true A[4][3]=true
A[5][0]=true A[5][1]=false A[5][2]=true A[5][3]=true 返回 2
A[0][0]=true A[0][1]=true A[0][2]=false A[0][3]=false A[1][0]=true
A[1][1]=false A[1][2]=false A[1][3]=false A[2][0]=false
A[2][1]=true A[2][2]=false A[2][3]=true 返回 0 A[1][1]=true 返回 1
假設N和M是范圍為[1,200]的整數

5.*問答題(建議編程實現)

假設你站在120層摩天大樓的天臺，手握兩個iphone
x，并且可輕易到達任一樓層的陽臺。請用最少的嘗試次數nTry，確定能夠讓iphone自由下落而不會摔壞的最高層數nMaxLayer。比如20層摔不壞，21層摔壞，則nMaxLayer=21。在嘗試中你可以摔壞這兩個iphone，只要能得到答案。請說明最壞情況需要多少次嘗試以及你的思路。