算法课程设计

吉林财经大学课程设计报告

课程名称：算法课程设计

设计题目：插棒游戏

所在院系：管理科学与信息工程学院计算机科学与技术

指导教师：

职称：副教授

提交时间： 2017年4月

目录

一、题目描述与设计要求 (1)

1 题目描述与设计要求 (1)

二、问题分析 (1)

1 解空间 (1)

2 解空间结构 (2)

3 剪枝 (2)

4 回溯法的基本思想 (2)

5 回溯法的适用条件 (3)

6 回溯法的空间树 (4)

7 回溯法的基本步骤 (4)

三、算法设计 (5)

1 伪代码 (5)

四、复杂性分析 (6)

1 时间复杂度 (6)

2 空间复杂度该 (6)

五、样本测试、分析与总结 (6)

1 样本测试 (6)

2 分析 (7)

2.1、数据类型 (7)

2.2 主要函数思路 (7)

2.3 回溯 (8)

3 总结 (8)

参考文献 (9)

附录 (10)

一、题目描述与设计要求

1 题目描述与设计要求

这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本：

a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。

b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。

图1

二、问题分析

1 解空间

由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。

例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。

图2

同构的状态要么都无解，要么有相同数量的解，且他们的解可以根据同构对应变化得到。

本题所描述的问题可能无解，也可能有多个解，且同构状态的解也有一定关联。

2 解空间结构

分析整个游戏的过程，发现每合法地走出一步，棋盘上就会少一个棋子,故当该问题有解时，最后都需要走13步。如果无解，必然小于或等于13步。因此，我们的状态树的深度将达到13层，每一个点的分支数量不确定。

3 剪枝

考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。

4 回溯法的基本思想

回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重

复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案，在尝试了所有可能的分步方法后宣告该问题没有答案。

回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

