祁俊，王璐，王曉青

?

基于數(shù)學(xué)思維與M cCabe方法的編程優(yōu)化問(wèn)題研究

祁俊，王璐，王曉青

摘 要：針對(duì)程序復(fù)雜度高的問(wèn)題，提出在結(jié)構(gòu)化程序設(shè)計(jì)中利用數(shù)學(xué)思維方法來(lái)進(jìn)行代碼剖析、發(fā)現(xiàn)客觀規(guī)律并歸納抽象，從而實(shí)現(xiàn)編程優(yōu)化的思路。結(jié)合McCabe方法對(duì)程序進(jìn)行復(fù)雜度度量，來(lái)說(shuō)明利用數(shù)學(xué)思維進(jìn)行編程可以明顯降低程序的復(fù)雜程度，達(dá)到編程優(yōu)化的目的。

關(guān)鍵詞：數(shù)學(xué)思維；McCabe方法；程序復(fù)雜度；編程優(yōu)化

0 引言

計(jì)算機(jī)編程是軟件開發(fā)的主要手段，編程質(zhì)量直接影響著軟件的質(zhì)量。計(jì)算機(jī)科學(xué)是算法的科學(xué)，同一問(wèn)題采用的算法多種多樣，編寫出的程序質(zhì)量也有很大差距。體現(xiàn)一個(gè)程序員水平最重要的地方就是算法，一個(gè)好的算法使用非常少的代碼就能實(shí)現(xiàn)原來(lái)很復(fù)雜的操作。在編程過(guò)程中只有選取高效的算法不斷進(jìn)行代碼的優(yōu)化才能提高程序的質(zhì)量，其中衡量編程質(zhì)量的重要指標(biāo)之一是程序復(fù)雜度［1］。

程序復(fù)雜程度關(guān)系著程序編寫難度，也關(guān)系著程序設(shè)計(jì)和程序測(cè)試的難度。度量程序復(fù)雜度的目的在于衡量軟件人員的價(jià)值和軟件價(jià)值。對(duì)于解決同一問(wèn)題的不同程序代碼，復(fù)雜度越低則程序價(jià)值越高，通用性越好。因此通過(guò)使用高效的算法對(duì)軟件程序進(jìn)行編程優(yōu)化，降低程序復(fù)雜度來(lái)提高軟件質(zhì)量是軟件編程人員一直以來(lái)追求的目標(biāo)。

本文提出在結(jié)構(gòu)化程序設(shè)計(jì)中通過(guò)利用數(shù)學(xué)思維對(duì)程序進(jìn)行編程優(yōu)化的思路，以達(dá)到降低程序復(fù)雜度，提高軟件質(zhì)量的目的。

1 數(shù)學(xué)思維編程優(yōu)化思想

結(jié)構(gòu)化程序設(shè)計(jì)的先驅(qū)Niklaus W irth提出著名公式“程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)”，從中可以看出算法是程序設(shè)計(jì)的靈魂。算法和程序之間是密不可分的關(guān)系，沒(méi)有算法就編不出好的程序［2］。對(duì)計(jì)算機(jī)編程優(yōu)化起著至關(guān)重要的作用就是對(duì)于算法的選擇。

根據(jù)維基百科的定義，算法可以理解為求解問(wèn)題的具體過(guò)程、步驟、方法。常用的算法有：窮舉法、遞推法、遞歸法、迭代法等等。計(jì)算機(jī)編程過(guò)程中僅僅依靠常規(guī)算法進(jìn)行編程并不能直接得到簡(jiǎn)潔、高效的程序代碼，特別是對(duì)于需要多重循環(huán)、多重判斷實(shí)現(xiàn)的算法而言，往往會(huì)帶來(lái)程序復(fù)雜度高的問(wèn)題，不利于提高軟件的質(zhì)量。因此編程過(guò)程中對(duì)于程序進(jìn)行進(jìn)一步的優(yōu)化是非常有必要的。

萬(wàn)事萬(wàn)物都隱含著規(guī)律，我們發(fā)現(xiàn)結(jié)合實(shí)際問(wèn)題利用數(shù)學(xué)思維觀察程序代碼，進(jìn)行代碼剖析，就可以發(fā)現(xiàn)代碼中隱藏的規(guī)律。通過(guò)利用數(shù)學(xué)思維，科學(xué)的進(jìn)行歸納和抽象就可以優(yōu)化算法、簡(jiǎn)化代碼、實(shí)現(xiàn)編程優(yōu)化，達(dá)到降低程序復(fù)雜度的目的。

