错了啊!....晚自习回来再想想....

[ 本帖最后由 Susake 于 2013-4-21 21:27 编辑 ]

估计还是的用贪婪算法，前不久刚学完动态规划，贪婪刚接触，有时候会把他们弄混，我相信不久就可以解决（如果有高人也可指点一二，自己学不易）

贪心算法其实是动态规划的特例，而动态规划是分治法的特例。

一个问题可以分解为若干个子问题求解时，可以用分治法。

如果这个这些子问题拥有最优子结构时，可以用动态规划。

如果最优子结构只涉及一个子问题时，可以用贪心算法。

好好体会一下这些算法的本质。

2013年4月27日竞赛题目
小H是一个程序员。但是他很喜欢一些新奇的东西。

有一次，他去找物理实验室的朋友玩。他见到了一串非常有意思的粒子。N个粒子排成一排。每一秒中，每一段连续的粒子中会随意有一个爆炸，爆炸后该粒子就消失了，且将原来连续的一段粒子分隔成两段。

小H希望知道所有粒子都爆炸完的期望时间。

Input

         第一行为一个整数T（1 <= T<= 400），表示有T组测试数据；

         每组数据一个正整数N（1<=N<=400），表示一开始的粒子数。

Output

         对于每组数据，输出期望时间（秒）。保留五位小数。

Sample Input
3
1
2
3
 
Sample Output
1.00000
2.00000
2.66667
 
Sample Cl.
对N=3，若第一个爆炸的粒子在旁边，则还需两秒；若第一个爆炸的在中间，则再过一秒即可。故答案为2/3*3+1/3*2=8/3。

在贴一道，

#include<stdio.h>
double qiwang(int n)
{
double q=0.00000;
int j;
if(1==n)
  return 1.00000;
else if(2==n)
  return 2.00000;
else
{
  if(n%2==0)
  {
   for(j=n;j>n/2;j--)
   q+=(1.0/n)*2*(qiwang(j-1)+1);
   return q;

  }
  else
  {
   for(j=n;j>n/2;j--)
   q+=(1.0/n)*2*(qiwang(j-1)+1);
   q=q-1.0/n*(qiwang(j)+1);
   return q;
  }

 

}
}
void main()
{
int t,n[400],i;
scanf("%d",&t);
for(i=0;i<t;i++)
scanf("%d",&n[i]);
for(i=0;i<t;i++)
printf("%f\n",qiwang(n[i]));
}
都说效率不高

呵呵，这效率都不能用不高来形容了。

抛开算法正确与否不说，O(2^(n/2))的时间复杂度，简直低的离谱，当n达到几十的时候计算消耗的时间已经无法忍受，不具有实用性。

这题是典型的动态规划应用案例，时间复杂度O(n^2)足矣。优化一下动规步骤可以达到O(n)的水平。这等同于贪心算法的水平。

既然是新题，建议你开新贴讨论。否则也许有人以为在讨论旧题，可能连点开看看的欲望都没有。错过一个潜在的讨论机会岂不可惜