5 回溯法的适用条件

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，x n）组成的一个状态空间E={（x1，x2，…，x n）∣x i∈S i，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中S i是分量x i的定义域，且 |S i| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，x i）满足D中仅涉及到x1，x2，…，x i的所有约束意味着j（j<=i）元组（x1，x2，…，x j）一定也满足D中仅涉及到x1，x2，…，x j的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，x j）违反D中仅涉及到x1，x2，…，x j的约束之一，则以（x1，x2，…，x j）为前缀的任何n 元组（x1，x2，…，x j，x j+1，…，x n）一定也违反D中仅涉及到x1，x2，…，x i 的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，x j）违反D中仅涉及x1，x2，…，x j的一个约束，就可以肯定，以（x1，x2，…，x j）为前缀的任何n元组（x1，x2，…，x j，x j+1，…，

x n）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

6 回溯法的空间树

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：

设S i中的元素可排成x i(1) ，x i(2) ，…，x i(m i-1) ，|S i| =m i，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有m i个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权x i+1(1) ，x i+1(2) ，…，x i+1(m i) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x1，x2，…，x n）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，x n，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，x n）的一个前缀I元组（x1，x2，…，x i）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，x i，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，x n满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，x i），…，直到i=n为止。

在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P 的一个回答状态结点，它对应于问题P的一个解

7 回溯法的基本步骤

回溯法解决问题，一般有三个步骤：

（1）针对所给问题，定义问题的解空间；

（2）（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

三、算法设计

1 伪代码

ALGORITHM Get_all_moves(i,j)

//Get_avail_peg then updates the variables move and move_set

//Input :Two nonnegative,integer i and j

//Output:Update the peg-board

For i?0 to max_peg_hole do

If pegboard[i]?-1

For j?0 to num_of_rules do

move_set[move].move_what?peg_move_rules[j].move_what;

move_set[move].del_what?peg_move_rules[j].del_what;

move_set[move].move_where?peg_move_rules[j].move_where;

move++

ALGORITHM Reset_pegboard(i)

//Resets the pegboard to the original problem

//Input :integer

//Output:original pegboard

For i?0 to max_peg_hole do

Swap pegboard[i] and orig_pegboard[i]

ALGORITHM Is_solve(i)

//Judge problem is solved or not

//Input :integer i

//Output: 0 or 1

For i?0 to max_peg_hole do

If pegboard[i]=1

Count++

If count=1

Return 1

Return 0

四、复杂性分析

1 时间复杂度

该算法在最好情况下，求得第一种解需要试探13次。因为每次的走法数目不确定，也就是状态数的子孩子数量不确定，状态总数量不确定。但是该数目不大于 215-2种。无解时，就是这种情况。

对于要求所有的解时，需要遍历整个状态树。

2 空间复杂度该

算法需要维护一个状态栈和一个走法栈。走法栈的深度不超过13，为常数。状态空间树只记录当前路径有关的状态。假设树的平均子树数目为N，则该堆栈的大小约为1/N。

五、样本测试、分析与总结

1 样本测试

2 分析

2.1、数据类型

棋盘。正三角形的棋盘用数组很难表示。自定义最多有六个子节点的Node 类，用双向多维链表构成图，表示棋盘。但是这样不适合随机读写，切在判断同构上没有太大优势，因此采用变形的数组表示棋盘。把正三角形的棋盘上的孔左对齐，用5*5的数组的左下半部分表示。此时，棋棒可以左右跳、上下跳、沿着从左上到右下的对角线方向跳。

状态空间。把每一步的移动信息（从哪个坐标到哪个坐标）记录下来，构成隐式多叉树。因为用的是回溯法，故只需维护一个棋盘对象，根据走棋信息就可以得到上下的棋盘状态。

堆栈。维护一个堆栈，把每一个带探测的状态点放入，方便回溯。

链表。考虑到多解的可能性，用一个链表记录结果集。每个节点是一个解的全部移动棒子流程。

2.2 主要函数思路

判断同构。先判断最内部三个点空点数量，若一致再继续判断，否则肯定不是同构。合理选择关键点，可以避免多次遍历数列。

剪枝。判断是否剪掉该分支的依据是该状态是否与无解状态集合中的某个元素同构。其本质是查找，按照含有棋子数量、中心三角形元素个数、外顶点状态等信息可以对无解状态集合构建二叉书，查找时效率就会高狠多。

2.3 回溯

把初始状态放入堆栈。

把堆栈最顶上元素取出，判断棋盘状态，若：棋盘只剩一个元素。把全部堆栈信息复制，作为一个解记录到解集中。棋盘剩多个元素还有孩子节点。把该节点的所有不与空解状态集合中同构的下一状态的走法记录到堆栈中。没有孩子节点。把这时的棋盘复制，放到空解状态集合中若堆栈不为空，重复b。根据问题A、B筛选解集，并打印。

3 总结

回溯算法主要是通过深度试探查询的方法，找到解空间，并对不满足条件和不是最优组合的方法进行剪枝，从而得到最优解的方法。

通过这次运用回溯算法的课程设计，使我们对回溯算法原理和特点有了更深的理解和掌握。并且通过这次合作形式的作业，我们更加懂得了分工合作的意义，增强了自己的协作能力和团队合作的意识。

参考文献

[1]. 侯焯明.面向教育云平台的智能排课系统的设计与实现[D]中山大学出版社.2015

[2]. 刘彦.基于优先级与回溯算法的排课系统的设计与实现[D]黑龙江大学出版社.2012

[3]. (美) Anany Levitin .算法设计与分析基础（第三版影印版）清华大学出版社.2013

附录

//pegsolve.cpp

#include

#include

#include

#include

#include

using namespace std;

const int MAX_PEG_HOLE=15;

const int NUM_OF_RULES=36;

const int MOVES=0;

const int DATA_OFFSET=1;

const int INV ALID_PEG=-1;

//pegboard to play on

static int pegboard[15];

//default pegboard

//(1 means there is a peg; 0 means there is no peg) static int orig_pegboard[15] =

{

1,

1 , 1,

1 , 1 , 1,

1 , 1 , 1 , 1,

1 , 1 , 1 , 1 , 1

};

#define V ALID_HOLE(x) (x>=0 && x<=14) /*

* Layout of the pegboard:

*

* 00,

* 01, 02

* 03, 04, 05,

* 06, 07, 08, 09,

* 10, 11, 12, 13, 14

*

*/

static int move;

//data structure representing a move

struct _move_set

{

int move_what;

int del_what;

int move_where;

};

typedef _move_set MOVE_SET;

static MOVE_SET move_set[MAX_PEG_HOLE];

static MOVE_SET peg_move_rules[NUM_OF_RULES]= {

/* move_what OVER del_what TO move_where

* == {,,} */

{0,1,3}, {0,2,5},

{1,4,8}, {1,3,6},

{2,4,7}, {2,5,9},

{3,1,0}, {3,4,5}, {3,7,12}, {3,6,10},

{4,8,13}, {4,7,11},

{5,9,14}, {5,2,0}, {5,4,3}, {5,8,12},

{6,3,1}, {6,7,8},

{7,4,2}, {7,8,9},

{8,4,1}, {8,7,6},

{9,5,2}, {9,8,7},

{10,6,3}, {10,11,12},

{11,7,4}, {11,12,13},

{12,7,3}, {12,8,5}, {12,11,10}, {12,13,14},

{13,8,4}, {13,12,11},

{14,9,5}, {14,13,12}

};

/*======================

reset_pegboard() resets

the pegboard to the

original problem.

======================*/

void reset_pegboard( )

{

int i;

for( i = 0; i < MAX_PEG_HOLE; i++ )

pegboard[i] = orig_pegboard[i];

}//end of reset_pegboard

/*=======================

is_solved() returns TRUE

if pegboard is solved.

=======================*/

unsigned char is_solved( )

{

int i;

int count = 0; //count how many pegs there are

for( i = 0; i < MAX_PEG_HOLE; i++ )

if ( pegboard[i] ) count++ ;

if ( count == 1 ) return 1; //pegboard solved!

return 0;

}//end of is_solved

/*======================

display_pegboard displays

the current status

of the pegboard.

=======================*/

void display_pegboard( )

{

printf( "\n" );

printf( " %d\n" , pegboard[0] );

printf( " %d %d\n" , pegboard[1] , pegboard[2] );

printf( " %d %d %d\n" , pegboard[3] , pegboard[4] , pegboard[5] );

printf( " %d %d %d %d\n" , pegboard[6] , pegboard[7] , pegboard[8] , pegboard[9] ); printf( "%d %d %d %d %d\n",

pegboard[10] , pegboard[11] , pegboard[12] , pegboard[13] , pegboard[14] );

printf( "\n" );

}//end of display_pegboard

/*===========================

get_avail_peg updates

the variables move and

move_set

===========================*/

void get_all_moves( )

{

int i , j; //loop counters

move = 0; //initialize # of moves

move_set[move].move_what = -1;

move_set[move].del_what = -1;

move_set[move].move_where = -1;

for( i = 0; i < MAX_PEG_HOLE; i++ ) //check all holes

{

if ( !pegboard[i] ) //if there is a hole

{

for( j = 0; j < NUM_OF_RULES; j++)

{

if ((i==peg_move_rules[j].move_where) &&

(pegboard[peg_move_rules[j].del_what]))

{

/* can we move a peg to this hole? */

if (pegboard[peg_move_rules[j].move_what])

{

move_set[move].move_what=peg_move_rules[j].move_what; move_set[move].del_what=peg_move_rules[j].del_what; move_set[move].move_where=peg_move_rules[j].move_where; move++; //increment move count

} //end of if

} //end of if

}//end of for

}//end of if

}//end of for

}//end of get_avail_peg

/*======================

movepeg() does the

actual moving of a peg.

======================*/

void movepeg( int move_what , int del_what , int move_where ) {

pegboard[move_what] = 0;

pegboard[del_what] = 0;

pegboard[move_where] = 1;

}//end of movepeg

/*======================

usage() displays

how this app can

be invoked.

======================*/

void usage()

{

printf("The Pegboard Solver\n");

printf("Usage:\n");

printf("\tpegsolve \n");

printf("where,\n");

printf("\t\tis the empty hole on the pegboard.\n");

printf("\t\tHole# is between 1 and 15, inclusive.\n");

printf("\nLayout of the pegboard:\n");

printf(" 01,\n");

printf(" 02, 03\n");

printf(" 04, 05, 06,\n");

printf(" 07, 08, 09, 10,\n");

printf("11, 12, 13, 14, 15\n");

}//end of usage()

/*======================

main starts here

======================*/

int main( )

{

int argc;

int hole_num; // initial hole number

time_t t; // seed value for the random generator unsigned long l = 0; // attempt number to solve problem

int trace = 0; // when a solution is found, remember the steps int i; // loop counter

int s;

MOVE_SET step_to_solve[100]; // steps to the solution

int rnd_move; // for random selection in a move seta

/* check if the user gave a valid scenario*/

cout<<"请输入孔洞的位置："<<"";

cin>>argc;

//cout<<"请输入要解决的题目序号：";

//cin>>s;

/* validate the hole# */

hole_num = argc-1;

if(!V ALID_HOLE(hole_num))

{

exit(1);

}

/* create the hole on the pegboard */

orig_pegboard[hole_num] = 0;

srand((unsigned)time(NULL));

//play until a solution is reached

//while(step_to_solve[trace].move_where==13){

do{

while ( ! is_solved() )

{

/// while(step_to_solve[trace].move_where==13){

l++;

reset_pegboard(); //reset to the original problem

get_all_moves(); //get # of moves, and the set of moves

trace = 0; //initialize solution tracer

//while there is a move that can be made...play the game

// do{

while ( move )

{

//pick a move

rnd_move = rand() % move;

//move peg

movepeg( move_set[rnd_move].move_what,

move_set[rnd_move].del_what,

move_set[rnd_move].move_where );

// remember the move; useful if this iteration

// turns out to be a solution

step_to_solve[trace].move_what = move_set[rnd_move].move_what; step_to_solve[trace].del_what = move_set[rnd_move].del_what;

step_to_solve[trace].move_where = move_set[rnd_move].move_where; // remember the actual # of moves towards a solution

trace++;

//get new possibilities for a move

get_all_moves( );

}

//}while(step_to_solve[trace-1].move_where==12);

}

}while(step_to_solve[trace-1].move_where==argc-1);

cout<<"木棒最终位置"<

display_pegboard( );

printf("Solution to the pegboard problem: in (%d) iterations\n", l);

i < trace; i++ )

{

printf( "Step (%02d): Move %02d To %02d" , i+1, step_to_solve[i].move_what+1,

step_to_solve[i].move_where+1 );

if (((i+1) % 2 == 0) || (i==trace-1))

{

printf("\n"); //new line after 2 steps

}

else

{

printf(" -->");

}

}

//let the user know what the problem was

reset_pegboard( );

printf("Press Any key...\n");

getch( ); //wait

return 0;

} //end of main

