前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇計算機程序設(shè)計藝術(shù)范文，相信會為您的寫作帶來幫助，發(fā)現(xiàn)更多的寫作思路和靈感。

計算機程序設(shè)計藝術(shù)范文第1篇

關(guān)鍵詞：算法；程序結(jié)構(gòu)；循環(huán)；遞歸

中圖分類號：TP391文獻標識碼：B

文章編號：1672-5913(2007)12-0083-05

1問題的提出

結(jié)構(gòu)化程序設(shè)計中，只有三種基本的結(jié)構(gòu)：順序、選擇和循環(huán)。

順序結(jié)構(gòu)是程序設(shè)計過程中自然形成的，也是三種結(jié)構(gòu)中最簡單的一種。選擇結(jié)構(gòu)與我們?nèi)粘Ｖ惺褂玫淖匀徽Z言“如果...則...否則...”十分相近，只是其嵌套時的二義性在形式上必須有一個明確的規(guī)定。

而循環(huán)結(jié)構(gòu)是三者中最為復雜的，也是使用最多的。一個算法往往要用循環(huán)結(jié)構(gòu)來描述，一個程序能否正確編寫又往往取決于對循環(huán)結(jié)構(gòu)的正確理解和使用。因此，有必要深入對循環(huán)結(jié)構(gòu)做一個分析。本文從循環(huán)結(jié)構(gòu)的三個要素、循環(huán)結(jié)構(gòu)與程序的閱讀、循環(huán)與遞歸的聯(lián)系等三個方面進行分析與論述，而這些在目前的教學中往往很少提到，甚至是被忽略的。

2循環(huán)結(jié)構(gòu)的三要素

初學程序設(shè)計的人，對于如何在程序中使用循環(huán)結(jié)構(gòu)實現(xiàn)算法，總覺得不知從何入手，有時即使編出程序，也不盡人意。下面我們從一個簡單的典型實例說起。為了說明問題，本文對有關(guān)編程的問題都以C語言函數(shù)的方式列出解答。

2.1一個典型實例及其兩種解答

例2.1雞兔同籠，有h個頭，f只腳，求雞兔各多少。這是我國古代一個典型的算術(shù)問題?，F(xiàn)在要設(shè)計一個函數(shù)，求出兔子的數(shù)目(求出兔子的數(shù)目，自然就可以得到雞的數(shù)目)。不妨設(shè)這個函數(shù)為：

int hab(int h, int f);

函數(shù)的定義如下：

int rabbit (int h, int f)// h為頭數(shù), f為腳數(shù)

{

int i;

i=h;

while (i＞=0 )

{

if (i*4+(h-i)*2==f) break;

i--;

}

return i; //-1表示該該問題無解。

}

這個程序的運行結(jié)果是正確的，但是很遺憾，這并不是一個完美的程序，盡管很多教科書也是這樣寫的。我們再來看看下面的另一種解法：

int rabbit (int h, int f)// h為頭數(shù), f為腳數(shù)

{

int i;

i=h

while((i＞=0)&& (i*4+(h-i)*2!=f ))

i--;

return i;//-1表示該問題無解。

}

以上兩個程序都用到循環(huán)結(jié)構(gòu)，第一個程序在循環(huán)結(jié)構(gòu)中嵌套了一個選擇結(jié)構(gòu)，并且使用了break語句。而在第二個程序中，無需這樣做。無論從程序的結(jié)構(gòu)，還是從程序的可讀性來說，后者顯得比前者要好得多。那么問題出在哪里呢？

2.2深入分析

比較兩個程序可以發(fā)現(xiàn)，關(guān)鍵是對條件表達式(i*4+(h-i)*2!=l)的運用。前者把條件表達式放在循環(huán)體中，后者把它作為循環(huán)條件。看來，有必要對循環(huán)結(jié)構(gòu)做深入的分析。

不管一個循環(huán)結(jié)構(gòu)有多復雜，都可以從以下三個方面來分析：

1) 初始狀態(tài)：所有參與循環(huán)的變量在循環(huán)之前都必須有一個確定的值。

2) 循環(huán)條件：當條件滿足時，循環(huán)繼續(xù)，否則循環(huán)終止。循環(huán)條件應是一個邏輯表達式。

3) 循環(huán)體：每次循環(huán)要執(zhí)行的語句。

這就是我們所講的循環(huán)結(jié)構(gòu)三要素。從這個角度再來分析上面的例子，就很容易找到問題的結(jié)癥：(i*4+(h-i)*2!=l)是循環(huán)條件之一，因此不應放在循環(huán)體內(nèi)使用。第一種方法雖然也能得到正確的結(jié)果，但并不是好的方法，甚至是不正確的方法。

2.3一個應用實例

例2.2 裴波那契序列數(shù)的遞歸表示如下：

f0=0

f1=1

fn=fn-2+fn-1(n＞=2)

