鄧定勝

摘要：作為一個擁有離散結(jié)構(gòu)的數(shù)字電子計算機(jī)，它的操作對象只有離散和離散化了的數(shù)量關(guān)系，所以不光是計算機(jī)科學(xué)，還有與它和它的應(yīng)用緊密相連的現(xiàn)代科學(xué)研究領(lǐng)域都面臨著同一個難題，那就是在建立與離散結(jié)構(gòu)對應(yīng)的數(shù)學(xué)模型同時，怎樣離散已經(jīng)利用連續(xù)數(shù)量關(guān)系而建成的數(shù)字模型，并利用計算機(jī)來進(jìn)行處理。事實上離散數(shù)學(xué)大致可以被認(rèn)為是抽象化了的計算機(jī)問題，數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計中都能夠體現(xiàn)出離散性。計算機(jī)里能夠表現(xiàn)離散性的問題有很多，因此計算機(jī)科學(xué)在研究離散數(shù)學(xué)時有多種選擇，這些表現(xiàn)大致都能夠被認(rèn)為是計算機(jī)中的二進(jìn)制。本文主要從其算法、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)與數(shù)字電子、計算機(jī)中的離散型問題以及實驗仿真五個方面出發(fā)，對計算機(jī)的算法設(shè)計和數(shù)據(jù)結(jié)構(gòu)離散進(jìn)行了一定的研究和分析。希望可以對有關(guān)方面的改善和促進(jìn)起到一定的借鑒作用和指導(dǎo)意義。

關(guān)鍵詞：C程序設(shè)計;數(shù)據(jù)結(jié)構(gòu);離散型;算法

中圖分類號：TP311 ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）14-0210-03

Abstract： As a digital computer with discrete structure， its operating object only has discrete and discrete quantitative relationship， so not only computer science， but also modern scientific research fields closely linked with its application are facing the same problem， that is， how to discretize the continuous number while establishing the mathematical model corresponding to the discrete structure The digital model built by the relationship is processed by computer. In fact， discrete mathematics can be roughly regarded as abstract computer problems， which can be reflected in data structure and algorithm design. There are many problems in computer that can express discreteness， so computer science has many choices in the study of discrete mathematics， which can be roughly considered as binary in computer. In this paper， the algorithm design and data structure discretization of computer are studied and analyzed from five aspects： algorithm， data structure， discrete mathematics and digital electronics， discrete problems in computer and experimental simulation. I hope it can play a certain role in reference and guiding significance for the improvement and promotion of relevant parties.

Key words： C Programming; Data Structure; Discrete Type; Algorithms

互聯(lián)網(wǎng)行業(yè)的發(fā)展日新月異，引起了人們的高度重視，尤其是其中最為重要的計算機(jī)行業(yè)。理論上最應(yīng)該受到重視的就是數(shù)據(jù)結(jié)構(gòu)與程序算法，可大多數(shù)人本末倒置，對程序結(jié)果更為重視。

本文就如何體現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計的離散性提出了方法，具體地說明了怎樣解決抽象化了的計算機(jī)問題，以達(dá)到把連續(xù)性到離散性的思維方法傳輸給讀者的目的。

作為一種科學(xué)知識，計算機(jī)算法與結(jié)構(gòu)是計算機(jī)科學(xué)中必不可少的，它是模擬實驗和進(jìn)行計算機(jī)科學(xué)計算的主要工具，能夠促進(jìn)未來計算機(jī)科學(xué)的發(fā)展。最近幾年，計算機(jī)科學(xué)發(fā)展迅速，獲得了非常多的成就。基礎(chǔ)科學(xué)給計算機(jī)科學(xué)提供了應(yīng)有的理論支持，把計算機(jī)科學(xué)應(yīng)用在現(xiàn)實生活之中，并結(jié)合基礎(chǔ)科學(xué)構(gòu)成了其發(fā)展的基礎(chǔ)性理論[1]。數(shù)學(xué)知識是計算機(jī)科學(xué)的理論基礎(chǔ)，在解決存在于應(yīng)用過程中的各種各樣的問題時，需要把計算機(jī)問題抽象化，從而把它當(dāng)作數(shù)學(xué)問題。

1 算法

