[编程题]机器人跳跃问题

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号,从左到右排列。编号为0的建筑高度为0个单位,编号为i的建筑的高度为H(i)个单位。

起初, 机器人在编号为0的建筑处。每一步,它跳到下一个(右边)建筑。假设机器人在第k个建筑,且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值,否则它将得到 E - H(k+1) 的能量值。

游戏目标是到达第个N建筑,在这个过程中,能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏?

输入描述:

第一行输入,表示一共有 N 组数据.

第二个是 N 个空格分隔的整数,H1, H2, H3, ..., Hn 代表建筑物的高度

输出描述:

输出一个单独的数表示完成游戏所需的最少单位的初始能量

示例:

输入
5
3 4 3 2 4
输出
4

解析:
能量的盈亏的状况分为两种:
E(k)=E(k-1)-(H(k)-E(k-1))=2E(k-1)-H(k) E(k-1)<H(k)
E(k)=E(k-1)+(E(k-1)-H(k))=2E(k-1)-H(k) E(k-1)<H(k)

得无论下一根柱子高度如何,E(k)永远是上一次能量E(k-1)的两倍减去下一根柱子长度->E(k)=2E(k-1)-H(k)

所以我们可以进行逆推,由在最后的第n根柱子上所有的能量逐步推出上一根直至我们所求的第0根上的能量。

归纳步骤:

E(n)=2E(n-1)-H(n)
=2*(2E(n-2)-H(n-1))-H(n)
=2^2*(2E(n-3)-H(n-2)-2H(n-1)-H(n)
……
=2^n*E(0)-2^0*H(n-0)-2^1*H(n-1)……-2^(n-1)*H(n-(n-1))
=2^n*E(0)-sum(2^(k)*H(n-k))  k取[0,n-1]

由于能量数额为非负数,所以有:

E(n)=2^n*E(0)-sum(2^(k)*H(n-k))≧0  k取[0,n-1]

则有:

2^n*E(0)≧sum(2^(k)*H(n-k))  k取[0,n-1]

然后两边同时除以2^n,有:

E(0)≧sum(2^(k)*H(n-k))/2^n
=sum(2^(k)/2^n*H(n-k))
=sum(H(n-k)/2^(n-k)  k取[0,n-1]

变换一下,即:

E(0)≧sum(H(i)/2^i)  i取[1,n]

显然这里面存在浮点数,因为能量不能取负数,所以应当对答案向上取整:

代码:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int n,height,ans;
	float sum=0;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> height;
		sum += height/pow(2, i);
	}
	//注:因为要向上取整,所以推荐直接使用ceil()。因为输入数据可能是刚好是2的整幂次数,
	//用int()+1的话有失误的可能-->98%
	ans = ceil(sum);
	cout << ans;
	return 0;
}

附录:
c++中浮点数取整有一下四种方法:floor()、ceil()、round()、int()。它们都在cmath头文件下定义,使用时需引入。
其中:
floor(x):向下取整,取小于等于x的整数
ceil(x):向上取整,取大于等于x的整数
round(x):对x进行四舍五入
int(x):取x的整数部分

上一篇:《Think Python 2e》作业实现(四): 案例研究—接口设计


下一篇:c – 使用QFile()设置读写权限.setPermissions()