資料結構
網路
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 次檢視
廣告