算法在程序中的應(yīng)用

摘? 要：算法是用于解決一個(gè)實(shí)際問題而采取的方法或思路，通過自然語(yǔ)言、流程圖的方式可以將算法實(shí)現(xiàn)的基本步驟和流程表示出來。算法具有有窮性、確定性、有效性等特點(diǎn)，對(duì)于同一個(gè)問題，其實(shí)現(xiàn)的算法可以有多個(gè)。一般為了有效地解決實(shí)際問題，不僅要保證算法正確，還要考慮到算法的質(zhì)量，所以選擇一個(gè)合適的算法尤其重要。在進(jìn)行了算法的表示之后，可以利用相應(yīng)的程序設(shè)計(jì)語(yǔ)言將算法實(shí)現(xiàn)，最終解決實(shí)際問題。

關(guān)鍵詞：算法;程序設(shè)計(jì);線段分割

中圖分類號(hào)：TP311.1? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）22-0107-03

Abstract：The algorithm is a method or idea used to solve a practical problem. Through the natural language and flow chart，the basic steps and processes of the algorithm can be expressed. The algorithm has the characteristics of poverty，certainty，validity，etc. For the same problem，there are many algorithms that can be implemented. In general，in order to effectively solve practical problems，not only to ensure the correctness of the algorithm，but also to consider the quality of the algorithm. Therefore，it is particularly important to choose a suitable algorithm. After the representation of the algorithm，we can use the corresponding programming language to implement the algorithm and finally solve the actual problem.

Keywords：algorithm;program design;segment segmentation

0? 引? 言

算法是解題的基本思路和方案，是對(duì)一個(gè)問題的準(zhǔn)確而完整的表述，可以是一系列指令或流程框圖，也可以是自然語(yǔ)言。同一個(gè)問題有很多種解決方法，也就產(chǎn)生了多個(gè)算法。而算法的優(yōu)劣直接影響到程序的執(zhí)行效率。所以，設(shè)計(jì)一個(gè)優(yōu)秀的算法對(duì)于程序設(shè)計(jì)至關(guān)重要。

1? 算法與程序設(shè)計(jì)的關(guān)系

一個(gè)好的程序設(shè)計(jì)，必然存在一個(gè)最優(yōu)的算法設(shè)計(jì)。算法是程序設(shè)計(jì)的核心，算法的好壞在很大程度上決定了一個(gè)程序的效率。一個(gè)好的算法可以降低程序運(yùn)行的時(shí)間復(fù)雜度和空間復(fù)雜度，先選出一個(gè)好的算法，再配合以一種適宜的數(shù)據(jù)結(jié)構(gòu)，這樣程序的效率會(huì)大大提高。一個(gè)程序的設(shè)計(jì)包含數(shù)據(jù)結(jié)構(gòu)和算法兩部分，其中數(shù)據(jù)結(jié)構(gòu)是程序的中心，是設(shè)計(jì)程序的底層，而算法則是圍繞一定的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行操作，所以要進(jìn)行利用程序設(shè)計(jì)解決實(shí)際問題之前，應(yīng)首要選擇正確的數(shù)據(jù)結(jié)構(gòu)，然后基于此結(jié)構(gòu)再設(shè)計(jì)合適的算法，選擇合理的算法實(shí)現(xiàn)。比如，在一個(gè)學(xué)生表的基本操作中，往往會(huì)涉及一些學(xué)生信息的增、刪、查、改操作，在這類操作中就有數(shù)組和鏈表兩種數(shù)據(jù)結(jié)構(gòu)和基于兩種結(jié)構(gòu)的不同算法。其中數(shù)組結(jié)構(gòu)會(huì)因?yàn)樵黾?、刪除操作移動(dòng)大量的元素，導(dǎo)致運(yùn)行效率降低。而鏈表結(jié)構(gòu)直接修改相應(yīng)的指針指向就能夠高效地完成該操作，所以在程序設(shè)計(jì)解決此類問題的時(shí)候，會(huì)選擇鏈表結(jié)構(gòu)，并基于此結(jié)構(gòu)進(jìn)行算法的設(shè)計(jì)。

