第六届蓝桥杯国赛:机器人繁殖从公式推导到C++/Python的实现算法

题目 1831: 机器人繁殖时间限制: 1Sec 内存限制: 128MB 提交: 883 解决: 227
题目描述 X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己，然后就失去复制能力。
每年X星系都会选出1个新出生的机器人发往太空。也就是说，如果X星系原有机器人5个，
1年后总数是：5 + 9 = 14
2年后总数是：5 + 9 + 17 = 31
如果已经探测经过n年后的机器人总数s，你能算出最初有多少机器人吗？
输入
输入一行两个数字n和s，用空格分开，含义如上。n不大于100，s位数不超过50位。
输出
要求输出一行，一个整数，表示最初有机器人多少个。
样例输入

2 31

样例输出

5

思路我们很容易发现，对于这一道题目，是有迹可循的，对于此我们可以简单的进行分析。
首先我们规定以下符号：
n：年数 s：机器人总数 k：最初的机器人数量

首先我们先看一下题目，其中我们可以发现：
第 n 年所能产生的机器人个数 = 2 ? 第 ( n ? 1 ) 年所能产生的机器人个数 ? 1 第n年所能产生的机器人个数 = 2*第(n-1)年所能产生的机器人个数-1 第n年所能产生的机器人个数=2?第(n?1)年所能产生的机器人个数?1
那么我们将这个公式进行推广，通过数学归纳法可以得到这样的一个公式：
第 n 年所能产生的机器人个数 = 2 n k ? 2 n + 1 第n年所能产生的机器人个数 = 2^{n}k-2^{n}+1 第n年所能产生的机器人个数=2nk?2n+1
这个公式不难理解，原因也很简单，每年新增人数如下：
n = 0 : k n = 1 : k + ( k ? 1 ) n = 2 : k + ( k ? 1 ) + ( k ? 1 ) + ( k ? 2 ) . . . . . . n = m : k + ( k ? 1 ) + ( k ? 1 ) + ( k ? 2 ) + ( k ? 2 ) + ( k ? 3 ) . . . . . . ( k ? m ? 1 ) + ( k ? m ) n=0:k\\ n=1:k+(k-1)\\ n=2:k+(k-1)+(k-1)+(k-2)\\ ......\\ n=m:k+(k-1)+(k-1)+(k-2)+(k-2)+(k-3)......(k-m-1)+(k-m) n=0:kn=1:k+(k?1)n=2:k+(k?1)+(k?1)+(k?2)......n=m:k+(k?1)+(k?1)+(k?2)+(k?2)+(k?3)......(k?m?1)+(k?m)
我们很容易发现k前的系数是2{n-1} 而后面的偏置就是系数-1。
接下来我们在推导一下机器人总数s:
我们知道机器人总数s不过就是每年新增人数之和，故：
s = ∑ i = 1 n ( 2 i k ? 2 i + 1 ) + 1 s = ( 2 n + 1 ? 1 ) k ? ( 2 n + 1 ? 1 ) + n + 1 s = \sum_{i=1}^n(2^{i}k-2^{i}+1)+1\\ s = (2^{n+1}-1)k-(2^{n+1}-1)+n+1 s=i=1∑n?(2ik?2i+1)+1s=(2n+1?1)k?(2n+1?1)+n+1
【第六届蓝桥杯国赛:机器人繁殖从公式推导到C++/Python的实现】那么当这个等式出来以后，我们就可以惊奇的发现，整个题目都变成了一个三元方程，后面我们只需要把这个方程解出来即可，唯一需要注意的可能就是关于大数除法的问题了。为了方便计算，我们把等式稍微变形一下：
s ? n ? 1 = ( 2 n + 1 ? 1 ) ( k ? 1 ) s-n-1 = (2^{n+1}-1)(k-1) s?n?1=(2n+1?1)(k?1)

代码描述 python

string = input('') n = int(string.split()[0]) s = int(string.split()[1]) k = (s-n-1)/(2**(n+1)-1)+1 print(int(k))

C++

#include #include using namespace std; int main(){ //需要注意，这里可能会用到大数运算，但非常神奇的就是这里的double居然不会出错 double s; int n, k; cin >> n >> s; k = (s-n-1)/(pow(2, n+1) -1) +1; cout << k; return 0; }