資料結構與演算法 課程教學投影片.

Slides:



Advertisements
Similar presentations
九族文化村兩天一夜遊 組員 : 傅淳鈺 9A0E0019 黃湘蓉 4A 陳誌龍 9A0K0026 潘韋舜 9A0B0951 何奇龍 4A
Advertisements

北汽集团越野车分公司 校园宣讲会 北汽集团越野车分公司 校园宣讲会. 公司概况 目标与意义 1 目标: 落实市政府关于打造中 国专业化军车、越野车 基地指示的重要举措; 落实北汽集团自主品牌 乘用车发展战略的具体 举措。 北汽越野车分公司 意义: 完善集团已有产品体系 和生产布局,合理配置 资源;
与优秀的人在一起
2009年广播影视人事人才统计年报业务培训 广东省广电局人事处 2010年1月6日
共通能力科研習計劃書 簡 報 篇.
102年度統一入學測驗 報名作業說明會 時 間:101年12月14日(星期五) A.M.9:00~10:20 地 點:行政七樓講堂
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
普 通 话.
26个英语字母 let's go!.
《马克思主义基本原理概论》 第四章  资本主义的形成及其本质.
小微企业融资担保产品介绍 再担保业务二部 贾天
2007年房地产建筑安装企业 税收自查方略 河北省地方税务局稽查局 杨文国.
佛教大雄中學 2007年度香港中學會考 放榜輔導 升學及就業輔導組.
第三讲 匀变速直线运动 学 科:物 理 主讲人:吴含章. 第三讲 匀变速直线运动 学 科:物 理 主讲人:吴含章.
2016届高三期初调研 分析 徐国民
凉山州2015届高考情况分析 暨2016届高三复习建议 四川省凉山州教育科学研究所 谌业锋.
[聚會時, 請將傳呼機和手提電話關掉, 多謝合作]
二综防火设计分析.
致亲爱的同学们 天空的幸福是穿一身蓝 森林的幸福是披一身绿 阳光的幸福是如钻石般耀眼 老师的幸福是因为认识了你们 愿你们努力进取,永不言败.
增值评价 2014级 初中起点报告 解读培训 辽宁省基础教育质量监测与评价中心.
网络游戏 对 大学生生活方式 影响 11影视动画2班 石天启组.
动态规划 中山纪念中学 宋新波 本模板来源于网络,由第一课件网整理发布,免费分享给大家使用。
第四章 时间序列的分析 本章教学目的:①了解从数量方面研究社会经济现象发展变化过程和发展趋势是统计分析的一种重要方法;②掌握时间数列编制的基本要求;③理解和掌握水平速度两方面指标的计算及运用④理解和掌握长期趋势分析和预测的方法。 本章教学重点:现象发展的水平指标和速度指标。 本章教学难点:现象变动的趋势分析。
講師:聯捷聯合會計師事務所 張志勝會計師(所長)
基因分离规律习题课.
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
C语言基础——指针的高级应用 Week 05.
組員:蔡典龍4970E027 蕭積遠4970E026 王建智4970E050 李雅俐4970E025 賴品言4970E054
会计账簿 6 会计账簿的概念、意义、种类 会计账簿的格式及登记 结帐与对账 上海大学 会计系.
课标教材下教研工作的 实践与思考 山东临沂市教育科学研究中心 郭允远.
天气和气候.
建筑业能源年定报布置会 第三次全国经济普查暨 2013年统计年报和2014年统计定报
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
運輸與空間的交互作用 運輸發展的階段 一、分散的港口 二、侵入路線 三、發展支線 四、初步相互連結 五、完全相互連結 六、高度優越的幹線
普及组近5年NOIP试题分析 安徽师大附中 叶国平.
专题研讨课二: 数组在解决复杂问题中的作用
你一定要認識的數學家.
第5章 函数与模块化设计 学习目的与要求: 掌握函数的定义及调用方法 理解并掌握参数的传递方法 理解函数的嵌套与递归调用
循环结构又称为重复结构:用来处理需要重复处理的问题,它是程序中一种很重要的结构。
张沛老师带你玩转国际英标.
建國國小英語教學線上課程 字母拼讀篇(一) 製作者:秦翠虹老師、林玉川老師.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
第八章 欧氏空间 8.1 向量的内积 8.2 正交基 8.3 正交变换 8.4 对称变换和对称矩阵.
数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军
中央广播电视大学开放教育试点课程 数据结构 辅导教师 倪政林.
耆康會長者中央議會 <<長者與社會參與>>計劃培訓
引例 囚徒困境: 甲、乙两个人一起携枪准备作案,被警察发现抓了起来。如果两个人都不坦白,警察会以非法携带枪支罪而将二人各判1年;如果其中一人招供而另一人不招,坦白者作为证人将不会被起诉,另一人将会被重判15年;如果两人都招供,则两人都会因罪名各判10年。这两个囚犯该怎么办? 斗鸡博弈: 两只斗鸡遇到一起,每只斗鸡都有两个行动选择:一是退下来,一是进攻。如果一方退下来,而对方没有退下来,对方获得胜利,这只公鸡则很丢面子;如果对方也退下来,则双方打个平手;如果自己没退下来,而对方退下来,自己则胜利,对方则失败
第 4 章 递 归 教学要求 本章重点 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例
第四章 第三节 最短路径算法.
概率论 ( Probability) 2016年 2019年4月15日5时31分.
二元一次聯立方程式 代入消去法 加減消去法 自我評量.
陣列 (Array)      授課老師:蕭志明.
1.3 算法案例 第一课时.
光电子技术学课件之二: ——激光原理和技术简介
请编写程序在屏幕上打印出一个“*”? printf(”*\n”); 请编写程序在屏幕上打印四行,每行一个“*”?
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
课前注意 课前注意 大家好!欢迎加入0118班! 请注意以下几点: 1.服务:卡顿、听不清声音、看不见ppt—管家( ) 2.课堂秩序:公共课堂,勿谈与课堂无关或消极的话题。 3.答疑:上课听讲,课后答疑,微信留言。 4.联系方式:提示老师手机/微信: QQ:
陣列的位址計算.
指数 对数 指数 幂函数举例 对数 幂函数举例.
1. 电能表是测量 的仪表,1kW·h电能可供一只“220V 40W”灯泡正常工作 _____h.
电的重要性.
第3章 多维随机向量及其分布 3.1 随机向量及其联合分布函数 3.2 二维离散型随机向量 3.3 二维连续型随机向量
第三节 二项式定理.
指 數 記 法 指 數 律 自我評量.
线性回归.
第八章 服務部門成本分攤.
顺序查找与二分查找复习.
顺序查找与二分查找复习.
“微讲座”(八)——带电粒子在复合场中的运动轨迹分析
幂的乘方.
Presentation transcript:

