導航:首頁 > 源碼編譯 > 大學計算機第七版演算法設計枚舉法

大學計算機第七版演算法設計枚舉法

發布時間:2023-02-04 09:21:51

⑴ 大一計算機專業應該掌握的演算法有哪些

大一的話不用掌握太專一的演算法,主要是真正理解程序設計的3中流程,知道數組能幹哪些事情,嘗試理解函數遞歸,理解RAM機模型。掌握以下基本演算法:
篩選法、試除法求素數,漢諾塔,放蘋果,簡單枚舉法,N皇後問題等簡單回溯法,簡單模擬法,高精度演算法(+-*/),GCD演算法,二分法、牛頓發求根,選擇、冒泡排序等基本演算法。
一開始,學會用程序表達自己的演算法思想是最基本的基本功。
年級高了以後,等你學了離散數學。數據結構,演算法設計與分析以後,就能設計些較復雜的演算法了。

推薦幾本書:
演算法導論,英文叫Introction to Algorithms,2nd Edition,這個很經典
計算機程序設計藝術,這個也是經典著作,最好看看
數據結構與演算法分析
如果你們學校有ACM校隊的話最好和他們交流交流。

⑵ 枚舉法是什麼

在進行歸納推理時,如果逐個考察了某類事件的所有可能情況,因而得出一般結論,那麼這結論是可靠的,這種歸納方法叫做枚舉法. 一、特點:將問題的所有可能的答案一一列舉,然後根據條件判斷此答案是否合適,合適就保留,不合適就丟棄。例如: 找出1到100之間的素數。需要將1到100之間的所有整數進行判斷。 枚舉演算法因為要列舉問題的所有可能的答案,所有它具備以下幾個特點: 1、得到的結果肯定是正確的; 2、可能做了很多的無用功,浪費了寶貴的時間,效率低下。 3、通常會涉及到求極值(如最大,最小,最重等)。 二、枚舉演算法的一般結構:while循環。 首先考慮一個問題:將1到100之間的所有整數轉換為二進制數表示。 演算法一: for i:=1 to 100 do begin 將i轉換為二進制,採用不斷除以2,余數即為轉換為2進制以後的結果。一直除商為0為止。 end; 演算法二:二進制加法,此時需要數組來幫忙。 program p; var a:array[1..100] of integer; {用於保存轉換後的二進制結果} i,j,k:integer; begin fillchar(a,sizeof(a),0); {100個數組元素全部初始化為0} for i:=1 to 100 do begin k:=100; while a[k]=1 do dec(k); {找高位第一個為0的位置} a[k]:=1; {找到了立刻賦值為1} for j:=k+1 to 100 do a[j]:=0; {它後面的低位全部賦值為0} k:=1; while a[k]=0 do inc(k); {從最高位開始找不為0的位置} write('(',i,')2='); for j:=k to 100 do write(a[j]); {輸出轉換以後的結果} writeln; end; end. 枚舉法,常常稱之為窮舉法,是指從可能的集合中一一枚舉各個元素,用題目給定的約束條件判定哪些是無用的,哪些是有用的。能使命題成立者,即為問題的解。 採用枚舉演算法解題的基本思路: (1) 確定枚舉對象、枚舉范圍和判定條件; (2) 一一枚舉可能的解,驗證是否是問題的解 下面我們就從枚舉演算法的的優化、枚舉對象的選擇以及判定條件的確定,這三個方面來探討如何用枚舉法解題。 例1:百錢買百雞問題:有一個人有一百塊錢,打算買一百隻雞。到市場一看,大雞三塊錢一隻,小雞一塊錢三隻,不大不小的雞兩塊錢一隻。現在,請你編一程序,幫他計劃一下,怎麼樣買法,才能剛好用一百塊錢買一百隻雞? 演算法分析:此題很顯然是用枚舉法,我們以三種雞的個數為枚舉對象(分別設為x,y,z),以三種雞的總數(x+y+z)和買雞用去的錢的總數(x*3+y*2+z)為判定條件,窮舉各種雞的個數。 下面是解這個百雞問題的程序 var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do{枚舉所有可能的解} if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); {驗證可能的解,並輸出符合題目要求的解} end. 上面的條件還有優化的空間,三種雞的和是固定的,我們只要枚舉二種雞(x,y),第三種雞就可以根據約束條件求得(z=100-x-y),這樣就縮小了枚舉范圍,請看下面的程序: var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y; if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); end; end. 未經優化的程序循環了1013 次,時間復雜度為O(n3);優化後的程序只循環了(102*101/2)次 ,時間復雜度為O(n2)。從上面的對比可以看出,對於枚舉演算法,加強約束條件,縮小枚舉的范圍,是程序優化的主要考慮方向。 在枚舉演算法中,枚舉對象的選擇也是非常重要的,它直接影響著演算法的時間復雜度,選擇適當的枚舉對象可以獲得更高的效率。如下例: 例2、將1,2...9共9個數分成三組,分別組成三個三位數,且使這三個三位數構成1:2:3的比例,試求出所有滿足條件的三個三位數. 例如:三個三位數192,384,576滿足以上條件.(NOIP1998pj) 演算法分析:這是1998年全國分區聯賽普及組試題(簡稱NOIP1998pj,以下同)。此題數據規模不大,可以進行枚舉,如果我們不加思地以每一個數位為枚舉對象,一位一位地去枚舉: for a:=1 to 9 do for b:=1 to 9 do ……… for i:=1 to 9 do 這樣下去,枚舉次數就有99次,如果我們分別設三個數為x,2x,3x,以x為枚舉對象,窮舉的范圍就減少為93,在細節上再進一步優化,枚舉范圍就更少了。程序如下: var t,x:integer; s,st:string; c:char; begin for x:=123 to 321 do{枚舉所有可能的解} begin t:=0; str(x,st);{把整數x轉化為字元串,存放在st中} str(x*2,s); st:=st+s; str(x*3,s); st:=st+s; for c:='1' to '9' do{枚舉9個字元,判斷是否都在st中} if pos(c,st)<>0 then inc(t) else break;{如果不在st中,則退出循環} if t=9 then writeln(x,' ',x*2,' ',x*3); end; end. 在枚舉法解題中,判定條件的確定也是很重要的,如果約束條件不對或者不全面,就窮舉不出正確的結果, 我們再看看下面的例子。 例3 一元三次方程求解(noip2001tg) 問題描述 有形如:ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(a,b,c,d 均為實數),並約定該方程存在三個不同實根(根的范圍在-100至100之間),且根與根之差的絕對值>=1。 要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格),並精確到小數點後2位。 提示:記方程f(x)=0,若存在2個數x1和x2,且x1<x2,f(x1)*(x2)<0,則在(x1,x2)之間一定有一個根。 樣例 輸入:1 -5 -4 20 輸出:-2.00 2.00 5.00 演算法分析:由題目的提示很符合二分法求解的原理,所以此題可以用二分法。用二分法解題相對於枚舉法來說很要復雜很多。此題是否能用枚舉法求解呢?再分析一下題目,根的范圍在-100到100之間,結果只要保留兩位小數,我們不妨將根的值域擴大100倍(-10000<=x<=10000),再以根為枚舉對象,枚舉范圍是-10000到10000,用原方程式進行一一驗證,找出方程的解。 有的同學在比賽中是這樣做 var k:integer; a,b,c,d,x :real; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' '); end; end. 用這種方法,很快就可以把程序編出來,再將樣例數據代入測試也是對的,等成績下來才發現這題沒有全對,只得了一半的分。 這種解法為什麼是錯的呢?錯在哪裡?前面的分析好象也沒錯啊,難道這題不能用枚舉法做嗎? 看到這里大家可能有點迷惑了。 在上面的解法中,枚舉范圍和枚舉對象都沒有錯,而是在驗證枚舉結果時,判定條件用錯了。因為要保留二位小數,所以求出來的解不一定是方程的精確根,再代入ax3+bx2+cx+d中,所得的結果也就不一定等於0,因此用原方程ax3+bx2+cx+d=0作為判斷條件是不準確的。 我們換一個角度來思考問題,設f(x)=ax3+bx2+cx+d,若x為方程的根,則根據提示可知,必有f(x-0.005)*(x+0.005)<0,如果我們以此為枚舉判定條件,問題就逆刃而解。另外,如果f(x-0.005)=0,哪么就說明x-0.005是方程的根,這時根據四舍5入,方程的根也為x。所以我們用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作為判定條件。為了程序設計的方便,我們設計一個函數f(x)計算ax3+bx2+cx+d的值,程序如下: {$N+} var k:integer; a,b,c,d,x:extended; function f(x:extended):extended; {計算ax3+bx2+cx+d的值} begin f:=((a*x+b)*x+c)*x+d; end; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若x兩端的函數值異號或x-0.005剛好是方程的根,則確定x為方程的根} end; end. 用枚舉法解題的最大的缺點是運算量比較大,解題效率不高,如果枚舉范圍太大(一般以不超過兩百萬次為限),在時間上就難以承受。但枚舉演算法的思路簡單,程序編寫和調試方便,比賽時也容易想到,在競賽中,時間是有限的,我們競賽的最終目標就是求出問題解,因此,如果題目的規模不是很大,在規定的時間與空間限制內能夠求出解,那麼我們最好是採用枚舉法,而不需太在意是否還有更快的演算法,這樣可以使你有更多的時間去解答其他難題

