数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 C++ 中找到一个包含 n 个整数的数组中，在删除每个元素后，剩余的最后一个元素
假定我们有一个包含 1 到 n 的整数的循环数组。找到列表中将保留的最后一个元素，从第一个元素开始每删除第二个元素后，它将保持在列表中。如果输入为 5，则数组将为 [1, 2, 3, 4, 5]。从 1 开始。在删除每个第二个元素后，将如下 −
1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0
因此，在列表中保留的元素为 3。
我们将使用递归来解决这个问题。假设 n 是偶数。将移除数字 2、4、6，然后我们将从 1 重新开始。因此移除了 n/2 个数字。而且我们开始就好像是从一个仅包含奇数位 1、3、5、…、n/2 的 n/2 数组中的 1 形式一样。所以我们可以写出如下公式 −
solve(n)=2*solve(n/2)-1[when n is even] solve(n)=2*solve(n-1/2)+1[when n is odd]
基本条件是 solve(1) = 1。
例
#include<iostream>
using namespace std;
int deleteSecondElement(int n) {
if (n == 1)
return 1;
if (n % 2 == 0)
return 2 * deleteSecondElement(n / 2) - 1;
else
return 2 * deleteSecondElement(((n - 1) / 2)) + 1;
}
int main() {
int n = 5;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
n = 10;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
}输出
Remaining Element: 3 Remaining Element: 5
更新于： 01-11-2019
398 次查看
广告