資料結構與演算法 課程教學投影片

第四章–陣列結構的演算法應用 本章各段大綱 4-1 多項式的運算 4-2 捉大頭抽籤遊戲 4-3 魔術方塊 4-4 對獎演算法與資料結構

4-1 多項式的運算 p(x)=anxn+an-1xn-1+…+a1x1+a0(運算式) 陣列表示法範例如下:   1 2 n n+1 陣列 an an-1 ............... a1 a0 註標 多項式階次要加以紀錄(紀錄於註標0的內容) 註標(i)與指數的關係是 指數=n-i+1

4-1 多項式的運算 練習2 方程式係數以陣列表示為p(m)=a31m31+a15m15+a7m7+a3m3+a1m1 法二指標之對應表 練習2 方程式係數以陣列表示為p(m)=a31m31+a15m15+a7m7+a3m3+a1m1 法一:設p(m)=a(31)m31+a(15)m15+a(7)m7+a(3)m3+a(1)m1,以基本陣列表示法進行運算 法二:以右表之關係式列出註標x與指數y的關係 令p(m)=a(4)m31+a(3)m15+a(2)m7+a(1)m3+a(0)m1, 假設關係式具有 y=a*2x+b 型式,將下表x,y帶入,可解得 y=2*2x-1=2(x+1)-1,因此演算法可以迴圈及陣列帶入計算 註標x 指數y 1 3 2 7 15 4 31 法一:基本陣列表示法之演算法 int a[n+2],i,pk=0,k=2; //此演算法中n=31 a[32]=n; // 存放項目大小, a[0]存放x0係數 a[1]=1;a[3]=3; a[7]=3;... // 給定係數 for(i=0;i<=n;i++) pk=pk+a[i]*pow(k,i); // k=2, pow()得到2i 法二:壓縮陣列表示法(於後說明)之演算法 int a[n+2],i,pk=0,k=2; //此演算法中n=4 a[5]=n; // a[5]不為係數項,用於存放項目大小 a[0]=1;a[1]=3; a[2]=7;... // 給定係數 for(i=0;i<=n;i++) pk=pk+a[i]*pow(k,pow(2,(i+1))-1); // k=2, pow()得到2i 此演算法的時間複雜度與空間複雜度均O(n) (n為迴圈大小,也是冪次項大小) 此演算法的時間複雜度與空間複雜度均O(n) (注意:為迴圈大小,非冪次項大小)