算法设计与分析课程设计(完整版)

HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日

一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。

操作系统课程设计

课程设计报告 2015～2016学年第一学期 操作系统综合实践课程设计 实习类别课程设计 学生姓名李旋 专业软件工程 学号130521105 指导教师崔广才、祝勇 学院计算机科学技术学院 二〇一六年一月

- 1 -

- 2 -

一、概述 一个目录文件是由目录项组成的。每个目录项包含16B，一个辅存磁盘块(512B)包含32个目录项。在目录项中，第1、2字节为相应文件的外存i节点号，是该文件的内部标识；后14B为文件名，是该文件的外部标识。所以，文件目录项记录了文件内、外部标识的对照关系。根据文件名可以找到辅存i节点号，由此便得到该文件的所有者、存取权、文件数据的地址健在等信息。UNIX 的存储介质以512B为单位划分为块，从0开始直到最大容量并顺序加以编号就成了一个文件卷，也叫文件系统。UNIX中的文件系统磁盘存储区分配图如下： 本次课程设计是要实现一个简单的模拟Linux文件系统。我们在内存中开辟一个虚拟磁盘空间(20MB)作为文件存储器，并将该虚拟文件系统保存到磁盘上(以一个文件的形式)，以便下次可以再将它恢复到内存的虚拟磁盘空间中。文件存储空间的管理可采用位示图方法。 二、设计的基本概念和原理 2.1 设计任务 多用户、多级目录结构文件系统的设计与实现。可以实现下列几条命令login 用户登录 logout 退出当前用户 dir 列文件目录 creat 创建文件 delete 删除文件 open 打开文件 close 关闭文件 - 3 -

