演算法作業01

1. 本週影片中提到的NP-complete問題有哪些？

1. 0/1有限背包問題
2. 旅行商問題
3. 分區問題
4. 畫廊監視器問題

2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。

最簡單的就是N皇后了
在

$N\times N$的西洋棋棋盤上放上

$N$個皇后棋，
並且要放置在讓它們不會互相攻擊到的位置上，問有幾種擺放方式。
最常見的是

$N=8$，也就是8皇后問題。

圖片來源：https://medium.com/@jamesjessian/solving-the-n-queens-completion-puzzle-ed8924ce8f1c

相關NP-complete證明

https://www-users.york.ac.uk/peter.nightingale/IJCAI2018-nQueens.pdf

下面是我寫的範例程式：

#include <bits/stdc++.h>
using namespace std;

int queen[20],sum,N;

void dfs(int row)
{
    if(row == N)
    {
        sum++;
        return;
    }
    int i,j;
    for(i=1;i<=N;i++)
    {
        for(j=0;j<row;j++)
        {
            if(queen[j]==i || abs(queen[j]-i)==row-j)
            {
                break;
            }
        }
        if(j==row)
        {
            queen[row]=i;
            dfs(row+1);
            queen[row]=0;
        }
    }
}

int main()
{
    sum=0;
    cin>>N;
    dfs(0);
    cout<<sum;
}

輸入是

$N$，代表棋盤邊長以及皇后數量，
輸出是可擺放的方式數量。

如果N=8
輸出會是92
因為有92種擺法

3. 二元搜尋應用：當數字可以重覆

1. 解題思路

把等於也認定為上界之外，
最後找到的

$l$ 就會是答案。

2. 程式碼

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target)
{
    int mid,l=0,r=nums.size()-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(nums[mid]>=target)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return ((nums[l]==target)?l:-1);
}


int main()
{
    vector<int> v={1,3,3,6};
    cout<<search(v,3)<<endl;
    cout<<search(v,2)<<endl;
    v={1,2,3,6,6,6,7,8,9};
    cout<<search(v,6);
}

3. 測試輸出輸入的畫面截圖

4. 花費時間

15分鐘

5. 完成程度

完全自己解出

4. 二元搜尋應用：找數字該插入的位置

1. 解題思路

把3.的程式最後return的地方改成回傳

$l$就可以了，
因為如果要插入的話也是要插入在第一個比他大的那個索引值。

2. 程式碼

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int mid,l=0,r=nums.size()-1;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(nums[mid]>=target)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
};

3. 測試輸出輸入的畫面截圖

4. 花費時間

2分鐘

5. 完成程度

完全自己解出

5. 二元搜尋應用：找到最早出問題的版本

1. 解題思路

在4.的基礎上把判斷條件改成是否為壞版本，
然後把

$(l+r)/2$改成

$(l+(r-l)/2)$，防止int溢位(私心不想用long long)

2. 程式碼

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int mid,l=0,r=n;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(isBadVersion(mid))
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
};

3. 測試輸出輸入的畫面截圖

4. 花費時間

6分鐘

5. 完成程度

完全自己解出

6. 二元搜尋應用：開根號後的整數部分

1. 解題思路

找到第一個大於解的數，然後再減一即可。
(超過份這題逼我用long long，討厭鬼)

2. 程式碼

class Solution {
public:
    int mySqrt(int x) {
        long long l=1,r=x,mid;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(mid*mid>x)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l-1;
    }
};

3. 測試輸出輸入的畫面截圖

4. 花費時間

5分鐘

5. 完成程度

完全自己解出

7. 本週心得

已填