4-1 多項式的運算 p(x)=3x100+2x50+ x25+4 (運算式,求p(k)) 以基本陣列存放註標及係數,過於浪費空間 法一:壓縮陣列表示法如下: V陣列代表係數,但V(0)放項目數m W陣列代表冪次 Index 1 2 ... m V an ai a0   W n i Index 1 2 3 4 V   W 100 50 25 int V[4+1],W[4+1],i,pk,k=2, m=4; V[0]=m; V[1]=3;V[2]=2;... // 設定係數 for(i=1;i<=m;i++) pk=pk+V[i]*pow(k,W[i]);

4-1 多項式的運算 p(x)=3x100+2x50+ x25+4 (運算式) 法二:壓縮陣列表示如下: 設非零項目m個,一維陣列W共2m+1,註標0存放項目m,其餘註標依序放入非零項目的係數及冪次。   1 2 3 4 ... 2m-1 2m W m an n ai i 第1項 第m項   1 2 3 4 5 6 7 8 W 100 50 25

以k帶入多項式,第i項值為:W[2*i-1]*pow(k,W[2*i]) p(x)=3x100+2x50+ x25+4 以k帶入多項式,第i項值為:W[2*i-1]*pow(k,W[2*i])   1 2 3 4 5 6 7 8 W 100 50 25 第1項 第2項 第3項 第4項 以係數看 項次與註標關係 關係式為2*i-1 以冪次看 項次與註標關係 關係式為2*i int W[2*4+1],i,pk,k=2, m=4; //m為項次 W[0]=m; W[1]=3;W[2]=100;... // 設定係數,冪次 for(i=1;i<=m;i++) pk=pk+W[2*i-1]*pow(k,W[2*i]); 項次 註標 1 2 3 5 4 7 項次 註標 1 2 4 3 6 8 空間複雜度:所需的空間數為2m+2(法一) 及2m+1(法二) ,複雜度為O(m) 時間複雜度:即迴圈數,O(m)

4-1-4 兩個變數的多項式的運算 -基本陣列表示法 基本陣列表示法如下, 宣告二維陣列(m+1)*(n+1):   範例 P(x,y)=x3+2x2y+3x+4y4+5y2+6 x0 x1 : xm y0 y1 ………… yn a00 a01 ………… a1n a10 a11 ………… a2n am1 an2 ………… amn 1 2 3 4 6 5 計算時只要使用陣列的走訪 (由左至右,由上至下) for(i=0;i<=m;i++) for(j=0;j<=n;j++) Pk=pk+A[i][j]*(x**i)*(y**j); 注意:此非完整C程式語法

4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法 p(x,y)=x100+2x50y50+3x25y50+4y100+5 要以基本陣列表示時,此陣列有(m+1)*(n+1)空間,但只利用五個元素,因此以壓縮陣列表示較為節省空間 法一:壓縮陣列表示法1如下:V存放係數,XW存放X的冪項,YW存放Y的冪項,時間複雜度O(mn)     1 2 3 4 5 V XW 100 50 25 YW

