---
# System prepended metadata

title: Algo hw1
tags: [Algorithm]

---

# 演算法作業一

## 1. 本週影片中提到的NP-complete問題有哪些？
1. 0/1 Knapsack Problem (01背包問題)
	- 輸入：
		1. 給你一個物品的集合，此物品的資訊有兩個：價值、重量
		2. 給你背包的最大重量
	- 輸出：
		1. 請找出該背包可裝那些屋品以達到最大價值

2. Traveling Salesperson Problem (旅行推銷員問題)
	- 輸入：
		1. 給你一個圖，邊上紀錄著長度
	- 輸出：
		1. 請找出一個路徑可以拜訪所有頂點，且長度最短
3. Partition Problem (分組問題)
	- 輸入：
		1. 給你一個集合
	- 輸出：
		1. 找出兩個子集合：$A,B$，使$\Sigma A=\Sigma B \space such \space that \space A\land B=\emptyset$ 

4. Art Gallery Problem (畫廊問題)
	- 輸入：
		1. 給你一個地圖
	- 輸出：
		1. 用最少的守衛使該地圖的每個角落都可以被照料到

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

1. Minesweeper(踩地雷)
	- 輸入：給定一個n*n的方格並有若干個地雷，包含一些已經打開的數字和可能會有的一些已經標記的地雷
	- 輸出：找出所有沒有地雷的方格

## 二分搜尋法
:::info
###### 防止mid溢位的對策
- python的int是無上限的，所以我們可以用
	```python= 
	mid = (left+right) // 2
	```
	**但是**，C++的整數存在範圍限制，所以可以用
	```c++=
	int mid = left + (right-left) / 2;
	```
- 證明如下
	As we know, $left<=right<=INT\_MAX$
	$left+(right-left) = right <= INT\_MAX$
	and, $left+(right-left)/2 <=left+(right-left) = right <= INT\_MAX$
	Q.E.D.
:::
### implement by recusive
```c++=
int binarySerch(vector<int>& arr, int target,int left,int right){
	int mid = left + (right - left) / 2;
	if (left > right)
		return -1;
	
	if (arr[mid]==target)
		return mid;
	else if (arr[mid]>target)
		return binarySerch(arr, target,left,mid-1);
	else
		return binarySerch(arr, target,mid+1,right);
}
```
### implement by iterative
```c++=
int binarySerch(vector<int>& arr,int target){
	int left  = 0;
	int right = arr.size()-1;
	
	while (left<=right){
		int mid = left + (right - left) / 2;
		
		if (arr[mid] == target){
			return mid;
		}
		else if (arr[mid]>target){
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	return -1;
}
```


