問題描述：
給定下列遞迴函式 :
- 11月 26 週五 202114:33
ITSA_基礎40題:題目12. 遞迴程式練習
問題描述：
給定下列遞迴函式 :
- 11月 25 週四 202123:34
ITSA_基礎40題:題目10. 輾轉相除法
問題描述：
給定二個正整數，利用輾轉相除法求其最大公因數。
給定二個正整數，利用輾轉相除法求其最大公因數。
- 11月 23 週二 202117:19
高中生城市解題:e563: 12694 - Meeting Room Arrangement
內容
PSU工程學院設有一個寬敞的會議室，可供教職員工辦活動和開會。會議室的使用必須提前預約。
由於會議室每天有10個小時可用，並且可能有多個活動要使用會議室，因此最佳使用策略是使一天中的活動數量最大化。
假設會議室的可用時間為0到10 (總共10小時)。
給定每個候選活動的開始時間和結束時間，請你寫一個程式來選擇適合會議室的活動(即活動的時間不重疊)，並給出一天可以辦的最大活動數量。
- 11月 23 週二 202116:11
高中生城市解題:d418. 00993 - Product of digits
內容
給你一個大於等於 0 的整數 N，請你你找到最小的自然數 Q ，使得在 Q 中所有數字（digit）的乘積等於 N 。
例如：N=10, 可以找到Q=25，因為 2*5=10
- 11月 23 週二 202115:04
高中生程式解題:e611: 11661 - Burger Time
內容
大家都知道，在高速公路上旁都有無數的快餐店。
人們可以輕鬆地買到漢堡包，熱狗，比薩，三明治等等食物。
但是很多時候，問題不是找到餐館而是藥局。一頓豐盛的午餐後，我們通常需要去買胃藥，因為我們年紀大了。
給定高速公路上餐廳和藥局的位置，你想要確定餐廳和藥局之間的最短距離。
- 11月 23 週二 202102:12
高中生程式解題:c088: 00516 - Prime Land
Content
在質數國中人們使用以質數為基底的數字系統來表達一個整數。若以我們的觀點來看的話，就是每一個大於1的整數X都用唯一的因數分解的形式來表現。即
X = Pkex * ...... * P1e1 * P0e0
例如：我們的整數40在質數國中以：5 1 2 3來表示。（表示5的1次方乘以2的3次方）
這樣的系統對我們來說實在是不尋常，或者說，有點難。事實上，在質數國中的小朋友需要花好幾年來學習加法和減法，但另一 方面，乘法及除法對他們來說卻是很容易的。現在你的任務就是幫質數國的人寫一個程式對一個數做"減1"的動作，然後輸出結果。當然，輸入輸出都是以質數國 的數字系統來表示（對我們來說也就是因數分解的形式）。
- 11月 21 週日 202120:55
高中生程式解題系統 :e529: 00482 - Permutation Arrays
Content
在許多電腦問題中，必須置換數據陣列。
也就是說，必須以某些指定順序重新排列數組中的數據。
置換任意數據數組的一種方法是使用索引數組指定置換，以指出元素在新數組中的位置。
- 11月 21 週日 202103:18
leetcode:704. Binary Search
C++
/*
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
*/
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int middle=left+((right-left)/2);//防止溢出
if(nums[middle]>target){
right=middle-1;
}
else if(nums[middle]<target){
left=middle+1;
}
else return middle; //找到
}
return -1; //未找到
}
};
/*
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
*/
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int middle=left+((right-left)/2);//防止溢出
if(nums[middle]>target){
right=middle-1;
}
else if(nums[middle]<target){
left=middle+1;
}
else return middle; //找到
}
return -1; //未找到
}
};
- 11月 19 週五 202116:33
leetcode:37. Sudoku Solver
class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++){ //跑直得
for (int j = 0; j < board[0].size(); j++){ //跑橫得
if (board[i][j] != '.') continue; //不是要跑的空格，跑下個迴圈
for (char k = '1'; k <= '9'; k++){
if(isValid(i, j, k, board)){ // (i, j) 位置放k是否合適，若合適的話
board[i][j] = k; //就把數字填上去
if (backtracking(board)) return true; // 如果找到合适立刻返回
board[i][j] = '.'; // 回溯，
}
}
return false; // 9個數字都不行，那么就返回false
}
}
return true; // 跑完全不沒有返回false，就是找到答案了
}
/*-----------------------------------------------------------------*/
bool isValid(int row, int col, char val, vector<vector<char>>& board){
//判斷橫的
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
//判斷直的
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
//判斷小框框內9格是否重複
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);//引入函式
}
};
private:
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++){ //跑直得
for (int j = 0; j < board[0].size(); j++){ //跑橫得
if (board[i][j] != '.') continue; //不是要跑的空格，跑下個迴圈
for (char k = '1'; k <= '9'; k++){
if(isValid(i, j, k, board)){ // (i, j) 位置放k是否合適，若合適的話
board[i][j] = k; //就把數字填上去
if (backtracking(board)) return true; // 如果找到合适立刻返回
board[i][j] = '.'; // 回溯，
}
}
return false; // 9個數字都不行，那么就返回false
}
}
return true; // 跑完全不沒有返回false，就是找到答案了
}
/*-----------------------------------------------------------------*/
bool isValid(int row, int col, char val, vector<vector<char>>& board){
//判斷橫的
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
//判斷直的
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
//判斷小框框內9格是否重複
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);//引入函式
}
};
- 11月 18 週四 202116:30
高中生程式競賽:d547: 4. 秘密(secrets)
內容
傳說 17 世紀著名的海盜船長基德曾將搶來一筆巨額財產藏匿在某無名小島上的洞穴中。因為是筆龐大的財富，所以在他死後，世界各地的寶藏探險家都想找到他寶藏的藏匿之處。但傳說因為基德船長怨靈的詛咒，進入洞穴的人都難逃一死，至今還沒有人活著出來過！因為恐懼，慢慢的大家不再提起這批寶藏，而寶藏的謎一直延續到現在。
傑克船長是一知名的寶藏探險家，至今已經找到許多傳說中藏匿的寶藏。某一天，傑克在酒吧裡因緣際會地得到這筆寶藏的藏寶圖，藏寶圖上除了揭露寶藏的所在地外還有一串由 0 與 1 組成的奇怪數字串。傑克船長於是根據藏寶圖率領他的船員順利地找到這無名的小島並進入洞穴中，最後抵達寶藏藏匿的地點。但他們卻發現藏匿寶藏的地點有無數道門，而每一扇門上都有一串奇怪的數列(包含 0 與 1 以外的其他整數值，整數之間有空格間隔)。而從白骨遍地的情景來推斷，這些門之中可能只有一扇門中有真正的寶藏，只有找對那扇門才能順利取得寶藏；而若開錯門，可能會引來殺身之禍！
傑克船長幾經推敲，終於發現門上的數列跟藏寶圖上的 0、1 數字串有某種關連，於是他將解法教給他的船員，要他們找出正確的門是哪一扇門。聰明的你(妳)，請幫助傑克船長的船員，寫一組程式算出看看哪一扇門後才是真正藏有寶藏，使他們能順利地取得寶藏！
例如，有 3 扇門，門上的數字串如下： 藏寶圖上提示密碼為：
27 13 45 57 30 0 1 0 1
3 7 21 30 81
20 42 61 123 145
解法過程
- 先解第一扇門的數字串 27 13 45 57 30
- 由後往前(即右往左)推算，最後兩個數字先比大小，後面大於等於前面則為 1，反之為 0
- 30 < 57→ 0
- 接著後兩個數字相減的值取絕對值跟第三個數字比大小，若大於等於第三個數字為 1，反之為 0
- 30–57 = -27，取絕對值為 27 < 45 → 0
- 以此類推，若前面已無數字可比，則結束
- 57–45 = 12 < 13 → 0
- 45–13 = 32 > 27 → 1
- 所以 27 13 45 57 30 對應的 0、1 數字串為 1 0 0 0
- 同樣推算出第二串與第三串數字對應的 0、1 數字串
- 3 7 21 30 81 → 1 1 1 1
- 20 42 61 123 145 → 0 1 0 1
- 三扇門的數字串中唯一與提示密碼 0 1 0 1 符合者為 20 42 61 123 145，則此一扇門後即是真正藏有寶藏