⑶ pascal基礎知識

一、演算法的基礎知識
1.用計算機解決問題的步驟:
① 分析問題
② 演算法設計
③ 描述演算法
編程實現
從上面的求解問題過程可以看出,關鍵在於前三步的解決:第一步就是解決模型的數據結構,第二步是解決問題的演算法,第三步是形式化地描寫演算法。
2.演算法的定義:
演算法是一組有窮的規則,它們規定了解決某一特定類型問題的一系列運算。演算法可以理解為:程序(數據處理)+ 數據結構(數據組織)。
3.演算法的性質:
① 有限性
② 確定性
③ 輸入輸出(可以沒有輸入,但一定有輸出)
④ 可行性
常見的演算法有:窮舉法、迭代法、遞推法、遞歸法、回溯法、深度及廣度搜索法、動態規劃、構造法等等。
2.N-S圖:
1973年,美國學者I.Nassi和B.Shneiderman提出了一種用圖形表示演算法的方法,稱為N-S流程圖。N-S圖包括順序、選擇和循環三種基本結構。
3.程序設計語言:
計算機中的語言分為低級語言和高級語言,而低級語言又分為機器語言和匯編語言。
機器語言是一種CPU的指令系統,它是CPU可以識別的一系列有0和1這種二進制代碼組成的指令。它依賴於機器,不同類型的計算機有不同的機器語言,機器語言的程序有許多機器指令組成,每條指令由操作碼和地址碼組成,數據和指令都放在不同的地址單元中。
匯編語言它是一種符號語言,為了克服機器語言固有的缺陷,20世紀50年代中期出現,將難以記憶和辨別的機器語言操作碼用有意義的英文單詞作為「助記符」來代替0、1進行編程。
高級語言,不再面向機器,而是接近人類的自然語言。常見的還有C/C++,Pascal,Basic,Java等。
數據類型、常量、變數及說明方法
數據類型確定了該類型數據項的表示、取值范圍以及所能參與的運算。在pascal語言中,無論常量還是變數都必須屬於一個確定的數據類型。
Pascal 提供了豐富的數據類型,可以分為三大類:
① 簡單類型:分為標准類型(整型、實型、字元型和布爾型)和自定義類型(枚舉型和子界型)
② 構造類型:分為數組類型、集合類型、記錄類型和文件類型
③ 指針類型
這些數據類型中除了指針類型是動態數據類型外,其他的都是靜態數據類型。另外,我們把整型、字元型、布爾型、枚舉型和子界型稱為順序類型。

