数据结构的一道题，一直不知道答案。请大虾们讨论

smallbarrow

试编写算法，计算i!*2^i (i=0,1,...,n-1) 的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大为MAX，则当n>arrsize或者对某一个k(0<=k<=n-1)使得k!*2^k > MAX时，应按出错处理。

anthony1983

这道题不是基础题么？？

smallbarrow

智力不好，没有办法。

smallbarrow

有朋友说比较n时的值是不是比n-1时的值小，如果小的话，说明已经是溢出后的值，此时报错退出。
可是会不会有n时的值在溢出以后仍然比n-1大一点的可能呢，即f(n-1) < 溢出后的f(n) < MAX。个人认为不应该排除此状况。

smallbarrow

唉，没有人回答，只能自己顶了。判断n时的值是不是比n-1时的值小这种方法确实能解决这个问题：）
不存在一个f(n)这样的函数，会造成f(n-1) < 溢出后的f(n) < MAX。：（

dxcnjupt

比较f(n-1)和MAX/2/n

smallbarrow

原帖由 dxcnjupt 于 2007-12-17 11:15 发表
比较f(n-1)和MAX/2/n

能给个理由吗？

yovn

f(k+1)/f(k)=2(K+1)

汗，再读了一遍题目，改一下。

这就是递归方程，从而计算K+1时，比较f(K)和MAX/2/(K+1)就可以了。

实现就很简单了

1. 
   
2. array[0]=1;
   
3. for(int i=0;i<n;i++)
   
4. {
   
5. if(array[i-1]>MAX/2/i)return;
   
6. array[i]=array[i-1]*2*i;
   
7. 
   
8. }
   

复制代码

[ 本帖最后由 yovn 于 2007-12-17 18:29 编辑 ]