2023年12月 青少年軟件編程（C/C++）等級(jí)考試試卷（四級(jí)）電子學(xué)會(huì)真題

1.移動(dòng)路線

題目描述

桌子上有一個(gè)m行n列的方格矩陣，將每個(gè)方格用坐標(biāo)表示，行坐標(biāo)從下到上依次遞增，列坐標(biāo)從左至右依次遞增，左下角方格的坐標(biāo)為(1,1)，則右上角方格的坐標(biāo)為(m,n)。

小明是個(gè)調(diào)皮的孩子，一天他捉來一只螞蟻，不小心把螞蟻的右腳弄傷了，于是螞蟻只能向上或向右移動(dòng)。小明把這只螞蟻放在左下角的方格中，螞蟻從左下角的方格中移動(dòng)到右上角的方格中，每步移動(dòng)一個(gè)方格。螞蟻始終在方格矩陣內(nèi)移動(dòng)，請(qǐng)計(jì)算出不同的移動(dòng)路線的數(shù)目。 ??

對(duì)于1行1列的方格矩陣，螞蟻原地移動(dòng)，移動(dòng)路線數(shù)為1；對(duì)于1行2列（或2行1列）的方格矩陣，螞蟻只需一次向右（或向上）移動(dòng)，移動(dòng)路線數(shù)也為1……對(duì)于一個(gè)2行3列的方格矩陣，如下圖所示：?
(2,1) - (2,2) - (2,3)
(1,1) - (1,2) - (1,3)
螞蟻一共有3種移動(dòng)路線：

路線1：(1,1) - (1,2) - (1,3) - (2,3)

路線2：(1,1) - (1,2) - (2,2) - (2,3)

路線3：(1,1) - (2,1) - (2,2) - (2,3)

輸入描述

輸入只有一行，包括兩個(gè)整數(shù)m和n（0 < m+n ≤ 20），代表方格矩陣的行數(shù)和列數(shù)，m、n之間用空格隔開。

輸出描述

輸出若干行，每行一個(gè)移動(dòng)路線，輸出形式如樣例所示。

（為保證輸出一致，螞蟻移動(dòng)時(shí)先向右，再向上）

輸入

2 3

輸出

3

//螞蟻共有3種移動(dòng)路線：

路線1：(1,1) - (1,2) - (1,3) - (2,3)

路線2：(1,1) - (1,2) - (2,2) - (2,3)

路線3：(1,1) - (2,1) - (2,2) - (2,3)

2.公共子序列

我們稱序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列當(dāng)且僅當(dāng)存在 嚴(yán)格上升 的序列< i1, i2, ..., ik >，使得對(duì)j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。?

現(xiàn)在給出兩個(gè)序列X和Y，你的任務(wù)是找到X和Y的最大公共子序列，也就是說要找到一個(gè)最長的序列Z，使得Z既是X的子序列也是Y的子序列。

輸入

輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個(gè)長度不超過200的字符串，表示兩個(gè)序列。兩個(gè)字符串之間由若干個(gè)空格隔開。

輸出

對(duì)每組輸入數(shù)據(jù)，輸出一行，給出兩個(gè)序列的最大公共子序列的長度。

樣例輸入

abcfbc ? ? ? ? ? ? ? ?abfcab

programming ? ?contest?

abcd ? ? ? ? ? ? ? ? ? mnp

樣例輸出

4

2

0

答案和更多內(nèi)容請(qǐng)查看網(wǎng)站：【試卷中心 -- C/C++ 四級(jí)】

網(wǎng)站鏈接?

青少年軟件編程歷年真題模擬題實(shí)時(shí)更新

================================================