[第68期]类似二分法查找<统计posi的转换频率>

wangg913

题目要求及说明：

题目主要是学习一下二分法查找的原理，弄懂原理后问题并不复杂
因此不提供模拟结果，以适当增加难度。公式长度不限定。版本也不限定

1、纯公式，不使用辅助列，输入后下拉完成；
2、与正确结果相差在5个“计算量”以内，评2分技术；
3、完全正确者，评3分技术；
4、只要有明确的答案，适当给予财富奖励；
5、题目截止至2011年1月15日

补充说明：
1、“题目说明”表第95行，如果 N=4 ，查找值 0 分别在位置1、位置2、位置3、位置4，posi分别的变换次数，然后求和，才是最终的要求。不是求单纯哪一种。
2、“表二”中的A列数据可变，不一定是顺序增加的，可能是任意可能的数字。

有问题不明白请发短信通知。




[ 本帖最后由 wangg913 于 2011-1-16 13:02 编辑 ]

wcymiss

B2=(A2^3+3*A2^2+IF(MOD(A2,2),5*A2+3,8*A2))/12
简化一下：
B2=(A2^2+3*A2+5+3*A2^-MOD(A2,2))/12*A2

[ 本帖最后由 wcymiss 于 2011-1-3 01:57 编辑 ]

leeyong

参与一下,还没有过期吧？应该

此贴没有答案，不能得分！<wangg913>

chunlin1wang

A2=SUM(IF(ROW(INDIRECT("1:"&A2))>=INT((A2+1)/2),ROW(INDIRECT("1:"&A2))),INT((ROW(INDIRECT("1:"&A2))-1)/2)*(A2+1-ROW(INDIRECT("1:"&A2))))
数组公式 下拉

Yangqianqian

不知对二分法的理解对否？

给一个短的，公式长度=40

不用递推公式：（长度38）
B2=(A2^2+3*A2+8)*A2/12+(-1^A2-1)*(A2-1)/8
然后下拉。

[ 本帖最后由 Yangqianqian 于 2011-1-3 00:01 编辑 ]

fugb-2010

公式：
表二中
B2=SUM(INT((A2-{0,1})/2)*(INT((A2-{0,1})/2)*(INT((A2-{0,1})/2)+3)+{2,5})/3)+1
数组公式后下拉

[ 本帖最后由 fugb-2010 于 2010-12-28 12:47 编辑 ]

鬼狐

=IF(A2<3,2*A2-1,SUM(ROW(INDIRECT("2:"&ROUND(A2/2,)))*(2*ROW(INDIRECT("1:"&INT(A2/2)-MOD(A2+1,2)))-1),ROW(INDIRECT("1:"&ROUND(A2/2,)+MOD(A2+1,2))))+IF(MOD(A2,2),(A2-1)/2,(A2/2-1)*(A2/2+2)))
附件公式在C列
1跟2还不知道怎么合并，只能另外独立出来了，希望能行
先上来，有空再看下
==================================================
重新找了一下规律
=IF(A2=1,1,SUM(INT((ROW(INDIRECT("1:"&A2-1))-1)/2)*INT((ROW(INDIRECT("1:"&A2-1))+1)/2),ROW(INDIRECT("1:"&A2))))
1还是只能独立出来

[ 本帖最后由 鬼狐 于 2010-12-23 16:25 编辑 ]

fangjianp

请大头先生指正.
短信收到，已回！
N(A1)=N(A2)-1,这里仅是要一个比Ai小1的数，题目中正好可取巧，所以就写成了N(A1),不行就改成（A2-1）,见第二次发的附件。还有问题吗？
弄懂了二分法原理后，剩下的只是求一串数据（或称数列)的通项公式为题，而该竞赛题的复杂性诚如版主所说，难点在于二分法原理，至于用何公式表达已不是本竞赛题的重要考点。事实上，若用递推公式An=An-1+...之类的公式表达还可以更短。

[ 本帖最后由 fangjianp 于 2010-12-22 09:50 编辑 ]

kkitt

如果按顺序排，可以取巧
B2=N(B1)+MOD(A2,2)+ROUNDUP((A2-1)/2,)*ROUNDUP((A2+1)/2,)

如果N值任意，则可以用公式
B2=2*SUM(ROW(INDIRECT("1:"&INT((A2+2)/2)))*(ROW(INDIRECT("1:"&INT((A2+2)/2)))-1))+(MOD(A2,2)*2-1)*INT((A2+1)/2)^(2-MOD(A2,2))

再减化
B2=2/3*PRODUCT({0;1;2}+INT(A2/2))-(-INT((A2+1)/2))^(2-MOD(A2,2))

[ 本帖最后由 kkitt 于 2010-12-23 09:13 编辑 ]

aa7701914

有时间再改改公式

更改.

[ 本帖最后由 aa7701914 于 2010-12-22 15:54 编辑 ]