[第126期]碾转式按档计算最大返利

micch

jivy1212 发表于 2019-3-1 18:27
思路一样的，我就是卡在只引用E3:F8,这样套用LOOKUP后，部分值就会异常，这也是太阳老师题目的坑点:如260 ...

我觉得，是不是有可能，只要不是彻底的乱序，lookup不怕两个相邻的数值顺序颠倒。反正二分到最后两个挨着的值是不会弄错的？？？？？？？？？？？？实在是对二分的规则，理解的很浅，不懂

江苏永能朱兴华

micch 发表于 2019-3-2 09:48
呃，我还没详细研究老师们的公式呢，想着等哪位老师总结了再研究。老实说二分法我几乎不懂，只明白基本的 ...

这个我有做过，当时发现不是完全升序排列。还特跑到二分法的贴子去学习去，结果还是晕晕的。

micch

江苏永能朱兴华 发表于 2019-3-1 22:44
这个我有做过，当时发现不是完全升序排列。还特跑到二分法的贴子去学习去，结果还是晕晕的。

所以我觉得自己公式是错了，因为如果标准的数字不是这个模拟题，就会出现二分的时候，正好错过正确结果。现在能和模拟结果一致，不过是因为模拟数据不影响而已。

江苏永能朱兴华

micch 发表于 2019-3-2 16:03
所以我觉得自己公式是错了，因为如果标准的数字不是这个模拟题，就会出现二分的时候，正好错过正确结果。 ...

我也是这样理解的，不过这题二分法不知道算不算正确答案，如果不算好多老师答题要掉了。

anonym

谈一谈本题的争议。

先谈“辗转累计”。
在我看来，按档辗转累计方式有两种：分别是单次累计和多次累计。
单次累计，各档返利只累计计算一次。
多次累计，各档返利需要累计计算多次，直至不能累计，转至较低一档。
原题的要求是，最高档多次累计，其余档单次累计。如果原题的“交易额返利查询表”的交易额各档数值是固定不变的（不可随意修改的），由于交易额档(n+1)/交易额档(n)<=2，那么实际不会发生多次累计，其实只能是单次累计。
对于单次累计，解题要用到二进制遍历，多次累计，则是n进制遍历。n进制遍历也是可以用公式做的，只是一则比较复杂，用一个公式会很长，不适合以公式长短为量化的竞赛考核。二则当n足够大时，公式长度会有限制，速度也会呈几何级数下降。

再谈“最大”。
在我看来“最大”可以有3种理解。
定义1，最大交易额档，即尽量取较高档，太阳出题的本意。
定义2，累计的返利为最大，jivy1212等的理解，也许是受“最大返利”的字面影响。只是这个定义，结果是依赖于返利值的。也许从消费者角度会这么考虑，但对于实际应用来说，该定义合理性相对较弱。
定义3，交易额档的累计值最大（累计值小于等于实际交易额值）。
举个例子，“交易额返利查询表”如下，
交易额 返利
0      0
40     10
50     13
70     18
90     20
110    28
如果实际交易额是135，只考虑单次累计方式。定义1，应该取交易额档110，返利28。定义2，应该取交易额档50+70，返利31。定义3，应该取交易额档40+90，返利30。

最后谈“LOOKUP”。
大家都知道，LOOKUP是“二分法”查询，对于未排序的数据，存在错误的风险。但是本题由于1<交易额档(n+1)/交易额档(n)<=2，所以实际结果是排序的（此处有错，详见下面的帖子），“二分法”的风险不会存在（相关的数学证明在此不再赘述）。但如果要扩展到n进制遍历，LOOKUP函数就会出错。

micch

anonym 发表于 2019-3-3 23:44
谈一谈本题的争议。

先谈“辗转累计”。

以本题为例，二进制得到的2700,2650对应交易额累计不是升序，不过两个数字也挨着连续的，二分法在这个模拟数据里好像不影响结果。

就是不知道如果二分法查找的时候正好落在两个不是升序的数字位置上时，是不是影响结果。实在是不懂二分法。我是以为查找的时候第一次落在不是升序的位置，然后后续的二分查找就错了，但是不懂到底怎么回事

anonym

micch 发表于 2019-3-4 20:37
以本题为例，二进制得到的2700,2650对应交易额累计不是升序，不过两个数字也挨着连续的，二分法在这个模 ...

micch说得对，我上帖关于LOOKUP那段描述有误，本题也存在错序的风险。2650/2700的问题，我做题的时候也发现了，今天怎么就忘了。

数学推导不能想当然，还是要完整写下来，想一想。

原证明是，已知Xm<X(m+1)<=2Xm，欲证明∑Xm<=X(m+1)。
∑Xm=X1+X2+..+Xm<=X1+2X1+4X1+..+2^(m-1)X1<=2^m*X1，
但X(m+1)<=2^m*X1，不是>=，不等号方向搞反了。
其实命题是不成立的。2650/2700就是反例。

