【刷題筆記(編程題)05】另類加法、走方格的方案數、井字棋、密碼強度等級

在這里插入圖片描述

1. 另類加法

給定兩個int A和B。編寫一個函數返回A+B的值，但不得使用+或其他算數運算符。
測試樣例：
1,2
返回：3
示例 1
輸入
輸出

思路1:
二進制0101和1101的相加
0 1 0 1
1 1 0 1
其實就是
不帶進位的結果1000
和進位產生的1010相加
無進位加法： 兩個二進制數異或后得到的結果
就是它們無進位相加的結果
進位： 兩個二進制數按位與后左移1位
就是它們相加的進位結果
在每一輪計算中
利用異或運算符計算不進位部分
利用與運算符和左移運算符計算進位部分
并將進位部分賦值給另一個操作數
直到沒有進位為止
最終，不進位部分的結果即為加法的結果
在這里插入圖片描述

class UnusualAdd {
public:int addAB(int A, int B) {while (B) {int a = A ^ B;int b = (A & B) << 1; A = a;B = b;}return A;}
};

2. 走方格的方案數

請計算n*m的棋盤格子（n為橫向的格子數，m為豎向的格子數）從棋盤左上角出發沿著邊緣線從左上角走到右下角，總共有多少種走法，要求不能走回頭路，即：只能往右和往下走，不能往左和往上走。
注：沿棋盤格之間的邊緣線行走
數據范圍：
輸入描述
輸入兩個正整數n和m，用空格隔開。(1≤n,m≤8)
輸出描述
輸出一行結果
示例 1
輸入
2 2
輸出
6

思路1: 遞歸
本題說的是沿著邊緣線走
而非在格子里面走
第一步可以往右或往下
起始路徑(0, 0)可以選擇沿著
(0+1, 0)和(0, 0+1)的路徑走
而(0+1, 0)和(0, 0+1)是起始路徑(0, 0)的子問題
繼續往下遞歸，用(i, j)表示當前位置
后續限制邊界的向下或向右
因為不能走回頭路
當向下(向右)走到邊界
表示只有向右(向下)這一條路徑可走
即可結束遞歸，無需完全走到右下角
在這里插入圖片描述

#include <iostream>
using namespace std;int scheme(int i, int j, int n, int m)
{if (i == n || j == m)return 1;return scheme(i + 1, j, n, m) + scheme(i, j + 1, n, m);
}int main() {int n, m;while (cin >> n >> m) { cout << scheme(0, 0, n, m) << endl;}return 0;
}

思路2: 動態規劃
用dp[i][j]表示到第 i 行 j 列為止的路徑數
它等于到它左邊的路徑數
加上到它上邊的路徑數的總和
如果是首行或者首列路徑數為1
在這里插入圖片描述
(0, 0)到(0, 1)只有1條路徑
(0, 0)到(1, 0)也只有1條路徑
(0, 0)到(1, 1)的路徑等于
它左邊的路徑加上它上邊的路徑
(0, 0)到(0, 1)的路徑加上(0, 0)到(1, 0)的路徑
1 + 1 = 2

int main() {int n, m;while(cin >> n >> m){vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); //dp[i][j]表示到第i行j列為止的路徑數for(int i = 0; i <= n; i++)for(int j = 0; j <= m; j++){if(i == 0 && j == 0) //起始位置只有一條路徑dp[i][j] = 1;else if(i == 0) //起始行，等于左邊列的路徑dp[i][j] = dp[i][j - 1];else if(j == 0) //起始列，等于上邊行的路徑dp[i][j] = dp[i - 1][j];else //等于左邊加上邊的路徑dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}cout << dp[n][m] << endl;}return 0;
}

3. 井字棋

給定一個二維數組board，代表棋盤，其中元素為1的代表是當前玩家的棋子，0表示沒有棋子，-1代表是對方玩家的棋子。當一方棋子在橫豎斜方向上有連成排的及獲勝（及井字棋規則），返回當前玩家是否勝出。
測試樣例：
[[1,0,1],[1,-1,-1],[1,-1,0]]
返回：true
示例 1
輸入
輸出

思路1:
先判斷兩個對角線
再for循環判斷橫縱

class Board {
public:bool checkWon(vector<vector<int> > board) {if (board[0][0] + board[1][1] + board[2][2] == 3|| board[0][2] + board[1][1] + board[2][0] == 3)return true;for (int i = 0; i < board.size(); i++) {if (board[i][0]+board[i][1]+board[i][2] == 3)return true;if (board[0][i]+board[1][i]+board[2][i] == 3)return true;}return false;}
};

4. 密碼強度等級