對于任意給定的正整數(shù)x，判別其是否在裴波那契序列中。

現(xiàn)在要求判別一個給定的正整數(shù)x是否在裴波那契序列中，一個直觀的判別方法是從f0和f1出發(fā)，不停地求后面的裴波那契序列數(shù)。每得到一個裴波那契序列數(shù)，就同這個待判別數(shù)進行比較，直到相等時輸出“真”。或當?shù)玫揭粋€裴波那契序列數(shù)大于這個待判別數(shù)時，輸出“假”。

要實現(xiàn)這個算法，需用到循環(huán)結(jié)構(gòu)。我們來分析一下這個循環(huán)結(jié)構(gòu)的三個要素：

(1) 初始狀態(tài)：f0=0; f1=1，x=?；

(2) 循環(huán)條件：當前求得的裴波那契序列數(shù) < 待判別數(shù)x；

(3) 循環(huán)體：計算一個新的裴波那契序列數(shù)。

根據(jù)以上的分析，判別一個給定的正整數(shù)x是否在求裴波那契序列中的C函數(shù)如下：

int in_fib(int x)

{

int f0=0, f1=1;

while (f1＜x)

{

t=f1+f0;

f0=f1;

f1=t;

}

return (x==f1|| x==f0);

}

3循環(huán)結(jié)構(gòu)與程序的閱讀

3.1閱讀的意義

對于計算機程序的閱讀，著名的計算機科學家克努特曾說過：閱讀他人的計算機程序獲得技巧是極其重要的，但在許許多多的計算機課程中這樣一種訓練卻可悲地被忽視了，因此導致計算機極其低效率的使用。

學習一種計算機程序設(shè)計語言，不管是匯編語言還是高級語言，一個重要而又常用的方法就是閱讀：閱讀書中的例題，閱讀別人寫的程序，更多的是閱讀自已寫的程序。在某種意義上來說，一個程序是“被閱讀”的。首先是被計算機閱讀，這是毫無疑義的，但更多時候是被人閱讀。

3.2閱讀的方法

閱讀的目的是為了分析程序中的語句是如何實現(xiàn)算法的。對于一些較為復雜的程序，如果一開始就去分析每一個語句的功能，就很容易掉進“迷宮”。因此在分析一個程序時應該先分析程序的結(jié)構(gòu)，然后再對每個結(jié)構(gòu)中的語句逐一進行跟蹤閱讀。

1. 程序結(jié)構(gòu)的分析

程序結(jié)構(gòu)的分析過程分為兩個步驟：第一是找出組成程序的各種結(jié)構(gòu)，第二是找出這些結(jié)構(gòu)之間的連接方式。

程序結(jié)構(gòu)的分析應符合結(jié)構(gòu)化程序設(shè)計的原則。一種結(jié)構(gòu)化程序設(shè)計語言(如C語言，Pascal)，只包含三種基本結(jié)構(gòu)：順序、選擇和循環(huán)。每種結(jié)構(gòu)只有一個入口和一個出口。而各個結(jié)構(gòu)之間的連接方式有兩種：積木式和嵌套式。積木式的連接是一個結(jié)構(gòu)的出口與另一個結(jié)構(gòu)的入口的連接，而嵌套式的連接是在一個結(jié)構(gòu)的內(nèi)部嵌套另一個結(jié)構(gòu)。一般來說，我們應先分析出程序中積木式連接的各個結(jié)構(gòu)，然后再找出這些結(jié)構(gòu)中的嵌套式連接的結(jié)構(gòu)。分析程序結(jié)構(gòu)時可以借用一些工具，如N-S圖、偽代碼等，即根據(jù)源程序畫出能反映程序結(jié)構(gòu)的N-S圖或?qū)懗龅刃У膫未a。這是一個與編程過程剛好相反的過程。

2. 語句的跟蹤閱讀

對于順序結(jié)構(gòu)的語句，閱讀是不成問題的。而對于選擇結(jié)構(gòu)的語句，由于與我們平時所用的自然語言比較一致，也不是太大的困難。關(guān)鍵在于，當有兩個選擇結(jié)構(gòu)連接時，采用積木式的連接與采用嵌套式連接的差別是很大，有時甚至使得程序運行的結(jié)果截然相反。

循環(huán)結(jié)構(gòu)是三種結(jié)構(gòu)中最為復雜的一種，對這種結(jié)構(gòu)的跟蹤閱讀可以用列表的方法，將循環(huán)過程中各語句執(zhí)行的結(jié)果一一列出。這個表包含了循環(huán)結(jié)構(gòu)的三個要素。

我們還是從著名的歐幾里德算法說起。

例3.1求兩個正整數(shù)的最大公約數(shù)。

【歐幾里德算法】

E1.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=r＜n)。

E2.[余數(shù)為0?] 若r=0, 算法結(jié)束, n即為答案。

E3.[互換] 置mn, nr, 并返回步驟E1。