read 读文件 write 写文件 mkdir 创建目录 ch 改变文件目录 rd 删除目录树 format 格式化文件系统 Exit 退出文件系统 2.2设计要求 1) 多用户：usr1,usr2,usr3,……,usr8 (1-8个用户) 2) 多级目录：可有多级子目录； 3) 具有login (用户登录)4) 系统初始化（建文件卷、提供登录模块） 5) 文件的创建：create (用命令行来实现)6) 文件的打开：open 7) 文件的读：read8) 文件的写：write 9) 文件关闭：close10) 删除文件：delete 11) 创建目录（建立子目录）：mkdir12) 改变当前目录：cd 13) 列出文件目录：dir14) 退出：logout 新增加的功能： 15) 删除目录树：rd 16) 格式化文件系统：format 2.3算法的总体思想 - 4 -

数值计算方法课程设计(C语言)

数值计算方法课程设计 姓名 学号 成绩

课程实际报告 实验一：秦九韶算法 题目 用选列主元高斯消去法解线性方程组 ???????=+- =-+-=-+-=--02 02 0 21 34343232121x x x x x x x x x x 算法语言： 利用c 语言的知识编写该算法程序 算法步骤叙述： 秦九昭算法的基思路是v[0]=a[0]*x+a[1] v[i]=v[i-1]*x+a[i+1];利用秦九昭算法计算多项式函数。 程序清单： #include void main() { float a[5],x,sum; int i; printf("presase input the value of x="); scanf("%f",&x); for (i =5;i >=0;i --) { printf("please input the value of a%d=",i); scanf("%f",&a[i]); } sum =a[5];

for(i=5;i>=1;i--) {sum=sum*x+a[i-1]; } printf("f(x)=%f/n",sum); } 输出结果计算：

