學編程最重要的是學思想！！！

這些題都是嘗試去找目標數所在位置，而不是去模擬每一次程序

目錄：

約瑟夫

LC 390.消除游戲

約瑟夫

簡單約瑟夫

題目鏈接：OnlineJudge

目錄

約瑟夫

簡單約瑟夫

復雜約瑟夫

一、遞回寫法

二、迭代寫法

思路：n 的范圍足夠小，所以我們直接模擬

記錄出圈人數out，記錄報數count，通過陣列的狀態判斷是否出圈a[105]，走到了哪個位置i

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    int out,count,a[105],i;
    memset(a,-1,sizeof(a));
    out=0; count=0; i=s;
    while(out<n)
    {
        for(;i<=n;i++)
        {
            if(a[i]) count++;
            if(count==m){
                printf("%3d",i); count=0; out++; a[i]=0;
            }
        }
        i=1;
    }
    return 0;
}

復雜約瑟夫

題目鏈接：力扣

思路：n的范圍太大了，所以我們要想辦法簡化演算法或者找規律

約瑟夫環——公式法（遞推公式）

它的思路相當于，每一次淘汰就把所有人重新編號，勝利者的編號每一次都往前移動m個單位，

拓展：迭代和遞回的理解和區別

一、遞回寫法

class Solution {
public:
    int f(int n,int m){
                if(n==1) return 0;
                else return (f(n-1,m)+m)%n;
            }
    int lastRemaining(int n, int m) {
            int x;
            x=f(n,m);
            return x;
    }
};

二、迭代寫法

class Solution {
public:
    int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }
};

迭代是建立在遞推公式上的，如果遞回超時或者是想要求得最優解，可以考慮將遞回改成迭代

LC 390.消除游戲

題目鏈接：??????https://leetcode-cn.com/problems/elimination-game/

本題與約瑟夫環類似，但又有區別，（疑問：解決約瑟夫環的最優方法是什么？）

不可能把每一個數列出來，然后一次一次地去模擬，所以我們要想辦法進行簡化

目錄

一、自己的思路

二、簡化演算法

AC代碼

三、遞回寫法

一、自己的思路

通過自己的觀察：

1.每執行一次操作后，剩下的數為等引數列

2.不管n為多少，執行3次后，就只剩下一個數了（×）執行次數：?log2?n?+1

3.n為奇數的時候，會刪去末尾的數；n為偶數的時候，不會刪去末尾的數

自己有兩個思路：

1.草稿紙上推出公式（x）

2.簡化演算法

二、簡化演算法

正確的思路：

每次洗掉后，引數的變化是這樣的：

d->2d

n->n/2

a0=a0或a0=a0+d

程式最優解的時間復雜度可達到O(logn)

我們把它當做等引數列，等引數列的第一項也就是最后一項就是答案

AC代碼

class Solution {
public:
    int lastRemaining(int n) {
        int loop_cnt=0; //用來判斷是從左到右還是從右到左
        int a0=1,d=1;
        while(n!=1)
        {
            if(n%2!=0)
                a0=a0+d;
            else
            {
                bool left_to_right = (loop_cnt%2==0);
                if(left_to_right) //左往右
                    a0=a0+d;
                else
                    a0=a0;
            }
            n/=2;
            d*=2;
            loop_cnt++;
        }
        return a0;
    }
};

當然可以寫得更簡單一點：

class Solution {
public:
    int lastRemaining(int n) {
        int a0 = 1, d = 1;
        bool left_to_right = true;
        while(n > 1)
        {
            if(left_to_right || n % 2 == 1)
                a0 += d;
            
            n /= 2;
            d *= 2;
            left_to_right = ! left_to_right;
        }
        return a0;
    }
};

三、遞回寫法

作者：daydayUppp

因為每次往下遞回 , 資料規模減少 一半 , 所以 時間復雜度 為 : O(logn)

class Solution {
public:
    int help(int n,bool L2R) {
        // L2R = true 從左到右
        if(n == 1) return 1;// 最小子問題
        if(L2R) return 2 * help(n / 2,!L2R);// 左到右
        //  1 2 3 4 5 6 7 8
        //    2   4   6   8
        // 2*(1   2   3   4)  

        // 右到左
        // 奇數長度的情況
        if(n & 1) return 2 * help(n / 2,!L2R);
        //  1 2 3 4 5 6 7
        //    2   4   6  
        // 2*(1   2   3  )  
        // 偶數長度的情況
        return help(n / 2,!L2R) * 2 - 1;
        //   1 2 3 4 5 6 7 8
        //   1   3   5   7
        // 2*(1   2   3   4) - 1  
    }
    int lastRemaining(int n) {
        return help(n,true);
    }
};

LeetCode里面還有很多變態的解法，這里就不研究了，