為了使計算過程更為緊湊，也考慮到當n=0時，算法仍然有效，可將以上算法稍作改動如下：

E'1.[n為0?] 若n=0, 算法結(jié)束, m即為答案。

E'2.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=n＜n)。

E'3.[互換] 置mn, nr, 并返回步驟E'1。

根據(jù)以上所描述的算法，我們可以用C語言寫出相應的函數(shù)：

int gcd(int m,int n)

{

int r;

while (n!=0)

{

r=m%n;

m=n;

n=r;

}

return m;

}

我們通過一組真實的數(shù)據(jù)(例如：m=20, n=12)分析循環(huán)結(jié)構(gòu)的執(zhí)行過程，即對循環(huán)體內(nèi)的語句逐一進行跟蹤閱讀，直至循環(huán)條件不成立。分析程序執(zhí)行的過程如下：

閱讀的過程是艱苦的，初學者對此可能不十分習慣。但是這是學習一種計算機程序設(shè)計語言所必須掌握的方法，也是必須經(jīng)歷的過程。企圖繞開這個過程，尋找別的捷徑是不可能的。

4循環(huán)與遞歸

遞歸是計算科學中一個很重要的核心概念，它出現(xiàn)在計算科學的各門分支學科中，如計算理論基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計方法、程序設(shè)計語言等等。那么，遞歸與循環(huán)有什么聯(lián)系和區(qū)別呢？

在關(guān)于循環(huán)結(jié)構(gòu)三要素中，我們說循環(huán)結(jié)構(gòu)中的第一個要素是循環(huán)的初始狀態(tài)，那么每循環(huán)一次，參與循環(huán)的變量中至少有一個會發(fā)生變化(否則就會出現(xiàn)“死循環(huán)”)。因此，循環(huán)的過程就是從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)，在經(jīng)歷了若干個狀態(tài)之后，到達終結(jié)狀態(tài)，循環(huán)就結(jié)束。因此可以把一個循環(huán)結(jié)構(gòu)看成是一個有窮狀態(tài)機。在計算理論上，有窮狀態(tài)機能計算的問題，圖靈機必能計算，而圖靈機與遞歸函數(shù)是等價的。從這個意義上講，一個可以用循環(huán)結(jié)構(gòu)解決的問題必然也可以用遞歸方法來解決。對現(xiàn)在一般在大學一、二年級學習程序設(shè)計的學生來說，還不可能深入討論這個問題。但我們可以用一些典型的實例，通過循環(huán)與遞歸的對比，使得低年級的學生們對遞歸有一個初步的認識。

4.1遞歸的意義與遞歸函數(shù)

我們來看一個簡單的例子。

例4.1求一個正整數(shù)n的階乘。

根據(jù)正整數(shù)階乘的定義n！＝1×2×3×......×n，用一個循環(huán)結(jié)構(gòu)即可很容易編寫出計算階乘的程序。如果用一個函數(shù)f(n)來表示n的階乘，也可以這樣來定義f(n)：

1 n=0

