UC知道算法分析与设计题目
来源：百度知道 编辑：UC知道 时间：2024/05/11 16:36:15
大家好，现在要考试了，，分不多，请大家帮帮我
1、设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法。
第二题：算法理解：本大题2个小题，每小题12分，共24分。
1.写出用背包问题贪心算法解决下列实例的过程。
P=(10,6,3,2)
W=(15,12,8,3)
M=30
2.写出4皇后回溯算法的状态空间树。
第三题：简答题：
1.为什么要分析最坏情况下的算法时间复杂性？
2.简述贪心算法的基本思想
3.阐述归并排序的分治思路
4、4.写出0/1背包问题的递推式，并简述其表述的意义
1、设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法。
第二题：算法理解：本大题2个小题，每小题12分，共24分。
1.写出用背包问题贪心算法解决下列实例的过程。
P=(10,6,3,2)
W=(15,12,8,3)
M=30
2.写出4皇后回溯算法的状态空间树。
第三题：简答题：
1.为什么要分析最坏情况下的算法时间复杂性？
2.简述贪心算法的基本思想
3.阐述归并排序的分治思路
4、4.写出0/1背包问题的递推式，并简述其表述的意义
第一题用贪心思想 找出用时最短的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)