不过，我确实也认为LOOKUP函数，只是特殊情况下没出现错误，不能算是完全正确的答案。我想太阳出题也是这个意思，不能用LOOKUP。用TEXT的解法无法处理小数（未知位数的小数，不算已知位数的小数，先处理成整数然后再还原成小数的情况），所以太阳在题目中加了正整数的限制。

我的解法：=MMULT(--ISODD(IF(MOD(A2,E$9)>=E$2,MAX(-(MOD(A2,E$9)<MMULT(--ISODD(ROW($1:$127)/2^COLUMN(A:G)*2),E$2:E$8))+ROW($1:$127)%%)/1%%,)/2^COLUMN(A:G)*2),F$2:F$8)+INT(A2/E$9)*F$9。虽然长点，但适用于小数（LOOKUP也适用于交易额档和返利是小数的情况），也能容易地扩展到可随意修改交易额档的n进制遍历。

anonym

举一个在本题中LOOKUP出错的例子（在本题的当前数据下是不会出错的）。

提取LOOKUP公式为，=LOOKUP(A2,MMULT(--ISODD(ROW($1:$127)/2^COLUMN(A:G)*2),E$2:E$8))。
简化条件，假设只有3档交易额，依次为E2=2，E3=3，E4=4。
上式变成，=LOOKUP(A2,MMULT(--ISODD(ROW($1:$7)/2^COLUMN(A:C)*2),E$2:E$4))。
此时，MMULT的结果为{2;3;5;4;6;7;9}。当查询值A2=2,3,4,6,7,8,9时，结果都是正确的，分别为2,3,4,6,7,7,9。但查询值A2=5时，应该是5，结果却是错误的4。

anonym

在原题基础上做了个更新。
1.加大了数据可更改的范围；
2.设置了按档累计方式；
3.“最大”的定义用了定义1（详见本人前面的帖子）；
4.附件中的版本不支持表格扩缩。目前设了9档，如果只要较少的档数，比如3档，就把最高3档设置成你要的数值，下面几档交易额设置成依次递减的数值（因为支持小数，这个不难做到），返利设置成0。只是有防错功能，数据有时无法一次性改到你希望的数值，需要耐心反复多改几次。有时候，容错性和便利性会成为两难。

附件做了个保护，一则，避免表格扩缩操作。虽然对于表格扩缩，单元格公式能做到自适应，但因为加了数据有效性，数据有效性不支持数组公式，所以表格扩缩后的数据有效性需要手动添加或更新（VBA倒是可以自动实现，但不在本题讨论范围），算是瑕疵。二则，卖个关子，不喜勿喷。

anonym

“授之以鱼，不如授之以渔”。何谓“授之以渔”？我觉得更具体点应该是，“授之以渔而渔”。前面一个“渔”是“渔具”，后面一个“渔”是“打渔”。

那么“渔具”又是什么？

技巧？技巧其实就是经验。所谓“熟能生巧”。中国现在的教育有追求技巧的趋势。题做多了，自然熟能生巧。但偏又搞出什么答题技巧，猜题技巧。于教者，或是为了“升学率”，或是为了“柴米钱”。于学者，没准一会儿窃喜于搏中的一两分，一会儿懊恼于失败的运气不佳。好歹这些技巧也只是属于“擦边球”，比之于弄虚作假，冒名顶替等来说，还算光明的。对于EHer来说，技巧可以是相互切磋追求提高的解题技艺，但不可“舍本逐末”，否则不管成为自娱自乐的手段，还是成为巧而无用的“炫技”，总是“过犹不及”。那么，不会也罢。“大巧若拙”，还是要回归解决问题的本质。

方法？方法其实就是思路、算法，比技巧重要。算法为主，技巧为辅，才能做到触类旁通。没有算法，只讲技巧，就是“皮之不存，毛将焉附”。EH竞赛版是一个很好的园地，“黑盒”的出题、做题和竞赛，“白盒”的讨论、总结和分享，总会激发起一些精妙的算法、和谐的碰撞和智慧的火花。

“渔具”，我觉得就是安全可复用的工具。安全很重要，哪怕不是在解题之初就考虑，也要做个标识，留待以后补救。其次就是可复用。技巧，算法，虽然都是可复用的，但都只是竞赛版的高手们，才能游刃有余地驾驭的东西。只有做出实际的“渔具”来，一般的“渔民”才可以用来“打渔”，甚至于高手也能乐于使用。可复用就是，要可以钓小鱼，也可以钓大鱼；要可以在河里钓，也可以在海里钓；要可以钓鱼，也可以钓龙虾，等等。总之，就是要有一定的灵活性，可扩展，可防错，可维护。

EH的函数竞赛题，都是不错的题目，很有实际应用的意义。而我更多地喜欢把这些题做成相关的应用。虽然有时会有取舍，有时只能尽量，但我考虑的原则依次是合理性，普遍性，安全性，然后扩展性，易用性，高效性，最后美观性，简洁性，兼容性。

兹是体会，以飨诸位。若有不对，匹夫无罪。