4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法 p(x,y)=x100+2x50y50+3x25y50+4y100+5 法一:稀疏矩陣的壓縮陣列表示法   1 2 3 4 5 V XW 100 50 25 YW int V[m+1],XW[m+1],YW[m+1]… for(i=0;i<=m;i++) pk=pk+V[i]*(x**XW[i])*(y**YW[i]); 若共m個非零項,所需空間 3m+1,空間複雜度O(m) 執行迴圈m 次,時間複雜度O(m) ,效率比基本矩陣運算高出許多

4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法 p(x,y)=x100+2x50y50+3x25y50+4y100+5 (運算式) 法二:稀疏矩陣的壓縮陣列表示法如下:     1 2 3 4 5 6 … 3r-2 3r-1 3r r 第一項 係數 X冪次 Y冪次 第二項 第r項 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 100 50 25

4-1-4 兩個變數的多項式的運算 -壓縮陣列表示法 p(x,y)=x100+2x50y50+3x25y50+4y100+5 (運算式) 法二:稀疏矩陣的壓縮陣列表示法     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 100 50 25 int V[3m+1]…//非零項有m項 for(i=0;i<=m;i++) pk=pk+V[3*i-2]*(x**V[3*i-1])*(y**V[3*i]); 若共m個非零項,所需空間 3m+1,空間複雜度O(m) 執行迴圈m 次,時間複雜度O(m) ,效率比基本矩陣運算高出許多

4-1 多項式的運算 4-1-5 多項式相加 基本陣列表示法的演算法 將相同註標的A矩陣與B矩陣資料相加即可 01 02 03 04 05 06 07 08 09 10 /* 演算法名稱:兩個多項式相加的演算法 (兩個多項式的項數要相同) */ /* 輸入:二個用陣列代表的多項式 */ /* 輸出:用陣列代表的二個多項式相加的結果 */   poyadd(A,B,C,n) { int A[n+2],B[n+2],C[n+2],i; for (i=1;i<=n;i++) C[i]=A[i]+B[i]; }

4-1 多項式的運算 4-1-5 多項式相加 陣列AV,AW代表A(x)多項式的係數及冪次,陣列BV,BW代表B(x)多項式的係數及冪次,底下為壓縮陣列表示法的演算法 比較A[i]及B[j] ,如果 i或j超過m,到步驟五 如果AW[i]=BW[j] ,即冪次相同,則CV[k]=AV[i]+BV[j] ,CW[k]=AW[i] ,k是目前多項式的項數,AW[i]及BW[j]運算後,i,j均往後加一 如果AW[i]>BW[j] ,即AW[i]冪次較高,則CV[k]=AV[i] ,CW[k]=AW[i] ,i往後加1,回至步驟1,再重新檢查。 如果AW[i]<BW[j] ,即BW[j]冪次較高,則CV[k]=BV[j] ,CW[k]=BW[j] ,j往後加1,回至步驟1,再重新檢查。 如果i=m+1,而j<m+1,代表B陣列尚有資料尚未運算,將B陣列剩餘的值全部搬到C陣列目前位置之後;如果i<m+1,而j=m+1,代表A陣列尚有資料尚未運算,將A陣列剩餘的值全部搬到C陣列目前位置之後。 範例:假設有二個多項式A(x)=x3+2x+2,B(x)=2x3+2x2+3,求C(x)=A(x)+B(x) ?

4-1 多項式的運算-多項式相加 範例:假設有二個多項式A(x)=x3+2x+2,B(x)=2x3+2x2+3,求C(x)=A(x)+B(x) ?   1 2 3 AV AW   1 2 3 BV BW   1 2 3 4 CV CW

4-1 多項式的運算-多項式相加

