网站建设可行性分析表,先做网站还是服务器,网站添加新闻栏怎么做,鞍山seo外包我们先看题目 题目描述 小 Y 的桌子上放着 n 个苹果从左到右排成一列#xff0c;编号为从 11到 n。 小苞是小 Y 的好朋友#xff0c;每天她都会从中拿走一些苹果。 每天在拿的时候#xff0c;小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。随后小苞会将剩下的…我们先看题目 题目描述 小 Y 的桌子上放着 n 个苹果从左到右排成一列编号为从 11到 n。 小苞是小 Y 的好朋友每天她都会从中拿走一些苹果。 每天在拿的时候小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。 小苞想知道多少天能拿完所有的苹果而编号为 n 的苹果是在第几天被拿走的 输入格式 输入的第一行包含一个正整数 n表示苹果的总数。 输出格式 输出一行包含两个正整数两个整数之间由一个空格隔开分别表示小苞拿走所有苹果所需的天数以及拿走编号为 n 的苹果是在第几天。 输入输出样例输入 8输出 5 5 说明/提示【样例 1 解释】 小苞的桌上一共放了 8 个苹果。 小苞第一天拿走了编号为 1、4、7 的苹果。 小苞第二天拿走了编号为 2、6 的苹果。 小苞第三天拿走了编号为 3 的苹果。 小苞第四天拿走了编号为 5 的苹果。 小苞第五天拿走了编号为 8 的苹果。 【样例 2】 见选手目录下的 apple/apple2.in 与 apple/apple2.ans。 【数据范围】 对于所有测试数据有1≤n≤10^9。 这道题我们用什么方法做呢首先不太建议用也就是大多数人想的用数组模拟的方法因为这这种方法不是官方给出的也不被认为是解题最好的思路这里就不为大家展示代码了。接下来我要说的另外一种方法用的不是数组而是-------递归
如果你还不知道递归是什么可以详细的了解一下我的文章c详解递归_c 递归_不懂编程的小王的博客-CSDN博客
在此给大家简单的讲一下递归就是一个函数反复调用自己的过程递归被广泛用于累加和阶乘还有一些特定增长的序列等等程序上。比如斐波那契数列等等。
那有人就问了那这道题到底用什么思路呢原来我们没有必要把第几个苹果在不在全部记下因为题目并没有让我们输出各个苹果被吃掉的顺序所以我们每次只需要知道
1.小苞是否拿走第n个苹果
2.苹果是否拿完。
3.小苞本轮拿走了几个苹果
关于第一个条件如果满足我们需要输出当时的小苞拿了几次苹果就可以了。那我们如何判断这个条件满不满足呢就是if(n%31),也就是如果剩余的苹果数满足这个条件就代表小苞会拿走编号为最后一个的苹果。那这个n%31是怎么来的呢这块需要一点数学知识就是这个拿苹果的周期为先从4个里面拿两个之后就每三个里面拿一个我们发现小苞一次拿的应该是剩余苹果数的第147101316……个苹果而这些数都能满足被3除余1的条件。
第二个条件我们就判断苹果数0接着算如果等于0那我们就可以输出时的小苞拿了几次苹果然后就可以退出递归了。
第三个条件也有一个公式找规律可以得出拿走的苹果数总苹果数-1/31.跟据这个公式我们就可以把总苹果数-由公式得出的小苞本轮要拿走的苹果数就可以了。
接下来上代码
#includebits/stdc.h
using namespace std;
int cnt1;
bool flagtrue;
int apple(int n) {if(n%31flagtrue) { //判断是否拿走编号为n的苹果 coutcnt ;flagfalse; //防止再次找到 }nn-((n-1)/31); //减掉小苞这轮拿走的苹果数 if(n0) { //判断苹果数是否为0 coutcnt; //输出小苞拿苹果的轮数 return 0; //苹果全部拿完退出递归函数 }cnt; //增加小苞拿苹果的轮数 apple(n); //递归苹果没拿完接着拿
}
int main() {int n;cinn;apple(n); //apple函数自带输出 无需添加输出 return 0;
}
只用了23行是不是比数组模拟简单多了
