當前位置:首頁 > 公眾號精選 > 玩轉(zhuǎn)嵌入式
[導讀]算法(Algorithm)指計算機解題的基本思想方法和步驟。算法的描述是對要解決一個問題或要完成一項任務(wù)所采取的方法和步驟的描述,包括需要什么數(shù)據(jù)(輸入什么數(shù)據(jù)、輸出什么結(jié)果)、采用什么結(jié)構(gòu)、使用什么語句以及如何安排這些語句等。通常使用自然語言、結(jié)構(gòu)化流程圖、偽代碼等來描述算法。

文章來源于:單片機與嵌入式

算法(Algorithm):計算機解題的基本思想方法和步驟。

算法的描述:是對要解決一個問題或要完成一項任務(wù)所采取的方法和步驟的描述,包括需要什么數(shù)據(jù)(輸入什么數(shù)據(jù)、輸出什么結(jié)果)、采用什么結(jié)構(gòu)、使用什么語句以及如何安排這些語句等。通常使用自然語言、結(jié)構(gòu)化流程圖、偽代碼等來描述算法。
一、計數(shù)、求和、求階乘等簡單算法
此類問題都要使用循環(huán),要注意根據(jù)問題確定循環(huán)變量的初值、終值或結(jié)束條件,更要注意用來表示計數(shù)、和、階乘的變量的初值。
例:用隨機函數(shù)產(chǎn)生100個[0,99]范圍內(nèi)的隨機整數(shù),統(tǒng)計個位上的數(shù)字分別為1,2,3,4,5,6,7,8,9,0的數(shù)的個數(shù)并打印出來。
本題使用數(shù)組來處理,用數(shù)組a[100]存放產(chǎn)生的確100個隨機整數(shù),數(shù)組x[10]來存放個位上的數(shù)字分別為1,2,3,4,5,6,7,8,9,0的數(shù)的個數(shù)。即個位是1的個數(shù)存放在x[1]中,個位是2的個數(shù)存放在x[2]中,……個位是0的個數(shù)存放在數(shù)組x[10]。
二、求兩個整數(shù)的最大公約數(shù)、最小公倍數(shù)
分析:求最大公約數(shù)的算法思想:(最小公倍數(shù)=兩個整數(shù)之積/最大公約數(shù))
(1) 對于已知兩數(shù)m,n,使得m>n;
(2) m除以n得余數(shù)r;
(3) 若r=0,則n為求得的最大公約數(shù),算法結(jié)束;否則執(zhí)行(4);
(4) m←n,n←r,再重復執(zhí)行(2)。
例如: 求 m="14" ,n=6 的最大公約數(shù).
m n r
14 6 2
6 2 0
三、判斷素數(shù)
只能被1或本身整除的數(shù)稱為素數(shù) 基本思想:把m作為被除數(shù),將2—INT( )作為除數(shù),如果都除不盡,m就是素數(shù),否則就不是。(可用以下程序段實現(xiàn))
四、驗證哥德巴赫猜想
(任意一個大于等于6的偶數(shù)都可以分解為兩個素數(shù)之和)
基本思想:n為大于等于6的任一偶數(shù),可分解為n1和n2兩個數(shù),分別檢查n1和n2是否為素數(shù),如都是,則為一組解。如n1不是素數(shù),就不必再檢查n2是否素數(shù)。先從n1=3開始,檢驗n1和n2(n2=N-n1)是否素數(shù)。然后使n1+2 再檢驗n1、n2是否素數(shù),… 直到n1=n/2為止。
利用上面的prime函數(shù),驗證哥德巴赫猜想的程序代碼如下:
五、排序問題
1.選擇法排序(升序)
基本思想:
1)對有n個數(shù)的序列(存放在數(shù)組a(n)中),從中選出最小的數(shù),與第1個數(shù)交換位置;
2)除第1 個數(shù)外,其余n-1個數(shù)中選最小的數(shù),與第2個數(shù)交換位置;
3)依次類推,選擇了n-1次后,這個數(shù)列已按升序排列。
程序代碼如下:
2.冒泡法排序(升序)
基本思想:(將相鄰兩個數(shù)比較,小的調(diào)到前頭)
1)有n個數(shù)(存放在數(shù)組a(n)中),第一趟將每相鄰兩個數(shù)比較,小的調(diào)到前頭,經(jīng)n-1次兩兩相鄰比較后,最大的數(shù)已“沉底”,放在最后一個位置,小數(shù)上升“浮起”;
2)第二趟對余下的n-1個數(shù)(最大的數(shù)已“沉底”)按上法比較,經(jīng)n-2次兩兩相鄰比較后得次大的數(shù);
3)依次類推,n個數(shù)共進行n-1趟比較,在第j趟中要進行n-j次兩兩比較。
程序段如下:
3.合并法排序(將兩個有序數(shù)組A、B合并成另一個有序的數(shù)組C,升序)
基本思想:
1)先在A、B數(shù)組中各取第一個元素進行比較,將小的元素放入C數(shù)組;
2)取小的元素所在數(shù)組的下一個元素與另一數(shù)組中上次比較后較大的元素比較,重復上述比較過程,直到某個數(shù)組被先排完;
3)將另一個數(shù)組剩余元素抄入C數(shù)組,合并排序完成。
程序段如下:
六、查找問題
順序查找法(在一列數(shù)中查找某數(shù)x)
基本思想:一列數(shù)放在數(shù)組a[1]---a[n]中,待查找的數(shù)放在x 中,把x與a數(shù)組中的元素從頭到尾一一進行比較查找。用變量p表示a數(shù)組元素下標,p初值為
1,使x與a[p]比較,如果x不等于a[p],則使p=p+1,不斷重復這個過程;一旦x等于a[p]則退出循環(huán);另外,如果p大于數(shù)組長度,循環(huán)也應(yīng)該停止。(這個過程可由下語句實現(xiàn))
思考:將上面程序改寫一查找函數(shù)Find,若找到則返回下標值,找不到返回-1
②基本思想:一列數(shù)放在數(shù)組a[1]---a[n]中,待查找的關(guān)鍵值為key,把key與a數(shù)組中的元素從頭到尾一一進行比較查找,若相同,查找成功,若找不到,則查找失敗。(查找子過程如下。index:存放找到元素的下標。)
七、二分法
在一個數(shù)組中,知道一個數(shù)值,想確定他在數(shù)組中的位置下標,如數(shù)組:A[5] = {1,2,6,7,9};我知道其中的值為6,那么他的下標位置就是3。
八、限幅濾波法
對于隨機干擾 , 限幅濾波是一種有效的方法;
基本方法:比較相鄰n 和 n - 1時刻的兩個采樣值y(n)和 y(n – 1),根據(jù)經(jīng)驗確定兩次采樣允許的最大偏差。如果兩次采樣值的差值超過最大偏差范圍 ,認為發(fā)生可隨機干擾 ,并認為后一次采樣值y(n)為非法值 ,應(yīng)予刪除 ,刪除y(n)后 ,可用y(n – 1) 代替y(n);若未超過所允許的最大偏差范圍 ,則認為本次采樣值有效。
下面是限幅濾波程序:(A值可根據(jù)實際情況調(diào)整,value 為有效值 ,new_value 為當前采樣值濾波程序返回有效的實際值 )
九、中位值濾波法
中位值濾波法能有效克服偶然因素引起的波動或采樣不穩(wěn)定引起的誤碼等脈沖干擾;
對溫度 液位等緩慢變化的被測參數(shù)用此法能收到良好的濾波效果 ,但是對于流量壓力等快速變化的參數(shù)一般不宜采用中位值濾波法;
基本方法:對某一被測參數(shù)連續(xù)采樣 n次(一般 n 取奇數(shù)) ,然后再把采樣值按大小排列 ,取中間值為本次采樣值。
下面是中位值濾波程序:
十.算術(shù)平均濾波法
算術(shù)平均濾波法適用于對一般的具有隨機干擾的信號進行濾波。這種信號的特點是信號本身在某一數(shù)值范圍附近上下波動 ,如測量流量、 液位;
基本方法:按輸入的N 個采樣數(shù)據(jù) ,尋找這樣一個 Y ,使得 Y 與各個采樣值之間的偏差的平方和最小。
編寫算術(shù)平均濾波法程序時嚴格注意:
一.為了加快數(shù)據(jù)測量的速度 ,可采用先測量數(shù)據(jù) 存放在存儲器中 ,測完 N 點后 ,再對 N 個數(shù)據(jù)進行平均值計算;
二.選取適當?shù)臄?shù)據(jù)格式 ,也就是說采用定點數(shù)還是采用浮點數(shù)。其程序如下所示:
十一、遞推平均濾波法
基本方法:采用隊列作為測量數(shù)據(jù)存儲器 , 設(shè)隊列的長度為 N ,每進行一次測量 ,把測量結(jié)果放于隊尾 ,而扔掉原來隊首的一個數(shù)據(jù) ,這樣在隊列中始終就有 N 個 “最新” 的數(shù)據(jù)。當計算平均值時 ,只要把隊列中的 N 個數(shù)據(jù)進行算數(shù)平均 ,就可得到新的算數(shù)平均值。這樣每進行一次測量 ,就可得到一個新的算術(shù)平均值。
十二、一階滯后濾波法
優(yōu)點:對周期性干擾具有良好的抑制作用,適用于波動頻率較高的場合;
缺點:相位滯后,靈敏度低.滯后程度取決于a值大小.不能消除濾波頻率高于采樣頻率的1/2的干擾信號。程序如下:
十三、PID控制算法
在過程控制中,按偏差的比例(P)、積分(I)和微分(D)進行控制的PID控制器(亦稱PID調(diào)節(jié)器)是應(yīng)用最為廣泛的一種自動控制器;
對于過程控制的典型對象──“一階滯后+純滯后”與“二階滯后+純滯后”的控制對象,PID控制器是一種最優(yōu)控制;
PID調(diào)節(jié)規(guī)律是連續(xù)系統(tǒng)動態(tài)品質(zhì)校正的一種有效方法,它的參數(shù)整定方式簡便,結(jié)構(gòu)改變靈活(PI、PD、…)。
一 模擬PID調(diào)節(jié)器
PID調(diào)節(jié)器各校正環(huán)節(jié)的作用:
比例環(huán)節(jié):即時成比例地反應(yīng)控制系統(tǒng)的偏差信號e(t),偏差一旦產(chǎn)生,調(diào)節(jié)器立即產(chǎn)生控制作用以減小偏差;
積分環(huán)節(jié):主要用于消除靜差,提高系統(tǒng)的無差度。積分時間常數(shù)TI越大,積分作用越弱,反之則越強;
微分環(huán)節(jié):能反應(yīng)偏差信號的變化趨勢(變化速率),并能在偏差信號的值變得太大之前,在系統(tǒng)中引入一個有效的早期修正信號,從而加快系統(tǒng)的動作速度,減小調(diào)節(jié)時間。
PID調(diào)節(jié)器是一種線性調(diào)節(jié)器,它將給定值r(t)與實際輸出值c(t)的偏差的比例(P)、積分(I)、微分(D)通過線性組合構(gòu)成控制量,對控制對象進行控制。
程序片段如下:
十四、開根號算法
單片機開平方的快速算法
因為工作的需要,要在單片機上實現(xiàn)開根號的操作。目前開平方的方法大部分是用牛頓迭代法。我在查了一些資料以后找到了一個比牛頓迭代法更加快速的方法。不敢獨享,介紹給大家,希望會有些幫助。
1.原理
因為排版的原因,用pow(X,Y)表示X的Y次冪,用B[0],B[1],...,B[m-1]表示一個序列,其中[x]為下標。
假設(shè):
B[x],b[x]都是二進制序列,取值0或1。
M = B[m-1]*pow(2,m-1) + B[m-2]*pow(2,m-2) + ... + B[1]*pow(2,1) + B[0]*pow(2,0)
N = b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2) + ... + b[1]*pow(2,1) + n[0]*pow(2,0)
pow(N,2) = M
(1) N的最高位b[n-1]可以根據(jù)M的最高位B[m-1]直接求得。
設(shè) m 已知,因為 pow(2, m-1) <= M <= pow(2, m),所以 pow(2, (m-1)/2) <= N <= pow(2, m/2)
如果 m 是奇數(shù),設(shè)m=2*k+1,
那么 pow(2,k) <= N < pow(2, 1/2+k) < pow(2, k+1),
n-1=k, n=k+1=(m+1)/2
如果 m 是偶數(shù),設(shè)m=2k,
那么 pow(2,k) > N >= pow(2, k-1/2) > pow(2, k-1),
n-1=k-1,n=k=m/2
所以b[n-1]完全由B[m-1]決定。
余數(shù) M[1] = M - b[n-1]*pow(2, 2*n-2)
(2) N的次高位b[n-2]可以采用試探法來確定。
因為b[n-1]=1,假設(shè)b[n-2]=1,則 pow(b[n-1]*pow(2,n-1) + b[n-1]*pow(2,n-2), 2) = b[n-1]*pow(2,2*n-2) + (b[n-1]*pow(2,2*n-2) + b[n-2]*pow(2,2*n-4)),
然后比較余數(shù)M[1]是否大于等于 (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4)。這種比較只須根據(jù)B[m-1]、B[m-2]、...、B[2*n-4]便可做出判斷,其余低位不做比較。
若 M[1] >= (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 則假設(shè)有效,b[n-2] = 1;
余數(shù) M[2] = M[1] - pow(pow(2,n-1)*b[n-1] + pow(2,n-2)*b[n-2], 2) = M[1] - (pow(2,2)+1)*pow(2,2*n-4);
若 M[1] < (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 則假設(shè)無效,b[n-2] = 0;余數(shù) M[2] = M[1]。
(3) 同理,可以從高位到低位逐位求出M的平方根N的各位。
使用這種算法計算32位數(shù)的平方根時最多只須比較16次,而且每次比較時不必把M的各位逐一比較,尤其是開始時比較的位數(shù)很少,所以消耗的時間遠低于牛頓迭代法。
2. 實現(xiàn)代碼
這里給出實現(xiàn)32位無符號整數(shù)開方得到16位無符號整數(shù)的C語言代碼。

關(guān)注微信公眾號『玩轉(zhuǎn)嵌入式』,后臺回復“128”獲取干貨資料匯總,回復“256”加入技術(shù)交流群。

精彩技術(shù)文章推薦



01

求伯君:中國最“?!背绦騿T,一己之力挑戰(zhàn)微軟


02

一個博士應(yīng)聘華為,大疆的經(jīng)歷...


03

華為員工裸辭之后悟出的那些“坑”!


04

學習經(jīng)歷分享,單片機大神是如何煉成的!



免責聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!

本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