4-1 多項式的運算 有關兩個多項式相加減的詳細演算法 (兩個多項式的項數不同),請參考程式4_1.cpp的函式  void polyadd(AV,AW,BV,BW,CV,CW); polyadd演算法必須走訪過所有A、B陣列中的項目,所以走訪次數為A項次數+B項次數,假設A(x),B(x)多項式的非零項目分別有m1和m2個,則其時間複雜度為O(m1+m2),0≤m1,m2≤n。最差情況是m1=m2=n,時間複雜度為O(n) 多項式減法運算的演算法與加法運算的演算法相類似,只是將加法運算改為減法運算

4-2 捉大頭抽籤遊戲 遊戲解釋: 捉大頭抽籤遊戲如下一頁的附圖,最上面一排是參加抽籤者的名字,最下面一排是籤號、獎品或工差。每個人依序順著直線往下走,當碰到有橫線時,即轉向橫向前進,碰到直線再往下,以此累堆,則只要橫線不要跨過3條直線(只能跨在二直線之間),則此遊戲執行完畢後,最上面一排的每個人會一一對應到最下面一排的位直,且是1對1對應。

4-2 捉大頭抽籤遊戲 人名 簽號

4-2 捉大頭抽籤遊戲 遊戲的原理是應用到矩陣的交換運算,當你每劃一條橫線時,即代表這兩條直線的資料順序交換 例如上一頁的圖中, 原來{A0,A1,A2,A3,A4}順序的資料,經過第0層橫線後的順序為{A1,A0,A3,A2,A4},再經過第1層橫線後的順序為{A1,A3,A0,A2,A4},以此類堆,到最後一排的順序為{A4,A1,A0,A2,A3},對應到{P0,P1,P2,P3,P4}。

4-2 捉大頭抽籤遊戲

4-2 捉大頭抽籤遊戲 範例: 右圖之 變數設計 A陣列存放人名 A B C D... 0 1 2 3... ... 1 0 3 2... 0 1 2 3... ... 1 0 3 2... 0 1 2 3 1 3 0 2... 3 1 0 2... 3 1 2 0... B陣列存放編號 隨著演算過程變更順序 1 2 3 ... 1 3 2 ... ... B陣列最後結果 3 1 2 ... P陣列存放簽號 1 2 ... 預設2號為大頭

4-2 捉大頭抽籤遊戲 陣列M存放路徑佈局 1 2 3 A B C D... 0 1 2 3... 1 0 3 2... ... 0 1 2 3... ... 1 0 3 2... 0 1 2 3 1 3 0 2... 3 1 0 2... 3 1 2 0... 1 2 3

4-2 捉大頭抽籤遊戲 捉大頭抽籤遊戲的演算法如下, 其中bighead演算法的時間複雜度計算是走訪M陣列元素的次數,共有(mr+1)*(mc+1),其時間複雜度為O(mr*mc)。 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 /* 演算法名稱:捉大頭抽籤遊戲的演算法 */ /* 輸入:用陣列代表的資料,mr是最大層編號,mc是最大橫線編號 */ /* 輸出:捉大頭抽籤遊戲的結果 */ void bighead(A,B,P,M,mr,mc) { int i,j; for(i=0;i<=mr;i++) for(j=o;j<=mc;j++) if(M[i][j]==1)swap(B[j],B[j+1]); for(j=0;j<=mc;j++) printf(“第%d位抽籤者,名字%C,對應到籤號%d”, B[j],A[B[j]],P[j]); /*假設A陣列存放字元*/ }

4-3 魔術方塊 「魔術方塊」是一個古老的問題,它是在一個n×n的矩陣中填入1到n2的數字,n為奇數,使得每一行、每一列,每條對角線、橫線及直線加總的值都相等,例如圖4-4即為3×3和5×5的魔術方塊。

4-3 魔術方塊 H.Coxeter提出產生魔術方塊的規則如下,且這規則可用程式來實作。 由1開始填資料,且放在第0列的中間位置,如果是n×n的魔術方塊,則宣告陣列A為此魔術方塊,註標編號由0~n-1,所以中間位置為(n-1)/2。 將魔術方塊想像成上下左右相接,往左上角填入下一個數字,則有下列情況: (A)位置超出上方範圍,則用最底層相對應的位置。 (B)位置超出左邊範圍,則用最右邊相對應的位置。 (C)如果找到的位置已放入資料,則位置調為下一行,同一列位置且放入下一個數字。 (D)如果找到的位置未放入資料,則放入下一個數字。