本文提出的數(shù)學(xué)思維編程優(yōu)化的思想是在常規(guī)方法實(shí)現(xiàn)的代碼基礎(chǔ)上，利用數(shù)學(xué)思維結(jié)合實(shí)際問(wèn)題，通過(guò)觀察發(fā)現(xiàn)客觀規(guī)律歸納出抽象模型從而實(shí)現(xiàn)編程優(yōu)化的一種編程思路。在編程過(guò)程中利用數(shù)學(xué)的思維和理論來(lái)解決實(shí)際問(wèn)題，研究和分析實(shí)際問(wèn)題的本質(zhì)，以及隱含的規(guī)律，經(jīng)過(guò)抽象轉(zhuǎn)化為合理的數(shù)學(xué)結(jié)論。通過(guò)利用數(shù)學(xué)的思想和方法進(jìn)行分析、探討、研究，最終實(shí)現(xiàn)編程優(yōu)化的目的。整個(gè)過(guò)程大致可分為三步，如圖1所示：

圖1 編程優(yōu)化過(guò)程

本文結(jié)合度量結(jié)構(gòu)化程序復(fù)雜度的M cCabe方法來(lái)說(shuō)明，利用數(shù)學(xué)思維進(jìn)行編程優(yōu)化可以顯著提高程序的通用性和降低程序復(fù)雜程度。

2 結(jié)構(gòu)化程序復(fù)雜性度量方法

M cCabe復(fù)雜性度量又稱環(huán)路度量，是由Thomas M cCabe提出的一種基于程序控制流的復(fù)雜性度量方法。它認(rèn)為程序的復(fù)雜性很大程度上取決于程序圖的復(fù)雜性。單一的順序結(jié)構(gòu)最為簡(jiǎn)單，循環(huán)和選擇所構(gòu)成的環(huán)路越多，程序就越復(fù)雜。被認(rèn)為是動(dòng)態(tài)白盒測(cè)試技術(shù)中嚴(yán)謹(jǐn)而有效的測(cè)試方法［3］。M cCabe復(fù)雜度是用來(lái)衡量一個(gè)模塊判定結(jié)構(gòu)的復(fù)雜程度，數(shù)量上表現(xiàn)為獨(dú)立現(xiàn)行路徑條數(shù)，即合理的預(yù)防錯(cuò)誤所需測(cè)試的最少路徑條數(shù)［4］。顯示了在測(cè)試一個(gè)單元時(shí)，為保證軟件質(zhì)量而需要測(cè)試的基本路徑的最小數(shù)目［5］。復(fù)雜度高說(shuō)明代碼質(zhì)量可能很差，難于測(cè)試和維護(hù)。根據(jù)經(jīng)驗(yàn)，程序的可能錯(cuò)誤和復(fù)雜度高有著很大關(guān)系［6］。

具體方法是先給出程序流程圖，把每一個(gè)圖框都認(rèn)為是一個(gè)結(jié)點(diǎn)，得到計(jì)算M cCabe復(fù)雜度。如公式（1）：

V（ G） = m - n + p （1）

其中，V（G）表示初始框節(jié)點(diǎn)和結(jié)束框節(jié)點(diǎn)相連的程序圖中線性無(wú)關(guān)環(huán)個(gè)數(shù)。 m 是有向圖中的弧數(shù)，n 是有向圖中的結(jié)點(diǎn)數(shù)，p 是圖 G 中的強(qiáng)連通分量的個(gè)數(shù)。

由于McCabe方法是以圖論為基礎(chǔ)，所以通過(guò)程序的控制流圖可以獲得程序的復(fù)雜度，還可用以下3個(gè)數(shù)據(jù)表示［7］：

①流圖中區(qū)域的數(shù)量；

②流圖中邊的數(shù)量－流圖中節(jié)點(diǎn)的數(shù)量+2；

③流圖中判定節(jié)點(diǎn)的數(shù)量+1。

