算法分析与设计样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
1. 利用数组实现原始信息与处理结果的对应存储。
编程统计身高( 单位为厘米) 。统计分150——154; 155——159; 160——164; 165——169; 170——174; 175——179及低于是150、 高于是179共八档次进行。
考虑关系式身高/5-29 与 数组小标的对应关系
#include<stdio.h>
int main( )
{
int i,sg,a[8];
for(i=0;i<=7;i=i+1)
a[i]=0;
printf("input height data until input -1\n");
scanf("%d",&sg);
while (sg!=-1)
{ if (sg>179) a[7]=a[7]+1;
else if (sg<150) a[0]=a[0]+1;
else a[sg/5-29]=a[sg/5-29]+1;
scanf("%d",&sg);
}
for (i=0;i<=7;i=i+1)
printf("%d field the number of people: %d\n",i+1,a[i]);
return 0;
}
2. 二维趣味矩阵的应用
练习:
编程打印形如下规律的n*n方阵。例如下图: 使左对角线和右对角线上的元素为0,它们上方的元素为1,左方的元素为2,下方元素为3,右方元素为4,下图是一个符合条件的阶矩阵。
0 1 1 1 0
2 0 1 0 4
2 2 0 4 4
2 0 3 0 4
0 3 3 3 0
主对角线元素i=j;
副对角线元素: 下标下界为1时 i+j=n+1,
下标下界为0时i+j=n-1;
主上三角◥元素: i <=j;
主下三角◣元素: i >=j;
次上三角◤元素: 下标下界为1时i +j<=n+1,
下标下界为0时i+j<=n-1;
次下三角◢元素: 下标下界为1时i +j>=n+1,
下标下界为0时i+j>=n-1;

#include<stdio.h>
int main( )
{int i,j,a[100][100],n;
scanf("%d",&n);
for(i=1;i<=n;i=i+1)
for(j=1;j<=n;j=j+1)
{if (i==j || i+j==n+1) a [i][j]=0;
if (i+j<n+1 && i<j) a [i][j]=1;
if (i+j<n+1 && i>j) a [i][j]=2;
if (i+j>n+1 && i>j) a [i][j]=3;
if (i+j>n+1 && i<j) a [i][j]=4;}
for(i=1;i<=n;i=i+1)
{
printf("\n");
for( j=1;j<=n;j=j+1)
printf("%4d",a[i][j]);
printf("\n");}
return 0;}

3. 算法优化技巧中算术运算的妙用。
练习:
开灯问题: 有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉; 2号同学将编号为2的倍数的灯都打开; 3号同学则将编号为3的倍数的灯作相反处理( 该号灯如打开的, 则关掉; 如关闭的, 则打开) ; 以后的同学都将自己编号的倍数的灯, 作相反处理。问经n个同学操作后, 哪些灯是打开的?
#include<stdio.h>

int main( )
{ int n,a[1000],i,k;
printf("input a number:\n");
scanf("%d",&n);
for( i=1;i<=n;i++)
a[i]=0;
for( i=2;i<=n;i++)
{ k=1;
while ( i*k<=n)
{ a[i*k]=1-a[i*k];
k=k+1;}
}
for( i=1;i<=n;i++)
printf( "%4d\n",a[i]);
return 0;
}
4.非数值问题的处理
练习: 警察局抓了a, b, c, d四名偷窃嫌疑犯, 其中只有一人是小偷。审问中的描述如下:
a说: ”我不是小偷。”
b说: ”c是小偷。”
c说: ”小偷肯定是d。”
d说: ”c在冤枉人。”
现在已经知道四个人中三人说的是真话, 一人说的是假话, 问到底谁是小偷?
提示: 将以上信息数字化, 用变量x存放小偷的编号, 则x的取值范围从1取到4, 就假设了她们中的某人是小偷的所有情况。四个人所说的话就能够分别写成:
a说的话: x<>1
b说的话: x=3
c说的话: x=4
d说的话: x<>4或not(x=4)

#include <stdio.h>
int main()
{ int x;
for(x=1;x<=4;x++)
{
if((x!=1)+(x==3)+(x==4)+(x!=4)==3)
printf("%c is a thief. \n",x+64);

}
return 0;
}
运行结果:
c is a thief .