4-3 魔術方塊 以3×3魔術方塊的產生方式為例,說明如下: 1. (n-1)/2=(3-1)/2=1,所以M[0][1]=1

4-3 魔術方塊 2. (0,1)位置往左上的位置為(-1,0),-1超出範圍,調整位置為(2,0),放入2。

4-3 魔術方塊 3. (2,0)位置往左上的位置為(1,-1),-1超出範圍,調整位置為(1,2),放入3。

4-3 魔術方塊 4. (1,2)位置往左上的位置為(0,1),目前已有資料,調整位置為往下,新位置為(2,2),放入4。

4-3 魔術方塊 5. (2,2)位置往左上的位置為(1,1),放入5。

4-3 魔術方塊 6. (1,1)位置往左上的位置為(0,0),放入6。

4-3 魔術方塊 7. (0,0)往左上的位置為(-1,-1),-1超出範圍,調整位置為(2,2),但(2,2)已有資料,所以往下,新位置為(1,0),放入7。

4-3 魔術方塊 8. (1,0)往左上的位置為(0,-1),-1超出範圍,調整範圍為(0,2),放入8。

4-3 魔術方塊 9. (0,2)往左上的位置為(-1,-1),-1超出範圍,調整範圍為(2,1),放入9。

4-3 魔術方塊 公式推演 位置(i,j)左上角位置為(i-1,j-1) 若(i-1)<0,則x座標調整為(i-1+n) 若(j-1)<0,則y座標調整為(j-1+n) 不管是否超出範圍,(i,j)左上角座標可以用下式求得 若放置位置已有資料時則下移一行 p=(i-1+n)%n g=(j-1+n)%n p=(i+1)%n 課本範例及光碟程式均有錯

4-3 魔術方塊 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /* 演算法名稱:魔術方塊的演算法 */ /* 輸入:一個正方形陣列M和維度n,n必須是奇數 */ /* 輸出:魔術方塊 */ void square(int *M,int n) { int p,q,k; p=0; q=(n-1)/2; M[0][q]=1; for(k=2;k<=n*n;k++) p=(p-1+n)%n; q=(q-1+n)%n; if(M[p][q]>0) p=(p+2+n)%n; q=(q+1+n)%n; M[p][q]=k; }else{ } 課本範例及光碟程式均有錯

4-3 魔術方塊 square演算法中由一個迴圈所構成,其執行了n2-1次,時間複雜度為O(n2),而n×n的魔術方塊至少要填入n2個數字,至少須Ω(n2)的時間,所以square演算法已達解這個問題的最佳演算法,其時間複雜度可表示為θ(n2)。

4-4 對獎演算法與資料結構 一般對獎的方式有許多型式 統一發票對獎(統一發票號碼的後幾位與開獎號碼相同) 序號對獎(用搖號碼球或抽籤方式開出中獎號碼,再從對獎資料中找尋是否有相同序號者)及樂透彩對獎。 以台灣發行的樂透彩為例,簽注的方式是從1到42的號碼中選出6個不重覆的號碼a0,a1,a2,a3,a4,a5,而主辦單位會開出6個號碼P0,P1,P2,P3,P4,P5,外加一個特別號P6,得獎方式如下頁

4-4 對獎演算法與資料結構 頭獎: 貳獎: 參獎 肆獎 伍獎 { a0,a1,a2,a3,a4,a5}={ P0,P1,P2,P3,P4,P5} 即6個號碼完全相同。 貳獎: { a0,a1,a2,a3,a4,a5}中的5個號碼出現在{ P0,P1,P2,P3,P4,P5}中 且另1個號碼等於P6。 參獎 { a0,a1,a2,a3,a4,a5}中有5個號碼出現在{ P0,P1,P2,P3,P4,P5}中 且另1個號碼不等於P6。 肆獎 { a0,a1,a2,a3,a4,a5}中有4個號碼出現在{ P0,P1,P2,P3,P4,P5}中。 伍獎 { a0,a1,a2,a3,a4,a5}中有3個號碼出現在{ P0,P1,P2,P3,P4,P5}中。