实验总结： 通过运用C 语言，解决了秦九韶算法手写的复杂。为以后的雪地打下基础。 实验二：用选列主元高斯消去法解线性方程组 题目 用选列主元高斯消去法解线性方程组 ???????=+- =-+-=-+-=--02 0 2 0 21 34343232121x x x x x x x x x x 算法步骤叙述 第一步消元——在增广矩阵（A,b ）第一列中找到绝对值最大的元素，将其所在行与第一行交换，再对（A,b ）做初等行变换使原方程组的第一列元素除了第一行的全变为0； 第二步消元——在增广矩阵（A,b ）中第二列中（从第二行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A,b ）做初等行变换使原方程组的第二列元素除了第一和第二行的全变为0； 第三步消元——在增广矩阵（A,b ）中第三列中（从第三行开始）找到绝对值最大的元素，将其所在行与第三行交换，再对（A,b ）做初等行变换使原方程组的第三列第四行元素为0； 第四，按x4-x3-x2-x1的顺序回代求解出方程组的解,x[n]=b[n]/a[n][n],x[i]=(b[i]-Σa[i][j]x[j])/a[i][i],i=n-1,…,2,1 程序清单： #include #include$\#define\; N\; 4\; static\; double\; A[N][N]\; =\; \{-3，-1,0,0，-1,2，-1,0，0，-1,2，-1，0,0，-1,2\};\; static\; double\; B[N]=\{1,0,0,0\};$

算法课程设计资料

吉林财经大学课程设计报告 课程名称：算法课程设计 设计题目：插棒游戏 所在院系：管理科学与信息工程学院计算机科学与技术 指导教师： 职称：副教授 提交时间： 2017年4月

目录 一、题目描述与设计要求 (1) 1 题目描述与设计要求 (1) 二、问题分析 (1) 1 解空间 (1) 2 解空间结构 (2) 3 剪枝 (2) 4 回溯法的基本思想 (2) 5 回溯法的适用条件 (3) 6 回溯法的空间树 (4) 7 回溯法的基本步骤 (4) 三、算法设计 (5) 1 伪代码 (5) 四、复杂性分析 (6) 1 时间复杂度 (6) 2 空间复杂度该 (6) 五、样本测试、分析与总结 (6) 1 样本测试 (6) 2 分析 (7) 2.1、数据类型 (7) 2.2 主要函数思路 (7) 2.3 回溯 (8) 3 总结 (8) 参考文献 (9) 附录 (10)

一、题目描述与设计要求 1 题目描述与设计要求 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本： a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。 b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。 图1 二、问题分析 1 解空间 由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。 例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。

内部堆排序算法的实现课程设计说明书

数据结构课程设计设计说明书 内部堆排序算法的实现 学生姓名金少伟 学号1121024029 班级信管1101 成绩 指导教师曹阳 数学与计算机科学学院 2013年3月15日

课程设计任务书 2012—2013学年第二学期 课程设计名称：数据结构课程设计 课程设计题目：内部堆排序算法的实现 完成期限：自2013年3 月4日至2013年3 月15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。指导教师：曹阳教研室负责人：申静 课程设计评阅

摘要 堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词：堆排序；C语言；时间复杂度

数值计算方法课程设计

重庆邮电大学 数学与应用数学 专业 《数值计算方法》课程设计 姓名： 李金徽 王莹 刘姝楠 班级： 1131001 1131002 1131002 学号： 2010213542 2010213570 2010213571 设计时间： 2012-6-4 指导教师： 朱伟

一、课程设计目的 在科学计算与工程设计中，我们常会遇到求解线性方程组的问题，对于系数矩阵为低阶稠密矩阵的线性方程组，可以用直接法进行消元，而对于系数矩阵为大型稀疏矩阵的情况，直接法就显得比较繁琐，而迭代法比较适用。比较常用的迭代法有Jacobi 迭代与Gauss － seidel 迭代。本文基于两种方法设计算法，并比较他们的优劣。 二、课程设计内容 给出Jacobi 迭代法和Gauss-Seidel 迭代法求解线性方程组的算法思想和MATLAB 程序实现，并对比分析这两种算法的优劣。 三、问题的分析（含涉及的理论知识、算法等） Jacobi 迭代法 方程组迭代法的基本思想和求根的迭代法思想类似，即对于线性 方程组Ax = b( 其中n n n R b R R A ∈?∈,），即方程组 )1(2211222221211 1212111?? ???? ?=+?++??=+?++=+?++n n nn n n n n n n b x a x a x a b x a x a x a b x a x a x a 将系数矩阵A 写为 )2(000000 21122 12122 11U L D a a a a a a a a a A n n n n nn --≡??? ?? ? ? ??---- ??????? ??----??????? ??= 若选取D M =，则U L A M N +=-=，方程组)1(转化为等价方程组 b x U L Dx ++=)(

Dijkstra算法的实现-数据结构与算法课程设计报告

合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第2 学期 课程数据结构与算法 课程设计名称Dijkstra算法的实现 学生姓名张睿辰 学号0804012044 专业班级08计科(2)班 指导教师王昆仑张贯虹 2010 年6月

Dijkstra算法的实现 一、问题分析与任务定义 1、课程设计题目： 1.1题目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径 的Dijkstra算法 1.2 要求：设计合理的数据结构存储图，简单有效的实现Dijkstra算法。 1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短 路径，并显示出来！ 2、原始数据的输入格式： 2.1建图模块：2.1.1数字 2.2.2数字+空格+数字+空格+数字+回车 2.3显示模块：回车 3、实现功能： 3.1 建立有向图 3.2 显示存储的有向图 3.3 显示从顶点到其他各顶点的最短路径 4、测试用例： 4.1正确数据：a）顶点：3；边值信息：0 1 6；0 2 4；1 2 5；2 0 6；0 0 0； b）顶点：0；边值信息：0 0 0； 输出结果：a) v0到v1的最短路径是6，v0到v2的最短路径是4 b) 没有最短路径 4.2错误数据：a) 顶点：a b）顶点：2；边值信息：0 3 6；0 4 4；13 5；0 0 0； c）顶点：3；边值信息：0 1 a； 输出结果：边值错误，请从新输入 5、问题分析： 实现本程序要解决以下几个问题： 5.1如何存储一个有向图。 5.2如何在界面中输出该有向图。 5.3如何定义起始源点。 5.4如何选择出最短路径。 5.5找到的最短路径如何输出。 二、数据结构的选择和概要设计 1、数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的