5. 数学模型的应用
练习2: 求n次二项式各项的系数: 已知二项式的展开式为:
, 要求利用杨辉三角形的规律来求解此问题。
各阶多项式的系数呈杨辉三角形的规律, 因此可利用杨辉三角形的规律来编程实现。
(a+b)0 1
(a+b)1 1 　 1
(a+b)2 　 1 　 2 　 1
(a+b)3 1 　 3 3 1
(a+b)4 1 4 6 4 1
(a+b)5 ……
则求n次二项式的系数的数学模型就是求n阶杨辉三角形。
算法设计要点: 除了首尾两项系数为1外, 当n>1时, (a+b)n的中间各项系数是(a+b)n-1的相应两项系数之和, 如果把(a+b)n的n+1的系数列为数组c, 则除了c(1)、 c(n+1)恒为1外, 设(a+b)n的系数为c(i), (a+b)n-1 的系数设为c’(i)。则有:
c(i)=c’(i)+c’(i-1)
而当n=1时, 只有两个系数 c(1) 和 c(2) (值都为1)。不难看出, 对任何n, (a+b)n的二项式系数可由(a+b)n-1的系数求得, 直到n=1时, 两个系数有确定值, 故可写成递归子算法。
#include<stdio.h>
void coeff(int a[],int n);
void coeff(int a[],int n)
{ int i;
if(n==0) a[1]=1;
else if (n==1)
{ a[1]=1;
a[2]=1;}
else
{ coeff(a,n-1);
a[n+1]=1;
for (i=n;i>=2;i--)
a[i]=a[i]+a[i-1];
a[1]=1;
}
}
int main( )
{int a[100]={0},i,n;
scanf("%d",&n);
coeff(a,n);
for(i=1;i<=n+1;i=i+1)
printf("%4d",a[i]);
printf("\n");
return 0;
}
6.分治算法的应用
练习3:
求数列的最大子段和。给定n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段, 使其和为最大。如果该序列的所有元素都是负整数时定义其最大子段和为0。
对于此问题可采用二分法逐步分解来完成。算法的设计思想如下:
将所给的序列a[1..n]分为长度相等的2段a[1—(n/2)]和a[(n/2)+1—n],分别求出这2段的最大子段和,则a[1.n]的最大子段和有3种情形。
1) a[1..n]的最大子段和与a[1..(n/2)]的最大子段和相同;
2) a[1..n]的最最大子段和与a[(n/2)+1..n]的最大子段和相同;
3) a[1..n]的最大子段和为a[i:j], 且1≤i≤(n/2), (n/2)+1≤j≤n。
情况1) 和情况2) 可分别递归求得。
对于情况3) ,a[(n/2)]与a[(n/2)+1]一定在最大子段中, 因此能够以(n/2)为中心, 分次求出i: (n/2), (n/2)+1: j两子段的和, 并相加返回 。
#include<stdio.h>
int maxSubSum(int a[],int left,int right)
{
int i,j,sum=0;
if(left==right)//这是递归调用必须要有的终值情况。
{
sum=(a[left]>0?a[left]:0);
}
else
{
int center=(left+right)/2;
int leftSum=maxSubSum(a,left,center);//求出左序列最大子段和
int rightSum=maxSubSum(a,center+1,right);//求出右序列最大子段和
//求跨前后两段的情况, 从中间分别向两端扩展。从中间向左扩展。这里注意, 中间往左的第一个必然包含在内。
int ls=0;int lefts=0;
int tempi=center,tempj=center+1;
for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>ls)
ls=lefts;
}
int rs=0;int rights=0;
for(j=++center;j<=right;j++)
{
rights+=a[j];
if(rights>rs)
rs=rights;
}
sum=ls+rs;//sum保存跨前后两段情况的最大子段和求跨前后两段的情况完成
if(sum<leftSum)
sum=leftSum;//记住, leftSum表示前段序列的最大子段和
if(sum<rightSum)
sum=rightSum;//rightSum表示后段序列的最大字段和

}
return sum;
}
void main()
{ int a[5]={8,-2,9,10,-4};
int d=maxSubSum(a,0,4);
printf("%d\n",d);
}
7．算法基本技巧的应用
练习1:
楼梯上有n阶台阶, 上楼能够一步上1阶, 也能够一步上2阶, 编写算法计算共有多少种不同的上楼梯方法。
算法的设计思想:
此问题如果按照习惯, 从前向后思考, 也就是从第一阶开始, 考虑怎么样走到第二阶、 第三阶、 第四阶……, 则很难找出问题的规律; 而反过来先思考”到第n阶有哪几种情况? ”, 答案就简单了, 只有两种情况:
1)   从第n-1阶到第n阶;
2)   从第n-2阶到第n阶。
记n阶台阶的走法数为f(n), 则
   f(n)=1 n=1
