苹果有多少

来自计算思维百科
跳转至: 导航搜索
苹果有多少1.png

果园里,种植者准备把收获的苹果每10个一袋,但是分装到最后,剩下9个。如果按9个分,剩下8个;于是种植者就试按8个分,结果多7个;按7个分,多6个;按6个分,多5个。

种植者对苹果数量产生好奇,于是算了一下。把全部苹果总数除以5,余4;除以4,余3;除以3,余2;除以2,余1;

这批苹果究竟至少有多少?

解决方案

方案1—最小公倍数法

分析问题,可以发现,不管怎么分苹果,总是缺一只苹果就能保证分成的每堆苹果数量都相等。即,如果多一只苹果,那么苹果的总数就可以被10,9,8,7,6,5,4,3,2,整除了。可以被一堆数字整除的数就是这些数字的最小公倍数或者这些最小公倍数的倍数了。所以其实这个问题就等价转换为求2到10的连续自然数的最小公倍数了。

用质因数分解求最小公倍数如下:

10=5×2

  1. ×3
  2. ×2×2
  3. ×1
  4. ×2
  5. ×1
  6. ×2
  7. ×1
  8. ×1

对每个不同的质因子,取所有数中最大次方的质因子相乘。因此,最小公倍数就是5×23×32×7=2520。即苹果至少有2520 -1 =2519只。

运用的计算思维

方案一通过分析问题的规律并利用问题规律等价转换为求最小公倍数的问题,体现了转化的计算思维,在求最小公倍数的时候采用已经解决的算法求解,提高了计算效率,体现了嵌入的计算思维。

参考资料

《魔法数学》 白丁 编著  现代出版社