f(n)={

n?f(n-1)n＞0

在定義f(n)時又用到f這個函數(shù)，這就是遞歸。注意，在定義式中用到函數(shù)f，但它的自變量是n-1，計算n-1的階乘要比計算n的階乘容易一些。而且當n=0時，可以直接得到答案f(0)=1。

例4.2求兩個正整數(shù)的最小公倍數(shù)。

歐幾里德算法(見例3.1)與以下的遞歸函數(shù)是等價的：

m n=0

gcd(m,n)= {

gcd(n,m%n)n＞0

在這里，當n>0時，計算的是n和m%n的最小公倍數(shù)。顯然，這時的兩個正整數(shù)要比原來的兩個正整數(shù)(m, n)要小，計算也變得容易一些。

通過以上的例子，我們可以這樣來理解遞歸的意義：把一個復雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個問題，直至可以直接得到問題的解。

4.2用遞歸函數(shù)取代循環(huán)結(jié)構(gòu)

一個程序如果可以用循環(huán)結(jié)構(gòu)來實現(xiàn)，那么也可以用一個遞歸函數(shù)來實現(xiàn)。我們先來看一個簡單的例子。

例4.3求一個有n個元素的數(shù)組中的最大元素。

用循環(huán)結(jié)構(gòu)的方法如下：

int max(int a[])

{

int i, m;

m=a[0]

for (i=1; i＜10,i++)

if(max＜a[i])m=a[i];

return m;

}

用遞歸函數(shù)。設(shè)一遞歸函數(shù)max(a,k)是求a數(shù)組中第k個元素及其后所有元素的最大者：

a[k]k=n-1;

max(a,k)= {

a[k]＞max(a,k+1)?a[k]：max(a,k+1) k＜n-1

用C語言編寫的函數(shù)如下：

int max(int a[], int k, int n)

{ int m;

if (k==n-1)return ( a[k] )

else {m=max(a,k+1);

return ( a[k]＞m?a[k]：m ); }

}

這是一個簡單的例子，下面再看一個較為復雜性的例子。

例4.4用遞歸函數(shù)求解例2.1。

用遞歸函數(shù)來求解例2.1，應如何考慮呢？正如以上所說，遞歸的意義是把一個復雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個問題，直至可以直接得到問題的解。因此我們可以這樣來考慮：把籠中的一只雞抓走，籠中的兔子的數(shù)目是不變的，顯然這仍然是雞兔同籠的問題，但少了一只雞，問題就變得簡單了一點。當所有的雞都被抓走時，剩下的都是兔，這時就可以直接得到答案――腿數(shù)除以頭數(shù)就是兔子的數(shù)目。

我們用robb(h,g)這樣一個函數(shù)表示求兔子的數(shù)目，參數(shù)h、g分別表示頭數(shù)和腿數(shù)，因此有：

robb(x,y)=robb(x-1,y-2)

但在什么情況下能直接得到結(jié)果呢？顯然，當雞全部抓走只留下兔子時，就可以直接得到答案，這時腿數(shù)應是頭的4倍：

roob(x,y)=x當4*x=y

另外還要考慮在什么情況下問題沒有解。顯然，當4*h＜g時，這個問題無解。

x

4*x=y

robb(x,y)={ robb(x-1,y-2)　4*x＞y

-1

4*x＜y(-1表示問題無解)

在求得兔子的數(shù)目之后，只要用總數(shù)減去兔子的數(shù)目，就能求出雞的數(shù)目。

結(jié)束語

程序設(shè)計作為一門學科，經(jīng)歷了子程序、高級語言、結(jié)構(gòu)化程序設(shè)計三個里程碑[2]。近十幾年興起的面向?qū)ο蟪绦蛟O(shè)計可以說是第四個里程碑。程序設(shè)計在計算科學這門年輕的學科中，是一門“古老”的分支學科，又是一門久經(jīng)不衰的學科。計算科學中的許多新思想、新方法、新技術(shù)都首先體現(xiàn)在程序設(shè)計上。這種現(xiàn)象使我們不得不領(lǐng)悟到，這門課程中的許多知識反映了計算科學深刻的內(nèi)涵，程序設(shè)計的教學應體現(xiàn)這一點。例如上述的循環(huán)結(jié)構(gòu)，就很值得我們?nèi)ヌ接?。本文提出的一些觀點，確實很膚淺，希望能起到一個拋磚引玉的作用。

參考文獻：

[1] 蘇運霖譯. 計算機程序設(shè)計藝術(shù) 第1卷 基本算法［M］. 北京：國防工業(yè)出版社，2002.

[2] 王選. 王選文集［M］.北京大學出版社，1997.

[3] 趙致琢. 計算科學導論(第二版)［M］. 北京：科學出版社，1998.

收稿日期：2006-5-27

通信地址：廣東省廣州市 華南師范大學計算機學院， 510631

計算機程序設(shè)計藝術(shù)范文第2篇

關(guān)鍵詞:算法;復雜認知技能;4C/ID

尼克勞斯•威茨,結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者和圖靈獎獲得者,提出了一個著名論斷:程序=算法+數(shù)據(jù)結(jié)構(gòu)。這說明了算法的重要地位。什么是算法?算法和程序設(shè)計技術(shù)的先驅(qū)者高德納把算法比喻成菜譜。他認為“算法是一組有窮的規(guī)則,這些規(guī)則給出求解特定類型問題的運算序列”,他強調(diào)“我們不僅要算法,而且還要在某種不明確定義的意義下的好算法”[1]――算法分析。《高等學校計算機科學與技術(shù)專業(yè)實踐教學體系與規(guī)范》把算法設(shè)計與分析能力界定為計算機專業(yè)高級人才的基本學科能力之一[2]。可見,“算法設(shè)計與分析”課程的重要性。然而,學生普遍覺得該課程難學。為了解決這個問題,應用四要素教學設(shè)計模型(以下簡稱4C/ID)進行教學改革。4C/ID是提高復雜認知技能的方法,在國外,4C/ID的研究已有30年的歷史,曾經(jīng)成功地將4C/ID應用與計算機編程。在國內(nèi),4C/ID的研究還處于起步階段。本文主要研究了4C/ID在“算法設(shè)計與分析”課程教學中的實踐。

1課程教學中存在的問題

1.1學生學習有畏難情緒

算法是問題的程序化解決方案[3]。首先,要理解問題,確定問題的條件和應用范圍。然后,建立數(shù)學模型。最后,證明算法的正確性和分析算法的效率。這需要微積分、線性代數(shù)、離散數(shù)學等數(shù)學知識。所以,對于這門復雜、抽象的課程,學生自然感到難學。

1.2算法實現(xiàn)有難度

算法實現(xiàn)指編制與調(diào)試算法。算法實現(xiàn)有助于加深對算法的理解,是不可缺少的環(huán)節(jié)。算法的實現(xiàn)取決于:(1)豐富的程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)實踐經(jīng)驗。如學生在程序調(diào)試時經(jīng)常出的錯是缺少函數(shù)聲明;在進行“分支限界”實訓時,很多學生由于沒有掌握隊列而無法實現(xiàn)裝載問題算法。這是程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)不扎實造成的。過多的出錯會嚴重影響上機實踐的質(zhì)量,造成學生不愿動手。(2)對算法的理解。算法通常是由偽代碼來描述的,如果不理解算法,很難準確地將算法轉(zhuǎn)換成可以運行的程序。如果這兩個問題不能很好地解決,算法設(shè)計與分析能力的培養(yǎng)就成為一句空話。

