算法课程设计

open_world 贡献于2013-12-29

作者 lib  创建于2012-12-19 03:26:00   修改者liushuai  修改于2013-12-27 14:55:08字数7715

文档摘要:通过本次课程设计,我们更加清晰的了解到蛮力法与贪心法的基本概念。能够更加灵活的运用蛮力法与贪心法解决实际问题。在比较蛮力法与贪心法解决实际问题的过程中,我们回忆了计算算法效率的递推过程,并对蛮力法与贪心法求正整数数列极差的算法效率进行分析与比较。同时,本次课程设计也使我们重新回忆了一遍C++的基本语句与运用方式,能过更加灵活的使用C++进行编程。 在对算法进行实现的过程中发现思维简单的算法实现起来反而有着更多的困难,在对整个过程的反思中,发现了一些不足,且通过与大家的讨论,使思路更加开阔,得出解决问题时应集思广益的结论。
关键词:

 算法实验周 算法实验周 ******************************** — 所做任务说明及题目相关知识说明 文档编号:NUC-2013-C04-01 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 ©2013中北大学计算机与控制工程学院 算法实验周 所做任务说明及题目相关知识说明 极差问题: 问题描述: 在黑板上写了N个正整数作成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min。对于给定的数列,编程计算出极差M。   解题提示:当看到此题时,我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开,着重探讨求max的问题。   下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论:假设经(N-3)次变换后得到3个数:a,b,max'(max'≥a≥b), 其中max'是(N-2)个数经(N-3)次f变换后所得的最大值,此时有两种求值方式,设其所求值分别为 , ,则有: =(a×b+1)×max'+1, =(a×max'+1)×b+1 所以  - =max'-b≥0若经(N-2)次变换后所得的3个数为:m,a,b(m≥a≥b)且m不为(N-2)次变换后的最大值,即m<max'则此时所求得的最大值为: =(a×b+1)×m+1 此时 - =(1+ab)(max'-m)>0 所以此时不为最优解。   所以若使第k(1≤k≤N-1)次变换后所得值最大,必使(k-1)次变换后所得值最大(符合贪心策略的性质2,最有子结构性质),在进行第k次变换时,只需取在进行(k-1)次变换后所得数列中的两最小数p,q施加f操作:p←p×q+1,q←∞即可(符合贪心策略性质1,贪心选择性质),因此此题可用贪心策略求解。讨论完毕。   在求min时,我们只需在每次变换的数列中找到两个最大数p,q施加作用f:p←p×q+1,q←-∞即可.原理同上。 注释: 分别采用蛮力法和贪心策略进行问题的解决。 1)蛮力法是一种简单直接的解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。即对于极差问题,我们直接按极差的求解过程来解决问题。 ©2013中北大学计算机与控制工程学院 算法实验周 2)贪心策略建议同过一系列步骤来构造问题的解,每一步对目前构造的部分解 做一个扩展,直到获得问题的完整解为止。这个技术的核心是,所做的每一步选择都必须满足以下条件: 1.可行的,即它必须满足问题的约束。 2.局部最优,它是当前步骤中所有可行选择中最佳的局部选择。 3不可取消,即一旦做出选择,在算法的后面步骤中就无法改变了。 所以在极差问题中找到数列中最大值的最优解和最小值的最优解就可算出极差。 3)分治法 将问题划分为几个同一问题的较小实例(最好等规模),对较小实例分析求解,必要时可合并较小实例的解。使用了合并排序对数据预处理。 ©2013中北大学计算机与控制工程学院 算法实验周 ******************************** — 数据结构设计说明 文档编号:NUC-2013-C04-02 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 ©2013中北大学计算机与控制工程学院 算法实验周 数据结构设计说明 ©2013中北大学计算机与控制工程学院 我们在两种方法中大量采用了数组这一数据结构来存储数据 算法实验周 ******************************** — 程序模块及流程设计 文档编号:NUC-2013-C04-03 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 ©2013中北大学计算机与控制工程学院 算法实验周 程序模块及流程设计 开 始 输入数据 确定数据个数和数组个数 判断是否遍历全部数组 否 执行求极差的基本过程 输出数据 结 束 判断是否遍历该数组中的其余元素 判断是否遍历该数组中的所有元素 否 否 ©2013中北大学计算机与控制工程学院 算法实验周 消去b[0]b[1],插入c 开 始 文件输入 合并排序到b[] 求最大值 C=b[0]*b[1]+1 求最小值 C=b[n]*b[n-1]+1 消去b[n]b[n-1],插入c J1,J-- 否 否 结 束 将 结 果 存 储 到 文 件 Jicha = Max - Min Max = b[0]; Min = b[n]; 是 是 ©2013中北大学计算机与控制工程学院 算法实验周 ******************************** — 源程序清单及说明 文档编号:NUC-2013-C04-04 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 ©2013中北大学计算机与控制工程学院 算法实验周 蛮力法求极差 #include #include #include #include void main() { fstream infile,outfile; infile.open("1234.txt",ios::in); if(!infile) { cout<<"filein.txt can't open"<>a[0][m]; cout<2;z--) //求数组的个数 { w=w*z*(z-1)/2; t=t+w; } for(k=0;k2) //当元素大于2时,执行该过程 { for(i=0;id) { d=c[i]; } } for(i=0;i #include #include #include #include #include using namespace std; #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif class Txf { public : Txf(int b[],int m) { for(int i=0;i1) { j--; c=b[0]*b[1]+1; Paix1(b,c,j); } return b[0]; } void Txf::Paix1(int b[],int c,int p) { int i,j; //可以用折半查找优化 b[0]=0; b[1]=0; for(i=2;i<=p;i++) { if(c<=b[i]) { for(j=0;jb[p]) { for(j=0;j<=p-2;j++) b[j]=b[j+2]; b[p-1]=c; } b[p]=0; } void Txf::Paix2(int b[],int c,int p) { int i,j; //可以用折半查找优化 b[n-1]=0; b[n-2]=0; for(i=n-3;i>=p;i--) { if(c>=b[i]) { for(j=n-1;j>i+2;j--) b[j]=b[j-2]; b[j]=c; // cout<p;j--) b[j]=b[j-1]; break; } } ©2013中北大学计算机与控制工程学院 算法实验周 if(c=p+2;j--) b[j]=b[j-2]; b[p+1]=c; } // cout<1) { for(i=0;i<=n/2-1;i++) { ©2013中北大学计算机与控制工程学院 算法实验周 b[i]=a[i]; } for(;iSelectObject(&pen); pDC->BeginPath(); CFont* mlFont=pDC->SelectObject(&Font); pDC->SetBkMode(TRANSPARENT); pDC->TextOut(35,35,"正整数数列极差问题"); pDC->EndPath(); ©2013中北大学计算机与控制工程学院 算法实验周 pDC->StrokePath(); Font.DeleteObject(); pDC->SelectObject(mlFont); // TODO: add draw code for native data here } ///////////////////////////////////////////////////////////////////////////// // CLlytView printing BOOL CLlytView::OnPreparePrinting(CPrintInfo* pInfo) { // default preparation return DoPreparePrinting(pInfo); } void CLlytView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: add extra initialization before printing } void CLlytView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: add c leanup after printing } ///////////////////////////////////////////////////////////////////// CLlytView diagnostics ©2013中北大学计算机与控制工程学院 算法实验周 #ifdef _DEBUG void CLlytView::AssertValid() const { CView::AssertValid(); } void CLlytView::Dump(CDumpContext& dc) const { CView::Dump(dc); } CLlytDoc* CLlytView::GetDocument() // non-debug version is inline { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CLlytDoc))); return (CLlytDoc*)m_pDocument; } #endif //_DEBUG ///////////////////////////////////////////////////////////////////////////// // CLlytView message handlers void CLlytView::OnStart1() { // TODO: Add your command handler code here MessageBox("确认执行"); int i=0,t=80; int n=2,b[100],a[50],j=0; ©2013中北大学计算机与控制工程学院 算法实验周 FILE *fp=fopen("today.txt","r"); fscanf(fp,"%d",&a[j]); for(j=2;j<=2*a[0];j++) { fscanf(fp,"%d",&a[j]); // printf("%d\n",a[j++]); } for(i=0;nTextOut(300+b[i]*30,t+5,m_ye); //SetTimer(0,1000,NULL); Sleep(500); } Chup(b,a[0]); for(i=0;iTextOut(300+b[i]*30,t+55,m_ye); //SetTimer(0,1000,NULL); Sleep(500); } Txf lls(b,a[0]); // lls.Quid(); // cout<TextOut(300+b[i]*30,t+105,m_ye); Sleep(1000); Drawc(300+b[a[0]-1]*30,t+100); m_ye.Format("%d %c",lls.Quid(),' '); pDC->TextOut(300+b[a[0]-1]*30,t+105,m_ye); Sleep(1000); Drawc(300+b[a[0]/2]*30,t+200); m_ye.Format("%d %c",lls.Quid()-lls.Quix(),' '); pDC->TextOut(300+b[a[0]/2]*30,t+205,m_ye); FILE *fp1=fopen("tomorrow.txt","w"); if(!!feof(fp1)) { MessageBox("打开方式错误"); exit(1); } fprintf(fp1,"%d",lls.Quid()-lls.Quix()); ©2013中北大学计算机与控制工程学院 fclose(fp1); 算法实验周 ******************************** — 算法效率分析说明 文档编号:NUC-2013-C04-05 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 ©2013中北大学计算机与控制工程学院 算法实验周 算法效率分析说明 1)蛮力法: 对于极差问题用三层循环来实现,第一层是所用数组的个数:n*(n-1)/2+…+3*2/2+1; 第二层是当前执行数组的元素个数建义,依次为:n-1,n-2,……3,2,1; 第三层是当前执行数组的剩余元素个数,依次为:n-1,n-2,……3,2,1; 所以该蛮力法的算法效率大约是n*n*n*n,即f(x)∈O(n*n*n*n)。 2)贪心策略: 贪心法中使用了合并排序,其复杂程度为nlogn; 在贪心策略中基础步为:j++ 在递归排序中执行n-1次,每次执行n-1,n-2..1; ©2013中北大学计算机与控制工程学院 因而其算法效率是(n*n-n)/2,即f( x ) ∈O ( n*n ) 算法实验周 ******************************** — 总结 文档编号:NUC-2013-C04-06 版 本: 第一版本 作 者: 刘帅,李四伟 打印日期:2013/12/26 拷贝份数:1 算法实验周 总结 总结:通过本次课程设计,我们更加清晰的了解到蛮力法与贪心法的基本概念。能够更加灵活的运用蛮力法与贪心法解决实际问题。在比较蛮力法与贪心法解决实际问题的过程中,我们回忆了计算算法效率的递推过程,并对蛮力法与贪心法求正整数数列极差的算法效率进行分析与比较。同时,本次课程设计也使我们重新回忆了一遍C++的基本语句与运用方式,能过更加灵活的使用C++进行编程。 在对算法进行实现的过程中发现思维简单的算法实现起来反而有着更多的困难,在对整个过程的反思中,发现了一些不足,且通过与大家的讨论,使思路更加开阔,得出解决问题时应集思广益的结论。 ©2013中北大学计算机与控制工程学院 算法实验周 ©2013中北大学计算机与控制工程学院

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档