程序設(shè)計計算機科學(xué)與技術(shù)的核心

程序設(shè)計：計算機科學(xué)與技術(shù)的核心教學(xué)時間：2024年6月27日教學(xué)講師：XXX內(nèi)容程序設(shè)計課程算法+數(shù)據(jù)結(jié)構(gòu)=程序程序設(shè)計課程課程性質(zhì)科學(xué)？技術(shù)？工程？技術(shù)課程課程目的編寫程序解決問題教學(xué)方式課堂講授/理論學(xué)習實驗程序設(shè)計課程數(shù)據(jù)類型基本數(shù)據(jù)類型：整型、浮點型、字符型數(shù)組、指針、結(jié)構(gòu)、文件語言、結(jié)構(gòu)（嵌套）順序（賦值）選擇（if,ifelse,switch）循環(huán)（while,dowhile,for）程序設(shè)計課程“輸入—處理—輸出”的模式處理：現(xiàn)實世界中的對象的表示現(xiàn)實世界中的問題的解決程序設(shè)計課程試題1：FinancialManagement試題來源：ACMMid-Atlantic2001在線測試地址：POJ1004，ZOJ1048，UVA2362Larry今年畢業(yè)，找到了工作，并賺了很多錢。但不知為何，Larry總感覺錢不夠用。因此，Larry要用財務(wù)報表來解決他的財務(wù)問題：他要計算他能用多少錢?，F(xiàn)在可以通過Larry的銀行帳號看到他的財務(wù)狀況。請您幫Larry寫一個程序，根據(jù)過去12個月他每個月的收入，計算要達到收支平衡，每個月他平均能用多少錢。輸入輸入12行，每一行是一個月的收入，收入的數(shù)字是正數(shù)，精確到分，沒有美元的符號。輸出輸出一個數(shù)字，是這12個月收入的平均值。精確到分，前面加美元的符號，后面加行結(jié)束符。在輸出中沒有空格或其他字符。解析本題采用了非常簡單的“輸入—處理—輸出”模式：通過結(jié)構(gòu)為for(i=0;i<12;i++)的循環(huán)輸入12個月的收入a[0..11]；累計總收入sum，計算月平均收入avg；最后輸出avg。實數(shù)精度二分法離線技術(shù)實數(shù)精度在實數(shù)運算中，經(jīng)常需要判斷實數(shù)x和實數(shù)y是否相等，而編程者往往把判斷條件簡單設(shè)成y-x是否等于0。但這樣的做法可能會產(chǎn)生精度誤差。避免精度誤差的辦法是設(shè)一個精度常量delta。若y-x的實數(shù)值與0之間的區(qū)間長度小于delta，則認定x和y相等，這樣就可將誤差控制在delta范圍內(nèi)，如圖所示。二分法在有些情況下，問題的所有數(shù)據(jù)對象為一個有序區(qū)間。二分法將這個區(qū)間等分成兩個子區(qū)間，根據(jù)計算要求決定下一步計算是在左子區(qū)間還是在右子區(qū)間進行；然后再根據(jù)計算要求等分所在區(qū)間，直至找到解為止。顯然，對一個規(guī)模為O(n)的問題，如果采用盲目枚舉的辦法，則效率為O(n)；若采用二分法，則計算效率可提高至O(log2(n))。試題2：Hangover試題來源：ACMMid-CentralUSA2001在線測試地址：POJ1003，UVA2294您能使一疊在桌子上的卡片向桌子外伸出多遠？如果是一張卡片，這張卡片向桌子外伸出卡片的一半長度。（卡片以直角伸出桌子。）如果有兩張卡片，就讓上面一張卡片向外伸出下面那張卡片的一半長度，而下面的那張卡片向桌子外伸出卡片的三分之一長度，所以兩張卡片向桌子外延伸的總長度是1/2+1/3=5/6卡片長度。依次類推，n張卡片向桌子外延伸的總長度是1/2+1/3+1/4+...+1/(n+1)卡片長度：最上面的卡片向外延伸1/2，第二張卡片向外延伸1/3，第三張卡片向外延伸1/4，……，最下面一張卡片向桌子外延伸1/(n+1)，如圖所示。輸入輸入由一個或多個測試用例組成，最后一行用0.00表示輸入結(jié)束，每個測試用例一行，是一個3位數(shù)正浮點數(shù)c，最小值0.01，最大值5.20。輸出對每個測試數(shù)據(jù)c，輸出要伸出卡片長度c所最少要用的卡片的數(shù)目，輸出形式見樣例輸出。解析算法+數(shù)據(jù)結(jié)構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)計算機存儲、組織數(shù)據(jù)的方式。算法通過編程解決問題的方法。算法+數(shù)據(jù)結(jié)構(gòu)=程序評價一個人的專業(yè)能力，是看這個人的兩個方面：1）知識體系結(jié)構(gòu)，他能用哪些知識去解決問題，或者說，是他所真正掌握、并能應(yīng)用的知識，而不僅僅是他學(xué)過的知識；2）思維方式，在他面對問題，特別是不太標準化的問題的時候，他解決問題的策略是什么？算法+數(shù)據(jù)結(jié)構(gòu)=程序從程序設(shè)計的本質(zhì)上說，程序設(shè)計是技術(shù)。練習、練習、再練習；系統(tǒng)地練習；算法+數(shù)據(jù)結(jié)構(gòu)=程序程序設(shè)計的知識體系可以概括為“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這一公式，這也是計算機科學(xué)與技術(shù)的知識體系結(jié)構(gòu)的核心。所謂的系統(tǒng)地練習，就是在試題及其測試數(shù)據(jù)、解答程序以及解題分析的引導(dǎo)之下，通過解題，系統(tǒng)磨煉學(xué)生應(yīng)用算法和數(shù)據(jù)結(jié)構(gòu)各個知識點解決實際問題的能力，以有效地掌握程序設(shè)計的知識體系。算法+數(shù)據(jù)結(jié)構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)線性表：表格樹：層次關(guān)系、物以類聚人以群分的關(guān)系圖：對象以及對象之間的關(guān)聯(lián)算法+數(shù)據(jù)結(jié)構(gòu)=程序算法AdHoc模擬搜索貪心動態(tài)規(guī)劃數(shù)論組合數(shù)學(xué)計算幾何。。。。。。高精度運算程序設(shè)計語言所能表示和處理的整數(shù)和實數(shù)的精度通常是有限的，如：在雙精度方式下，計算機最多只能輸出16位有效的十進制數(shù)，17位有效數(shù)字的正確性為90%（Double類型數(shù)據(jù)）。如果超過了這個范圍，計算機就無法正確表示了。在這種情況下，只能通過編程來解決。對于高精度數(shù)，有兩個基本問題：高精度數(shù)的表示；高精度數(shù)的基本運算；高精度數(shù)的表示用一個數(shù)組來表示一個高精度數(shù)：將數(shù)字按十進制位進行分離，每位十進制數(shù)依次存儲到一個數(shù)組中。在具體的實現(xiàn)中，先采用字符串來接收數(shù)據(jù)，然后將字符串中的各位字符轉(zhuǎn)換為對應(yīng)的十進制數(shù)，并按十進制位的順序存儲到一個數(shù)組中。對于一個高精度正整數(shù)，接收與存儲的程序段如下：inta[100]={0};//數(shù)組a用來按位存放高精度正整數(shù)，初值全為0intn;//n用來存放高精度正整數(shù)的位數(shù) strings;//字符串s用來接收數(shù)據(jù) cin>>s;//輸入數(shù)串

