###### tags: `演算法`
# 演算法作業HW1
## 1.本週影片中提到的NP-complete問題有哪些？

- 0/1 Knapsack problem
- Traveling salesperson problem
- partition problem
- Art gallery problem
## 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。
- 採地雷
- 因為我們要知道這個格子安不安全，要先知道整格盤面的狀況，幾乎是把整個盤面還沒開的格子檢查一遍，就是暴力解，在條件充足下用數字去做比對，如果未知的方塊中沒有地雷，就表示安全，如果一行出現121這個數字表示具有唯一解，地雷都在兩個1的旁邊，出現1221地雷只會出現在2的旁邊，還有其他的例如212、2112、211112、2111112、122221，在已知條件不足下只能用猜測的。
- 輸入:找出具有唯一解的組合
- 輸出:標示出所有地雷
## 二元搜尋法-Leecode704(自己練習)
1.程式碼

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

            return -1;
 }
                };

2.圖片
3.花費時間:50分鐘(4)完成程度:GOOLE觀念自己在理解寫程式。
## 3.二元搜尋應用：當數字可以重覆
1.程式碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int search(vector<int>& nums, int target)
{

    int left=0;
    int right=nums.size()-1;
    while(left <= right)
    {
        int mid=int((left+right)/2);


        if(target>nums[mid])
            left=mid+1;
        else if(target<=nums[mid])

            right=mid-1;//解題關鍵
    }
    if(nums[left]==target)
    {
        return left;//當N未在數列中則輸出>N的最小index
    }

    return -1;
}
int main() {
    vector<int> nums = {1,3,3,6};
    cout << search(nums, 2) ;
    }

2.圖片

3.花費30分鐘(4)完成程度:跟同學討論，程式部分自己完成
## 4. 二元搜尋應用：找數字該插入的位置
1.程式碼

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

            right=mid-1;
    }

    return left;
    }
};
 

2.圖片

3.花費時間:1hr
4.完成狀態:用紙筆找出規律理解
## 5. 二元搜尋應用：找到最早出問題的版本

1.程式碼

class Solution {
public:
    int firstBadVersion(int n) 
    {
    int left=1;
    int right=n;
    int mid;
    while(right>left)//等於會無限循環
    {
        mid=left+((right-left)/2); //防止溢位
        if(isBadVersion(mid))
        {
           right=mid; 
            
        }
        else
        {
            left=mid+1;
        }
    }
    return left;        
    }
};

2.圖片

3.花費時間:1hr
4.因為一些BUG找不出來發現是溢位的問題，參考第三題
## 6. 二元搜尋應用：開根號後的整數部分

1.程式碼

#include<iostream>
using namespace std;
int intsqrt(int x)
{
    long int left=1;
    long int right=x;
    while(left<=right)
    {
        long int mid=left+(right-left)/2;
        if(mid*mid<x)
        {
            left=mid+1;
        }
        else if(mid*mid>x)
        {
            right=mid-1;
        }
        else
            return (int)mid;
    }
    if(left*left>x)//解決非完全平方數left會停留在>X的平方數
    {
        return(int)(left-1);
    }
    else
        return(int)left;//多餘
}
int main()
{
    int x;
    cin>> x;
    int y;
    y=intsqrt(x);
    cout<<y<<endl;
}

2.圖片

3.花費時間:50分鐘
4.完成狀況:有GOOLE並且已經學會。
## 7.心得感想
這次作業雖然題目的難度都是簡單，但是好像是因為太久沒寫程式了，有一點生疏，花了一整個下午，課程部分都還聽得懂，寫完的確更了解二元搜尋法如何運作跟應用，一開始看到四題星期二要交很緊張，怕來不及，好險這四題都有關聯，因為之前在寫UVA的時候卡題都是可以卡一整天的，我自己本身寫程式方面較弱，很多東西都要比別人學的還來的久，希望下次題目可以提早公布!