2 “4C/ID”是解決問題的途徑

算法設(shè)計與分析是復雜的認知技能,其構(gòu)成見圖1。復雜的認知技能是由一系列的技能所構(gòu)成,其中一部分構(gòu)成技能體現(xiàn)為自動的處理過程,其它多數(shù)的構(gòu)成技能涉及認知的領(lǐng)域[4]。從圖1可以看出,這是一個復雜的學習過程。如果從頭到尾地講解給學生聽,然后再讓學生上機實踐,這就不能了解學生哪些技能掌握了,哪些沒有掌握,從而影響了上機實踐的質(zhì)量。而且,直線式講解不符合問題求解的規(guī)律,有些過程需要反復實踐,有些過程需要思考和補充相關(guān)信息。4C/ID是面向復雜認知技能培訓的教學設(shè)計模型,由約倫•范麥里恩伯爾基于學習和信息加工的認知心理學理論創(chuàng)造。該模型之所以能提高復雜認知技能的原因是它將復雜認知技能分成再用性構(gòu)成技能和非再用性構(gòu)成技能,并對它們分別進行實際練習設(shè)計和信息呈現(xiàn)設(shè)計。再用性構(gòu)成技能是指在不同問題情境中以極為類似的方式而操作的技能,非再用性構(gòu)成技能是指在不同的問題情境中進行不同操作的技能[5]。再用性構(gòu)成技能的熟練掌握可以解決問題中熟悉的方面,非再用性構(gòu)成技能通過圖式建構(gòu)可以運用于問題情境中新的、不熟悉的方面。兩者相互促進,能提高解決問題的整體水平。所以,將4C/ID應用于“算法設(shè)計與分析”教學中會比傳統(tǒng)的教學方法更能提高算法設(shè)計與分析的能力。

3 “4C/ID”的教學實踐

4C/ID分成教學分析和教學設(shè)計兩個部分。這兩個部分又各分成兩層,共4層。它們是:(1)原理性技能的分解;(2)構(gòu)成技能及相關(guān)知識的分析;(3)教學方法的選擇;(4)訓練策略的合成。

3.1原理性技能的分解

4C/ID的第一步是將復雜認知技能分成不同類型的構(gòu)成技能。分解的過程依據(jù)一定的原則,因此稱為“原理性”分解。原理性技能的分解遵循以下的原則:(1)識別。識別組成復雜認知技能的構(gòu)成技能,產(chǎn)生一個技能分層結(jié)構(gòu)。這個分層結(jié)構(gòu)包含了確定的構(gòu)成技能及它們之間的關(guān)系。(2)描述。清晰描述每個構(gòu)成技能。(3)分類。將構(gòu)成技能分成用于培訓和不用于培訓的技能。對于用于培訓的構(gòu)成技能將進一步分成再用性構(gòu)成技能和非再用性構(gòu)成技能。(4)排序。將被選擇用于培訓的構(gòu)成技能排序。這里重點講一下如何區(qū)別再用性構(gòu)成技能和非再用性構(gòu)成技能。它們的區(qū)別主要反映在執(zhí)行時表現(xiàn)不同。再用性構(gòu)成技能的表現(xiàn)特征為:(1)執(zhí)行很快;(2)顯示錯誤很少或沒有;(3)能和其他構(gòu)成技能同時執(zhí)行;(4)只能在特定的問題情境中產(chǎn)生上述特點,不易遷移到新的、不熟悉的情境中。再用性構(gòu)成技能的執(zhí)行過程可以被制定成一套執(zhí)行程序,只要配以必備的知識,總能成功的執(zhí)行。非再用性構(gòu)成技能的表現(xiàn)特點:(1)執(zhí)行緩慢;(2)執(zhí)行過程容易出錯;(3)不適合與其他的非再用性構(gòu)成技能同時執(zhí)行。如,深度優(yōu)先搜索算法就是再用性構(gòu)成技能,在求解動態(tài)規(guī)劃問題時分析最優(yōu)子結(jié)構(gòu)是非再用性構(gòu)成技能。