n=s.length();//計算位長 for(i=0;i<n;i++)//數(shù)組a從右向左，按位存儲高精度正整數(shù)

a[i]=s[n-i-1]-'0';高精度數(shù)的基本運算高精度數(shù)的基本運算包括‘+’、‘-’、‘*’、‘/’。高精度數(shù)的加減運算高精度數(shù)最基本的運算是加和減。和算術(shù)的加減規(guī)則一樣，程序中高精度數(shù)的加運算要考慮進位處理，高精度數(shù)的減運算則要考慮借位處理。求兩個非負的高精度整數(shù)x和y相加的和。x和y按如上的形式存儲在數(shù)組a和數(shù)組b中，n1為x的位數(shù)，n2為y的位數(shù)，程序段如下：for(i=0;i<(n1>n2?n1:n2);i++){//進行max{n1,n2}位加法

a[i]=a[i]+b[i];//逐位相加

if(a[i]>9){//進位處理

a[i]=a[i]-10;

a[i+1]++; } }求兩個高精度正整數(shù)x和y（x>y）相減的差。x和y按如上的形式存儲在數(shù)組a和數(shù)組b中，n為x的位數(shù)。若(x<y)，則a和b對換，相減后的差取負。數(shù)組a和數(shù)組b相減的程序段如下：for(i=0;i<n;i++){ if(a[i]>=b[i])a[i]=a[i]-b[i];//若對應(yīng)位夠減，則直接相減，否則借位相減 else{a[i]=a[i]+10-b[i];

a[i+1]--; }}高精度數(shù)的乘除運算在高精度數(shù)的加減運算的基礎(chǔ)上，可以實現(xiàn)高精度數(shù)的乘運算和除運算。進行高精度數(shù)的乘法運算，首先要確定積的位數(shù)。設(shè)兩個高精度正整數(shù)a和b，LA為a的位數(shù)，LB為b的位數(shù)。a和b乘積的位數(shù)至少為LA+LB-1，若乘后的第LA+LB-1位有進位，則乘積位數(shù)為LA+LB。所以，高精度正整數(shù)a和b的乘積的位數(shù)上限為LA+LB。高精度數(shù)乘運算的算法思想和算術(shù)的乘法規(guī)則一樣：首先計算被乘數(shù)與乘數(shù)的每位數(shù)字的乘積，其中a[i]乘b[j]的積累加到數(shù)組c[i+j]上，然后對累加結(jié)果c作一次性進位。for(i=0;i<=LA-1;i++)//被乘數(shù)a與乘數(shù)b的每位數(shù)字的乘積累加到積數(shù)組c的對應(yīng)位上for(j=0;j<=LB-1;j++)

