C ++でn個の整数の配列の1つおきの要素を削除した後、最後の要素を検索します

1からnまでの整数を含む1つの循環配列があるとします。最初の要素から始まる2つおきの要素を削除した後、リストに残る最後の要素を見つけます。入力が5の場合、配列は[1、2、3、4、5]になります。 1から開始します。2番目の要素を削除すると、次のようになります-

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