解析算法设计

‘壹’ 学习算法分析与设计需要那些基础(是否需要学习离散数学和线性代数)

算法分析与设计，目前国内本科生和硕士生的教材好像都是从国外翻译过来的。听起来挺复杂的样子，如果简单地掌握和运用还是不难的，大部分内容在数据结构中都涉及过，实际编程中也运用比较多，难的在于算法的理论研究，如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：我忘了。