## 3. 二元搜尋應用：當數字可以重覆
- 程式碼
```c++=
#include<bits/stdc++.h>
using namespace std;

int lowerBound(vector<int>& arr,int target){
	int left  = 0;
	int right = arr.size()-1;

	int ans = -1;
	while (left<=right){
		// prevent overflow
		int mid = left + (right-left)/2;
		if (arr[mid] < target){
			left = mid+1;
		}
		else{
			right = mid-1;
			ans = mid;
		}
	}
	if (ans == -1){
		return ans;
	}
	return arr[ans]==target?ans:-1;
}

int main(){
	vector<int> arr;
	int n;
	cout<<"How many Element?\n";
	cin>>n;
	while (n--){
		int element;
		cin>>element;
		arr.push_back(element);
	}
	int target;
	cin>>target;
	cout<<lowerBound(arr,target)<<endl;
	return 0;
}
```
- 執行結果
![image](https://hackmd.io/_uploads/Syt1AhHhT.png)
- Program Language：C++
- 花費時間：15分鐘
- 完成程度：靠自己
- 思路：
	1. 先對vector進行二分搜
	2. 有個問題：因為有重複值所以要找最小index的地方，因此可以使用lowerBound的概念找出
	3. 這時我們可以使用ans存取，如果`target == arr[mid]`我就用ans存取，並向左邊查詢還有沒有該值

## 4. 二元搜尋應用：找數字該插入的位置
[leetcode 35](https://leetcode.com/problems/search-insert-position/)
- 程式碼：
```c++=
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return upperBound(nums,target);
    }
private:
    int upperBound(vector<int>& arr,int target){
        int left  = 0;
        int right = arr.size()-1;

        int ans = 0;
        while (left<=right){
            int mid = left + (right - left)/2;

            if (arr[mid] == target){
                return mid;
            }
            else if(arr[mid]>target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
                ans = left;
            }
        } 
        return ans;
    }
};
```
- 執行結果
![image](https://hackmd.io/_uploads/H1QbJur3T.png)
- Program Language：C++
- 花費時間：5分鐘
- 完成程度：靠自己
- 思路：
	1. 跟剛剛那題目很像，只是改成找upperBound而已


## 5. 二元搜尋應用：找到最早出問題的版本
[leetcode 278](https://leetcode.com/problems/first-bad-version/)
- 程式碼
```c++=
class Solution {
public:
    int firstBadVersion(int n) {
        int left  = 1;
        int right = n;

        int ans = -1;
        while (left<=right){
            int mid = left + (right - left)/2;

            if (isBadVersion(mid)){
                ans   = mid;
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return ans;
    }
};
```
- 執行結果
![image](https://hackmd.io/_uploads/SJ1Viqr26.png)
- Program Language：C++
- 花費時間：1分鐘
- 完成程度：靠自己
- 思路：
	1. 可以將版本看成一個序列
		:::success
		###### **以測試資料1為例子，我們可以將版本看成**
		version = [0,0,0,1,1]

		>0：true, 1: false
		:::
	2. 如此一來問題簡化成尋找1，且index最少，和第三題一模模一樣樣


## 6. 二元搜尋應用：開根號後的整數部分
[leetcode 69](https://leetcode.com/problems/sqrtx/)
- 程式碼
```c++=
class Solution {
public:
    int mySqrt(int x) {
        int left  = 1;
        int right = x;

        if (x==1 || x == 0) return x; // Sepcial case

        int ans = 1;
        while (left <= right){
            int mid = left + (right-left)/2;

            if (mid > x/mid){ //In order to prevent mid * mid overflow, I use mid > x/mid
                right = mid - 1; 
            }
            else {
                left = mid + 1;
                ans = mid;
            }
        }
        return ans;
    }
};
```
- 執行結果
![image](https://hackmd.io/_uploads/SyZ-Jor2T.png)
- Program Language：C++
- 花費時間：5分鐘
- 完成程度：大部分靠自己，但有看解答(等等說明)
- 思路：
	~~我本來想用牛頓法後來想說算了好累哈哈~~
	1. 一樣我們可以把他看成一個序列進行搜尋
		:::success
		###### **我們以case 2舉例(case 1太理想了哈)**
		ans = [$1$,$2^2$,$3^2$,$4^2$,$5^2$,$6^2$,$7^2$,$8^2$]
		:::
	2. 則我們要找的答案就是target在ans的lowerBound
	3. 好我查網路的原因來了，我的程式碼就這樣寫
		```c++=
		if (mid*mid > x){ 
            right = mid - 1; 
        }
        else {
            left = mid + 1;
            ans = mid;
        }
		```
		 阿結果就overflow了討厭，所以我去查答案，有一個大師把mid除過去，以防止overflow，讚
		 ```c++=
		if (mid > x/mid){ 
            right = mid - 1; 
        }
        else {
            left = mid + 1;
            ans = mid;
        }
		```


## 7. 本週心得
今天寫了好多二分搜，我以為我二分搜超級熟，結果沒有:<，我比較印象深刻的還是第三題，我記得我有卡了一下，但後來有想到他其實跟lowerBound的概念有點像，結果扣就剛好被我搞出來了好港動。

我其實針對這周比較有問題的是，我要怎麼去評斷該問題是NP完全，我知道P問題跟NP問題差別是，P問題是該問題可再多項式時間答出來，NP問題是我可以在多項式時間驗證出來，但我不太懂NP完全要怎麼判斷，希望老師可以說明一下。