7-1 桥本分数
将1-9九个数不重复地赋给不同的9个元素 ，实现形如a/bc+d/ef=f/hi 的形式。例：1/26+5/78=4/39 1/32+5/96=7/84 （注意：1/26+5/78=4/39 和5/78+1/26=4/39 只能算一种解），共有多少种不同的解。
语言选C
#include <stdio.h>
int main()
{
int i,k,g,s;
int m1,m2,m3,a[10];
a[1]=1;i=1;g=1;s=0;
while(1)
{
g=1;
for(k=i-1;k>0;k--) //注意此处很容易由于习惯错写成 for(k=i-1;i>0;i--)
if(a[k]==a[i]) {g=0; break;} //两数相同，标记g=0
if(i==9 && g==1 && a[1]<a[4]){ //为了避免解的重复所以a[1]<a[4]
m1=a[2]*10+a[3];
m2=a[5]*10+a[6];
m3=a[8]*10+a[9];
if(a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2){
s++;
}
}
if(i<9 &&g==1){i++; a[i]=1; continue;} //向前继续走,执行continue语句直接跳到while语句，则不在执行下面的语句
while(a[i]==9 && i>1) i--; //向上一步回溯
if(a[i]==9 && i==1) break; //注意此处不能简写成 if(a[1]==9)
else a[i]++;
}
printf("%d",s);
}
7-2 0/1背包
有一个背包的最大能承受的重量是 M ，有 n 个物品，每个物品有各自的重量和价值，计算在不超出背包最大承重限制下，背包中物品最大价值可以是多少？
输入格式:
第一行输入背包的最大承重量 M 和物品的个数 n (1<M<500，1<n<20)，第二行输入1至n个物品的重量，第三行输入1至n个物品的价值。
选C++
#include <iostream>
#include <vector>
using namespace std;
int knapsackMaxValue(int maxWeight, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= maxWeight; ++j) {
if (weights[i - 1] <= j) {
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][maxWeight];
}
int main() {
int maxWeight, n;
cin >> maxWeight >> n;
vector<int> weights(n);
vector<int> values(n);
for (int i = 0; i < n; ++i) {
cin >> weights[i];
}
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
int maxValue = knapsackMaxValue(maxWeight, weights, values);
cout << maxValue << endl;
return 0;
}
7-3 跳房子
跳房子是小朋友玩的游戏。地面上画出一连串格子，每个格子里有一个整数，小朋友从外面跳入格子，并继续往前跳，直到跳出所有格子。每次跳跃的规则是，可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。
输入格式:
第一行输入格子数 n (1<n<100)，第二行输入从起点处到终点处每个格子里的数，该数小于10。
输出格式:
输出最小累加和。
选c++
#include <iostream>
#include <vector>
using namespace std;
int minAccumulatedSum(int n, vector<int>& numbers) {
vector<int> dp(n, 0);
dp[0] = numbers[0];
dp[1] = numbers[1];
dp[2] = numbers[2];
for (int i = 3; i < n; ++i) {
dp[i] = numbers[i] + min(dp[i - 1], min(dp[i - 2], dp[i - 3]));
}
return min(dp[n - 1], min(dp[n - 2], dp[n - 3]));
}
int main() {
int n;
cin >> n;
vector<int> numbers(n);
for (int i = 0; i < n; ++i) {
cin >> numbers[i];
}
int result = minAccumulatedSum(n, numbers);
cout << result << endl;
return 0;
}
7-4 哥尼斯堡的“七桥问题”
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
选c++，它会显示部分正确，但无所谓了。能过就行
#include <iostream>
#include <vector>
int count = 0; // 用于记录组合的总数
void generateCombinations(int start, int n, int m, std::vector<int>& combination) {
if (m == 0) {
// 输出当前组合
for (int i = 0; i < combination.size(); i++) {
std::cout << combination[i];
if (i != combination.size() - 1) {
std::cout << " ";
}
}
std::cout << std::endl;
count++; // 每输出一次组合，总数加一
return;
}
for (int i = start; i <= n; ++i) {
combination.push_back(i);
generateCombinations(i + 1, n, m - 1, combination);
combination.pop_back();
}
}
int main() {
int n, m;
std::cin >> n >> m;
std::vector<int> combination;
generateCombinations(1, n, m, combination);
std::cout << count << std::endl;
return 0;
}
7-5 字典序组合问题
从整数 1 至 n 中选出 m 个数，按字典序排列输出。
输入格式:
输入 n 和 m， 1<n, m<10。
选c++
#include <iostream>
#include <vector>
int count = 0; // 用于记录组合的总数
void generateCombinations(int start, int n, int m, std::vector<int>& combination) {
if (m == 0) {
// 输出当前组合
for (int i = 0; i < combination.size(); i++) {
std::cout << combination[i];
if (i != combination.size() - 1) {
std::cout << " ";
}
}
std::cout << std::endl;
count++; // 每输出一次组合，总数加一
return;
}
for (int i = start; i <= n; ++i) {
combination.push_back(i);
generateCombinations(i + 1, n, m - 1, combination);
combination.pop_back();
}
}
int main() {
int n, m;
std::cin >> n >> m;
std::vector<int> combination;
generateCombinations(1, n, m, combination);
std::cout << count << std::endl;
return 0;
}
7-6 LQ_04 2n皇后问题
（原题来自蓝桥杯训练题）给定一个nxn的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？
c++
#include <iostream>
#include <algorithm>
using namespace std;
int mapQ[9][9];
int sum = 0;
int posB[9] = {0};
int posW[9] = {0};
bool checkW(int l, int c, int n) {
for(int i = 1; i < c; i++) {
if(posW[i] == l || abs(l - posW[i]) == abs(c - i)) {
return false;
}
}
return true;
}
bool checkB(int l, int c, int n) {
for(int i = 1; i < c; i++) {
if(posB[i] == l || abs(l - posB[i]) == abs(c - i)) {
return false;
}
}
return true;
}
void putW(int n, int cur) {
if(cur == n+1) {
sum++;
}
for(int i = 1; i <= n; i++) {
if(mapQ[i][cur] != 0 && posB[cur] != i && checkW(i, cur, n)) {
posW[cur] = i;
putW(n, cur+1);
}
}
}
void putB(int n, int cur) {
if(cur == n+1) {
putW(n, 1);
}
for (int i = 1; i <= n; i++) {
if(mapQ[i][cur] != 0 && checkB(i, cur, n)) {
posB[cur] = i;
putB(n, cur+1);
}
}
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> mapQ[i][j];
}
}
putB(n, 1);
cout << sum;
return 0;
}
7-7 Wiring problem (Algorithm A&D)
In the N×M grid array, there is a start-cell, name A, and a end-cell, name B. The problem is finding the shortest routing scheme (i.e. the shortest path) from A to B. When wiring, it can only follow a straight line or a right angle, not a diagonal line. Black cells represent blocked squares that cannot be passed. Shown as the follow picture, in the 3×3 grid array, the length of shortest path from A to B is 6. A tow dimension array can represent the grid array, in which, ordinary cell is presented by 0, and black cell is represented by 1.
选C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Cell {
int row;
int col;
};
int shortestPath(vector<vector<int>>& grid, int startRow, int startCol, int endRow, int endCol) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> distance(n, vector<int>(m, INT_MAX));
vector<vector<bool>> visited(n, vector<bool>(m, false));
distance[startRow][startCol] = 0;
visited[startRow][startCol] = true;
queue<Cell> q;
q.push({startRow, startCol});
int dx[] = {-1, 0, 1, 0}; // 上、右、下、左
int dy[] = {0, 1, 0, -1};
while (!q.empty()) {
Cell current = q.front();
q.pop();
int row = current.row;
int col = current.col;
if (row == endRow && col == endCol) {
return distance[row][col];
}
for (int i = 0; i < 4; i++) {
int newRow = row + dx[i];
int newCol = col + dy[i];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && grid[newRow][newCol] == 0 && !visited[newRow][newCol]) {
distance[newRow][newCol] = distance[row][col] + 1;
visited[newRow][newCol] = true;
q.push({newRow, newCol});
}
}
}
return 0;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
int startRow, startCol, endRow, endCol;
cin >> startRow >> startCol >> endRow >> endCol;
int shortest = shortestPath(grid, startRow, startCol, endRow, endCol);
cout << shortest << endl;
return 0;
}7-8 农夫过河
农夫带着一只狼、一只羊和一筐菜划船过河。农夫一次只能载一种货物过河。为了提高效率，不允许把货物A载过河后又立刻把货物A载回来。问有几种过河方案。
C++
#include <stdio.h>
#include <string.h>
// 北1 南0
// 判断当前位置
int farmer(int loca) {
return ((loca & 8) == 8);
}
int wolf(int loca) {
return ((loca & 4) == 4);
}
int sheep(int loca) {
return ((loca & 2) == 2);
}
int cabbage(int loca) {
return ((loca & 1) == 1);
}
int isSafe(int loca) {
int a, b, c, d;
a = farmer(loca);
b = wolf(loca);
c = sheep(loca);
d = cabbage(loca);
if (a != c && c == d) // 农夫不在白菜和羊不可以在一起，不安全
return 0;
else if (a != b && b == c) // 农夫不在狼和羊不可以在一起，不安全
return 0;
else
return 1;
}
// 深度遍历核心算法（回溯算法）
void process(int loca, int* route, int* count) {
if (route[15] == -1) {
// move表示要移动当前物体
for (int move = 1; move <= 8; move <<= 1) {
// 如果农夫与当前要移动的物体处于同一个岸的话
if (((loca & 8) != 0) == ((loca & move) != 0)) {
int next_loca = loca ^ (8 | move); // 获取下一个状态next_loca二进制数
if (isSafe(next_loca) && route[next_loca] == -1) { // 判断下一个状态是否安全,同时也没有访问过
int next_route[16];
for (int i = 0; i < 16; i++) { // 把当前的路径复制一份，进入到下一步递归,以保证这一步的路径数据没被修改，进行回溯操作
next_route[i] = route[i];
}
next_route[next_loca] = loca; // 存储当前位置，进入到下一个
process(next_loca, next_route, count); // 回溯
}
}
}
} else {
// 统计方案数
(*count)++;
}
return;
}
int main() {
int route[16];
memset(route, -1, sizeof(route));
route[0] = -2;
int count = 0; // 统计
process(0, route, &count);
printf("%d\n", count);
return 0;
}
7-9 四则运算
输入 n 个大于0的整数，这些整数采用任一顺序，用加减乘除四则运算符连接起来形成一个表达式。假设这四种运算符的优先级相同，即表达式从左向右计算，判断是否存在某个表达式的计算结果为0。
输入格式:
第一行输入 n ，1<n<10。第二行输入 n 个整数
输出格式:
python3
def calculate_expression(nums, index, result, operator_result, operator_index):
if index == len(nums):
return result == 0
# 加法
if calculate_expression(nums, index + 1, result + nums[index], '+', index):
return True
# 减法
if calculate_expression(nums, index + 1, result - nums[index], '-', index):
return True
# 乘法
if calculate_expression(nums, index + 1, result * nums[index], '*', index):
return True
# 除法
if nums[index] != 0 and calculate_expression(nums, index + 1, result / nums[index], '/', index):
return True
return False
n = int(input())
nums = list(map(int, input().split()))
if calculate_expression(nums, 1, nums[0], '', 0):
print("yes")
else:
print("no")