4-4 對獎演算法與資料結構

4-4 對獎演算法與資料結構

4-4 對獎演算法與資料結構 第一個演算法 lottol演算法用了三個迴圈來比較A和P陣列的值,總共執行6×6×n=36n的比較次數,時間複雜度為O(n)。 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 /* 演算法名稱:對獎的演算法一 */ /* 輸入:對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出:對獎結果陣列C */   void lottol(P,A,C,n) { int i,j,k; for(i=0;i<=n-1;i++) for(j=0;j<=5;j++) for(k=0;k<=5;k++) if(A[i][j]==p[k]) C[i]=C[i]+1; }

4-4 對獎演算法與資料結構 第二個演算法 條件: 1. 如果lotto1演算法所用的資料結構陣列P除了特別號之外,其餘6個中獎號碼已排序過 2. 陣列A中的每行(row)資料已排序 比較的方法可以用類似多項式加法polyadd演算法一樣,第0個中獎號碼P[0]和第0個簽注號碼A[k][0]比較,則有下列情況: P[0]=A[k][0],用i代表P的註標,j代表A的第2維註標,則i=i+1,j=j+1,預備再比較下一個號碼。 P[0]>A[k][0],代表P[0]比較大,則P[0]再準備與下一個A[k][1]比較,即j=j+1。 P[0]<A[k][0],代表P[0]比較小,則準備下一個P[1]與A[k][0]相比較,即i=i+1。

4-4 對獎演算法與資料結構 所以調整上述的想法後,其演算法步驟如下: i=0;j=0。 如果i或j超出5,跳至步驟6。 如果P[i]=M[k][j],則count[k]=count[k]+1,i=i+1,j=j+1,回到步驟2。 如果P[i]>M[k][j],則j=j+1,回到步驟2。 如果P[i]<M[k][j],則i=i+1,回到步驟3。 結束。

4-4 對獎演算法與資料結構

4-4 對獎演算法與資料結構 由上述演算步驟和說明可得知lotto2演算法如下 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /* 演算法名稱:對獎的演算法二 */ /* 輸入:對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出:對獎結果陣列C */   void lotto2(P,A,C,n) { int i,j,k; for(k=0;k<=n-1;k++) i=o;j=0; while(i<=6&&j<=6) if(P[i]==A[k][j]) i++;j++; C[k]=C[k]+1; } else if(P[i]>A[k][j]) i++; else j++;

4-4 對獎演算法與資料結構 述lotto2演算法用了一個不定迴圈while,執行迴圈的次數最少6次(當6個號碼都一樣時),最多12次(當i,j的值皆從0開始,逐步遞增到6時),如果有n筆資料,則最佳情況是執行6n次,最差情況是執行12n次,時間複雜度雖然也是O(n),但是就實際執行次數來看,它比reloto1演算法的固定36n次,兩者相比為1/6~1/3倍,即lotto2較lotto1快3至6倍。而且lotto2演算法是用到多項式加法polyadd演算法的原理,所以學習「資料結構與演算法」時,所學習過的方法或結構,並不是只限用於解決該類問題而已,而是廣泛地吸收各種演算法的原理和結構設計,以利於應用在各類問題的解答。

4-4 對獎演算法與資料結構 第三個演算法 前述lotto1及lotto2研算法以比較數字為基礎 只要提取陣列註標的值再加以累加即可得到相同數字的個數 方法: 陣列P的大小改為43(註標由0~42) ,陣列數值以0或1標示中簽號碼 例如中獎號碼為5,10,15,22,32,42,則P陣列為 簽注號碼為A[k][j] ,欲知第k筆的第j個號碼是否中獎,只要提出P陣列註標為A[k][j]的值即可知道,並將其值加到C[k]中 C[k]=C[k]+P[A[k][j]] 如果號碼相同,則C[k]會加1否則加0 要計算一筆資料中獎號碼,只要用一層迴圈取得簽注號碼,再應用上述程式即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . 41 42 for(j=0;j<6;j++) C[k]=C[k]+P[A[k][j])