本節(jié)在表述計算機(jī)離散性問題時通常利用算法。本節(jié)就算法的基本概念給出了概述，同時利用雙算法設(shè)計的方式來表現(xiàn)離散性。本節(jié)在表述算法時都利用了c語言。

1.1算法的基本概念

算法就是準(zhǔn)確又具體地去描述解題方案，是能夠把問題解決的一連串的明確指令，而且算法作為一種策略機(jī)制，在描述與解決問題時能夠利用系統(tǒng)的方法。意思就是，可以在短時間內(nèi)得到一定規(guī)范的輸入所對應(yīng)要求的輸出。

算法應(yīng)用在流程型的程序中時沒有什么特別高的要求，可是在人機(jī)交互、圖形圖像識別、人工智能、虛擬現(xiàn)實、社會工程學(xué)、大數(shù)據(jù)分析、音視頻識別、現(xiàn)實增強(qiáng)、云計算、大型網(wǎng)絡(luò)拓?fù)涞阮I(lǐng)域中應(yīng)用時，對算法的要求就比較高了。

在日常生活中就能發(fā)現(xiàn)一些比較好的算法設(shè)計，例如手機(jī)中各種各樣的美圖軟件。軟件怎樣把人臉識別出來？怎樣確定眼睛、嘴巴和鼻子在人臉上的位置？怎樣在人臉上進(jìn)行一定的不失真的美化？

在世界第二次大戰(zhàn)進(jìn)行時，以人工智能之父、計算機(jī)科學(xué)之父阿蘭·圖靈為領(lǐng)頭人的小組幫助盟軍把能夠破譯德國密碼系統(tǒng)Enigma的機(jī)器設(shè)計了出來。當(dāng)中對機(jī)器的設(shè)計過程可以被認(rèn)為是算法的設(shè)計過程。事實上可以說是圖靈設(shè)計小組做出了一個能夠把德國納粹密碼系統(tǒng)在短時間內(nèi)解密出來的算法，同時為之相應(yīng)的設(shè)計出了機(jī)器。

由此可知，程序的根本就是算法。不管是普通的高等院校還是在世界上都處于前沿的科技企業(yè)，在進(jìn)行關(guān)于計算機(jī)或者程序的科學(xué)性研究時，都必然會涉及算法的研究。算法的設(shè)計是所有的系統(tǒng)中最基礎(chǔ)、最關(guān)鍵的首要步驟。

1.2算法體現(xiàn)的離散性

在進(jìn)行算法的設(shè)計時，通常能夠體現(xiàn)離散性[2]，離散性作為一種不連續(xù)的特性在計算機(jī)科學(xué)中可以經(jīng)常見到。

1.2.1算法設(shè)計常用的方法

算法設(shè)計有許多方法與有關(guān)文獻(xiàn)。這里介紹了兩種最簡單的方法：遞推法和遞歸法，而且在后面做出了相關(guān)舉例。

（1）遞推法

遞推算法在序列計算機(jī)中是比較常見的，它的特點是化難為易，化繁為簡。因為計算機(jī)是一種機(jī)器，它的運(yùn)行速度非?？?，而且不會疲憊，所以在計算序列各項時，有一定的規(guī)律可循，一般要想知道序列中指定的項，需要利用計算機(jī)前面的一些項來求得。其原理是把龐大又復(fù)雜的計算過程分割成多次重復(fù)的簡單又容易的過程[3]。

（2）遞歸法

遞歸就是程序?qū)⒆陨淼木幊碳记杉右赃\(yùn)用的過程。表現(xiàn)為一個過程或者函數(shù)在它的說明和定義中涉及自身的調(diào)用，它一般是將一個比較龐大復(fù)雜的問題一點點轉(zhuǎn)化成一個大概等同于原問題的比較小型且簡單的問題，并求解。在將一個有著多次重復(fù)計算的解題過程簡化時，需要運(yùn)用遞歸法，而且僅僅需要很少的程序量就能夠解決，使程序的代碼量降低了很多。遞歸的能力表現(xiàn)在定義對象的無限集合時用的是有限的語句。通常遞歸的三要素是有邊界條件、遞歸前進(jìn)段以及遞歸返回段。如果邊界條件不滿足，那么遞歸前進(jìn)，反之，遞歸返回。

