解析演算法設計

『壹』 學習演算法分析與設計需要那些基礎(是否需要學習離散數學和線性代數)

演算法分析與設計，目前國內本科生和碩士生的教材好像都是從國外翻譯過來的。聽起來挺復雜的樣子，如果簡單地掌握和運用還是不難的，大部分內容在數據結構中都涉及過，實際編程中也運用比較多，難的在於演算法的理論研究，如21世紀的七大難題之一的NP問題就是演算法問題（涉及邏輯可滿足性問題）。

簡單地講需要的基礎有以下幾類：
1、基礎類（相對一般本科生而言）：（1）把數據結構學好了演算法就不難的，而數據結構其實就是圖論的運用，如果是非數學專業的學生可以看離散數學中的圖論部分。（2）演算法分析設計時間和空間復雜度的計算，常用的還是毛澤東的戰略思想——以空間換取時間。所以要學會簡單的數量級運算，涉及部分代數式和數論的知識。只要簡單掌握運算就可以了，不必深究。
2、提高型（研究生水平）：圖論、組合數學、數理邏輯學要專門學習，可以採用數學系本科生的圖論、組合數學、數理邏輯學等專業課的教材。其中組合數學中的組合設計在一定程度上和演算法設計有異曲同工之處。
3、研究型（專業研究）：這主要看自己的研究方向了，如果研究能力強的話可以在很短時間內可以把需要遇到的數學知識搞懂，沒有現成的固定模式。其中如研究NP問題，需要非常精深的邏輯學知識和數論基礎。但不管哪個研究方向，數學的縝密思維和推理能力都是必備的，這不是一朝一夕可以練就的，需要長時間的鍛煉。

以上僅個人一點點體會，僅供參考。

『貳』 演算法分析與設計題目

第一題用貪心思想 找出用時最短的m個作業交給機器同時開始加工 然後再依次將剩下的作業中最短完成作業取出放入已完成的機器加工 當最後一台機器完工時間就是所用最短時間 思路是這樣子 具體演算法實現的話。。由於我也是學生=、=寫代碼還不是很熟練。。可能等我寫好了你考試來不及。。。你還是自己來吧

第二題
1.背包問題是什麼=、=我們教材不一樣 不了解具體問題。。
2.4皇後
#include<iostream.h>
const int n = 4 ;
const int n_sub = n - 1 ;
int queen[n] ;
bool row[n] ;
bool passive[2*n-1];
bool negative[2*n-1];
int main()
{
int cur = 0 ;
bool flag = false ;
queen[0] = -1 ;
int count = 0 ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag)
{
queen[cur]++ ;
if(queen[cur] >= n)
{
queen[cur] = -1 ;
cur-- ;
if(cur>=0)
{
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
false ;
}
else
{
if(row[queen[cur]] == false)
{
flag = true ;
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
}
else
flag = true ;
if(flag) {
if(cur == n-1)
{
count++ ;
}
row[queen[cur]] = true ;
passive[queen[cur] + cur] = true ;
negative[n_sub + cur - queen[cur]] = true ;
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
flag = false ;
}
}
}
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
這個是代碼。。。狀態空間樹這里畫不出來。。。

第三題
你網路下基本都有的=、=。。。我網路出來不好意思貼了你自己去看下吧
比如1.的答案：
最壞情況給出了演算法執行時間的上界，我們可以確信，無論給什麼輸入，演算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。

『叄』 演算法設計與分析：3階魔方陣

1、累加和=所有數字和/行數=（1+n2)*n2/2n=n(n2+1)/2

2、這叫幻方

3、奇數階幻方有構造方法：

從1開始，往右斜上順次填寫。

特殊情況：如果數字出了幻方，將該數填至行或列的另一端。

特殊情況2：如果要填寫的格子被佔了，數填在格子下方一格。

特殊情況3：我忘了。