2? 算法的表示

要將算法的思路和基本步驟表示出來，常用的方法有：自然語(yǔ)言、流程圖和偽代碼等。自然語(yǔ)言是采用漢語(yǔ)、英語(yǔ)或其他語(yǔ)言的方式，表述通俗易懂，但表示方法不嚴(yán)格，對(duì)于一些分支、循環(huán)的算法表示出來不太方便，這種方式一般不常用。流程圖是用圖框的形式表示各種操作，包括傳統(tǒng)流程圖和N-S結(jié)構(gòu)化流程圖，傳統(tǒng)流程圖利用不同的圖框表達(dá)不同的含義，常用的圖框表示符號(hào)如圖1所示。例如表示1+2+3+…+10的和，可以用傳統(tǒng)流程圖表示，如圖2所示。

N-S流程圖去掉了帶箭頭的流程線，將算法寫在了一個(gè)矩形框內(nèi)，這個(gè)矩形框還可以包含其他的從屬于它的框。其包含順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)三種結(jié)構(gòu)，分別以圖3（a）—（d）的形式表示。

1+2+3+…+10的和用N-S流程圖表示如圖4所示。

流程圖的表示方式雖然直觀易懂，但繪制稍微復(fù)雜，并且當(dāng)遇到復(fù)雜的程序設(shè)計(jì)時(shí)，會(huì)進(jìn)行反復(fù)修改，為了更方便地設(shè)計(jì)算法，常用偽代碼表示復(fù)雜的算法。偽代碼用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)表示算法。仍以1+2+3+…+10的和為例，用偽代碼表示：

有了以上表示算法的幾種方式，對(duì)于提出的實(shí)際問題首先通過流程圖或偽代碼的形式表達(dá)出算法的基本思路，然后利用編程語(yǔ)言將算法表示出來。

3? 應(yīng)用線段分割算法實(shí)現(xiàn)微信紅包隨機(jī)發(fā)放

要給10個(gè)人隨機(jī)發(fā)放50元的紅包，要求紅包最小不能低于0.01元，每個(gè)紅包保留2位小數(shù)。針對(duì)此實(shí)際問題，提出了多種方法，目前用得較多的是二倍均值法和線段切割法。其中二倍均值法保證了每次隨機(jī)金額的平均值是公平的。例如，對(duì)于第1人：50/10*2，隨機(jī)范圍為（0，10），平均可以搶到5元。

對(duì)于第2人：45/9*2，隨機(jī)范圍為（0，10），平均可以搶到5元。

以此類推，這樣每次隨機(jī)的范圍均值都是一樣的，但這種方式并不是真正的隨機(jī)數(shù)。而線段分割法的原理則是將紅包的總額當(dāng)成是一條長(zhǎng)度為紅包金額的線段，將紅包隨機(jī)拆分成若干條子線段，每個(gè)子線段的長(zhǎng)度即為紅包的金額。這里有10個(gè)人，那就需要確定9個(gè)切割點(diǎn)。所以首先要進(jìn)行切割點(diǎn)的確定，然后將各個(gè)相鄰切割點(diǎn)之間的距離求出，即為隨機(jī)的紅包金額。為了滿足紅包最小不能低于0.01和紅包保留2位小數(shù)，先將紅包金額*100，這樣相當(dāng)于線段的長(zhǎng)度為5000，將其分割刻度設(shè)置為1。在確定好分割點(diǎn)后，求出相鄰分割點(diǎn)的距離并除以100，得出隨機(jī)的金額，保留2位小數(shù)。

begin

50=>money

10=>n

（int）（money*100）=>point

List<Integer>? list=new ArrayList<>（）可以用鏈表也可以用數(shù)組

list.add（0）

list.add（point）

while（list.size（）<=n）將線段進(jìn)行分割，確定分割點(diǎn)坐標(biāo)

{

（int）（Math.random（）*money）=>p

if（list.contains（p））

continue

list.add（p）

}

