[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述-文庫(kù)吧
2024-12-08 12:46 本頁(yè)面
【正文】 ，就是程序。 本書(shū)采用 C語(yǔ)言與自然語(yǔ)言相結(jié)合來(lái)描述算法。 例 11 求兩個(gè)整數(shù) a,b的最大公約數(shù)的歐幾里德算法 ? (1) 數(shù) a 除以 b 得余數(shù) r；若 r=0，則 b為所求的最大公約數(shù)。 ? (2) 若 r≠0 ，以 b為 a， r為 b，繼續(xù) (1). ? 歐幾里德算法具體描述如下： ? input(a,b)； // 輸入的簡(jiǎn)略表示 ? r=a%b。 ? while(r!=0) // 實(shí)施輾轉(zhuǎn)相除 ? { a=b。 b=r。 r=a%b。 } ? print(b)。 // 輸出的簡(jiǎn)略表示 例 12 由 n個(gè) 1組成的整數(shù)能被 2021整除，求 n至少為多大？ (1) 試模擬整數(shù)豎式除法： ? 可以證明， n是存在的，且不大于 2021，因而以上豎式運(yùn)算總會(huì)停止。當(dāng)除運(yùn)算的余數(shù)為“ 0”時(shí)，數(shù)一數(shù)被除數(shù)中有多少個(gè)“ 1” 即可。 ? 設(shè)整數(shù)豎式除法每次試商的被除數(shù)為 a, 除數(shù)為2021，每次試商的余數(shù)為 c。 ? 循環(huán)以余數(shù) c≠0 作為循環(huán)條件。循環(huán)外賦初值：c=1111， n=4或 c=111， n=3等等。 ? 設(shè)置豎式除法模擬循環(huán)，循環(huán)中被除數(shù)a=c*10+1，試商余數(shù) c=a%2021。 ? 若余數(shù) c=0，結(jié)束循環(huán)，輸出結(jié)果； ? 否則，計(jì)算 a=c*10+1為下一輪運(yùn)算的被除數(shù)，繼續(xù)試商。每商一位，統(tǒng)計(jì)被除數(shù)中“ 1” 的個(gè)數(shù)的變量 n增 1。 (2) 豎式除法模擬描述 ? c=1111。n=4。 // 變量 c與 n賦初值 ? while(c!=0) // 模擬豎式除法 ? { a=c*10+1。 ? c=a%2021。 ? n=n+1。 // 每試商一位 n增 1 ? } ? print(n)。 // 輸出的簡(jiǎn)略表示 算法的復(fù)雜性分析 ? 算法的復(fù)雜性越高，所需的計(jì)算機(jī)資源越多。 ? 最重要的計(jì)算機(jī)資源是時(shí)間資源與空間資源。 ? 需要計(jì)算機(jī)時(shí)間資源的量稱(chēng)為時(shí)間復(fù)雜度，需要計(jì)算機(jī)空間資源的量稱(chēng)為空間復(fù)雜度。 ? 時(shí)間復(fù)雜度與空間復(fù)雜度集中反映算法的效率。 時(shí)間復(fù)雜度 要想充分理解算法并有效地應(yīng)用算法求解實(shí)際案例，關(guān)鍵是對(duì)算法的分析。通常我們可以利用 實(shí)驗(yàn)對(duì)比方法、數(shù)學(xué)方法 來(lái)分析算法 。 實(shí)驗(yàn)對(duì)比分析很簡(jiǎn)單，兩個(gè)算法相互比較求解時(shí)間 。 數(shù)學(xué)方法能在嚴(yán)密的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1