4-4 對獎演算法與資料結構

4-4 對獎演算法與資料結構

4-4 對獎演算法與資料結構 01 02 03 04 05 06 07 08 09 10 11 /* 演算法名稱:對獎的演算法三 */ /* 演算法名稱:對獎的演算法三 */ /* 輸入:對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出:對獎結果陣列C */   void lotto3(P,A,C,n) { int k,j; for(k=0;k<=n-1;k++) for(j=0;j<=6;j++) C[k]=C[k]+P[A[k][j]]; }

4-4 對獎演算法與資料結構 第4個演算法 將多個數字的比較換算為一個數字的比較 (執行時間:比較敘述 > 一般的四則運算) 樂透數字為6個1~42的數字(現在小樂透1~38,大樂透為1~49) 以原先設計的開獎陣列P每個號碼(由小到大)分別乘上1005, 1004, 1003, 1002, 1001, 1000, 則得到新數字PM PM=1005*P[0]+1004*P[1]+1003*P[2]+1002*P[3]+1001*P[4]+1000*P[5]

4-4 對獎演算法與資料結構 例如6個號碼5,10,15,22,32,42經上述公式換算結果PM=51015223242。則樂透彩的演算法如下: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 /* 演算法名稱:對獎的演算法四 */ /* 輸入:對獎號碼陣列P,簽注號碼陣列A,n為號碼個數 */ /* 輸出:對獎結果陣列C */   void lotto4(P,A,C,n) { int i,j; long PM,AM; PM=0;AM=0; for(i=0;i<=6;i++) PM=PM+P[i]*10**(2*i) for(i=0;i<=n-1;i++) for(j=0;j<=6;j++) AM=AM+A[i][j]*10**(2*j); if(PM==AM) C[i]=C[i]+1; }

4-4 對獎演算法與資料結構 lotto4演算法的執行次數計算包括產生PM的6次,產生AM共有6n次,比較PM和AM共有n次,所以共有6+6n+n=6+7n次,時間複雜度是O(n)。 但lotto4只能比較出數字是否完全一樣,且數字序列必須先排序過,因為第k筆的數字全中時C[k]=1,否則C[k]=0,而lotto3演算法可由C[k]的值得知簽中幾個號碼,C[k]的值界於0~6之間。 Lotto4演算法主要是介紹有時候設計演算法時,可以朝數字系統方向思考,例如第13章介紹的雜湊函數即是利用雜湊法將資料安排在特定的位置,可利用於資料的搜尋,此即大家所執知的雜湊搜尋演算法。

4-4-5 問卷調查與電腦閱卷 以電腦閱卷模仿lotto3演算法為例,假設題目皆是選擇題,選答有1,2,3,4四種情況,共有m題,答對者給4分,答錯者倒扣1分,則可以宣告答案的陣列A為二維陣列,第1維是題目序號,第2維是答案序號,陣列中所存放的值是4或-1,4代表選答正確給4分,-1代表選答錯誤倒扣1分,則其結構如下:

4-4-5 問卷調查與電腦閱卷 另考生作答的資料以二維陣列S來存放,第1維是考生序號,第2維是題目序號,S陣列存放的資料為作答資料,則其陣列結構如下:

4-4-5 問卷調查與電腦閱卷

4-4-5 問卷調查與電腦閱卷 電腦閱卷的演算法如下: 01 02 03 04 05 06 07 08 09 10 11 /* 演算法名稱:電腦閱卷的演算法 */ /* 輸入:A為答案陣列資料,S作答陣列資料 */ /* 輸出:K為考生的陣列成績資料 */   void comexam(A,S,K,m,q,n) { int A[m+1][q+1],S[n][m+1],K[n]; for(i=0;i<=n-1;i++) for(j=0;j<=m;j++) R[i]=R[i]+A[j][S[i][j]]; }