密碼按如下規則進行計分，并根據不同的得分為密碼進行安全等級劃分。
一、密碼長度:
5 分: 小于等于4 個字符
10 分: 5 到7 字符
25 分: 大于等于8 個字符
二、字母:
0 分: 沒有字母
10 分: 密碼里的字母全都是小（大）寫字母
20 分: 密碼里的字母符合”大小寫混合“
三、數字:
0 分: 沒有數字
10 分: 1 個數字
20 分: 大于1 個數字
四、符號:
0 分: 沒有符號
10 分: 1 個符號
25 分: 大于1 個符號
五、獎勵（只能選符合最多的那一種獎勵）:
2 分: 字母和數字
3 分: 字母、數字和符號
5 分: 大小寫字母、數字和符號
最后的評分標準:
= 90: 非常安全
= 80: 安全（Secure）
= 70: 非常強
= 60: 強（Strong）
= 50: 一般（Average）
= 25: 弱（Weak）
= 0: 非常弱（Very_Weak）
對應輸出為：
VERY_SECURE
SECURE
VERY_STRONG
STRONG
AVERAGE
WEAK
VERY_WEAK
請根據輸入的密碼字符串，進行安全評定。
注：
字母：a-z, A-Z
數字：0-9
符號包含如下： (ASCII碼表可以在UltraEdit的菜單view->ASCII Table查看)
!"# $KaTeX parse error: Can't use function '\]' in math mode at position 76: …I碼：0x3A~0x40) [\?]?^_` …$ @NoNoN
輸出
VERY_SECURE
說明
樣例的密碼長度大于等于8個字符，得25分；大小寫字母都有所以得20分；有兩個數字，所以得20分；包含大于1符號，所以得25分；由于該密碼包含大小寫字母、數字和符號，所以獎勵部分得5分，經統計得該密碼的密碼強度為25+20+20+25+5=95分。
示例 2
輸入
Jl)M:+
輸出
AVERAGE
說明
示例2的密碼強度為10+20+0+25+0=55分。

思路1:
用好 if 和 else
對每個安全等級進行判斷

#include <iostream>
using namespace std;int passwordLength(string& s) {if (s.size() >= 5 && s.size() <= 7)return 10;else if (s.size() >= 8)return 25;else return 5;
}int passwordLetter(string& s) {bool Capital = false, Lowercase = false;for (int i = 0; i < s.size(); i++) {if (s[i] >= 'A' && s[i] <= 'Z')Capital = true;else if (s[i] >= 'a' && s[i] <= 'z')Lowercase = true;}if (Capital == false && Lowercase == false)return 0;else if (Capital == true && Lowercase == true)return 20;else return 10;
}int passwordFigure(string& s) {int count = 0;for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9')count++;if (count > 1) return 20;}if (count == 0) return 0;else return 10;
}int passwordSymbol(string& s) {int count = 0;for (int i = 0; i < s.size(); i++) {if (s[i] >= 0x21 && s[i] <= 0x2F) count++;else if (s[i] >= 0x3A && s[i] <= 0x40) count++;else if (s[i] >= 0x5B && s[i] <= 0x60) count++;else if (s[i] >= 0x7B && s[i] <= 0x7E) count++;}if (count == 0) return 0;else if (count == 1) return 10;else return 25;
}int passwordAward(int Letter, int Figure, int Symbol) {if (Letter == 20 && Figure >= 10 && Symbol >=10)return 5;else if (Letter == 10 && Figure >= 10 && Symbol >=10)return 3;else if (Letter == 10 && Figure >= 10)return 2;else return 0;
}int main() {string s;cin >> s;int Length, Letter, Figure, Symbol, Award;Length = passwordLength(s);Letter = passwordLetter(s);Figure = passwordFigure(s);Symbol = passwordSymbol(s);Award = passwordAward(Letter, Figure, Symbol);int score = Length + Letter + Figure + Symbol + Award;if (score >= 90) cout << "VERY_SECURE" << endl;else if (score >= 80) cout << "SECURE" << endl;else if (score >= 70) cout << "VERY_STRONG" << endl;else if (score >= 60) cout << "STRONG" << endl;else if (score >= 50) cout << "AVERAGE" << endl;else if (score >= 25) cout << "WEAK" << endl;else if (score >= 0) cout << "VERY_WEAK" << endl;return 0;
}

class password {
public:password(string& s): _pwd(s){}void passwordLength() {if (_pwd.size() >= 5 && _pwd.size() <= 7)_score += 10;else if (_pwd.size() >= 8)_score += 25;else if (_pwd.size() <= 4) _score += 5;}void passwordLetter() {for (auto l : _pwd) {if (isupper(l)) _bigLetter = true;else if (islower(l))_smallLetter = true;}if (_bigLetter && _smallLetter)_score += 20;else if (_bigLetter || _smallLetter ) _score += 10;}void passwordFigure() {int count = 0;for (auto f : _pwd) {if (isdigit(f))  count++;}if (count >= 1) _Figure = true;if (count == 1) _score += 10;else if (count > 1) _score += 20;
}void passwordSymbol() {int count = 0;for (auto c : _pwd) {if (ispunct(c)) count++;}if (count >= 1) _Symbol = true;if (count == 1) _score += 10;else if (count > 1) _score += 25;}void passwordAward() {if (_bigLetter && _smallLetter && _Figure && _Symbol)_score += 5;else if ((_bigLetter || _smallLetter) && _Figure && _Symbol)_score += 3;else if ((_bigLetter || _smallLetter) && _Figure)_score += 2;}void getTotalScore() {passwordLength();passwordLetter();passwordFigure();passwordSymbol();passwordAward();}void _printGrade() {getTotalScore();if (_score >= 90) cout << "VERY_SECURE" << endl;else if (_score >= 80) cout << "SECURE" << endl;else if (_score >= 70) cout << "VERY_STRONG" << endl;else if (_score >= 60) cout << "STRONG" << endl;else if (_score >= 50) cout << "AVERAGE" << endl;else if (_score >= 25) cout << "WEAK" << endl;else if (_score >= 0) cout << "VERY_WEAK" << endl;}
private:string _pwd;int _score = 0;bool _bigLetter = false;bool _smallLetter = false;bool _Figure = false;bool _Symbol = false;
};int main() {string s;while (cin >> s) {password pwd(s);pwd._printGrade();}return 0;
}