資源簡介

中小學教育資源及組卷應用平臺
第三單元練習及參考答案
1.假設有如下功能的演唱會門票預訂系統：
①按先到者先訂的規則進行預訂
②當門票都預訂完后，允許在隊伍中等待退票
請畫出算法流程圖并編程實現排隊預訂及等候退票功能。
參考答案
流程圖如下所示；
參考代碼如下所示：
#！/usr/bin/python
#-
-coding:utf-8-
-
total_tickets=3
#假設總票數為3
user_in_the_queue=[]
#定義排隊隊列，用列表模擬
def
get_ticket(user_name,amount)：
#如果還有票，返回購票數
#否則繼續排隊
global
total_
tickets
global
user_in_the_queue
left=total_tickets-amount
if
left>-1:
print(
user_name,
"get",amount,
"
tickets
successfully”)
total_tickets=total_tickets
-amount
return
else:
print(
user_name,
"can
not
get",amount,
"tickets,
wait
in
the
queue")
user_in_the_queue.append(user_name)
def
get_return_ticket(
user_name,
amount):
global
user_in_the_queue
first_user_in_the_queue=user_in_the_queue[len(user_in_the_queue)-1]
if
first_user_in_the_queue
==user_name:
get_ticket(
user_name,
amount)
else:
print(
user_name,
"can
not
get
ticket
first,
user
in
the
queue
now”)
user_in_the__queue.append(
user_name)
def
main():
user_name_a
="BoyA”
user_name_b
="BoyB”
user_name_c
="BoyC”
get_ticket(user_name_a,
3)
get_ticket(user_name_b,
3)
return_ticket(3)
get_return_ticket(user_name_c,
1)
get_return_ticket(user_name_b,
3)
def
return_ticket(amount):
global
total_tickets
total_tickets=total_tickets+amount
if
_name_==’_main_'：
main()
2.四方向迷官問題求解：假設有8X8的迷官如下所示(迷官用二維數組存放，可查閱資料了解二維數組)，1表示障礙不能通行，0表示通道可以通行。求解方法為：從人口開始出發沿著某一個方向向前試探，若能夠通行，則繼續試探前行：如果遇到障礙，馬上原路返回，并在該路口做上記號，換另一個方向繼續試探前行；重復上述步驟直到到達迷官的出口后結束。由于迷官錯綜復雜，靠人力來搜索迷官的所有通路是很費時、費力的一件事，因此可以借助計算機編程來完成。
入口00100010
00100010
00001100
01110000
00010000
01000100
01110110
00001000出口
①畫出求解迷官問題中，棧的變化過程。
②設計解四方向迷宮問題的算法并編程實現。
提示：在編程時，為避免考慮第一行不能朝上走、第一列不能朝左走，最后一列不能朝右走，最下一行不能朝下走，可以在迷官外圍設置一圈“圍墻”，這樣所有的位置都可考慮四個方向，圍墻等同于障礙(用1表示)，如下所示。
1111111111
1001000101
1001000101
1000011001
1011100001
1000100001
1010001001
1011101101
1000010001
1111111111
參考答案:
參考代碼如下所示：
#-
-coding:utf-8-
-
#！/usr/bin/python
import
sys
sys.setrecursionlimit(91832)
#set
the
maximum
depth
as
10000
Maze=[
[1,1,1,1,1,1,1,1,1,1],
[0,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,0,0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1]
]
used=[[
0
for
i
in
range(10)]
for
i
in
range(10)]
#use用于記錄已走過的坐標，防止重走，同時便于回溯
dx=[
]
dy=[
]
def
movel(i,srex,srey,dstx,dsty)：#i表示第幾步，當前坐標和終點坐標
print(i,
srex,
srey,
dstx,
dsty)
if
srex==dstx
and
srey==dsty:
print(‘run
away!’)
dx
append(
srex)
dy
append(
srey)
return
True
if
maze[srex+1][
srey]==0
and
used[
sex+1][srcy]==0:
print("down"，srcx+1，srcy)
dx.append(
srcx)
dy.append(
srcy)
srcx
+=1
used[srcx][srcy]=1
move(
i+1，srcx,
srcy,
dstx,
dsty)
used[srcx][srcy]=0
dx.
pop()
dy.
pop()
if
maze[srcx][srcy+1]==0
and
used[
srcx][
srcy+1]==0:
print("right"，srcx,
srcy+1)
dy.append(
srcx)
dy.append(
srcy)
srcy
+
=1
used[
srcx][srcy]=1
move(i+1，srcx,
srcy,
dstx,
dsty)
used[
srcx][srcy]=0
dx.
pop();
dy.pop();
if
maze[
srcx][
srcy-1]==0
and
used[
srcx][
srcy-1==0:
print("left",srcx,srcy+1)
dy.append(
srcx)
dy.append(
srcy)
srcy-=1
used[
srcx][srcy]=1
move(
i+1，srcx,
srcy,
dstx,
dsty)
dx.
pop()
dy.
pop()
if
maze[srcx-1][srcy]==0
and
used[srcx-1][srcy]==0:
print("up"，srcx,
srcy+1)
dx.append(srcx)
dy.append(srcy)
srcx-=
1
used[
srcx][srcy]=1
used[
srcx][srcy]=1
move(i+1，srcx,
srcy,
dstx,
dsty)
used[
srcx][srcy]=0
dx.
pop()
dy.pop()
def
main():
move(1,1,0,8,9)
#move(1,1,0,8,9)
for
i
in
range(len(dx)):
print('The{}step
is({},{})’.fomat(i+1,dx[i],dy[i]))
If
_name_=='_main_'：
main()
3.統計英文短文中某單詞出現的次數
(3)假設有一篇英文短文，請畫出算法流程圖并編程實現以下操作：
①統計英文短文中某單詞出現的次數。
②在英文短文中查找并替換某單詞。
參考答案：
采用遞歸的方式實現，流程圖如下所示：
參考代碼如下所示：
#！/usr/bin/python
#coding=utf-8
def
main()；
english_paragraph="Hello,world.This
is
a
new
world
for
you."
#紅色部分是編者假設的短文內容
find_word="word"
#紅色部分是編者假設的查找字符
replaced_word="you"
#紅色部分是編者假設的精換的字符
find(english_paragraph,find_word)
#查找字符
print("\r\n===========================\r\n”)
replace(english_paragraph,replaced_word,find_word)
#精換字符
def
alphabet_in_control_list(alphabet)：
control_list=["
",”,”,”.”,"\","\”]
if
alphabet
in
control_list:
return
True
return
False
def
find(english_paragraph,find_word)：
WillFind=”"
Total=0
for
alphabet
in
english_paragraph：
if
alphabet_in_control_list(alphabet)：
if
WillFind==find_word;
Total=Total+1
WillFind=””
else:
WillFind=WillFind+alphabet
print("find"，find_word,"in
paragraph,total:"，Total,".")
def
replace(english_paragraph,replaced_word,find_word)：
Will
Find=
“”
Replaced
Paragraph=""
for
alphabet
in
english_paragraph:
if
alphabet_in_control_list(alphabet):
if
Will
Find==find_word;
Replaced
Paragraph=Replaced
Paragraph+replaced_word+alphabet
else:
Replaced
Paragraph=Replaced
Paragraph+Will
Find+alphabet
Will
Find=””
else:
Will
Find=Will
Find+alphabet
print("replaced
result"，Replaced
Paragraph)
if
_name_=='_main_':
main()
棧dx存放路徑點的x坐標；棧dy存放路徑點的y坐標。
狀態(1)為初始狀態，dx,dy都是空棧。
狀態(2)為從入口進入，入口的x坐標1和y坐標1分別進棧。
狀態(4)為從(1,2)處繼續向前試探，如果路堵死，則回到(1,1)處，(1,2)點的x坐標1和y坐標2分別出棧。再從(1,1)處試探另一條路徑，通過這樣反復搜索與回溯，最終找到從入口到出口的路徑，而棧dx,dy中存放了路徑點的x坐標值和y坐標值。
狀態(3)為從(1,1)處繼續向前試探，如果有路，則下一點的坐標入棧，即x坐標1和y坐標2分別進棧。
開始
n←1
讀取英文段落的第n個字符
是否到達段落尾部？
是否標點符號？
WillFind是否要統計的單詞？
把字符追到臨時變量WillFind
Total←Total+1
清空臨時變量WillFind
n←n+1
輸出Total
結束
是
否
否
否
是
是
開始
n←1
讀取英文段落的第n個字符
是否到達段落尾部？
是否標點符號？
WillFind是否要替換的單詞？
ReplacedParagraph←ReplacedParaParagraph+WillFind+當前的標點符號
ReplacedParagraph←Replacedgraph+替換單詞+當前的標點符號
清空臨時變量WillFind
n←n+1
輸出ReplacedParagraph
結束
是
否
否
否
是
是
21世紀教育網
www.21cnjy.com
精品試卷·第
2
頁
（共
2
頁）
HYPERLINK
"http://21世紀教育網(www.21cnjy.com)
"
21世紀教育網(www.21cnjy.com)

展開更多......

收起↑