3.2構(gòu)成技能及相關(guān)知識的分析

構(gòu)成技能的分析方法有程序分析法和基于規(guī)則的分析法。程序分析法用于可以觀察的、具有先后執(zhí)行順序的再用性構(gòu)成技能,基于規(guī)則的分析法用于不可觀察的、不具有明顯先后執(zhí)行順序的非再用性構(gòu)成技能。

3.2.1再用性構(gòu)成技能

深度優(yōu)先搜索可以表示成固定的“算法”,如圖2。再用性構(gòu)成技能的成功執(zhí)行往往需要必備知識。必備知識包括事實、概念、原則等,見圖2中的注釋。

3.2.2非再用性構(gòu)成技能

非再用性構(gòu)成技能的執(zhí)行過程不能表示成固定的“程序”,它的執(zhí)行依賴于支撐性知識和策略性知識。其實,非再用性構(gòu)成技能的分析就是對支撐性知識和策略性知識的分析。支撐性知識的分析涉及到復雜的認知圖式。復雜的認知圖式由不同的、有相互關(guān)系的認知單元所組成,這些認知單元可以是陳述、概念、原理等。支撐性知識的分析是建立在對關(guān)系分析的基礎(chǔ)上,再從相關(guān)的關(guān)系中找出所有有用的認知單元。主要的關(guān)系包括種類關(guān)系、部分關(guān)系、方位關(guān)系、原因―結(jié)果關(guān)系、相似關(guān)系。確定關(guān)系和認知單元后,用概念模型、目標―方案層次結(jié)構(gòu)、原理功能模型、心智模型組織和顯示認知單元及它們之間的關(guān)系。策略性知識的分析主要采用解決問題的系統(tǒng)方法。該方法的目的是要建立一個描述解決問題的模型。為了建立這個模型,讓專家和教師解決他們領(lǐng)域內(nèi)和該問題相似的經(jīng)典問題,并且要求他們在思考問題的同時把思路講出來,這些話便被整理成描述解決問題的模型。如,在求解動態(tài)規(guī)劃問題時可以選擇矩陣鏈相乘、求最長公共子序列、最優(yōu)二叉搜索樹、裝配線調(diào)度等例子,通過分析經(jīng)典教材來建立描述解決問題的模型。

3.3教學方法選擇和訓練策略合成

教學方法通過現(xiàn)則支持再用性、非再用性構(gòu)成技能獲得的實際練習設(shè)計和信息呈現(xiàn)設(shè)計。學習者通過反復訓練都能掌握再用性構(gòu)成技能,相應的信息呈現(xiàn)可以采用分割、示范和搭建腳手架的方法。分割的作用是避免認知負荷,在同一時間內(nèi)僅提供直接的、可利用的信息。專家示范可以形象地說明規(guī)則和程序的運作。搭建腳手架就像幫助系統(tǒng)一樣,能因人而異地

提供及時的、直接有效的信息。非再用性構(gòu)成技能的獲得取決于圖式建構(gòu)。圖式建構(gòu)是指把低水平的圖式整合到高水平圖式中,逐漸形成更加復雜的圖式。復雜的圖式有助于非再用性構(gòu)成技能的獲得。圖式建構(gòu)取決于歸納的程度。歸納的作用為:(1)創(chuàng)建新的圖式;(2)調(diào)整已有圖式,使之適合更廣泛的事件。相應的信息呈現(xiàn)方式必須能為歸納所用。因此,必須要對知識精制化。精制化是指將新的知識整合到記憶中已有的認知結(jié)構(gòu)。這個過程通過類比來實現(xiàn)。

復雜認知技能的獲得是建立在整體任務(wù)實踐的基礎(chǔ)上。因此,訓練策略的合成是形成復雜認知技能的關(guān)鍵。這個過程必須遵循以下原則:(1)在實踐開始階段,為再用性和非再用性構(gòu)成技能提供需要的必備知識和支撐知識;(2)隨著專長的提高,相應地減少知識的呈現(xiàn),直至學習者能夠獨立地、在不需要幫助的情況下面對真實的問題。這時,學習者獲得了復雜認知技能。

4結(jié)論

經(jīng)過實踐檢驗,4C/ID能有效提高復雜認知技能。應用4C/ID于“算法設(shè)計與分析”課程,效果體現(xiàn)在兩方面:(1)解決問題的能力提高了。以前,答題是把算法從頭到尾背過來的,算法常有缺漏或搞亂算法語句順序。現(xiàn)在,答題內(nèi)容以實踐的經(jīng)驗體會居多,答對率提高了16%。(2)考證通過率提高了?！八惴ㄔO(shè)計與分析”是一門綜合性的課程,算法設(shè)計與分析能力的提高深化了學生對“程序設(shè)計語言”、“數(shù)據(jù)結(jié)構(gòu)”等課程的學習,考證通過率也增加了。4C/ID不盡人意之處在于要費很多時間去分析。所以,4C/ID一般和教學設(shè)計系統(tǒng)一起使用。