f(n)=2 n=2
f(n-1)+f(n-2) n>2
算法能够用递归完成, 下面是问题的递归算法。

int main( )
{
int n, fn;
printf('n=');
scanf("%d",&n);
fn=f(n);
}

int f(int x)
{
if (x== 1 ) return(1);
if (x==2 ) return(2);
else
return(f(x-1)+f(x-2));
}

8．贪婪算法应用
练习2:
问题描述:
　　今天张麻子打算去约会。大家都知道张麻子是超级大帅哥, 因此和她约会的MM也超级多, 她们每个人都和张麻子订了一个约会时间。可是今天张麻子刚打算出门的时候才发现, 某几个MM的约会时间有冲突。由于张麻子不会分身, 还不能和多个MM同时约会, 她只能忍痛割爱拒绝掉某些MM。可是张麻子这个花心大萝卜还是不死心, 她想知道, 她最多能够和多少个MM约会。

输入:
　　输入的第一行包含一个正整数N(0<N<=1000), 表示和张麻子约会的MM数。接下去N行, 每行描述一个MM, 格式为: Name starttime endtime, 表示在[starttime,endtime)这个半开区间是这个MM的约会时间, starttime < endtime。名字由大写或小写字母组成, 最长不超过15个字母, 保证没有两个人拥有相同的名字, 所有时间采用24小时制, 格式为XX:XX, 且在06:00到23:00之间。

输出:
　　输出的第一行是一个整数M表示张麻子最多能够和多少个MM约会。接下来那一行就是M个MM的名字, 用空格隔开。您能够按照任意的顺序输出。如果存在多个答案, 您能够任选一个输出。

输入示例:
4
Lucy 06:00 10:00
Lily 10:00 17:00
HanMeimei 16:00 21:00
Kate 11:00 13:00

输出示例:
3
Lucy Kate HanMeimei

算法分析:
典型的任务选择问题, 可先按完成时间排序然后贪心选择, 即在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列。

编程要点:
1、 谁结束时间早就选谁, 因此要排序;
2、 进行选择时, 还要考虑前一个被选人的结束时间与后一个开始时间是否有重叠。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;

struct girl
{
char name[20];
int first,second; //约会的开始时间与结束时间
};

//此段函数即为sort函数对girl排序所用的排序规则,
//贪心算法为尽可能多地选择约会, 因此要先对约会结束时间段按升序排列,
//但有可能结束时间相等的, 则考虑谁开始早谁排在前面, 否则谁结束早谁排在前面。
bool cmp(girl a,girl b)
{
if(a.second==b.second)
return a.first<b.first;
return a.second<b.second;
}

int main()
{
int i, n,hour,min;
char aa;
girl gf[1000];
string str[1000];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s%d%c%d",&gf[i].name,&hour,&aa,&min);
gf[i].first=hour*60+min;

scanf("%d%c%d",&hour,&aa,&min);
gf[i].second=hour*60+min;
}

sort(gf,gf+n,cmp); //对MM排序, sort为C++的函数, 使用要包括<algorithm> 头文件
//要求sort使用cmp规则来对gf结构体数组排序
str[0]=gf[0].name;
int count=1;
girl temp=gf[0];
for(i=1;i<n;i++) //贪心算法的选择
{
if(gf[i].first>=temp.second)
{
str[count++]=gf[i].name;
temp=gf[i];
}
}

cout<<count<<endl;
for(i=0;i<count;i++)
cout<<str[i]<<" ";
return 0;
}

9．动态规划算法求解数塔问题
有形如图4-1所示的一个数塔, 从顶部出发, 在每一结点能够选择向左走或是向右走, 一直走到底层, 要求找出一条路径, 使路径上的数值和最大。

