知识点1:啊哈算法之炸弹人(枚举!很暴力)
情景:小哼最近爱上了“炸弹人”游戏,现在有一个特殊的关卡如下:你只有一枚炸弹,但是这枚炸弹威力超强(杀伤距离超长,可以消灭杀伤范围内所有的敌人)。请问在哪里放置炸弹才可以消灭最多的敌人。
地图:
解决思路:
1.将地图模型化:
2.使用二维字符组来储存地图:a[i][j]
3.确定指向并枚举统计:
例如:
//向下统计可以消灭的敌人数
while(a[x][y]!='#')
{
if(a[x][y]=='G')
{
sum++;//对消灭的敌人计数
}
x++;//继续向下
}
判断其他方位的方式同上
完整代码如下:
#include<stdio.h>
int main()
{
char a[20][21];
int i,j,sum,map=0,p,q,x,y,n,m;
scanf("%d %d",&n,&m);
for(i=0;i<=n-1;i++)
{
scanf("%s",a[i]);
}
for(i=0;i<=n-1;i++)
{
for(j=0;j<m-1;j++)
{
if(a[i][j]=='.')
{
sum=0;
x=i;
y=j;
while(a[x][y]!='#')
{
if(a[x][y]=='G')
{
sum++;
}
x--;
}
x=i;
y=j;
while(a[x][y]!='#')
{
if(a[x][y]=='G')
{
sum++;
}
x++;
}
x=i;
y=j;
while(a[x][y]!='#')
{
if(a[x][y]=='G')
{
sum++;
}
y--;
}
x=i;
y=j;
while(a[x][y]!='#')
{
if(a[x][y]=='G')
{
sum++;
}
y++;
}
if(sum>map)
{
map=sum;
p=i;
q=j;
}
}
}
}
printf("将炸弹放置在(%d %d),最多可以消灭%d个敌人\n",p,q,map);
getchar();
getchar();
return 0;
}
测试结果:
知识点2: 算法的复杂度
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。
摩尔定律:每十八个月,半导体晶体管数量会增加一倍。
时间复杂度的概念:
时间复杂度的定义:在计算机科学中,算法的复杂度是一个函数(数学概念上的),它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是都可以上机测试。但是这很麻烦。所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本执行次数,为算法的时间复杂度。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。
注意:时间复杂度比较的不是时间,而是比较执行次数
嵌套循环时间复杂度的计算:
答案:F(N)=N*N+2*N+10
分解来看 :
第一部分:
for(int i=0;i<N;++i)
{
for(int j=0;j<N;==j)
{
++count;
}
}
次数:N*N
第二部分:
for(int k=0;k<2*N;++k)
{
++count:
}
次数:2*N
第三部分:
int M=10;
while(M--)
{
++count;
}
次数:10
注:
所以Func1的时间复杂度为O(N^2);
双重循环的时间复杂度:
常数循环的时间复杂度:
值得注意的是:
冒泡排序的时间复杂度:
二分查找的时间复杂度:
时间复杂度:O(log2N)
原因:
此处X为假设要查找X次
阶乘递归的时间复杂度:
故结果为:O(N)
斐波那契递归的时间复杂度:
空间复杂度的概念:
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。