參考文獻:

[1] DONALD E.KNUTH. 計算機程序設(shè)計藝術(shù):基本算法[M]. 蘇運霖,譯.北京:國防工業(yè)出版社,2007.

[2] 教育部高等學校計算機科學與技術(shù)教學指導委員會. 高等學校計算機科學與技術(shù)專業(yè)實踐教學體系與規(guī)范[M]. 北京:清華大學出版社,2008.

[3] Anany Levitin. 算法設(shè)計與分析基礎(chǔ)[M]. 潘彥,譯. 北京:清華大學出版社,2007.

[4] Jeroen J.G.Van Merrienboer,Paul A. Kirschner.Ten Steps to Complex Learning:A Systematic Approach to Four-component Instructional Design[M]. New Jersey:LAWRENCE ERLBAUM ASSOCIATES,2007.

[5] 羅伯特D.坦尼森,弗蘭茲•肖特,諾伯特M.西爾,等. 教學設(shè)計的國際觀:理論•研究•模型[M]. 任友群,裴新寧,譯. 北京:教育科學出版社,2007.

Improve Complex Cognitive Skills on "Algorithms Design and Analysis" Course

LUO Yi-sheng

(Department of Technology Education, Guangdong Polytechnic Normal University, Guangzhou 510630,China)

計算機程序設(shè)計藝術(shù)范文第3篇

數(shù)學在人類文明的發(fā)展歷史中發(fā)揮著重要的作用，推動了重大的科學技術(shù)進步。尤其是到了二十世紀中葉以后，數(shù)學的理論研究與實際應用之間的時間差已大大縮短。當前，隨著計算機應用的普及，信息的數(shù)字化和信息通道的大規(guī)模聯(lián)網(wǎng)，依據(jù)數(shù)學所作的創(chuàng)造設(shè)想已經(jīng)達到可即時試驗、即時實施的地步。數(shù)學技術(shù)一直是一種應用最廣泛、最直接、最及時、最富創(chuàng)造力的實用技術(shù)。數(shù)學為計算機的發(fā)明和發(fā)展壯大提供了堅實的理論基礎(chǔ)。早在1936年，英國數(shù)學家圖靈(Turing)發(fā)表了對計算機具有奠基意義的論文《論可計算數(shù)及其在判定問題上的應用》，里面提出了計算的圖靈機模型，該模型即為現(xiàn)代計算機模型的原型。為紀念數(shù)學家圖靈，美國計算機學會于1966年設(shè)立了計算機界最負盛名的“圖靈”獎，以表彰那些對計算機事業(yè)做出重要貢獻的個人。數(shù)學是所有工科的基礎(chǔ)，其中離散數(shù)學已經(jīng)成為計算機科學發(fā)展的理論基礎(chǔ)。圖靈獎的獲得者中有不少是學數(shù)學或者數(shù)學家出身。1974年獲獎的DonaldE.Knuth被稱為現(xiàn)代計算機之父，之前在加州理工獲得數(shù)學博士學位，著有經(jīng)典著作《計算機程序設(shè)計藝術(shù)》4卷。RichardM.Karp于1985年獲獎，之前在哈佛大學獲應用數(shù)學博士學位。1986獲獎的RobertE.Tarjan在斯坦福大學同時獲得數(shù)學和計算機的博士學位，主要研究圖論、算法和數(shù)據(jù)結(jié)構(gòu)。當前計算機理論及應用的壯大和發(fā)展更是離不開近代數(shù)學的發(fā)展，將計算機與數(shù)學的發(fā)展分割開來既不合理也不現(xiàn)實，和所有學科一樣，計算機領(lǐng)域也有自己的問題，比如什么是可計算的，什么是實際可計算的，這些計算模型本質(zhì)上是數(shù)學的應用。離散結(jié)構(gòu)上的算法研究無疑是計算機科學中的重要領(lǐng)域，研究算法需有扎實的數(shù)學功底，就機器學習領(lǐng)域的研究而言，通常要對所處理的數(shù)據(jù)建立不同的數(shù)學模型如分類模型、回歸模型和排序模型。一般地，先針對這些問題建立特定的模型，然后采用有效的優(yōu)化算法來求解這些模型。應用數(shù)學如矩陣論、多元統(tǒng)計分析和最優(yōu)化理論可以為深入地研究機器學習領(lǐng)域提供理論基礎(chǔ)。在實際的工作中，會經(jīng)?？吹綌?shù)學基礎(chǔ)好、具有一定數(shù)學素養(yǎng)的人解決問題會游刃有余且后勁足，學習新事物和新東西會比較快，會表現(xiàn)出一定的創(chuàng)造性。但是當前大學的課程安排普遍存在對學生的數(shù)學學習的掌握程度不是很重視，導致學生對數(shù)學課的態(tài)度停留在學習時僅了解，一學完就全忘，到用時就迷惑的一知半解狀態(tài)。教師在教授專業(yè)課和專業(yè)基礎(chǔ)課的過程中，沒有引導學生深入地發(fā)掘理論背后的數(shù)學本質(zhì)，導致學生對計算機科學理論的理解只能停留在表面，憑機械性記憶而沒有徹底理解。鑒于上述數(shù)學在計算機的發(fā)明發(fā)展和實際工作中的重要作用，因此，在計算機教育的過程中，迫切地需要培養(yǎng)學生的數(shù)學素養(yǎng)以滿足現(xiàn)實工作和學習中解決實際問題的需要。