程序参考:
#include <stdio.h>
main()
{
int data[50][50]; //存储原始信息
int decision[50][50]; //存储决策信息
/** 数组path[i][j] 存储data[i][j]选择路径,
取值为0 表示向左 取值为1表示向右
*/
int path[50][50];
int i,j,n;

/** 输入数塔有多少行 */
printf("please input the number of rows: ");
scanf("%d",&n);

/** 输入初始数据 */
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{
/** 输入数塔中的数据 */
scanf("%d",&data[i][j]);

/** 初始决策信息与原始数塔数据相同 */
decision[i][j]=data[i][j];

/** 置选择路径的初始值为0 */
path[i][j]=0;
}

/** 动态规划过程的存储 */
for(i=n-1;i>=1;i=i-1)
for(j=1;j<=i;j=j+1)
{
/* * 左结合 */
if(decision[i+1][j]>decision[i+1][j+1])
{
decision[i][j]=decision[i+1][j]+decision[i][j];
path[i][j]=0;
}

/* * 右结合 */
else
{
decision[i][j]=decision[i+1][j+1]+decision[i][j];
path[i][j]=1;
}
}

/** 动态规划过程结束 decision[1][1]为最大值 */
printf("max=%d\n",decision[1][1]);

/** 根据path[i][j] 找出最优解路径 */

j=1;
for(i=1;i<=n-1;i++)
{
printf("%d -> ",data[i][j]);
j=j+path[i][j];
}
printf("%d\n",data[n][j]);
}

10．求两个字符序列的最长公共字符子序列。

算法分析:

设 A=”a0, a1, …, am-1”,
B=”b0, b1, …, bn-1”,
Z=”z0,z1,…,zk-1” 为它们的最长公共子序列。

有以下结论:
1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且”z0,z1,…,zk-2”是”a0,a1,…,am-2”和”b0,b1,…,bn-2”的一个最长公共子序列;

2) 如果am-1≠bn-1, 则若zk-1≠am-1, 蕴涵”z0, z1, …, zk-1”是"a0,a1,…,am-2"和"b0,b1,…,bn-1"的一个最长公共子 序列;

3) 如果am-1≠bn-1, 则若zk-1≠bn-1, 蕴涵”z0, z1, …, zk-1”是”a0, a1, …, am-1”和”b0, b1, …, bn-2”的一个最长公共子序列。

定义c[i][j]为序列a0,a1,…,ai-2”和”b0,b1,…,bj-1”的 最长公共子序列的长度, 计算c[i][j]可递归地表述如下:
1) c[i][j]=0 如果i=0或j=0;

2) c[i][j]=c[i-1][j-1]+1 如果i,j>0,且a[i-1]=b[j-1];

3) c[i][j]=max(c[i][j-1],c[i-1][j]) 如果i,j>0,且a[i-1]≠b[j-1]。

参考程序:

#include <stdio.h>
#include <string.h>
char a[100],b[100],str[100];
int c[100][100];

int lcs_len(int i,int j)
{

int t1,t2;
if(i==0 || j==0)
c[i][j]=0;
else
{
if(a[i-1]==b[j-1])
c[i][j]=lcs_len(i-1,j-1)+1;
else
{
t1=lcs_len(i,j-1);
t2=lcs_len(i-1,j);
if(t1>t2)
c[i][j]=t1;
else
c[i][j]=t2;
}
}
return c[i][j];
}

void build_lcs(int k, int i, int j)
{

if(i==0 || j==0)
return;
if(c[i][j]==c[i-1][j])
build_lcs(k,i-1,j);
else
if(c[i][j]==c[i][j-1])
build_lcs(k,i,j-1);
else
{
str[k-1]=a[i-1];
build_lcs(k-1,i-1,j-1);
}

}

void main()
{
int m,n,k;
printf("Enter two string!\n");
gets(a);
gets(b);
m=strlen(a);
n=strlen(b);
k=lcs_len(n,m);
build_lcs(k,n,m);
puts(str);

}

11．求最长不降子序列。

设有由n个不相同的整数组成的数列, 记为:
a(1)、 a(2)、 ……、 a(n)且a(i)<>a(j) (i<>j)
若存在i1<i2<i3< … <ik 且有a(i1)<a(i2)< … <a(ik), 则称为长度为k的不下降序列。请求出一个数列的最长不下降序列。

参考程序:

#include <stdio.h>
int a[100],b[100],c[100];
main()
{

int n,i,j,max,p;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=1;
c[i]=0;
}

for(i=n-1;i>=1;i--)
{
max=0;
p=0;
for(j=i+1;j<=n;j++)
if(a[i]<a[j] && b[j]>max)
{
max=b[j];
p=j;
}
if(p!=0)
{
b[i]=b[p]+1;
c[i]=p;
}
}
max=0;
p=0;
for(i=1;i<=n;i++)
if(b[i]>max)
{
max=b[i];
p=i;
}
printf("maxlong=%d\n",max);
printf("result is: ");
while(p!=0)
{
printf("%5d",a[p]);
p=c[p];
}

}