Collections.sort（list）將分割點(diǎn)坐標(biāo)按大小排序，數(shù)組可以使用Arrays類

0=>i

while（i<n）

{

（list.get（i+1）-list.get（i））/100=>x

print x? ? ? ? 輸出搶到的紅包金額

}

end

有了算法的基本表示，該問題的解決思路也就明了了，這里將該算法用Java來實(shí)現(xiàn)，部分的代碼設(shè)計(jì)如下：

首先定義一個(gè)方法，該方法用于實(shí)現(xiàn)金額為money，紅包個(gè)數(shù)為n的隨機(jī)方法功能。該方法的代碼：

int[] fun（double money，int n） {

int x=（int）（money*100）;

int[] xx=new int[n+1];//利用數(shù)組的形式實(shí)現(xiàn)

int[] yy=new int[n];

xx[0]=0;

xx[n]=x;

int i=1;

while（i<n） {

int r=（int）（Math.random（）*x）+1;

if（r>=1） {

if（！query（r，xx）） {

continue;

}

xx[i]=r;

i++;

}

}

java.util.Arrays.sort（xx）;

//排序完成后，將每相鄰的兩個(gè)分割點(diǎn)之間的距離求出即為紅包的隨機(jī)數(shù)。

for（i=0;i<xx.length-1;i++） {

yy[i]=（xx[i+1]-xx[i]）;

}

return yy;

}

這里調(diào)用了一個(gè)自定義的方法query，用于查詢數(shù)組中是否已經(jīng)包含該分割點(diǎn)。query（）的功能如下：

boolean? query（int x，int[] z） {

int i=0;

for（;i<z.length;i++）

{

if（x==z[i]）

break;

}

if（i>=z.length） {

return true;

}

return false;

}

注：如果用鏈表List類框架實(shí)現(xiàn)的話，該框架中包含有contains（），用于判定是否在鏈表中已有該數(shù)據(jù)，如果有的話則返回true，否則返回false。

這樣就可以直接調(diào)用該方法以保證分割點(diǎn)的坐標(biāo)不重復(fù)。

最后在主方法中調(diào)用fun（）方法即可，如：int x[]=fun （50，10）;語(yǔ)句即可將50元隨機(jī)發(fā)放給10個(gè)人，然后再除以100獲取實(shí)際的金額數(shù)，并利用BigDecimal類設(shè)置該金額保留兩位小數(shù)，至此隨機(jī)發(fā)放紅包金額的問題得以解決。

4? 結(jié)? 論

本文首先闡述了算法在程序中的作用，明確了算法是程序設(shè)計(jì)中的核心地位，在程序設(shè)計(jì)中起著至關(guān)重要的作用，然后描述了算法的表示方式，以傳統(tǒng)流程圖和N-S流程圖為例完成了算法的設(shè)計(jì)過程，最后結(jié)合實(shí)際的微信紅包應(yīng)用案例描述了算法在程序設(shè)計(jì)中的重要性。在實(shí)際的程序開發(fā)中，算法的好壞直接決定了程序設(shè)計(jì)的運(yùn)行效率。所以我們一定要結(jié)合實(shí)際的數(shù)據(jù)結(jié)構(gòu)，確立優(yōu)秀的算法思路，以保證程序的高效執(zhí)行。

參考文獻(xiàn)：

[1] 楊克昌.計(jì)算機(jī)常用算法與程序設(shè)計(jì)教程 [M].北京：人民郵電出版社，2008.

[2] 譚浩強(qiáng).C程序設(shè)計(jì)：第5版 [M].北京：清華大學(xué)出版社，2017.

[3] 顧民.程序設(shè)計(jì)中的算法優(yōu)化思考 [J].中國(guó)新通信，2018，20（1）：65.

作者簡(jiǎn)介：王學(xué)梅（1979.08-），女，漢族，山東德州人，教師，講師，碩士，研究方向：數(shù)據(jù)庫(kù)應(yīng)用、軟件開發(fā)。