雖然利用M cCabe方法可以度量程序的復(fù)雜度，但是需要編程人員在編程同時(shí)人工繪制程序流程圖和程序圖并計(jì)算出節(jié)點(diǎn)和邊的個(gè)數(shù)，計(jì)算方式繁瑣。所以我們利用改進(jìn)的M cCabe 方法，如計(jì)算公式（2）：

V（ G） = M + N + 1 （2）

其中，M 為判斷語(yǔ)句 （ if） 的個(gè)數(shù)； N 為循環(huán)的總重?cái)?shù)［8］。該方法不用再繪制程序流程圖，更加容易統(tǒng)計(jì)弧數(shù)和結(jié)點(diǎn)數(shù)。

根據(jù)改進(jìn)M cCabe計(jì)算公式（2）可知數(shù)字1是常量，對(duì)于計(jì)算結(jié)果沒(méi)有影響，所以本文是在公式（2）的基礎(chǔ)上加以簡(jiǎn)化，如公式（3）：

V（ G） = M + N （3）

通過(guò)公式（3）可以更加方便快捷的計(jì)算出程序的復(fù)雜度。

3 數(shù)學(xué)思維編程優(yōu)化實(shí)例

3.1 窮舉法優(yōu)化問(wèn)題

窮舉法是最基本的編程方法之一。窮舉法主要是通過(guò)多重循環(huán)窮舉來(lái)得出計(jì)算結(jié)果。而程序運(yùn)行時(shí)間和循環(huán)重?cái)?shù)成正比關(guān)系，過(guò)多的循環(huán)重?cái)?shù)會(huì)極大降低程序的執(zhí)行效率，所以在進(jìn)行編程求解時(shí)要根據(jù)實(shí)際問(wèn)題結(jié)合數(shù)學(xué)思維進(jìn)行編程優(yōu)化，從而達(dá)到降低程序復(fù)雜度提高程序通用性的目的。下面通過(guò)幾個(gè)常見(jiàn)的問(wèn)題進(jìn)行說(shuō)明。

百元買百雞問(wèn)題

百元買百雞是一道古典數(shù)學(xué)問(wèn)題，問(wèn)題定義為：雞翁一值錢五，雞母一值錢三，雞雛三值錢一，百元買百雞，問(wèn)雞翁、雞母、雞雛各幾何？

這道題可以利用計(jì)算機(jī)中的窮舉算法來(lái)實(shí)現(xiàn)。具體編程中利用C語(yǔ)言中的for語(yǔ)句嵌套三層來(lái)實(shí)現(xiàn)。

代碼片段如下：

利用改進(jìn)的McCabe公式（3）可知：

V（ G） = M + N =1+3=4

通過(guò)觀察，利用數(shù)學(xué)思維對(duì)程序進(jìn)行優(yōu)化。首先根據(jù)題意可推出公式（4）：

根據(jù)公式（4）可推出z=100-x-y，帶入公式（4）化簡(jiǎn)可得：7x+4y=100。這樣可以化簡(jiǎn)掉一重循環(huán)。沿著這個(gè)思路繼續(xù)變換，可推出公式（5）：

根據(jù)公式（5）來(lái)對(duì)程序進(jìn)行編程優(yōu)化，可將三重循環(huán)降為一重。同樣從公式（5）可以觀察得出x是4的倍數(shù)而x又不能超過(guò)20。程序代碼片段如下：

通過(guò)數(shù)學(xué)思維進(jìn)行編程優(yōu)化后，將循環(huán)降為1重，并通過(guò)數(shù)學(xué)變換得出公式（5）后又可以省卻了1重判斷。McCabe方法度量可得出：

如表1所示：

表1 優(yōu)化前后程序?qū)Ρ?/p>

從表1可以看出，利用數(shù)學(xué)思維優(yōu)化后的程序無(wú)論從程序循環(huán)次數(shù)還是復(fù)雜度都有了極大的優(yōu)化。

求四位的卡普列加數(shù)問(wèn)題

卡普列加數(shù)定義即：對(duì)n位自然數(shù)N，將N2切分為兩半，右邊n位為一個(gè)數(shù)，左邊其余各位為另一個(gè)數(shù)，如果這兩個(gè)數(shù)之和恰好等于N，那么稱N和N2為一對(duì)卡普列加數(shù)，其中N為卡普列加底數(shù)，N2為卡普列加平方數(shù)。例如552=3025，30+25=55