操作系统课程设计报告

上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 2012053班 . 同组姓名：孙嘉轶 课程设计时间：—— 评语： 成绩： 目录 一、设计内容及要求 (4) 1. 1 设计题目 (4) 1．2 使用算法分析： (4)

1． FIFO算法（先进先出淘汰算法） (4) 1． LRU算法（最久未使用淘汰算法） (5) 1. OPT算法（最佳淘汰算法） (5) 分工情况 (5) 二、详细设计 (6) 原理概述 (6) 主要数据结构(主要代码) (6) 算法流程图 (9) 主流程图 (9) Optimal算法流程图 (10) FIFO算法流程图 (10) LRU算法流程图 (11) ．1源程序文件名 (11) . 2执行文件名 (11) 三、实验结果与分析 (11) Optimal页面置换算法结果与分析 (11) FIFO页面置换算法结果与分析 (16) LRU页面置换算法结果与分析 (20) 四、设计创新点 (24) 五、设计与总结 (27)

六、代码附录 (27) 课程设计题目 一、设计内容及要求 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N

块内存（N

算法课程设计

<<算法与程序设计>>课程作业 班级：计本08-1班 学号：3081817106 姓名：詹萍

简单算法 符号三角形问题：这个问题用的是回溯法解决的，符号三角形要求在符号三角形的第1行有n个由“+”和“-”组成的符号，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-”。计算有多少个不同的符号三角形，使其所含“+”和“-”的个数相同。 解题思路： 1、针对所给问题定义解空间，该问题的解空间为n元组x1,x2,x3...xn，其中xi ∈S，S={0，1}，其中0代表“+”， 1代表“-”； 2、确定易于搜索的解空间结构，例如子集树，排列树，该问题是子集树； 3、以深度优先原则搜索解空间树，并利用剪枝函数避免无效搜索，这里的约束函数应该为：在符号三角形的第一行的前i个符号x1...xi确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x(i+1)的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x1...x(i+1)所相应的符号三角形。最终由x1...xn所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束；用0和1代替+和-，执行异或操作推出下一行对应符号，当所有符号总数为奇数时无解，当某种符号超过总数一半时无解。 4.由于回溯法是对解空间的深度优先搜索，不断改变第一行每个符号，搜索符合条件的解，因此可以使用递归回溯。 #include using namespace std; class Triangle {friend int Computer(int);//定义友元函数 private: void Backtrack(int t); //t，第一行第t个符号 int n, //第1行符号的个数 half, //每个三角形总符号数的一半 count, // 统计减号的个数 **p; //指向三角形的二维指针 long sum; }; //统计符合条件的的三角形的个数 void Triangle::Backtrack(int t)//回溯法 {int i,j,k,s,f; if((count>half)||(t * (t-1)/2 - count > half)) return; //如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数if(t<=n) //回溯条件直到n for(i=0; i<2; i++) { p[1][t] = i; //第一行第t个符号 count += i; //“-”号统计 for(j=2; j<=t; j++) //当第一行符号>=2时，可以运算出下面行的某些符号 { p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2]; //通过异或运算下行符号 count += p[j][t-j+1];} if(t>=n)

JAVA实现计算器课程设计

JAVA实现计算器课程设计 计算机科学系 计应0701班 指导老师:刘其昌 设计人员:陈秀桃 设计日期:2009年11月10日——2009年12月20日 计算器的设计 目录 第一章绪 论 ..................................................................... .. (2)