1.2.2兩種方法的離散性體現(xiàn)

遞推法中，計算機(jī)在進(jìn)行一個比較復(fù)雜的運(yùn)算時，用的方法比較傻。例如算法1，通過一個求最大值的算法來解釋。

算法1：求最大值

int max（int *array，int size）

{int mval=*array;

int i;

for（i=1;i

if（array[i]>mval）

mval=array[i];

return（mval）;

}

由此可見，不管有多少數(shù)字，只要還沒有得出最終結(jié)果，計算機(jī)就會一直按部就班地用已知的最大的數(shù)去比較數(shù)組中的下一個數(shù)。相比來說，人類就不會用這種死板的方式去比較數(shù)字的大小，在數(shù)字特別多的情況下時，人們就會先把數(shù)字的位數(shù)最高的挑出來，如果有多個位數(shù)最高的數(shù)字，再讓它們?nèi)ケ容^。人類比較習(xí)慣應(yīng)用連續(xù)性的思維模式，所以由人而產(chǎn)生的初等數(shù)學(xué)都是建立在連續(xù)的基礎(chǔ)之上，從而也出現(xiàn)了幾何的概念。可是計算機(jī)作為硬邦邦的機(jī)器，不具備人類思維靈活的特點，也就很難有這種連續(xù)的思維。要想讓計算機(jī)模擬人類的連續(xù)性思維，必須為之設(shè)計出更為復(fù)雜多變的算法。人類之所以能夠擁有這種連續(xù)性的思維，是因為作為思維控制中心的人類大腦這個驅(qū)動器非常的高級，自身就能夠擁有足夠復(fù)雜的算法。目前有不少的相關(guān)研究和文獻(xiàn)能夠為如何設(shè)計出更為復(fù)雜的算法、讓計算機(jī)的運(yùn)行更為快速并能模擬出人腦的思維方式提供資料，然而這并不是本文的重點。

有時能夠用遞歸法來讓算法更加的簡單，例如在求兩個自然數(shù)的最大公約數(shù)時，如算法2，其改用遞歸算法后如算法3。

算法2：求最大公約數(shù)

void swap（int *x，int *y）

{int tmp=*x;

*x=*y;

*y=tmp;

}

int ged（int m，int n）

{int r;

do

{if（m

swap（&m，&n）;

r=m%n;

m=n;

n=r;

}while（n！=0）

return（m）;

}

算法3：遞歸法求最大公約數(shù)

int gcd（int a，int b）

{if（a%b）

return（gcd（b，a%b）;

return（b）;

}

可以把遞歸法理解為“自己調(diào)用自己”。一種離散性的表現(xiàn)和先前的例子差不多，這里就不再重復(fù)了。這里就程序運(yùn)行所表現(xiàn)出來的離散性做出表述。計算機(jī)是在以“后進(jìn)先出”為特點的棧中進(jìn)行運(yùn)行程序的。在這個遞歸算法的運(yùn)行過程中，“自己”就可以滿足返回值的需要，就是參數(shù)不同而已。一直到返回出一個確定的值，再層層返回，如圖1 所示。

由此可知，在計算完成之前，計算機(jī)每用遞歸法計算一次，就伴隨著一次Push內(nèi)存，在計算完成之時，再開始一次一次有序的Pop出，這體現(xiàn)出了計算的離散性，與人類連續(xù)的思維模式是有區(qū)別的。

2 數(shù)據(jù)結(jié)構(gòu)

本節(jié)在表述計算機(jī)中的離散性問題時主要利用數(shù)據(jù)結(jié)構(gòu)，就數(shù)據(jù)結(jié)構(gòu)的基本概念與其離散性的基本理解給出了概括。

2.1數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)中有著舉足輕重的地位。因為數(shù)據(jù)元素之間有著不同的特性關(guān)系，通?？梢园哑浠窘Y(jié)構(gòu)分為四種：樹形結(jié)構(gòu)、集合、線性結(jié)構(gòu)、網(wǎng)狀或圖狀結(jié)構(gòu)，圖2就表示了來自于數(shù)據(jù)結(jié)構(gòu)的元素之中的離散性特征[4]。