题记：若立志投身算法研究，可精研理论算法：动态规划、递归、深度搜索等；若以解决问题为目的，主要为了工作内容，当尝试快而简单的方法，这该是学习的本意。
素数又叫质数（prime number），有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
方案一：匈牙利算法
偶数+偶数=偶数，必不是素数，因此素数只能是奇数+偶数。我们把输入的这一组数分成奇数和偶数，就得到了二分图，在这两组之间用匈牙利算法作匹配。
1.首先我们遍历一遍所有数字，建立他们之间所有可能的联系，便于后面的调整。接下来开始找最优连接方案。
2.每次取奇数p，遍历偶数，判断是否能和奇数组成素数伴侣，如果偶数q没有和别人结成伴侣则建立p和q之间的关系；如果这个偶数q已经和别的奇数k结成伴侣，那么递归查找k的下一位能建立关系的偶数，如果找到了p和q建立关系，如果没有找到，则不改变偶数q和奇数k的关系。
#include <iostream>
#include<vector>
using namespace std;
bool isprime(int i)//判断是否为素数
{
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
return false;
}
return true;
}
bool find(const int & n,vector<vector<bool>> &map,vector<int>& match,vector<bool>&visit)
{
for (int i = 0; i < match.size(); i++)
{
if (!visit[i] && map[i][n])//当前偶数未被访问过并且能和奇数n是素数伴侣
{
visit[i] = true;
if (match[i] == -1 || find(match[i], map, match, visit))//当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
{
match[i] = n;//建立偶数和奇数之间的连接
return true;
}
}
}
return false;
}
int main()
{
int n=0;
while(cin>>n)
{
int k=0;//读取数据
vector<int> even;
vector<int> odd;
int count=0;//匹配对数
while(n--){//逐个输入按奇偶分类
cin>>k;
if(k%2==0){
odd.push_back(k);
}else{
even.push_back(k);
}
}
if(odd.empty()||even.empty()){//奇数或偶数为空则不会有素数伴侣
cout<<count<<endl;
continue;
}
vector<vector<bool>> map(even.size(),vector<bool>(odd.size(),false));
for(int i=0;i<even.size();i++)//建立关系图，找出所有可能的连接
{
for(int j=0;j<odd.size();j++){
if(isprime(even[i]+odd[j])){
map[i][j]=true;
}
}
}
vector<int> match(even.size(),-1);
for (int i = 0; i < odd.size(); i++){
vector<bool> visit(even.size(), false);//建立在当前奇数下对偶数的访问情况
if (find(i, map, match, visit))
{
count++;
}
}
cout << count << endl;
}
return 0;
}
方法二：
也是匈牙利算法，区别在于方法二去掉了了存储偶数和奇数之间关系的图，减少了空间，但是提高了时间复杂度，每次find函数递归遍历的时候都需要重新判断当前两个数是否为素数伴侣。
#include <iostream>
#include<vector>
using namespace std;
bool isprime(int i)//判断是否为素数
{
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
return false;
}
return true;
}
bool find(const int & n,vector<int> &even,vector<int>& match,vector<bool>&visit)
{
for (int i = 0; i < even.size(); i++)
{
if (!visit[i] && isprime(even[i]+n))//当前偶数未被访问过并且能和奇数n是素数伴侣
{
visit[i] = true;
if (match[i] == -1 || find(match[i], even, match, visit))//当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
{
match[i] = n;//建立偶数和奇数之间的连接
return true;
}
}
}
return false;
}
int main()
{
int n=0;
while(cin>>n)
{
int k=0;//读取数据
vector<int> even;
vector<int> odd;
int count=0;//匹配对数
while(n--){//逐个输入按奇偶分类
cin>>k;
if(k%2==0){
odd.push_back(k);
}else{
even.push_back(k);
}
}
if(odd.empty()||even.empty()){//奇数或偶数为空则不会有素数伴侣
cout<<count<<endl;
continue;
}
vector<int> match(even.size(),-1);
for (int i = 0; i < odd.size(); i++){
vector<bool> visit(even.size(), false);//建立在当前奇数下对偶数的访问情况
if (find(odd[i], even, match, visit))
{
count++;
}
}
cout << count << endl;
}
return 0;
}
从左上角开始去遍历这个数独。
对于没有填入的格子（即格子数值为0），我们去枚举1～9每个数字填入，然后根据数独的性质（同行、同列、同一个九宫格不能有相同数字）去判断填入。如果可以成功填完所有格子那么就是找到了答案。找到答案后可以用一个bool变量，然后注意在回溯的地方根据这个变量及时的return，防止已经找到答案后又回溯为0。
对于初始化就有值的格子，我们往右走（列数值加一），那么因为一行只有9个，所以当列走到头的时候，列的值变成0，行的值加1（其实就是换到了下一行的开头）。
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int mp[N][N];//存储数独
bool find_answer_ok;
bool check(int row, int col, int val) { //检验在当前位置填入val后，满足要求与否
//同行
for(int i = 0; i < 9; i++) {
if(mp[row][i] == val) {
return false;
}
}
//同列
for(int i = 0; i < 9; i++) {
if(mp[i][col] == val) {
return false;
}
}
//同一个九宫格
int limit_row = row / 3 * 3 + 3;//九宫格行的终点
int limit_col = col / 3 * 3 + 3;//九宫格列的终点
for(int i = limit_row - 3; i < limit_row; i++) {
for(int j = limit_col - 3; j < limit_col; j++) {
if(mp[i][j] == val) {
return false;
}
}
}
return true;
}
void dfs(int row, int col) { //当前行、列
if(col == 9) {
row++;
col = 0;
}
if(row == 9 && col == 0) {
find_answer_ok = true;
return ;
}
if(mp[row][col] == 0) {
for(int i = 1; i <= 9; i++) {
if(check(row, col, i)) { //check后满足
mp[row][col] = i;
dfs(row, col + 1);
if(find_answer_ok) { //已经找到答案了，直接return
return ;
}
mp[row][col] = 0; //没找到答案，回溯
}
}
} else {
dfs(row, col + 1);
}
}
int main() {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cin >> mp[i][j];
}
}
dfs(0, 0);//起点坐标（0，0）
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cout << mp[i][j] << ' ';
}
cout << endl;
}
return 0;
}
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
|
商品
名称
|
单价
|
数量
|
| A1 | 2 | X |
| A2 | 3 | X |
| A3 | 4 | X |
| A4 | 5 | X |
| A5 | 8 | X |
| A6 | 6 | X |
|
钱币面额
|
张数
|
|
10元
| X |
|
5元
| X |
| 2元 | X |
| 1元 | X |
|
参数名称
|
参数说明
|
类型
|
取值范围
|
|
A1数量
|
商品A1数量
|
整数
|
[0,30]
|
|
A2数量
|
商品A2数量
|
整数
|
[0,30]
|
|
A3数量
|
商品A3数量
|
整数
|
[0,30]
|
|
A4数量
|
商品A4数量
|
整数
|
[0,30]
|
|
A5数量
|
商品A5数量
|
整数
|
[0,30]
|
|
A6数量
|
商品A6数量
|
整数
|
[0,30]
|
|
1元张数
|
面额1元钱币张数
|
整数
|
[0,30]
|
|
2元张数
|
面额2元钱币张数
|
整数
|
[0,30]
|
|
5元张数
|
面额5元钱币张数
|
整数
|
[0,30]
|
|
10元张数
|
面额10元钱币张数
|
整数
|
[0,30]
|
| 命令 | 输出 | 含义 |
| r 6-5-4-3-2-1 4-3-2-1; | S001:Initialization is successful | 初始化成功 |
|
命令
|
输出
|
|
p 10;
|
S002:Pay success,balance=10
|
|
命令
|
输出
|
|
b A1;
|
S003:Buy success,balance=8
|
|
命令
|
输出
|
|
c;
|
1 yuan coin number=0
2 yuan coin number=0
5 yuan coin number=1
10 yuan coin number=0
|
|
查询类别
|
查询内容
|
|
查询商品信息
| |
| 1 | 查询存钱盒信息 |
|
命令
|
输出
|
|
q 0;
|
A1 2 6
A2 3 5
A3 4 4
A4 5 3
A5 8 2
A6 6 0
|
|
命令
|
输出
| |
|
q 1;
|
1 yuan coin number=4
2 yuan coin number=3
5 yuan coin number=2
10 yuan coin number=1
| |
依照说明中的命令码格式输入命令。
输出执行结果
r 22-18-21-21-7-20 3-23-10-6;c;q0;p 1;b A6;c;b A5;b A1;c;q1;p 5;
S001:Initialization is successful
E009:Work failure
E010:Parameter error
S002:Pay success,balance=1
E008:Lack of balance
1 yuan coin number=1
2 yuan coin number=0
5 yuan coin number=0
10 yuan coin number=0
E008:Lack of balance
E008:Lack of balance
E009:Work failure
E010:Parameter error
S002:Pay success,balance=5
算法实现
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<sstream>
using namespace std;
bool cmp(pair<pair<string, int>, int>& a, pair<pair<string, int>, int>& b){ //重载比较
if(a.second != a.second) //优先比较商品数量
return a.second > b.second;
else //再比较商品名字
return a.first.first < b.first.first;
}
class Vending{
private:
vector<int> price = {2, 3, 4, 5, 8, 6}; // 商品价格
int money = 0;
vector<int> goods; //商品数量
vector<int> coins; //零钱数量
public:
void init(string& s){ //初始化函数
money = 0; //初始化投入的钱
s = s.substr(2, s.length() - 2); //去掉前面的r和空格
goods.resize(6);
coins.resize(4);
goods[0] = goods[1] = goods[2] = goods[3] = goods[4] = goods[5] = 0;
coins[0] = coins[1] = coins[2] = coins[3] = 0;
int i = 0;
bool flag = false; //判别是前面部分商品价格还是后面部分零钱盒
for(auto c: s){
if(isdigit(c) && !flag) //数字且是价格
goods[i] = goods[i] * 10 + (c -' 0'); //根据字符计算数字
else if(isdigit(c) && flag) //数字且是零钱
coins[i] = coins[i] * 10 + (c - '0'); //根据字符计算数字
else if(c == ' '){ //遇到空格换成零钱
flag = true;
i = 0;
}
else if(c == '-') //遇到-后移一位商品或零钱
i++;
}
cout << "S001:Initialization is successful" << endl;
}
void pay(string& s){ //投币函数
int num = 0;
for(auto &c: s)
if(isdigit(c)) //只计算数字部分
num = num * 10 + (c - '0'); //一次只投一张
if(num == 1 || num == 2 || num == 5 || num == 10){ //投入合法的币种
if(num > 2 && num > (coins[0] + coins[1] * 2)) //存钱盒中1元和2元面额钱币总额小于本次投入的钱币面额
cout << "E003:Change is not enough, pay fail" << endl;
else if((goods[0] || goods[1] || goods[2] || goods[3] || goods[4] || goods[5]) == 0) //商品全部为0
cout << "E005:All the goods sold out" << endl;
else{ //零钱盒中钱数增加
if(num == 1 || num == 2)
coins[num-1]++;
else if(num == 5)
coins[2]++;
else coins[3]++;
money += num; //投入的总钱数增加
cout << "S002:Pay success,balance=" << money << endl;
}
}
else //不合法币种
cout << "E002:Denomination error" << endl;
}
void buy(string& s){ //购买函数
//检查命令是否是4位，第三位是否为A，第四位是否数字1-6
if(s.length() == 4 && (s[2] == 'A') && (s[3] - '0' < 7) && isdigit(s[3]) && (s[3] != '0')){
if(goods[s[3] - '1'] == 0) //该商品的售罄
cout << "E007:The goods sold out" << endl;
else if(price[s[3] - '1'] > money) //该商品价格大于投入的钱
cout << "E008:Lack of balance" << endl;
else{ //成功购买
money -= price[s[3] - '1']; //投入的钱要减去买的商品
goods[s[3] - '1']--;
cout << "S003:Buy success,balance=" << money << endl;
}
}
else //输入命令不合法，商品不存在
cout << "E006:Goods does not exist" << endl;
}
void back(){//退币函数
int a = 0, b = 0, c = 0, d = 0; //四个币种
if(money == 0) //投入的没有钱了，不用退
cout << "E009:Work failure" << endl;
else{
d = money / 10; //优先退大币额的数量
if(d <= coins[3]){ //10块的钱够退
money = money % 10;
coins[3] -= d;
}
else{ //10块的钱不够退
d = coins[3]; //全部退完
coins[3] = 0;
money -= d * 10; //剩余要退的
}
c = money / 5; //再计算要退的5块钱的数量
if(c <= coins[2]){ //5块的钱够退
money = money % 5;
coins[2] -= c;
}
else{ //5块的钱不够退
c = coins[2]; //全部退完
coins[2] = 0;
money -= d * 5; //剩余要退的
}
b = money / 2; //再计算要退的2块钱的数量
if(b <= coins[1]){ //2块的钱够退
money = money % 2;
coins[1] -= b;
}
else{ //2块的钱不够退
b = coins[1]; //全部退完
coins[1] = 0;
money -= d * 2; //剩余要退的
}
a = money; //再计算要退的1块钱的数量
if(a <= coins[0]){ //1块的钱够退
coins[0] -= a;
money = 0;
}
else{ //1块的钱不够退
coins[0] = 0;
money -= a;
}
cout << "1 yuan coin number=" << a << endl << "2 yuan coin number=" << b << endl << "5 yuan coin number=" << c << endl << "10 yuan coin number=" << d << endl;
}
}
void query(string& s){ //查询函数
if(s[1] == ' ' && s.length() == 3){ //检查查询命令的合法性
if(s[2] == 0){ //类别为0
vector<pair<pair<string, int>, int> > temp;
for(int i = 0; i < 6; i++) //商品信息入vector方便排序输出
temp.push_back(make_pair(make_pair("A" + char(i + 1), price[i]), goods[i]));
sort(temp.begin(), temp.end(), cmp); //按照重载后的比较排序
for(int i = 0; i < 6; i++) //输出
cout << temp[i].first.first << " " << temp[i].first.second << " " << temp[i].second << endl;
}
else if(s[2] == 1){ //类别为1
cout << "1 yuan coin number=" << coins[0] << endl
<< "2 yuan coin number=" << coins[1] << endl
<< "5 yuan coin number=" << coins[2] << endl
<< "10 yuan coin number=" << coins[3] << endl;
}
else
cout << "E010:Parameter error" << endl;
}
else
cout << "E010:Parameter error" << endl;
}
};
vector<string> split(string str, const char c){ //通过字符c分割字符串
vector<string> res;
istringstream iss(str); // 字符串流输入
string temp = "";
while(getline(iss, temp, c)) //根据流输入分割
res.push_back(temp);
return res;
}
int main(){
string s;
while(getline(cin, s)){
Vending sale; //实例化类
vector<string> orders = split(s, ';'); //以;分割字符串
for(auto c: orders){
switch(c[0]){
case 'r': //初始化
sale.init(c);
break;
case 'p': //投币
sale.pay(c);
break;
case 'b': //购买商品
sale.buy(c);
break;
case 'c': //退币
sale.back();
break;
case 'q': //查询
sale.query(c);
break;
}
}
}
return 0;
}