1.1 开发环 境 ..................................................................... . (2) 1.2 基本功能介 绍 ..................................................................... ......... 2 第二章系统设 计 ..................................................................... (3) 2.1 系统流程 图 ..................................................................... . (3) 2.2 系统功能框 图 ..................................................................... (3) 2.3 需求分 析 ..................................................................... ................ 4 第三章软件设 计 ..................................................................... (5) 3.1 界面设 计 ..................................................................... . (5) 3.2 代码设 计 .....................................................................

计算机算法设计与分析课程设计.

成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日

课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分

算法设计与分析课程设计-实验指导书

算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系

一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。

计算方法课程设计

数理学院2014级信息与计算科学 课程设计 姓名：刘金玉 学号： 3141301240 班级： 1402 成绩：

实验要求 1．应用自己熟悉的算法语言编写程序，使之尽可能具有通用性。2．上机前充分准备，复习有关算法，写出计算步骤，反复检查，调试程序。（注：在练习本上写，不上交） 3．完成计算后写出实验报告，内容包括:算法步骤叙述，变量说明，程序清单，输出计算结果，结构分析和小结等。（注：具体题目 具体分析，并不是所有的题目的实验报告都包含上述内容！）4．独立完成，如有雷同，一律判为零分！ 5．上机期间不允许做其他任何与课程设计无关的事情，否则被发现一次扣10分，被发现三次判为不及格！非特殊情况，不能请 假。旷课3个半天及以上者，直接判为不及格。

目录 一、基本技能训练 (4) 1、误差分析 (4) 2、求解非线性方程 (6) 3、插值 (12) 4、数值积分 (12) 二、提高技能训练 (16) 1、 (16) 2、 (18) 三、本课程设计的心得体会（500字左右） (21)

一、基本技能训练 1、误差分析 实验1.3 求一元二次方程的根 实验目的： 研究误差传播的原因与解决对策。 问题提出：求解一元二次方程20ax bx c ++= 实验内容： 一元二次方程的求根公式为 1,22b x a -+= 用求根公式求解下面两个方程： 2210(1)320(2)1010 x x x x +-=-+= 实验要求： （1） 考察单精度计算结果（与真解对比）； （2） 若计算结果与真解相差很大，分析其原因，提出新的算法（如先求1x 再 根据根与系数关系求2x ）以改进计算结果。 实验步骤： 方程（1）： 根据求根公式，写出程序： format long a=1;b=3;c=-2; x1=((-1)*b+sqrt(b^2-4*a*c))/2*a x2=((-1)*b-sqrt(b^2-4*a*c))/2*a

操作系统(一个小型操作系统的设计与实现)课程设计

南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间：

操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法

A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束

2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图

B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始

算法课程设计说明书

课程设计说明书 设计题目：二分法查找 专业：软件工程班级：11-2 设计人：王佳贺 山东科技大学 2013年11 月27日

课程设计任务书 学院：信息科学与工程学院专业：软件工程班级：2011-1 姓名：王佳贺 一、课程设计题目：二分法查找 二、课程设计主要参考资料 （1）《算法分析与设计》（第三版）王晓东电子工业出版社2007 （2） 三、课程设计应解决的主要问题 （1）查询数据 （2） （3） 四、课程设计相关附件（如：图纸、软件等）： （1） （2） 五、任务发出日期：2013-11-21 课程设计完成日期：2013-11-27 指导教师签字：系主任签字：

指导教师对课程设计的评语 成绩： 指导教师签字： 年月日

1二分法详细设计 1.1二分搜索算法 下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？ 如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果xL[i]，同理我们只要在L[i]的后面查找x即可。无论是在 L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。于是我们得到利用分治法在有序表中查找元素的算法。function Binary_Search(L,a,b,x); begin if a>b then return(-1) else begin m:=(a+b) div 2; if x=L[m] then return(m) else if x>L[m] then return(Binary_Search(L,m+1,b,x)); else return(Binary_Search(L,a,m-1,x)); end; end; 1.2二分法算法实现与编程

算法分析资料报告与设计-课程设计资料报告材料

XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师：

X X X X 大学

目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目2 切割木材 (10) 2.1题目描述 (10) 2.2算法文字描述 (10) 2.3算法程序流程 (11) 2.4算法的程序实现代码 (15) 题目3 设计题 (17) 3.1题目描述 (17) 3.2 输入要求 (17) 3.3输出要求 (17) 3.4样例输入 (17) 3.5样例输出 (17) 3.6测试样例输入 (17) 3.7测试样例输出 (18) 3.8算法实现的文字描述 (18) 3.9算法程序流程 (19) 3.10算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24)

题目1 电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1

计算机操作系统课程设计

计算机操作系统课程设计 班级：计091-1 姓名： 学号： 使用语言：C++ 指导老师： 学院：

