資源簡介

(共35張PPT)
常見的策略
川教版
八年級上
新知導入
03
常見策略
3
4
1
2
7
6
8
5
作為一名體育委員，需要把如右圖所示的8位同學，按照身高依次增高的順序，從左到右排序，你該怎么做?
新知講解
3
4
1
2
7
6
8
5
03
常見策略
總體思路：
選取一位同學，比這個同學矮的放在他左邊，比這個同學高的放在他右邊，并固定每一輪已選取過的同學。繼續對左右兩邊的同學執行上述過程，直到選取的同學左右兩邊未固定人數之和小于2。
排隊過程：
隨機選取4號同學為基準。
新知講解
03
常見策略
從右向左開始，依次將矮于4號的2號、1號同學放在左邊，4號同學固定住。
3
4
1
2
7
6
8
5
4號左邊的同學再重復上述步驟，可以固定住1、2、3號同學。
3
4
1
2
7
6
8
5
新知講解
03
常見策略
取6號同學為基準，將矮于6號的5號同學放在左邊，大于6號的7號同學放在最右邊，此時6號同學固定住，5號同學左右兩邊未固定人數之和為0，5號同學也固定住。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知講解
03
常見策略
以8號同學為基準，將矮于他的7號同學放在左邊，此時8號同學固定住。7號同學左右兩邊未固定人數之和為0，7號同學也固定住，此時所有同學排序完成。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知講解
03
常見策略
總體思路：
從左向右，依次兩兩比較，如果左邊同學高于右邊同學，就交換位置。重復執行上述過程，直到有一輪沒有任何一個同學移動位置。
3
4
1
2
7
6
8
5
排隊過程：
新知講解
03
常見策略
第一輪交換位置的結果如下，可以將最高的8號同學固定在最右側。
第二輪交換位置的結果如下，可以將7號同學固定。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知講解
03
常見策略
第三輪交換位置的結果如下，可以將6號同學固定。
第四輪沒有任何一個同學需要交換位置，所有同學排序完成。
3
4
1
2
7
6
8
5
新知講解
03
常見策略
總體思路:
每次選擇當前隊伍的最矮的同學，并把他放在當前隊伍的最左側。
每重復一次上述過程，當前隊伍中就排除上一輪移動的同學，隊伍長度便減一，直到沒有同學可以移動。
排隊過程:
第一輪排序，將最矮的1號同學和最左側的3號同學交換位置，當前隊伍去掉1號同學。
3
4
1
2
7
6
8
5
新知講解
第二輪排序，將最矮的2號同學和最左側的4號同學交換位置，當前隊伍再去掉2號同學。
第三輪排序，3號同學在當前隊伍中最矮，不需要調整，當前隊伍再去掉3號同學。
03
常見策略
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知講解
03
常見策略
第四輪排序與第三輪同理。第五輪排序，5號同學與最左側的7號同學交換位置。
第六輪排序與第三、四輪同理。第七輪排序交換7、8號同學位置，此時未排序隊伍長度為1，經過第八輪排序，與第三、四、六輪同理，排序完成。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知講解
03
常見策略
總體思路:
從左向右，把左邊第一個同學看成一個部分。拿右邊的同學一次跟左邊這個部分里的所有同學比較身高，如果高就站在右邊，如果矮就站在左邊，并把插隊的同學算入左邊部分。
重復執行上述過程，直到左邊部分裝滿8個同學。
排隊過程:
首先，將隊伍分為有序組和無序組兩部分，第一輪排序，默認將最左邊的3號同學分為有序組，剩余同學為無序組。
3
4
1
2
7
6
8
5
有序組
無序組
新知講解
03
常見策略
第二輪排序，無序組最左邊的4號同學出列與有序組內的同學從右到左開始比較，與3號同學相比較，因4號同學高于3號同學，則當前排列是有序的，4號同學回到空缺位置。此時3、4號同學組成了有序組，剩余同學則為無序組。
3
4
1
2
7
6
8
5
有序組
無序組
新知講解
03
常見策略
第三輪排序，1號同學出列比較，在有序組中從右到左依次與4號、3號同學進行比較，4號同學高于1號同學，則4號同學右移一位，3號同學也高于1號同學，則3號同學也右移一位。最終1號同學在有序組的第一個空缺位置固定下來。
有序組
3
1
2
7
6
8
5
4
無序組
3
1
2
7
6
8
5
4
有序組
無序組
新知講解
第四輪排序，2號同學依次與4、3、1號同學比較，4、3號同學依次右移一位，2號同學與1號同學比較，由于其高于1號同學，則回到3號同學空出來的位置。
第五輪排序與第二輪同理。
03
常見策略
3
1
2
7
6
8
5
4
有序組
無序組
3
1
2
7
6
8
5
4
有序組
無序組
新知講解
03
常見策略
第六輪排序，6號同學依次與7、4號同學比較。
第七輪排序，8號同學只與7號同學比較。
3
1
2
7
6
8
5
4
有序組
無序組
3
1
2
7
6
8
5
4
有序組
無序組
新知講解
03
常見策略
第八輪排序，5號同學依次與8、7、6、4號同學比較，最終回到6號同學移動后空出的位置，此時有序組已有8個同學，排序完成。
3
1
2
7
6
8
5
4
有序組
新知講解
03
常見策略
策略1
快速排序
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
快速排序源代碼如下：
新知講解
03
常見策略
策略2
排冒泡序
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
冒泡排序源代碼如下：
新知講解
03
常見策略
策略3
選擇排序
第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。
選擇排序源代碼如下：
新知講解
03
常見策略
策略4
插入排序
每一步將一個待排序的數據插入到前面已經排好序的有序序列中，直到插完所有元素為止。
插入排序源代碼如下：
新知講解
調試運行四個算法的源程序
想一想：四種排隊策略，哪一種排序效率更高?
任
務
一
試一試：列出寒假中你會做的事情，并用“策略2”的思維對這些事情的重要性進行排序。
任
務
二
合作探究
提出者：由美國數學家Bellman等人
提出時間：1957年
目的：用于研究多階段決策過程的優化問題。
作用：是解決多階段決策問題常用的最優化方法之一
概述：這個方法簡單來說，就是在當前狀態下，想要進入下一階段，什么樣的選擇是最優的。而且隨著狀態的變化，路徑也會發生改變。動態規劃是按照階段劃分的，把多階段問題轉化為一系列的單階段問題，然后利用各個階段之間的遞推關系，逐個確定每個階段的最優化決策，最終堆疊出多階段決策的最優化決策結果。
動態規劃中，前一個階段的結果影響著后一階段的決定。當前的決策受到之前決策的影響，下個階段的決策也會因為這次決策而發生改變。運用動態規劃的思路，就是在這條決策鏈里面實時調整，求得每個階段最優的那個解。
動態規劃
(
Dynamic
Programming)
在準備考試的過程中，你知道自己的目標（班級排名），也知道自己所處的階段（在班級的大概排名)，還知道實現目標的路徑（高效的學習方法和練習)。你要做的是根據整體的目標，選擇每個階段最優的行動。
舉例
步驟：
①建立數學模型來描述問題
②把求解的問題分成若干個子問題
③對每個子問題求解，得到子問題的局部最優解
④把子問題的解局部最優解合成原來解問題的一個解
貪心法(
Greedy
Algorithm)：
在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，算法得到的是在某種意義上的局部最優解
課堂練習
利用我們這節課所學策略，選擇一種策略幫助老師來按大小個給每位同學安排座位
總結本節課內容
課堂總結
常見的策略
選擇策略
策略1：快速排序
策略2：冒泡排序
策略3：選擇排序
策略4：插入排序
常見的策略
(四種排隊策略，哪一種排序效率更高？)
板書設計
https://www.21cnjy.com/help/help_extract.php中小學教育資源及組卷應用平臺
川教版信息技術八年級上冊《常見的策略》教學設計
課題
常見的策略
單元
第三單元
學科
信息技術
年級
八年級
學習目標
總結常見的策略選擇最合適的策略
重點
了解策略的制作過程
難點
能將策略轉變為偽代碼
教學過程
教學環節
教師活動
學生活動
設計意圖
導入新課
看視頻《月入百萬》在我們的生活、學習中，遇到的問題往往有各種不同的策略。選擇合適的策略對于解決問題能夠起到良好的促進作用，而一些策略也可以遷移到不同的問題中去。
看視頻
了解生活中的策略，知道策略可以應用到不同領域
講授新課
一
常見的策略作為一名體育委員，需要把如下圖所示的8位同學，按照身高依次增高的順序，從左到右排序，你該怎么做?
策略1：總體思路選取一位同學，比這個同學矮的放在他左邊，比這個同學高的放在他右邊，并固定每一輪已選取過的同學。繼續對左右兩邊的同學執行上述過程，直到選取的同學左右兩邊未固定人數之和小于2。排隊過程：隨機選取4號同學為基準。從右向左開始，依次將矮于4號的2號、1號同學放在左邊，4號同學固定住。4號左邊的同學再重復上述步驟，可以固定住1、2、3號同學。取6號同學為基準，將矮于6號的5號同學放在左邊，大于6號的7號同學放在最右邊，此時6號同學固定住，5號同學左右兩邊未固定人數之和為0，5號同學也固定住。以8號同學為基準，將矮于他的7號同學放在左邊，此時8號同學固定住。7號同學左右兩邊未固定人數之和為0，7號同學也固定住，此時所有同學排序完成。策略2：總體思路從左向右，依次兩兩比較，如果左邊同學高于右邊同學，就交換位置。重復執行上述過程，直到有一輪沒有任何一個同學移動位置。排隊過程:第一輪交換位置的結果如下，可以將最高的8號同學固定在最右側。第二輪交換位置的結果如下，可以將7號同學固定。第三輪交換位置的結果如下，可以將6號同學固定。第四輪沒有任何一個同學需要交換位置，所有同學排序完成。策略3：總體思路每次選擇當前隊伍的最矮的同學，并把他放在當前隊伍的最左側。每重復一次上述過程，當前隊伍中就排除上一輪移動的同學，隊伍長度便減一，直到沒有同學可以移動。排隊過程:第一輪排序，將最矮的1號同學和最左側的3號同學交換位置，當前隊伍去掉1號同學。第二輪排序，將最矮的2號同學和最左側的4號同學交換位置，當前隊伍再去掉2號同學。第三輪排序，3號同學在當前隊伍中最矮，不需要調整，當前隊伍再去掉3號同學。第四輪排序與第三輪同理。第五輪排序，5號同學與最左側的7號同學交換位置。第六輪排序與第三、四輪同理。第七輪排序交換7、8號同學位置，此時未排序隊伍長度為1，經過第八輪排序，與第三、四、六輪同理，排序完成。策略4：總體思路從左向右，把左邊第一個同學看成一個部分。拿右邊的同學一次跟左邊這個部分里的所有同學比較身高，如果高就站在右邊，如果矮就站在左邊，并把插隊的同學算入左邊部分。重復執行上述過程，直到左邊部分裝滿8個同學。排隊過程:首先，將隊伍分為有序組和無序組兩部分，第一輪排序，默認將最左邊的3號同學分為有序組，剩余同學為無序組。第二輪排序，無序組最左邊的4號同學出列與有序組內的同學從右到左開始比較，與3號同學相比較，因4號同學高于3號同學，則當前排列是有序的，4號同學回到空缺位置。此時3、4號同學組成了有序組，剩余同學則為無序組。第三輪排序，1號同學出列比較，在有序組中從右到左依次與4號、3號同學進行比較，4號同學高于1號同學，則4號同學右移一位，3號同學也高于1號同學，則3號同學也右移一位。最終1號同學在有序組的第一個空缺位置固定下來。第四輪排序，2號同學依次與4、3、1號同學比較，4、3號同學依次右移一位，2號同學與1號同學比較，由于其高于1號同學，則回到3號同學空出來的位置。第五輪排序與第二輪同理。第六輪排序，6號同學依次與7、4號同學比較。第七輪排序，8號同學只與7號同學比較。第八輪排序，5號同學依次與8、7、6、4號同學比較，最終回到6號同學移動后空出的位置，此時有序組已有8個同學，排序完成。上述四種不同的排隊策略，稍加完善就是快速排序、冒泡排序、選擇排序、插入排序四種算法，它們不僅僅在體育課上可以用到，在許多排序問題中都能夠使用，不過同樣的策略在不同的問題中，使用的效率不盡相同。①快速排序：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。源程序如下：②冒泡排序：類似于水中冒泡，較大的數沉下去，較小的數慢慢冒起來，假設從小到大，即為較大的數慢慢往后排，較小的數慢慢往前排。源程序如下：③選擇排序第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。源程序如下：④插入排序每一步將一個待排序的數據插入到前面已經排好序的有序序列中，直到插完所有元素為止。源程序如下：二
選擇策略雖然排隊策略的四種方法都能夠解決問題，但是它們耗費的時間和存儲空間是不同的，在指定策略的時候，應盡量從全局出發進行思考。任務一想一想：四種排隊策略，哪一種排序效率更高?試一試：列出寒假中你會做的事情，并用“策略2”的思維對這些事情的重要性進行排序。拓展閱讀：看視頻《了解動態規劃》動態規劃(
Dynamic
Programming)：作用：是解決多階段決策問題常用的最優化方法之一提出時間：1957年提出者：由美國數學家Bellman等人目的：用于研究多階段決策過程的優化問題。概述：這個方法簡單來說，就是在當前狀態下，想要進入下一階段，什么樣的選擇是最優的。而且隨著狀態的變化，路徑也會發生改變。動態規劃是按照階段劃分的，把多階段問題轉化為一系列的單階段問題，然后利用各個階段之間的遞推關系，逐個確定每個階段的最優化決策，最終堆疊出多階段決策的最優化決策結果。動態規劃中，前一個階段的結果影響著后一階段的決定。當前的決策受到之前決策的影響，下個階段的決策也會因為這次決策而發生改變。運用動態規劃的思路，就是在這條決策鏈里面實時調整，求得每個階段最優的那個解。舉例：在準備考試的過程中，你知道自己的目標（班級排名），也知道自己所處的階段（在班級的大概排名)，還知道實現目標的路徑（高效的學習方法和練習)。你要做的是根據整體的目標，選擇每個階段最優的行動。看視頻《貪心法》貪心法(
Greedy
Algorithm)：在對問題求解
(?https:?/??/?baike.?/?item?/?%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3?/?6693186"
\t
"https:?/??/?baike.?/?item?/?%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95?/?_blank?)時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，算法
(?https:?/??/?baike.?/?item?/?%E7%AE%97%E6%B3%95?/?209025"
\t
"https:?/??/?baike.?/?item?/?%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95?/?_blank?)得到的是在某種意義上的局部最優解步驟：??①建立數學模型來描述問題?②把求解的問題分成若干個子問題?③對每個子問題求解，得到子問題的局部最優解?④把子問題的解局部最優解合成原來解問題的一個解
課堂練習：利用我們這節課所學策略，選擇一種策略幫助老師來按大小個給每位同學安排座位
認真聽老師講解，不斷練習
小組合作完成看視頻看視頻
了解四種策略，知道策略的應用，深刻體會科技的不斷發展給生活帶來的便利學以致用，學會策略的應用了解什么是動態規劃了解什么是貪心法
課堂小結
總結本節課所講內容
學生總結概況
梳理本節課的知識點，完成學習目標，培養總結概況能力
板書設計
5
8
6
1
4
3
2
7
2
1
4
7
3
5
8
6
2
4
6
5
8
7
1
3
1
7
8
6
4
3
5
2
7
4
6
3
1
5
2
8
5
7
6
4
3
1
2
8
7
5
6
4
3
2
1
8
8
5
7
1
6
4
3
2
5
8
6
7
2
1
4
3
8
5
7
6
4
1
2
3
6
4
3
2
1
8
7
5
5
4
8
7
6
2
1
3
1
3
5
8
6
7
2
4
5
6
7
8
3
4
2
1
8
6
7
5
4
3
2
1
7
5
6
4
3
2
1
8
7
8
5
6
4
3
2
1
6
1
3
2
7
5
8
4
有序組
無序組
4
3
6
1
2
7
5
8
有序組
無序組
4
1
3
6
2
7
5
8
無序組
有序組
6
7
5
8
2
3
4
1
無序組
有序組
4
3
2
7
5
8
1
6
有序組
無序組
3
4
2
7
5
8
1
6
有序組
無序組
7
6
4
1
5
2
3
8
有序組
無序組
4
1
5
2
3
8
7
6
有序組
無序組
8
6
7
5
1
2
3
4
有序組
策略1：快速排序
策略2：冒泡排序
策略3：選擇排序
策略4：插入排序
常見的策略
常見的策略
選擇策略
21世紀教育網
www.21cnjy.com
精品試卷·第
2
頁
（共
2
頁）
HYPERLINK
"http://www.21cnjy.com/"
21世紀教育網(www.21cnjy.com)

展開更多......

收起↑