另:數據結構
-棧 隊列
– 並查集
– 堆
– 字母樹 線段樹 平衡樹 動態樹
– 塊狀鏈表
– 後綴數組
– ……


– 先進後出
* 隊列
– 先進先出
* 常見的應用有哪些?
– 表達式求值
– 搜索
* 深搜
* 廣搜
– 優化

* 集合用代表元表示
– representative?Getfather(x)
* 初始的時候,所有元素各自成為一個集合
– for i?1 to N
* father[i]?i
* 判斷是否在同一集合
– 代表元是否相同
* return Getfather(x)=Getfather(y)
* 合並兩個集合
– 將其中一集合的代表元指向另一集合代表元
* father[Getfather(x)]?y

並查集
* 如何尋找代表元?
– Getfather(x)
* if father[x]=x
– return x
* return Getfather(father[x])
* 如何優化?
– 路徑壓縮
* Getfather(x)
– if father[x]=x
>>return x
– father[x]?Getfather(father[x])
– return father[x]

* 用途
– 用於尋找最值
* 大根堆、小根堆
* 小根堆性質
– 是一棵完全二叉樹
* i的父親是誰?
– idiv 2
* i的左右兒子是誰?
– 2i和2i+1
– 樹上的每棵子樹,兒子的值不小於根
堆排序
– 建堆
– 取出根
– 刪除根
– 反復取、刪的過程
時間效率
– O(Nlog N)
塊狀數組
* 增加一下題目內容
– 詢問區間最大值
– 詢問區間和
– 詢問區間內的和最大連續串
– 可以修改一個數
– 可以將一串連續的數變為一個值
– 可以將一串連續的數旋轉一下
* 塊狀數組?塊狀鏈表
– 可以將一串連續的數翻轉一下

