编程实践课 - 程序设计导论 作业7
题目1：指针（5分）
创建一个名为Praktikum_7/Aufgabe_1的新项目，并在其中创建一个C++源文件zeiger.cpp。
a) 在main函数中定义三个int变量x、y和z，值分别为42、7和-11。然后声明三个指针a、b和c，并初始化这些指针，使a指向x，b指向y，c指向z。（1分）
b) 以表格形式输出声明的变量，格式如下：
--- 任务b)后的输出 ---
地址 内容 引用的值
变量 x 0x7fff0f3d69dc 42
变量 y 0x7fff0f3d69e0 7
变量 z 0x7fff0f3d69e4 -11
指针 a 0x7fff0f3d69e8 0x7fff0f3d69dc 42
指针 b 0x7fff0f3d69f0 0x7fff0f3d69e0 7
指针 c 0x7fff0f3d69f8 0x7fff0f3d69e4 -11
提示：使用空格和制表符（字符：\t）对齐列，例如printf("地址\t内容")。使用%p格式输出内存地址。（1分）
c) 交换指针值，使得之后a指向y，b指向x，然后输出变量。（1分） 限制：在此过程中，不得更改x和y的内容，也不能使用变量x和y本身。不要使用std::swap函数。
d) 用绘图（数字或手绘）说明交换操作。展示交换前和每次赋值后相关变量的状态。（1分）
e) 将变量z的值增加5。 限制：在此过程中，只能使用一个指针变量，不能直接使用变量z本身。（1分） 输出修改后的变量。
题目2：数独（8分）
在这个任务中，您需要实现一个递归的数独解题函数。数独是一个9x9的网格，被划分为3x3的子网格。目标是填充网格，使得每一行、每一列和每个3x3子网格都恰好包含1到9的数字各一次。
首先创建一个新目录Praktikum_7/Aufgabe_2，并在其中添加提供的sudoku.cpp文件。您需要实现以下函数：
a) 实现辅助函数bool naechsterZelle(int (feld)[9][9], int row, int col)，它在给定的网格中找到第一个空单元格（值为0的单元格），并通过row和*col将位置传递给调用函数。如果所有单元格都已填充，则返回false，否则返回true。（2分）
b) 实现辅助函数bool darfEintragen(int (*feld)[9][9], int row, int col, int num)，检查是否可以在给定位置插入数字num，而不会违反数独规则（即同行、同列、同3x3子网格中没有重复数字）。（3分）
c) 实现函数bool loeseSudoku(int (*feld)[9][9])，使用递归方法解决给定的数独谜题。使用模板中的示例测试您的函数。（3分）
解答 题目1实现 (zeiger.cpp)
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
// a) Define variables and initialize pointers
int x = 42, y = 7, z = -11;
int* a = &x;
int* b = &y;
int* c = &z;
// b) Output after subtask b)
cout << "--- Output after subtask b)---" << endl;
printf("%-10s %-18s %-18s %s\n", "", "Address", "Content", "referenced value");
printf("%-10s %-18p %-18d %d\n", "Variable x", (void*)&x, x, x);
printf("%-10s %-18p %-18d %d\n", "Variable y", (void*)&y, y, y);
printf("%-10s %-18p %-18d %d\n", "Variable z", (void*)&z, z, z);
printf("%-10s %-18p %-18p %d\n", "Pointer a", (void*)&a, (void*)a, *a);
printf("%-10s %-18p %-18p %d\n", "Pointer b", (void*)&b, (void*)b, *b);
printf("%-10s %-18p %-18p %d\n", "Pointer c", (void*)&c, (void*)c, *c);
// c) Swap pointer values (a should point to y, b to x)
int* temp = a;
a = b;
b = temp;
cout << endl << "--- Output after subtask c)---" << endl;
printf("%-10s %-18s %-18s %s\n", "", "Address", "Content", "referenced value");
printf("%-10s %-18p %-18d %d\n", "Variable x", (void*)&x, x, x);
printf("%-10s %-18p %-18d %d\n", "Variable y", (void*)&y, y, y);
printf("%-10s %-18p %-18d %d\n", "Variable z", (void*)&z, z, z);
printf("%-10s %-18p %-18p %d\n", "Pointer a", (void*)&a, (void*)a, *a);
printf("%-10s %-18p %-18p %d\n", "Pointer b", (void*)&b, (void*)b, *b);
printf("%-10s %-18p %-18p %d\n", "Pointer c", (void*)&c, (void*)c, *c);
// e) Increase the value of variable z by 5 (using only pointers)
*c += 5; // c points to z, so we increase the value via the pointer
cout << endl << "--- Output after subtask e)---" << endl;
printf("%-10s %-18s %-18s %s\n", "", "Address", "Content", "referenced value");
printf("%-10s %-18p %-18d %d\n", "Variable x", (void*)&x, x, x);
printf("%-10s %-18p %-18d %d\n", "Variable y", (void*)&y, y, y);
printf("%-10s %-18p %-18d %d\n", "Variable z", (void*)&z, z, z);
printf("%-10s %-18p %-18p %d\n", "Pointer a", (void*)&a, (void*)a, *a);
printf("%-10s %-18p %-18p %d\n", "Pointer b", (void*)&b, (void*)b, *b);
printf("%-10s %-18p %-18p %d\n", "Pointer c", (void*)&c, (void*)c, *c);
return 0;
}
题目2代码实现 (sudoku.cpp)
#include <iostream>
using namespace std;
/**
* @brief Finds the next empty cell in a Sudoku grid.
*
* This function searches the provided Sudoku grid for the next cell that is empty (contains a 0).
* If an empty cell is found, the function sets the row and column indices to the position of this cell.
*
* @param grid A pointer to a 9x9 Sudoku grid.
* @param row A pointer to an integer where the row index of the next empty cell will be stored.
* @param col A pointer to an integer where the column index of the next empty cell will be stored.
* @return `true` if an empty cell is found, `false` if the grid is completely filled.
*/
bool nextEmptyCell(int (*grid)[9][9], int* row, int* col) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if ((*grid)[i][j] == 0) {
*row = i;
*col = j;
return true;
}
}
}
return false; // No empty cells found
}
/**
* @brief Checks if a number can be placed in a specific cell of a Sudoku puzzle.
*
* This function checks if the given number `num` can be inserted into the cell at position `(row, col)`
* of the Sudoku puzzle `grid` without violating the Sudoku rules.
*
* @param grid A pointer to a 9x9 Sudoku grid.
* @param row The row of the cell to be checked.
* @param col The column of the cell to be checked.
* @param num The number to be inserted into the cell.
* @return `true` if the number can be inserted into the cell, otherwise `false`.
*/
bool canPlaceNumber(int (*grid)[9][9], int row, int col, int num) {
// Check the row
for (int i = 0; i < 9; i++) {
if ((*grid)[row][i] == num) {
return false;
}
}
// Check the column
for (int i = 0; i < 9; i++) {
if ((*grid)[i][col] == num) {
return false;
}
}
// Check the 3x3 subgrid
int startRow = row - row % 3;
int startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if ((*grid)[startRow + i][startCol + j] == num) {
return false;
}
}
}
return true;
}
/**
* @brief Solves a given Sudoku puzzle recursively.
*
* This function attempts to solve a given Sudoku puzzle by recursively
* placing numbers in empty cells and checking if the placement is valid.
* If a valid solution is found, it returns true. Otherwise, it returns false.
*
* @param grid A pointer to a 9x9 Sudoku grid. Empty cells are marked with 0.
* @return `true` if the Sudoku can be solved, otherwise `false`.
*/
bool solveSudoku(int (*grid)[9][9]) {
int row, col;
// Find the next empty cell
if (!nextEmptyCell(grid, &row, &col)) {
// No more empty cells - the Sudoku is solved
return true;
}
// Try placing numbers from 1 to 9 in the empty cell
for (int num = 1; num <= 9; num++) {
if (canPlaceNumber(grid, row, col, num)) {
// Place the number and continue recursively
(*grid)[row][col] = num;
if (solveSudoku(grid)) {
return true;
}
// Backtracking: If the number doesn't lead to a solution, remove it
(*grid)[row][col] = 0;
}
}
return false; // No number fits in this cell
}
/**
* @brief Displays a Sudoku grid.
*
* This function prints a 9x9 Sudoku grid to the standard output. Each cell
* is separated by a space, and the grid is divided into 3x3 subgrids by vertical and
* horizontal lines.
*
* @param grid A pointer to a 9x9 array representing the Sudoku grid. Each
* element should be an integer between 1 and 9. Cells with values
* outside this range are displayed as '.'.
*/
void printSudoku(int (*grid)[9][9]) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
std::cout << (char)((*grid)[i][j]<=9 && (*grid)[i][j]>=1 ? (*grid)[i][j]+'0' : '.') << " ";
if ((j + 1) % 3 == 0 && j != 8) std::cout << "| ";
}
std::cout << endl;
if ((i + 1) % 3 == 0 && i != 8) {
for (int k = 0; k < 21; ++k) {
std::cout << "-";
}
std::cout << endl;
}
}
}
int main() {
int grid[9][9] = {
{0, 0, 9, 0, 0, 0, 0, 0, 0},
{0, 3, 0, 2, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 8, 4, 0, 5, 1},
{0, 0, 0, 0, 3, 2, 9, 0, 0},
{0, 0, 6, 0, 0, 0, 0, 2, 0},
{0, 8, 0, 0, 0, 0, 5, 7, 0},
{0, 0, 0, 0, 6, 0, 7, 3, 0},
{7, 0, 0, 4, 0, 0, 0, 0, 0},
{4, 0, 5, 0, 0, 0, 0, 9, 0}
};
cout << "Sudoku puzzle:" << endl;
printSudoku(&grid);
if (solveSudoku(&grid)) {
std::cout << endl << "Solution:" << std::endl;
printSudoku(&grid);
return 0;
} else {
std::cout << "No solution found." << std::endl;
return 1;
}
}
题目1 d) 部分的图示说明
Before swap:
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+
| a |---->| x | | b |---->| y | | c |---->| z |
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+
| 42 | | 7 | | -11 |
+-----+ +-----+ +-----+
After "temp = a":
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+ +-------+
| a |---->| x | | b |---->| y | | c |---->| z | | temp |----+
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+ +-------+ |
| 42 | | 7 | | -11 | |
+-----+ +-----+ +-----+ |
|
After "a = b": |
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+ +-------+ |
| a |----------+ | b |---->| y | | c |---->| z | | temp |----+
+-------+ | +-------+ +-----+ +-------+ +-----+ +-------+
| | 7 | | -11 |
| +-----+ +-----+
|
| +-----+
+------->| x |
+-----+
| 42 |
+-----+
After "b = temp":
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+
| a |---->| y | | b |---->| x | | c |---->| z |
+-------+ +-----+ +-------+ +-----+ +-------+ +-----+
| 7 | | 42 | | -11 |
+-----+ +-----+ +-----+
Final state: a points to y, b points to x
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