二、數(shù)學素養(yǎng)的培養(yǎng)

《算法設(shè)計與分析》是計算機專業(yè)的一門重要的專業(yè)課，有利于培養(yǎng)學生分析問題和解決問題的能力，為學生學習后續(xù)課程打下堅實的基礎(chǔ)。下面結(jié)合這門課程來談?wù)勗谟嬎銠C課程中如何提高學生的數(shù)學素養(yǎng)。

(一)結(jié)合算法的發(fā)明史來講解算法

深入學習計算機科學需要有良好的數(shù)學基礎(chǔ)，對于算法的學習更是如此。研究算法的圖靈獎獲得者中有很多是數(shù)學家或者學數(shù)學出身，如圖論中有很多算法是以前面提到的RobertE.Tarjan的名字命名的，著名的Dijkstra最短路徑算法由EdsgerW.Dijkstra發(fā)明，而他2000年退休前一直是美國Taxas大學的計算機科學和數(shù)學教授。前面提到的DonaldE.Knuth則是字符串匹配算法KMP算法的發(fā)明人。給學生講解算法的發(fā)明歷史一方面幫助學生了解發(fā)明算法的背景和發(fā)明過程，激發(fā)學生的創(chuàng)新欲望；另一方面讓學生認識到數(shù)學的重要性和其在該課程所涉及的領(lǐng)域中發(fā)揮的重要作用。

(二)結(jié)合學生所掌握的數(shù)學知識來講解算法

修讀該門課程的對象一般為大學高年級學生，他們之前應該修過其他的數(shù)學課程，如高等數(shù)學(數(shù)學分析)、線性代數(shù)和離散數(shù)學。通常教師在講授該課程的過程中會認識到離散數(shù)學在其中發(fā)揮的作用，會有意識地提及離散數(shù)學的知識，但實際上學生學習的高等數(shù)學或線性代數(shù)的知識對理解該門課程也是有幫助的。下面通過一個例子來說明數(shù)學知識對理解算法正確性的重要作用。設(shè)計完算法如何證明算法的正確性呢？對于順序結(jié)構(gòu)和選擇結(jié)構(gòu)比較好驗證，而對于循環(huán)結(jié)構(gòu)就使用循環(huán)不變量(LoopInvariant)來證明。而循環(huán)不變量的證明實際上借鑒了數(shù)學歸納法的思想：循環(huán)發(fā)生前某個循環(huán)不變量為真，循環(huán)進行的過程中保持為真，那么循環(huán)結(jié)束時，該循環(huán)不變量仍然為真。因此可以斷定：無論循環(huán)體循環(huán)多少次，該循環(huán)不變量總為真。其他的例子，包括：比較算法的時間復雜度時可以引入高等數(shù)學中的無窮小量來講解；計算時間復雜度也會涉及到利用無窮級數(shù)的估計等等。

(三)結(jié)合數(shù)學工具來可視化算法

理論的發(fā)明通常是從簡單直觀的例子中歸納得來的，數(shù)學工具可以幫助我們理解和可視化算法。

(四)結(jié)合數(shù)學抽象思維來幫助學生理解算法

數(shù)學的抽象思維可以幫助學生站在更高的角度來看待問題和算法之間的聯(lián)系。算法通常是針對某一類問題的，而如何對問題進行歸類，如何選擇合適的算法解決是值得學生去探究的問題。講解算法時，應該幫助學生抽象出問題的本質(zhì)，同時注意算法之間的聯(lián)系與區(qū)別。計算點對之間的距離是算法設(shè)計中一個經(jīng)典問題，如果源點單一，可采用Dijkstra最短路徑算法，而計算圖中任意點之間的最短路徑，使用Floyd-Warshall最短路徑算法會合適一些，但是如果圖上的權(quán)重存在負值，那就要用帶松弛操作的Bellman-Ford算法求解。了解了這些知識后，學生在把問題抽象成特定的算法模型時，就可以正確地使用合適的算法了。其他問題包括使用矩陣胚理論來證明貪心算法的正確性以及靈活應用動態(tài)規(guī)劃來求解離散結(jié)構(gòu)上的最優(yōu)化問題等等。