祁俊，王璐，王曉青

?

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

祁俊，王璐，王曉青

摘 要：針對程序復(fù)雜度高的問題，提出在結(jié)構(gòu)化程序設(shè)計(jì)中利用數(shù)學(xué)思維方法來進(jìn)行代碼剖析、發(fā)現(xiàn)客觀規(guī)律并歸納抽象，從而實(shí)現(xiàn)編程優(yōu)化的思路。結(jié)合McCabe方法對程序進(jìn)行復(fù)雜度度量，來說明利用數(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é)，同一問題采用的算法多種多樣，編寫出的程序質(zhì)量也有很大差距。體現(xiàn)一個(gè)程序員水平最重要的地方就是算法，一個(gè)好的算法使用非常少的代碼就能實(shí)現(xiàn)原來很復(fù)雜的操作。在編程過程中只有選取高效的算法不斷進(jìn)行代碼的優(yōu)化才能提高程序的質(zhì)量，其中衡量編程質(zhì)量的重要指標(biāo)之一是程序復(fù)雜度［1］。

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

本文提出在結(jié)構(gòu)化程序設(shè)計(jì)中通過利用數(shù)學(xué)思維對程序進(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)系，沒有算法就編不出好的程序［2］。對計(jì)算機(jī)編程優(yōu)化起著至關(guān)重要的作用就是對于算法的選擇。

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

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

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

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

本文結(jié)合度量結(jié)構(gòu)化程序復(fù)雜度的M cCabe方法來說明，利用數(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)最為簡單，循環(huán)和選擇所構(gòu)成的環(huán)路越多，程序就越復(fù)雜。被認(rèn)為是動(dòng)態(tài)白盒測試技術(shù)中嚴(yán)謹(jǐn)而有效的測試方法［3］。M cCabe復(fù)雜度是用來衡量一個(gè)模塊判定結(jié)構(gòu)的復(fù)雜程度，數(shù)量上表現(xiàn)為獨(dú)立現(xiàn)行路徑條數(shù)，即合理的預(yù)防錯(cuò)誤所需測試的最少路徑條數(shù)［4］。顯示了在測試一個(gè)單元時(shí)，為保證軟件質(zhì)量而需要測試的基本路徑的最小數(shù)目［5］。復(fù)雜度高說明代碼質(zhì)量可能很差，難于測試和維護(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)相連的程序圖中線性無關(guān)環(huán)個(gè)數(shù)。 m 是有向圖中的弧數(shù)，n 是有向圖中的結(jié)點(diǎn)數(shù)，p 是圖 G 中的強(qiáng)連通分量的個(gè)數(shù)。

由于McCabe方法是以圖論為基礎(chǔ)，所以通過程序的控制流圖可以獲得程序的復(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 為判斷語句 （ 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是常量，對于計(jì)算結(jié)果沒有影響，所以本文是在公式（2）的基礎(chǔ)上加以簡化，如公式（3）：

V（ G） = M + N （3）

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

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

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

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

百元買百雞問題

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

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

代碼片段如下：

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

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

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

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

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

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

如表1所示：

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

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

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

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

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

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

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

程序代碼片段如下：

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

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

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

3.2 分段函數(shù)問題

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

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

計(jì)算可知：

如果問題改變，則相應(yīng)的if語句重?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)問題、行李寄存問題等等。這些問題都可以利用數(shù)學(xué)思維編程優(yōu)化的思想，通過觀察、歸納、抽象改為非常簡單的問題求解來進(jìn)行編程實(shí)現(xiàn)，極大降低了圈環(huán)重?cái)?shù)。即使程序問題規(guī)模變大，也只需要改動(dòng)數(shù)據(jù)即可，而不需要改動(dòng)程序，降低程序復(fù)雜度的同時(shí)也極大提高了程序的通用性。

4 總結(jié)

隨著計(jì)算機(jī)軟件的不斷發(fā)展，人們編寫的程序也越來越復(fù)雜，越來越龐大。隨之帶來的隱含錯(cuò)誤也越來越多，花費(fèi)在程序調(diào)試、測試和維護(hù)的代價(jià)甚至要占到總成本的70%以上，所以要減少程序的隱含錯(cuò)誤，便于測試和維護(hù)，就要從編程優(yōu)化、降低程序復(fù)雜度著手。在計(jì)算機(jī)編程中通過數(shù)學(xué)思維能夠把復(fù)雜的代碼高度抽象和歸納，從而優(yōu)化代碼，大大加快計(jì)算機(jī)程序的運(yùn)行時(shí)間，提高計(jì)算機(jī)執(zhí)行程序的效率，是計(jì)算機(jī)編程優(yōu)化和降低程序復(fù)雜度的關(guān)鍵。在實(shí)際的編寫程序過程中要充分的發(fā)揮數(shù)學(xué)思維對計(jì)算機(jī)編程的優(yōu)化作用。融入數(shù)學(xué)思維的編程思想，就是通過不斷地剖析、歸納和抽象程序的算法，而使計(jì)算機(jī)編程得到優(yōu)化的過程。在編程過程中，編程人員要善于發(fā)現(xiàn)，總結(jié)歸納問題的隱含規(guī)律。利用數(shù)學(xué)思維以數(shù)學(xué)科學(xué)的思維和角度去看待問題，從而在計(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］ 樊慶林，吳建國.提高軟件測試效率的方法究［J］ .計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（10）:52-54

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

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

［8］ 王冠，景小寧，王彥軍.基本路徑測試中的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

中圖分類號：TP312

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

文章編號：1007-757X（2016）05-0020-03

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

作者簡介：祁 俊（1977-），女，青海貴德，青海大學(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）