c[i+j]+=a[i]*b[j];

for(i=0;i<LA+LB;i++)//累加結(jié)果作一次性進位if(c[i]>=10)

{

c[i+1]+=c[i]/10;

c[i]%=10;

}試題3：AddingReversedNumbers試題來源：ACMCentralEurope1998在線測試地址：POJ1504，ZOJ2001，UVA713Malidinesia的古典喜劇演員（AntiqueComediansofMalidinesia，ACM）喜歡演喜劇，而不太喜歡演悲劇。但不幸的是，大多數(shù)古典戲劇是悲劇。所以ACM的戲劇導(dǎo)演決定將一些悲劇改編為喜劇。顯然，雖然所有的事物都改成了它們的反面，但因為必須保持劇本原有的意義，所以這項工作是很困難的。反向數(shù)是將一個阿拉伯數(shù)字按相反的次序?qū)憽０训谝粋€數(shù)字寫成最后一個數(shù)字，反之亦然。例如，在悲劇中主人公有1245只草莓，現(xiàn)在則有5421只草莓了。在本題中，數(shù)字的所有前導(dǎo)零要被省略。所以，如果數(shù)字結(jié)尾有零，寫反向數(shù)時零要被略去（例如，1200的反向數(shù)是21）。此外，在本題中，反向數(shù)沒有零結(jié)尾。ACM需要對反向數(shù)進行計算。請您將兩個反向數(shù)相加，并輸出它們的反向和。當然，結(jié)果不是唯一的，因為一個數(shù)可以是幾個數(shù)的反向形式（例如21在反向前可以是12,120或1200）。為此，本題設(shè)定沒有0因為反向而丟失（例如，設(shè)定原來的數(shù)是12）。輸入輸入由N個測試用例組成。輸入的第一行僅給出正整數(shù)N，然后給出若干測試用例。每個測試用例一行，由2個由空格分開的正整數(shù)組成。這是要相加的要被反向的數(shù)。輸出對每個測試用例，輸出一行，僅包含一個整數(shù)，將兩個反向數(shù)進行求和，之后再反向。在輸出時把前導(dǎo)0略去。解析數(shù)據(jù)結(jié)構(gòu)設(shè)Num[0][0]為被加數(shù)的長度，被加數(shù)按位存儲在Num[0][1..Num[0][0]]之中；Num[1][0]為加數(shù)的長度，加數(shù)按位存儲在Num[1][1..Num[1][0]]之中；Num[2][0]為和的長度，和按位存儲在Num[2][1..Num[2][0]]之中。算法首先，分別輸入被加數(shù)和加數(shù)的數(shù)串，在舍去了尾部的無用0后存入Num[0]和Num[1]，再將它們反向存儲。

然后，Num[0]和Num[1]相加，得出和數(shù)組Num[2]。最后反向輸出Num[2]，注意略去尾部的無用0。此處插入教材封面作者:吳永輝、王建德出版社:機械工業(yè)出版社副標題:大學(xué)程序設(shè)計課程與競賽訓(xùn)練教材出版年:2016-10頁數(shù):517定價:CNY79.00版次:2叢書:大學(xué)程序設(shè)計課程與競賽訓(xùn)練教材ISBN:9787111550556數(shù)據(jù)結(jié)構(gòu)編程實驗此處插入教材封面書名：提升程式設(shè)計的資料結(jié)構(gòu)力：國際程式設(shè)計競賽之資料結(jié)構(gòu)原理、題型、解題技巧與