可能有些難

⑷ 可以用什麼分支來實現枚舉法檢驗條件

枚舉演算法的結構特點 ①枚舉法的關鍵就是列舉和檢驗這兩個操作,如圖 3—1 所示。 圖3-1 列舉和檢驗 ②為了保證對所有可能的情況
2. 枚舉演算法的一般設計步驟 ①確定列舉的范圍:確定列舉的對象的范圍,不能隨意擴大和縮小列舉范圍,否則可能會造成多解 或漏解後果。 ②明確檢驗的條件
3. 枚舉法的優缺點 枚舉法充分利用了計算機快速高效的特點,讓計算機進行重復運算,以求得問題的解。由於枚舉法 是將所有可能的解無一例外地進行檢驗,
網路文庫

⑸ 求最大公因數的三種方法

、使用分解質因數法:把幾個數分解成幾個質因數的積,然後找相同的質因數,再把這幾個質因數相乘,積就是他們的最大公因數。
2、使用短除法:用短除法對要求公因數的數組一直往下除,除到不能再被整除為止,這樣在短除法運算過程中產生的除數就是要求的公因數了,其中最大的就是最大公因數。

⑹ 演算法設計(枚舉法和迭代法)

枚舉法:
求解百錢買百雞問題:我國古代數學家張丘建在《算經》一書中提出的數學問題:雞翁一值錢五,雞母一值錢三,雞雛三值錢一。百錢買百雞,問雞翁、雞母、雞雛各幾何?
迭代法:
不使用數組,輸入一個50以內的正整數,求解菲波那契數列的前n項。最前2項為1,1。

⑺ 數學里的枚舉法是什麼意思

在進行歸納推理時,如果逐個考察了某類事件的所有可能情況,因而得出一般結論,那麼這結論是可靠的,這種歸納方法叫做枚舉法。

枚舉法是利用計算機運算速度快、精確度高的特點,對要解決問題的所有可能情況,一個不漏地進行檢驗,從中找出符合要求的答案,因此枚舉法是通過犧牲時間來換取答案的全面性。

在數學和計算機科學理論中,一個集的枚舉是列出某些有窮序列集的所有成員的程序,或者是一種特定類型對象的計數。這兩種類型經常(但不總是)重疊。

(7)大學計算機第七版演算法設計枚舉法擴展閱讀:

枚舉法的時間復雜度可以用狀態總數*考察單個狀態的耗時來表示,因此優化主要是:

1、減少狀態總數(即減少枚舉變數和枚舉變數的值域);

2、降低單個狀態的考察代價。

優化過程從幾個方面考慮。具體講

1、提取有效信息;

2、減少重復計算;

3、將原問題化為更小的問題;

4、根據問題的性質進行截枝;

5、引進其他演算法。

閱讀全文

與大學計算機第七版演算法設計枚舉法相關的資料

熱點內容
歐拉app怎麼下訂單 瀏覽:422
肉文有聲小說 瀏覽:955
求個看片的網址 瀏覽:547
pythonsin函數圖像 瀏覽:329
身體不好當程序員 瀏覽:274
mount命令作用 瀏覽:220
畫江湖之不良人黑白無常雙修刪減 瀏覽:754
朵唯手機如何加密 瀏覽:504
安卓雙清指的什麼 瀏覽:179
phpredis所有keys 瀏覽:988
朋友賣房要解壓嗎 瀏覽:108
sar命令安裝 瀏覽:169
安卓怎麼看我自己去過哪裡 瀏覽:283
演算法分析里log沒有底數嗎 瀏覽:222
伺服器卡頓怎麼連接 瀏覽:957
手機拍照文件夾自動生成 瀏覽:788
瀏覽器如何運行在伺服器端 瀏覽:790
collinux 瀏覽:449
日本歐美韓國推理片電影大分享 瀏覽:615
怎麼下載香港app游戲 瀏覽:217