同樣通過(guò)常規(guī)編程可以用窮舉法來(lái)實(shí)現(xiàn)，但需要設(shè)置4重循環(huán)來(lái)進(jìn)行窮舉，內(nèi)層循環(huán)還需設(shè)置選擇語(yǔ)句做判斷。計(jì)算M cCabe環(huán)數(shù)可知：

V（ G） = M + N =1+4=5

多重循環(huán)會(huì)造成計(jì)效率低下，利用數(shù)學(xué)思維進(jìn)行程序優(yōu)化。如下：

程序代碼片段如下：

通過(guò)數(shù)學(xué)思維進(jìn)行編程優(yōu)化后，計(jì)算可知：

通過(guò)上例代碼優(yōu)化可以看出，程序復(fù)雜度從5降低到了2，循環(huán)的重?cái)?shù)也從4重降低到了1重，循環(huán)次數(shù)大大減少，極大提高了程序執(zhí)行效率，同時(shí)也降低了程序復(fù)雜度。

類似的窮舉問(wèn)題還有很多，特別是窮舉循環(huán)嵌套層數(shù)過(guò)多，循環(huán)次數(shù)比較大的情況下，如果在編程中只是單純的依靠多重循環(huán)嵌套讓計(jì)算機(jī)去計(jì)算，勢(shì)必帶來(lái)程序復(fù)雜度和效率問(wèn)題，這種算法就不能稱之為好的算法。我們一定要利用數(shù)學(xué)思維歸納問(wèn)題規(guī)律，對(duì)這類問(wèn)題進(jìn)行編碼優(yōu)化，才能實(shí)現(xiàn)降低程序復(fù)雜度，提高程序效率的目的。

3.2 分段函數(shù)問(wèn)題

分段函數(shù)是一個(gè)重要的數(shù)學(xué)函數(shù)模型，在現(xiàn)實(shí)生活中處處可見(jiàn)。比如，稅務(wù)計(jì)算、養(yǎng)老金核算、成本控制等。簡(jiǎn)單的問(wèn)題可以用一元函數(shù)來(lái)解決，復(fù)雜問(wèn)題就要用到多元函數(shù)。我們以求個(gè)人所得稅問(wèn)題來(lái)進(jìn)行編程優(yōu)化舉例。假設(shè)個(gè)人所得稅計(jì)算規(guī)則如下：

按照上式，可用多重if語(yǔ)句來(lái)實(shí)現(xiàn)求解。程序代碼片段如下所示：

計(jì)算可知：

如果問(wèn)題改變，則相應(yīng)的if語(yǔ)句重?cái)?shù)必定隨之增加。程序復(fù)雜度也會(huì)隨之加大。根據(jù)數(shù)學(xué)思維的思想，觀察程序代碼，得出假設(shè)：

a0=0，a1=1500，a2=5000，a3=10000，a4=40000；

b0=0，b1=0.03，b2=0.05，b3=0.1，b4=0.3；

則求解所得稅就可以改為：

則程序代碼片段如下：

根據(jù)優(yōu)化后的程序，計(jì)算可知：

此外類似的例子還有很多，比如求養(yǎng)老金保險(xiǎn)問(wèn)題、行李寄存問(wèn)題等等。這些問(wèn)題都可以利用數(shù)學(xué)思維編程優(yōu)化的思想，通過(guò)觀察、歸納、抽象改為非常簡(jiǎn)單的問(wèn)題求解來(lái)進(jìn)行編程實(shí)現(xiàn)，極大降低了圈環(huán)重?cái)?shù)。即使程序問(wèn)題規(guī)模變大，也只需要改動(dòng)數(shù)據(jù)即可，而不需要改動(dòng)程序，降低程序復(fù)雜度的同時(shí)也極大提高了程序的通用性。

4 總結(jié)

