盼盼

用户名：61664659

访问量：16317

签　名：

水货路过

等　　级
排　　名	583
经　　验	4112
参赛次数	14
文章发表	3
年　　龄	19
在职情况	学生
学　　校	内蒙古工业大学
专　　业	电子信息工程

　　自我简介：

TA的其他文章

蓝桥杯2015年第六届真题-机器人繁殖-题解（C++/Python代码）
浏览：615

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

优质题解

蓝桥杯2015年第六届真题-机器人繁殖-题解（C++/Python代码）

　　作者: 盼盼　　　　发表时间：2021-02-04 16:53:48 浏览：615　|　评论：1　

原题链接：蓝桥杯2015年第六届真题-机器人繁殖

# 题目 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：最初的机器人数量`

1. 首先我们先看一下题目，其中我们可以发现：
   $$
   第n年所能产生的机器人个数 = 2*第(n-1)年所能产生的机器人个数-1
   $$
   那么我们将这个公式进行推广，通过数学归纳法可以得到这样的一个公式：
   $$
   第n年所能产生的机器人个数 = 2^{n}k-2^{n}+1
   $$
   这个公式不难理解，原因也很简单，每年新增人数如下：
   ￥
   我们很容易发现k前的系数是2^{n-1}^ 而后面的偏置就是系数-1。

2. 接下来我们在推导一下机器人总数s:

我们知道机器人总数s不过就是每年新增人数之和，故：
   $$
   s = \sum_{i=1}^n(2^{i}k-2^{i}+1)+1\\
   s = (2^{n+1}-1)k-(2^{n+1}-1)+n+1
   $$

3. 那么当这个等式出来以后，我们就可以惊奇的发现，整个题目都变成了一个三元方程，后面我们只需要把这个方程解出来即可，唯一需要注意的可能就是关于大数除法的问题了。为了方便计算，我们把等式稍微变形一下：
   $$
   s-n-1 = (2^{n+1}-1)(k-1)
   $$

##  代码描述

### python

```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++

```c++
#include<iostream>
#include<cmath>
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;
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

後會無期

忽视了s的范围 果然换成double就对了hhh....

2021-02-13 22:15:07

盼盼

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

蓝桥杯2015年第六届真题-机器人繁殖-题解（C++/Python代码）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言训练-大、小写问题（C语言代码）

WU-格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

Tom数（C语言代码）

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

上车人数（C语言代码）

盼盼

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

蓝桥杯2015年第六届真题-机器人繁殖-题解（C++/Python代码）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

WU-格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

Tom数 （C语言代码）

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

上车人数 （C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言训练-大、小写问题（C语言代码）

WU-格式化数据输出（C语言代码）

Tom数（C语言代码）

矩形面积交（C语言代码）

上车人数（C语言代码）