一、系统要求 1、实验目的 通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能及内部实现。 2、实验内容 为linux系统设计一个简单的二级文件系统。要求做到以下几点： （1）可以实现下列几条命令（至少4条）； login 用户登陆 dir 列文件目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 （2）列目录时要列出文件名、物理地址、保护码和文件长度； （3）源文件可以进行读写保护。

二、系统分析 1、设计思想 本文件为二级文件系统，即要实现对文件的增删改查，同时又具备登陆系统、注册用户的功能，各个用户之间的文件系统互不干扰。 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 系统采用结构体来存储用户、文件目录、文件数据内容： 0 48*5 48*5+44*50 48*5+44*50+264*200 每个分区都是由结构体组成，每个个去的结构体的个数由格式化系统是决定。

整个系统的编码构成主要分为： Allstruct.h 定义了每个分区的结构体； Mysys.h 声明了对系统操作的各种方法；Myuserfile.h 声明了对文件操作的各种方法； Mymain.cpp 整个系统的主函数，操作入口； Mysys.cpp 包含了mysys.h，实现了操作系统的各种方法；Myuserfile.cpp 包含了myuserfile.h，实现了操作文件的各种方法； 2、主要数据结构 Allstruct.h文件的内容： struct s_user //用户区结构体 { long isuse; //是否使用 char name[20]; //用户名 char psd[20]; //密码 long address; //目录地址 };

操作系统课程设计(LRU算法)完整版内含代码

操作系统课程设计LRU页面调度算法 学号： 姓名： 学院： 专业： 班级： 指导老师： 日期：

目录 一、实验题目 (1) 二、课程设计的目的 (1) 三、设计容 (1) 四、设计要求 (1) 五、设计思想 (1) 六、主要数据结构及其说明 (2) 七、硬件支持 (3) 八、源程序文件 (3) 九、程序运行结果 (7) 十、实验体会 (8)

一实验题目 LRU页面调度算法 二课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 1.进一步巩固和复习操作系统的基础知识。 2. 培养学生结构化程序、模块化程序设计的方法和能力。 3.提高学生调试程序的技巧和软件设计的能力。 4.提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三设计容 程序应模拟实现LRU算法思想，对n个页面实现模拟调度。 四设计要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 五设计思想 最近最久未使用（LRU）页调度算法是选择最近最久未使用的页面予以淘汰。 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当所要访问的页面在存块中时，就不淘汰页面，否则，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。

操作系统课程设计题目

操作系统课程设计 一、课程设计题目 实现一个模拟操作系统。 二、课程设计的目的 通过模拟操作系统原理的实现，加深对操作系统工作原理理解，进一步了解操作系统的实现方法，并可练习合作完成系统的团队精神和提高程序设计能力。 三、小组人数 建议3~4人一组共同完成模拟系统的实现。 四、编程语言 建议使用VC、VB、C#、Java等Windows环境下的程序设计语言，以借助这些语言环境来模拟硬件的一些并行工作。 五、课程设计内容 模拟采用多道程序设计方法的单用户操作系统，该操作系统包括进程管理、存储管理、设备管理、文件管理和用户接口四部分。 六、课程设计具体要求和内容 1．文件管理和用户接口 文件管理和用户接口部分实现的主要是单用户的磁盘文件管理部分，包括文件的逻辑结构、物理结构、目录、磁盘分配回收、文件的保护和用户接口的实现。 ⑴文件的逻辑结构 文件的逻辑结构采用流式结构； 文件的内容均采用文本文件； 系统中有两种文件，一种是存放任意字符的文件，一种是可执行文件。可执行文件的内容就是模拟系统内进程的程序体。 文件中要有一种特定命令的“可执行”文件，该文件中的命令有： x=?; 给x赋值一位数 x++; x加1 x--; x减1 !??；第一个？为A,B,C中某个设备，第二个？为一位数，表示使用设备的时间（由于没有实际设备，所以无法知道设备何时工作完成，所以假定一个数，这个数随着系统时间增加而递减，减到0时，认为是设备工作完成）； end. 表示文件结束，同时将结果写入文件out，其中包括文件路径名和x的值。 ⑵磁盘模拟 用一个文件disk1模拟磁盘c，用一个文件disk2模拟磁盘d。两个磁盘一样大小，磁盘的每个盘块64字节，模拟磁盘共有128块。第0、1块存放文件分配表，第2块存放根目录，其余存放子目录和文件。 ⑶目录结构 目录结构采用树型目录结构。 ①目录项内容（8个字节）： 目录名、文件名：3个字节； 扩展名：2个字节（可执行文件扩展名为ex，目录没有扩展名）； 目录、文件属性：1字节（1位标识是文件还是目录，1位标识只读还是非只读，1位是隐藏属性，标识显示还是不显示）； 起始盘块号：1个字节； 文件长度：1字节（目录没有长度）。