隨著計(jì)算機(jī)軟件的不斷發(fā)展，人們編寫的程序也越來(lái)越復(fù)雜，越來(lái)越龐大。隨之帶來(lái)的隱含錯(cuò)誤也越來(lái)越多，花費(fèi)在程序調(diào)試、測(cè)試和維護(hù)的代價(jià)甚至要占到總成本的70%以上，所以要減少程序的隱含錯(cuò)誤，便于測(cè)試和維護(hù)，就要從編程優(yōu)化、降低程序復(fù)雜度著手。在計(jì)算機(jī)編程中通過(guò)數(shù)學(xué)思維能夠把復(fù)雜的代碼高度抽象和歸納，從而優(yōu)化代碼，大大加快計(jì)算機(jī)程序的運(yùn)行時(shí)間，提高計(jì)算機(jī)執(zhí)行程序的效率，是計(jì)算機(jī)編程優(yōu)化和降低程序復(fù)雜度的關(guān)鍵。在實(shí)際的編寫程序過(guò)程中要充分的發(fā)揮數(shù)學(xué)思維對(duì)計(jì)算機(jī)編程的優(yōu)化作用。融入數(shù)學(xué)思維的編程思想，就是通過(guò)不斷地剖析、歸納和抽象程序的算法，而使計(jì)算機(jī)編程得到優(yōu)化的過(guò)程。在編程過(guò)程中，編程人員要善于發(fā)現(xiàn)，總結(jié)歸納問(wèn)題的隱含規(guī)律。利用數(shù)學(xué)思維以數(shù)學(xué)科學(xué)的思維和角度去看待問(wèn)題，從而在計(jì)算機(jī)編程的世界里找到一把開啟優(yōu)化的鑰匙。

參考文獻(xiàn)

［1］ 覃征，虞凡，王志敏，楊博.程序設(shè)計(jì)方法與優(yōu)化［M］.西安:西安交通大學(xué)出版社，2007.

［2］ 齊悅，夏克儉，姚琳.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用［M］.北京:清華大學(xué)出版社，2015 .

［3］ WIJAYASIRIWARDHANET K，WIJAYARATHNA P G，KARUNARATHNA D D. An automated tool to generate test cases forperform ing basis path testing ［C］//ICTer 2011: Proceedings of the2011 International Conference on Advances in ICT for Emerging Regions.Piscataway: IEEE Press，2011: 95-101.

［4］ 朱鴻，金凌紫.軟件質(zhì)量與保證 ［M］. 北京:科學(xué)出版，1997.

［5］ 樊慶林，吳建國(guó).提高軟件測(cè)試效率的方法究［J］ .計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（10）:52-54

［6］ 黃華林.使用 M cCabe IQ提高測(cè)試質(zhì)量的研究［J］.微型機(jī)與應(yīng)用，2012（31）:69-70.

［7］ 王 敏，陳少敏，陳亞光.基本路徑測(cè)試用例設(shè)計(jì)算法，［J］計(jì)算機(jī)應(yīng)用，2013，33（11）:3262-3266.

［8］ 王冠，景小寧，王彥軍.基本路徑測(cè)試中的McCabe 算法改進(jìn)與應(yīng)用，［J］哈爾濱理工大學(xué)學(xué)報(bào)，2010（15）:48-51.

Research on Programm ing Optim ization Based on M athematical Thinking and M cCabe M ethod

Qi Jun， Wang Lu，Wang Xiaoqing
（Department of Computer Technology and Application， Qinghai University， Xining 810016， China）

Abstract:To aim at the high complexity of the program， it uses mathematical thinking method in the process of structural design to analyze the code and find the objective laws， so as to achieve the idea of programming optim ization. Using the M cCabe method to measure the complexity of the program， it can be used to reduce the complexity of the program and achieve the purpose of programm ing optim ization by programm ing w ith mathematical thinking.

Key words:Mathematical Thinking； M cCabe Mothed； Program Complexity； Programm ing Optimization

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-757X（2016）05-0020-03

基金項(xiàng)目：青海大學(xué)中青年科研基金項(xiàng)目（2015-QGY-11）；青海大學(xué)課堂教學(xué)改革和考試綜合改革項(xiàng)目（KG-14-04）

作者簡(jiǎn)介：祁 ?。?977-），女，青海貴德，青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系，副教授，碩士，研究方向：智能信息處理、計(jì)算機(jī)教育，西寧 ，810016 王 璐（1984-），女，河北廊坊，青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系，講師，碩士，研究方向：數(shù)據(jù)挖掘，西寧，810016王曉青（1964-），女，陜西彬縣，青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系，教授，學(xué)士，研究方向：計(jì)算機(jī)教育，西寧，810016

收稿日期:（2015.12.02）