下图是由14个“”和14个“-”组成的符号三角形.doc_第1页
下图是由14个“”和14个“-”组成的符号三角形.doc_第2页
下图是由14个“”和14个“-”组成的符号三角形.doc_第3页
下图是由14个“”和14个“-”组成的符号三角形.doc_第4页
下图是由14个“”和14个“-”组成的符号三角形.doc_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

宁夏师范学院数学与计算机科学学院算法设计与分析实验报告实验序号：实验项目名称：贪心算法应用学号06姓名赵正平专业、班10计本班实验地点321指导教师马 涛时间2013-5-30一、实验目的与要求(1)、熟悉贪心算法和回溯算法的区别；(2)、掌握符号三角形问题的算法；(3)、初步掌握回溯算法；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：Windows XP操作系统、Office2003、多媒体播放软件。三、实验内容与步骤下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 + + - + - + + - - - - +- + + + - - + + - - + - - - +在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。四、实验结果与数据处理#include using namespace std;typedef unsigned char uchar;int sum; uchar* p; /符号存储空间；/表示满足要求的三角形个数char ch2=+,-; int n; /第一行符号总数int half; int count; /用来计算-的个数void BackTrace(int t)if (tn)sum+;cout第sum个三角形：endl;for (int i=1;i=n;i+)for (int j=1;ji;j+)cout ;for (j=1;j=n-i+1;j+)coutchpij ;coutendl;elsefor (int i=0;i=1;i+)p1t=i;/确定第一行第t个的值；count+=i;/用来计算-的个数；for (int j=2;j=t;j+)pjt-j+1=pj-1t-j+1pj-1t-j+2;/第一行大于等于2时确定后面从第2行开始增加的一count+=pjt-j+1;/列中符号，计算-个数；if (count = half & (t*(t+1)/2-count) = half) /约束条件；BackTrace(t+1);for (j=2;j=t;j+) /回溯，判断另一种符号情况；count-=pjt-j+1;count-=p1t; int main()coutn;count=0;sum=0;half=n*(n+1)/2;if (half%2=0)half=half/2;p=new uchar* n+1;for (int i=0;i=n;i+)pi=new ucharn+1;memset(pi,0,sizeof(uchar)*(n+1);BackTrace(1);for (i=0;i=n;i+)delete pi;delete p;cout满足要求的三角形符号共有：s
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论