在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个数字。然后，我们开始于n/2数组中的形式1，该数组仅包含奇数1、3、5…n/2。因此我们可以将公式写成-
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
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短