- 36 - 成都树德实验中学Pascal程序设计
end； if st>0 then begin
c：=out；
c[ot+1]：=s[st]；
push(c，s，it，ot+1，st-1)； end； if ot=n then begin
num：= num+1； for k：=1 to n do write(out[k])； write(’’：5)； end； end； begin
for k：=n downto 1 do
inp[k] ：=chr(65-k+n)； num：=0；
push(t，t，n，0，0)； writeln（’num=’，num）； readln； end.
当程序运行后，其输出结果是__________。 4、
program exp2_4； var n：integer；
function d(n：integer)：longint； begin
case n of
1：d：=0； 2：d：=1；
else d：=(n-1)*(d(n-1)+d(n-2))； end； end； begin repeat
write(’n=’)； readln(n)；
if n<=0 then writeln(’Once more!’)； until n>0；
writeln（’d=’，d(n)）； readln； end.
当程序运行后，其输出结果是__________。 三、完善程序
1、求子串位置。从键盘输入两个字符串x1，x2，要求查找出x2在x1字符串中的位置（起始位置）。
【算法分析】
⑴用两个变量分别表示输入的字符串，并求出两个字符串的长度；
成都树德实验中学Pascal程序设计 - 37 -
⑵利用i，j变量作为扫描两个字符串的指针；
⑶扫描两个字符串，当其相等时，将指针向下一个字符，当j的值大于len2时，则输出x2在x1中的位置。
⑷若子串位置不匹配，则使I的指针回溯，j指针重新指向子串的第一个字符。 Program exp3_1；
var x1，x2：string；
i，j，len1，len2，ps：integer；
function pos1(r1，r2：string；l1，l2：integer)：integer； var i，j：integer； begin
i：=1；j：=1；
while (i<=l1) and ( j<=l2) do
if r1[i]= r2[j] then begin ③ ； ④ end
else begin ⑤ ； ⑥ end； if j>12 then ⑦ else ⑧ ； end； begin
readln(x1)； readln(x2)； writeln(x1)； writeln(x2)；
len1：= ① ； len2：= ② ；
ps：=pos1(x1，x2，len1，len2)； writeln(ps：5)； end.
2、背包问题 【问题描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为xk，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于xk，而价值的和为最大。
【算法分析】
① 记w(1), w(2), ?, w(n)每种物品的重量，u(1), u(2), ?, u(n)为每种物品的价值，x(1), x(2), ?, x(n)为每种物品选取的数量，问题成为满足条件∑x(i)w(i)≤xk，而且∑x(i)u(i)为最大。
② 记fk(y)为取前k种物品，限制重量为y时取得价值最大，则：f0(y)=0，即对一切y，一件物品都不取时，最大价值为0；fk(0)=0时，即最大重量限制为0时，不能取得任何物品，所以最大价值也为0；f1(y)=[y/w1]u1，即仅取第一种物品，则最大价值为尽可能多的装第一种物品，所以能装的数量为[y/w1]，而得到的价值为[y/w1]u1。
下面用一个具体的例子来说明求解的过程。 n=4, xk=10
w1=2, w2=3, w3=4, w4=7 u1=1, u2=3, u3=5, u4=9 下面列出fk(y)：
- 38 - 成都树德实验中学Pascal程序设计
y x 1 2 3 4 1 0 0 0 0 2 1 1 1 1 3 1 3 3 3 4 2 3 5 5 5 2 4 5 5 6 3 6 6 6 7 3 6 8 9 8 4 7 10 10 9 4 9 10 10 10 5 9 11 12 ③ 图中第1行表示k=1，即取第一种物品，当y=1时，无法取，所以f1(1)=0，当y=2时，可取1个第一种物品，价值为1，…，当y=10（即xk），此时，可取5个第一种物品，价值为5。
④ 当可以取2种物品时。若y=1则为0（什么都不能取）；当y=2时，仅能取第一种物品，所以f2(2)=1；当y=3时，有2种取法。取一个第一种物品，价值为1；取一个第二种物品价值为3，取大者，所以f2(3)=3。以此类推。计算f2(10)时，有2种考虑，第一种是全部取第一种，即f1(10)=5；第二种是由f2(7)+3=6+9，取大者，得到f2(10)=9。
⑤ 上面给出的是计算f(i , j)的方法，但是还不能确定每种物品的选取个数。下面我们用倒推法来求出每种物品的个数。
记f(n, xk)为目标，检查：f(n-1, xk)与f(n, xk-wn)+un，若前者大，则无输出，由f(n, xk) → f(n-1, xk)。若后者大，则输出wn，计算f(n, xk-wn)。当n-1， n-2，…，到达1时，则全部输出。
Program package；
const maxxk=400；maxn=20； type tlist=array [1..maxn] of byte；
tmake=array[0..maxn，0..maxxk] of integer； var n，xk：integer； w，u：tlist； f：tmake； procedure init； var i：byte； begin
fillchar(w，sizeof(w)，0)； fillchar(u，sizeof(u)，0)； readln(n，xk)； for i：=1 to n do
① ； end；
procedure make； xar i，j：byte； begin
for i：=1 to n do begin
for j：=1 to w[i] -1 do f[i，j]：=f[i-1，j]； for j：= w[i] to xk do
if f[i-1，j] >f[i，j-w[i]]+u[i] then ② ； else ③ ； end； end；
procedure print； var get：tlist；
成都树德实验中学Pascal程序设计 - 39 -
i，j：byte； begin
fillchar(get，sizeof(get)，0)；
i：= ④ ；j：= ⑤ ； while i>0 do
if f[i，j]=f[i-1，j] then dec(i) else begin
dec(j，w[i])； ⑥ ； end；
writeln(’n=’，n，’’，’xk=’，xk)； writeln(’max worth=’， ⑦ )； for i：=1 to n do
writeln(’no.’,i',weight:’,w[i]:2,’worth:’,u[i]:2,’get’,get[i]:2)； end； begin init； make； print； end.
四、编写下列程序（要求先写出问题的算法，再编写程序代码）
1、将1,2,…,9共9个数，排列成下列三角形（图1），其中a～i分别表示1,2,…,9中的一个数字，并要求同时满足下列条件：
a b c d e f g h i
图1
⑴ a ⑵ b ⑶ a+b+d+f=f+g+h+i=i+e+c+a=p。 程序要求：根据输入的边长之和P，输出所有满足上述条件的三角形的个数以及其中的一种方案。 2、如图2所示的数字三角形，请编写一个程序计算从顶到底的某处的一条路径，使该路径的数字和最大，并输出路径。 数据的输入采用：首先输入总行数，再按照每行进行数据输入。 5 7 7 3 8 3 8 8 1 0 8 1 0 2 7 4 4 2 7 4 4 4 5 2 6 5 4 5 2 6 5 图2 3、设函数定义如下： f(0)=0，f(1)=1； f(2n)=f(n)：f(2n+1)=f(n)+f(n+1)，n=1，2，3，…要求对给定的n>=0，计算函数f(n)的值。 - 40 - 成都树德实验中学Pascal程序设计 采用两种编程方法，递归设计和非递归程序设计。 4、设计一个算法，从n项不同价值不同重量的物件中选取一部分，在不超过规定重量的原则下，使所选物品的总价值最大。 5、从三个元素（例如1，2，3）的字符表中选取字符，生成一个有n个符号的序列，使得其中没有2个相邻的子序列相等。如长度n=5的序列“12321”是合格的，而“12323”和“12123”都是不合格的。 6、输入一个十进制数，将其转换成十六进制的数。十六进制数中的0—9，用十进制的0—9表示，而10—15则分别用A，B，C，D，E，F表示。例如： 11150=2×(16)3+11×(16)2+8×(16)1+14×(16)0 则其十六进制数表示为：2B8E。 7、已知6个城市，用c[i, j]表示从城市i到城市j是否有单向的直达汽车（1≤i≤6，1≤j≤6）。 1 城市i到城市j有单向直达汽车； c[i, j]={ 0 城市i到城市j无单向直达汽车。 编写一个程序，给出城市代号i，打印出从该城市出发乘汽车（包括转车）可以到达的所有城市。 其城市之间直达汽车情况如下图： 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 8、求多精度a除以多精度b的商和余数。 9、四塔问题 三塔问题是大家非常熟悉的问题，下面详细说明四塔问题。设有A，B，C，D四个柱子（有时称塔），在A柱上有由小到大堆放的n个盘子，如图所示。 今将a柱上的盘子移动到d柱上去。可以利用b，c柱作为工作栈用，移动的规则如下： ① 一次只能移动一个盘子； ② 在移动的过程中，小盘子只能放到大盘子的上面； 编写一个程序，输出需要移动的盘子数和移动的步数。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库全国青少年信息学奥林匹克联赛培训习题(8)在线全文阅读。
相关推荐：