《算法设计与分析》上机指导

《算法设计与分析》上机指导

《算法设计与分析》课程上机指导

（06软工A1A2、08计科S1）

上机常见错误与对策 1 上机指导1 上机指导2 上机指导3

计算机与信息学院 温敬和 wenjinghe@

2009-2-5

2 5 8

《算法设计与分析》上机指导

上机常见错误与对策

㈠创建工程时，选错工程类型（应选择倒数第三个“Win32 Console Application”）；创建源程序文件时，选错文件类型。

㈡要修改程序，应打开工作区（dsw）文件，而不是源程序（cpp）文件。 ㈢在VC++系统中，程序是用西文字符（ASCII码）来描述的，汉字只能出现在字符串常数或注释中。

请注意汉字双引号和西文双引号的区别 请注意汉字单引号和西文单引号的区别 请注意汉字分号和西文分号的区别 请注意汉字园括号和西文园括号的区别

㈣在一般情况下，一个工作区只有一个工程，一个工程对应一个程序。当一个程序完成，编制下一个程序时，一定要新建工程（不要修改系统默认设置“创建新工作区”）。最简单的方法是：退出VC++集成环境后，重新进入VC++。 ㈤当系统出现不可解释的现象时，此时应选择“编译”→“重建全部”，然后执行。若还不行，则重新启动计算机，利用硬盘保护卡功能恢复系统。操作步骤： 重新启动计算机后，出现菜单画面。 选中“Windows 2000 Professional”。 在按住“Ctrl”键的同时，按“R”健。 对于系统提问，按“Y”键回答。

㈥源程序若有错误，编译系统会在输出区显示错误信息。由于识别错误能力有限，指示的错误信息有时不一定完全正确，但至少提供了线索。双击错误信息条目，指针会自动指向出错语句，编程者可逐字符查找错误。

《算法设计与分析》上机指导

《算法设计与分析》上机指导1

㈠（每个）程序书写要求

// ******************************************************* // * 工 程 名：103.dsp * // * 程 序 名：103.cpp * // * 主要功能：自底向上合并排序法 * // * 学号姓名：57053001温敬和 * // * 编制时间：2007年7月13日 * // ******************************************************** #include <iostream.h> //#include <iostream> void main() //using namespace std; { //int main() …… //{

…… // …… …… // return 0; } //}

㈡实习内容

习题一（工程名为101、源程序名为101） 选择排序法的伪代码描述如下： 算法1.4 SelectionSort（参见Page 8） 输入：数组A[1..n]

输出：按升序排列的数组A[1..n]

1. for i←1 to n-1 2.

Selection(i)

3. end for 过程Selection(i)

1. k←i

2. for j←i+1 to n 3.

if A[j]<A[k] then k←j

4. end for

5. if k≠i then 交换A[i]和A[k]

用C语言实现上述算法并上机通过。

《算法设计与分析》上机指导

选做题：用递归方法（归纳法）实现选择排序法。

习题二（工程名为102、源程序名为102） 插入排序法的伪代码描述如下： 算法1.6 InsertionSort（参见Page 8-9） 输入：数组A[1..n]

输出：按升序排列的数组A[1..n]

1. for i←2 to n 2.

Insertion (i)

3. end for 过程Insertion(i)

1. x←A[i] 2. j←i-1

3. while (j>0) and (A[j]>x) 4. A[j+1]←A[j] 5.

j←j-1

6. end while 7. A[j+1]←x

用C语言实现上述算法并上机通过。

选做题：用递归方法（归纳法）实现插入排序法。

习题三（工程名为103、源程序名为103） 自底向上合并排序法的伪代码描述如下： 算法1.6 BottomUpSort（Page 10） 输入：n个元素的数组A[1..n] 输出：按升序排列的数组A[1..n]

1. t←1 2. while t<n 3.

s←t : t←2s : i←0

《算法设计与分析》上机指导

4. 5. 6. 7. 8.

while i+t≤n

Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) i←i+t

end while

if i+s<n then Merge(A,i+1,i+s,n)

9. end while //n-i>s表示剩余的元素个数大于被合并的子序列长度 过程Merge(A[1..m],p,q,r)

1. comment:B[p..r]是个辅助数组 //或B[1..m] 2. s←p : t←q+1 : k←p

//s和t分别指向数组A二个子数组元素 //k指向数组B当前空白元素位置

3. while (s≤q) and (t≤r) 4. 5. 6. 7.

if A[s]≤A[t] then B[k]←A[s] : s←s+1 else B[k]←A[t] : t←t+1 end if k←k+1

//指向数组B下一个空白位置

8. end while

9. if s=q+1 then B[k..r]←A[t..r] //说明子数组A[p..q]元素已处理完 10. else B[k..r]←A[s..q] 11. end if

12. A[p..r]← B[p..r]

用C语言实现上述算法并上机通过。

选做题：用递归方法（分治法）实现自底向上合并排序法。

//否则t=r+1，说明子数组A[q+1..r]已处理完。

《算法设计与分析》上机指导

习题四（工程名为104、源程序名为104）

参考下列程序，对习题一和习题三的程序作适当修改。通过上机运行，实验测评二种排序算法运行效率，以期在理论和实践上得出一致的结论。 ⑴选择排序算法修改

#include <iostream.h> #include <stdlib.h> #include <iomanip.h> #include <conio.h> #include <time.h> #define N 65536*2 void Selection(short[],int); void main() {

short A[N+1]; srand(time(NULL));

for(int i=1;i<=N;i++)A[i]=rand()%10000; time_t t1,t2; struct tm *pt; time(&t1);pt=gmtime(&t1); cout<<setfill('0'); cout<<"排序开始时间:";

cout<<setw(2)<<(pt->tm_hour+8)%24<<":"<<setw(2)<<pt->tm_min<<

":"<<setw(2)<<pt->tm_sec<<endl;

cout<<"SelectionSort排序中"<<flush; for(i=1;i<=N-1;i++){

if(i%2048==0)cout<<"."<<flush; Selection(A,i);

}

cout<<endl<<"排序结束时间:"; time(&t2);pt=gmtime(&t2);

cout<<setw(2)<<(pt->tm_hour+8)%24<<":"<<setw(2)<<pt->tm_min<<

《算法设计与分析》上机指导

":"<<setw(2)<<pt->tm_sec<<endl; }

⑵归并排序法修改

#include <iostream.h> #include <stdlib.h> #include <iomanip.h> #include <conio.h> #include <time.h> const int N=65536*2;

void BottomUpSort(short[],int); void Merg(short[],int,int,int); void main() {

short A[N+1]; srand(time(NULL));

for(int i=1;i< …… 此处隐藏：2954字，全部文档内容请下载后查看。喜欢就下载吧 ……