- Nov 26 Fri 2021 14:33
-
ITSA_基礎40題:題目12. 遞迴程式練習
- Nov 25 Thu 2021 23:34
-
ITSA_基礎40題:題目10. 輾轉相除法
- Nov 23 Tue 2021 17:19
-
高中生城市解題:e563: 12694 - Meeting Room Arrangement
內容
PSU工程學院設有一個寬敞的會議室，可供教職員工辦活動和開會。會議室的使用必須提前預約。
由於會議室每天有10個小時可用，並且可能有多個活動要使用會議室，因此最佳使用策略是使一天中的活動數量最大化。
假設會議室的可用時間為0到10 (總共10小時)。
給定每個候選活動的開始時間和結束時間，請你寫一個程式來選擇適合會議室的活動(即活動的時間不重疊)，並給出一天可以辦的最大活動數量。
- Nov 23 Tue 2021 16:11
-
高中生城市解題:d418. 00993 - Product of digits
- Nov 23 Tue 2021 15:04
-
高中生程式解題:e611: 11661 - Burger Time
內容
大家都知道，在高速公路上旁都有無數的快餐店。
人們可以輕鬆地買到漢堡包，熱狗，比薩，三明治等等食物。
但是很多時候，問題不是找到餐館而是藥局。一頓豐盛的午餐後，我們通常需要去買胃藥，因為我們年紀大了。
給定高速公路上餐廳和藥局的位置，你想要確定餐廳和藥局之間的最短距離。
- Nov 23 Tue 2021 02:12
-
高中生程式解題:c088: 00516 - Prime Land
Content
在質數國中人們使用以質數為基底的數字系統來表達一個整數。若以我們的觀點來看的話，就是每一個大於1的整數X都用唯一的因數分解的形式來表現。即
X = Pkex * ...... * P1e1 * P0e0
例如：我們的整數40在質數國中以：5 1 2 3來表示。（表示5的1次方乘以2的3次方）
這樣的系統對我們來說實在是不尋常，或者說，有點難。事實上，在質數國中的小朋友需要花好幾年來學習加法和減法，但另一 方面，乘法及除法對他們來說卻是很容易的。現在你的任務就是幫質數國的人寫一個程式對一個數做"減1"的動作，然後輸出結果。當然，輸入輸出都是以質數國 的數字系統來表示（對我們來說也就是因數分解的形式）。
- Nov 21 Sun 2021 20:55
-
高中生程式解題系統 :e529: 00482 - Permutation Arrays
- Nov 21 Sun 2021 03: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; //未找到
}
};
- Nov 19 Fri 2021 16: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);//引入函式
}
};
- Nov 18 Thu 2021 16: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，則此一扇門後即是真正藏有寶藏
- Nov 17 Wed 2021 13:57
-
高中生城市解題:a465: 12405 - Scarecrow
內容
Taso 有一塊條狀的田地。他計劃在下一季種植不同的作物。但是這個地區有很多烏鴉，Taso 怕他們會吃掉這些作物。因此他決定在田地的不同位置放置稻草人。
田地可以用 1 x N 的格子模擬。有些部分是不毛之地無法種植作物。一個稻草人除了所在的格子外也保護其左側及右側緊鄰的格子。
已知田地的描述，要保護所有可用田地最少需要幾個稻草人？
- Nov 17 Wed 2021 12:46
-
貪婪演算法:換錢
貪婪演算法:換錢 1元 5元 10元 50元 100元 500元 1000元 */
#include<iostream>
using namespace std;
int main()
{
int money[7]={1000,500,100,50,10,5,1} ;
int n;
cout<<"請輸入金額\n";
while(cin>>n){
cout<<n<<" = \n"; //單純輸出
for(int i=0;i<7;i++){
cout<<money[i]<<" * "<<n/money[i]<<"\n";
n%=money[i];
}
cout<<"\n";
cout<<"請輸入金額\n";
}
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int money[7]={1000,500,100,50,10,5,1} ;
int n;
cout<<"請輸入金額\n";
while(cin>>n){
cout<<n<<" = \n"; //單純輸出
for(int i=0;i<7;i++){
cout<<money[i]<<" * "<<n/money[i]<<"\n";
n%=money[i];
}
cout<<"\n";
cout<<"請輸入金額\n";
}
return 0;
}
