一道+ / edao.plus

拼数极值

给定一组数字,要拆成两个数使乘积最大:先让两数的位数尽量接近,再用“最大两数字打头、之后每次把当前最大数字接到较小数末尾”的规则一次填完。

直观场景

乘积 = 数 A × 数 B。位数差一位,乘积的“量级”就差一截,所以位数要尽量平分;同样一个数字 d,放在哪个数的末尾,会让那个数加上 d × 10^k,而另一个数会被乘上去——把它接在“目前较小”的那个数末尾,相当于拉平两数、扩大几何均值,从而抬高乘积。

推导思路

  1. ① 设共有 n 个非零数字。把它们分成 ⌈n/2⌉ 位和 ⌊n/2⌋ 位两个数(位数尽量接近)。
  2. ② 把降序排好的数字依次取出。第 1、2 大的两个数字分别作为两数的最高位。
  3. ③ 从第 3 个数字开始,每次比较当前两个“半成品”数的大小,把这个数字接在较小那个的末尾。
  4. ④ 重复直到所有数字用完,得到的两数即为最大乘积的拼法。

公式 / 要点

  • “位数尽量接近”是大前提:n 位数字拆成 k+(n−k),k 越接近 n/2 乘积越大;4+1 几乎总是输给 3+2。
  • “接在较小数末尾”等价于让两个数尽量接近——和一定时,两数越接近乘积越大(算术–几何均值)。
  • 首位放最大两个数字是“位数尽量接近”原则在最高位上的体现。

典型例题

1用 1、2、3、4、5 拼最大乘积
把数字 1、2、3、4、5 各用一次分成两组,组成两个数,求最大乘积。
  1. 5 个数字 → 拆成 3 位 + 2 位。降序排列:5, 4, 3, 2, 1。
  2. 5 → A 首位,4 → B 首位:A = 5, B = 4。
  3. 3 接到较小数末尾(B = 4):A = 5, B = 43。
  4. 2 接到较小数末尾(A = 5):A = 52, B = 43。
  5. 1 接到较小数末尾(B = 43):A = 52, B = 431。
  6. 最大乘积 = 52 × 431 = 22412。

小结:“较小数末尾”的判断每一步都要重新比一次,不要一直往同一个数上接。

2为什么不是 521 × 43
同样的数字,若把 5 放在三位数的首位(A = 5__、B = 4_),结果会怎样?
  1. 套规则:A = 5, B = 4 后,下一步 3 接到较小数 B → B = 43;再下一步比较 A = 5 与 B = 43,较小是 A,应把 2 接到 A → A = 52;最后 1 接到较小的 B → B = 431。
  2. 强行让 5 占三位首位(即写成 A = 5xy 不再调整),得到的最优摆法是 521 × 43 = 22403,比 431 × 52 = 22412 少 9。

小结:“最大数字一定放最长那个数的最高位”是常见错觉;正确口诀是“接到较小数末尾”,会自动把大数字调到该去的位置。

常见误区

  • 忘记每一步重新比较两数大小,机械地把数字交替放,会得到次优解。
  • 对位数差很大的情形(如 4+1)凭直觉觉得“数字越靠左越好”,忽略了位数本身才是主导因素,先把位数差缩到最小再谈位置。
  • 数字含 0 时要额外注意:首位不能为 0,0 应尽量放进较大那个数的低位。

用到「拼数极值」的题目

相关知识点