CoffeeLin

暴力算法

2023-12-19

a. 最接近点对问题的BF算法实现

#include <stdio.h>
#include <float.h>
#include <math.h>

struct Point {
	int x, y;
};

float calculateDistance(struct Point p1, struct Point p2) {
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

void closestPair(struct Point points[], int n) {
	float minDistance = FLT_MAX;
	int a, b;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			float distance = calculateDistance(points[i], points[j]);
			if (distance < minDistance) {
				minDistance = distance;
				a = i;
				b = j;
			}
		}
	}
	printf("最近点对的距离是 %f", minDistance);
	printf("最近点对是<%d,%d>,<%d,%d>", points[a].x, points[a].y, points[b].x, points[b].y);
}

int main() {
	struct Point points[] = {
		{8,-15},{9,-29},{29,-28},{-30,-13},{-3,45},{-33,-12},{-7,35},{47,-45},{43,-10},{24,-6},
	};
	int n = sizeof(points) / sizeof(points[0]);

	closestPair(points, n);
    
	return 0;
}

b. Hamilton回路问题的BF算法实现

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。

#include <stdio.h>  
#include <stdbool.h>  

#define V 4 // 图的顶点数  

void printSolution(int path[]);  

//pos:当前位置，表示当前在构建路径的过程中所处的位置
//函数用于检查在当前路径构建的情况下，是否可以安全地将指定的顶点 v 加入到路径中
bool isSafe(int v, bool graph[V][V], int path[], int pos) {  
	if (graph[path[pos - 1]][v] == 0) {  //前一个顶点到当前顶点是否有边相连
		return false;  
	}  
	
	for (int i = 0; i < pos; i++) {  
		if (path[i] == v) {  //检查路径中是否已经包含了顶点 v
			return false;  
		}  
	}  
	
	return true;  
}  

bool hamiltonianCycleUtil(bool graph[V][V], int path[], int pos) { //构建哈密尔顿回路的路径
	//最后一个点
	if (pos == V) {  
		if (graph[path[pos - 1]][path[0]] == 1) {  //最后一个点和起始点有连接，即构成回路
			return true;  
		} else {  
			return false;  
		}  
	}  
	
	for (int v = 1; v < V; v++) {  
		if (isSafe(v, graph, path, pos)) {  
			path[pos] = v;  
			
			if (hamiltonianCycleUtil(graph, path, pos + 1)) {  //构建哈密尔顿回路的路径
				return true;  
			}  
			
			path[pos] = -1; // 否则回溯
		}  
	}  
	
	return false;  
}  

bool hamiltonianCycle(bool graph[V][V]) {  
	int path[V];  
	for (int i = 0; i < V; i++) {  
		path[i] = -1;  
	}  
	
	path[0] = 0; // 从第一个顶点开始  
	
	if (!hamiltonianCycleUtil(graph, path, 1)) {  
		printf("No Hamiltonian Cycle exists");  
		return false;  
	}  
	
	printSolution(path);  
	return true;  
}  

void printSolution(int path[]) {  
	printf("Hamiltonian Cycle found: \n");  
	for (int i = 0; i < V; i++) {  
		printf("%d ", path[i]);  
	}  
	printf("%d", path[0]); //完成循环  
	printf("\n");  
}  

int main() {  
	bool graph[V][V] = {  
		{0, 1, 1, 1},
		{1, 0, 1, 1},
		{1, 1, 0, 1},
		{1, 1, 1, 0}
	};  
	
	hamiltonianCycle(graph);  
	return 0;  
}

Linux期末题目&源码

2023-12-19

Linux实验

1.文件处理

描述：小林想写一个程序实现文件操作，他想将任意数目的源文件复制到一个目标文件中，若目标文件没有则创建。出现错误时需要显示相应的错误。
用法示例：./mycp a.txt dest.txt ./mycp a.txt b.txt dest.txt
请编程解决。

//mycp.c
#include <stdio.h>
#include <stdlib.h>

#define BUFFER_SIZE 1024

void copyFilesToDestination(int numFiles, char *sourceFiles[], char *destinationFile) {
    // 打开目标文件，使用 "w" 模式，如果文件不存在则创建
    FILE *destFile = fopen(destinationFile, "w");

    // 检查目标文件是否成功打开
    if (destFile == NULL) {
        perror("Error opening destination file");
        return;
    }

    // 为复制设置缓冲区
    char buffer[BUFFER_SIZE];

    // 循环遍历每个待复制的文件
    for (int i = 0; i < numFiles; ++i) {
        // 打开当前待复制的源文件
        FILE *sourceFile = fopen(sourceFiles[i], "r");

        // 检查源文件是否成功打开
        if (sourceFile == NULL) {
            perror("Error opening source file");
            fclose(destFile);
            return;
        }

        // 逐块复制源文件到目标文件
        size_t bytesRead;
        while ((bytesRead = fread(buffer, 1, sizeof(buffer), sourceFile)) > 0) {
            fwrite(buffer, 1, bytesRead, destFile);
        }

        // 关闭当前源文件
        fclose(sourceFile);
    }

    // 关闭目标文件
    fclose(destFile);
    
    // 显示复制成功的消息
    printf("%d file(s) copied successfully to %s\n", numFiles, destinationFile);
}

int main(int argc, char *argv[]) {
    // 检查命令行参数数量
    if (argc < 3) {
        fprintf(stderr, "Usage: %s file1 file2 ... fileN destinationFile\n", argv[0]);
        return 1;
    }

    // 计算待复制文件的数量
    int numFiles = argc - 2;

    // 调用复制文件的函数
    copyFilesToDestination(numFiles, argv + 1, argv[argc - 1]);

    return 0;
}

2.进程通信

模拟随机密钥，现有8个用户，用户id分别为1,2,3,4,5,6,7,8。程序A定时一次性为8个用户生成一串长度为8的随机数作为密钥并显示用户id和对应密钥，并将其传送给程序B。程序B模拟用户登录，输入用户id和密钥正确才能返回“登录成功”。采用共享内存传递数据，写出程序代码。

//"mmap.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <string.h>
#include <time.h>

#define KEY_LENGTH 8
#define NUM_USERS 8
#define SHM_NAME "/myshm"

//a.c
#include "mmap.h"
#include <time.h>

// 定义用户结构体
struct User {
	int id;
	char key[KEY_LENGTH + 1];
};

int main() {
	// 打开或创建共享内存对象
	int shm_fd = shm_open(SHM_NAME, O_CREAT | O_RDWR, 0666);
	if (shm_fd == -1) {
		perror("shm_open");
		exit(EXIT_FAILURE);
	}

	// 设置共享内存对象的大小
	if (ftruncate(shm_fd, NUM_USERS * sizeof(struct User)) == -1) {
		perror("ftruncate");
		exit(EXIT_FAILURE);
	}

	// 将共享内存对象映射到进程地址空间
	struct User *users = (struct User *)mmap(NULL, NUM_USERS * sizeof(struct User), PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);
	if (users == MAP_FAILED) {
		perror("mmap");
		exit(EXIT_FAILURE);
	}

	// 生成一次性的随机数作为密钥，并写入用户信息到共享内存
	srand(time(NULL)); // 初始化随机数种子

	while (1) {
		printf("\033c");
		for (int i = 0; i < NUM_USERS; ++i) {
			users[i].id = i + 1;
			for (int j = 0; j < KEY_LENGTH; ++j) {
				users[i].key[j] = '0' + rand() % 10; // 生成数字字符
			}
			users[i].key[KEY_LENGTH] = '\0'; // 添加字符串结束符

			// 显示生成的用户ID和密钥
			printf("\x1b[32mUser %d:\x1b[0m Key \x1b[31m%s\x1b[0m\n", users[i].id, users[i].key);
		}
		sleep(10);
	}

	// 解除共享内存映射
	if (munmap(users, NUM_USERS * sizeof(struct User)) == -1) {
		perror("munmap");
	}

	// 关闭共享内存文件描述符
	close(shm_fd);

	return 0;
}

//b.c
#include "mmap.h"

// 定义用户结构体
struct User {
    int id;
    char key[KEY_LENGTH + 1];
};

int main() {
    // 打开共享内存对象
    int shm_fd = shm_open(SHM_NAME, O_RDONLY, 0666);
    if (shm_fd == -1) {
        perror("shm_open");
        exit(EXIT_FAILURE);
    }

    // 将共享内存对象映射到进程地址空间
    struct User *users = (struct User *)mmap(NULL, NUM_USERS * sizeof(struct User), PROT_READ, MAP_SHARED, shm_fd, 0);
    if (users == MAP_FAILED) {
        perror("mmap");
        exit(EXIT_FAILURE);
    }

    // 读取用户信息，并模拟用户登录
    while (1) {
        // 显示用户ID
        printf("Enter the ID for User (1-%d): ", NUM_USERS);
        int entered_id;
        scanf("%d", &entered_id);

        // 检查用户ID的有效性
        if (entered_id < 1 || entered_id > NUM_USERS) {
            printf("Invalid ID. Please enter a valid ID (1-%d).\n", NUM_USERS);
            continue;
        }

        // 显示用户对应的密钥
        printf("Enter the key for User %d: ", entered_id);

        // 模拟用户输入
        char entered_key[KEY_LENGTH + 1];
        scanf("%s", entered_key);

        // 比较密钥
        int user_index = entered_id - 1;
        if (strncmp(entered_key, users[user_index].key, KEY_LENGTH) == 0) {
            printf("User %d: Login successful!\n", users[user_index].id);
        } else {
            printf("User %d: Login failed. Incorrect key or ID.\n", users[user_index].id);
        }
    }

    // 解除共享内存映射
    if (munmap(users, NUM_USERS * sizeof(struct User)) == -1) {
        perror("munmap");
    }

    // 关闭共享内存文件描述符
    close(shm_fd);

    return 0;
}

3.线程同步互斥

用线程同步互斥模拟一个回合制游戏：皮卡丘和卡比兽相互对战。皮卡丘的攻击伤害是5，血量是30。卡比兽的攻击伤害是3，血量是50。轮流攻击对方，即同一时间内只能有一只能攻击对方，另一只只能被攻击。假设皮卡丘先发起攻击，试模拟最后谁赢了。

//pokemon.c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
//Pikachu:皮卡丘
//Snorlax：卡比兽
// 定义宝可梦结构体
struct Pokemon {
    const char *name;
    int health;
    int attack;
    sem_t turnSemaphore;
};

// 函数：宝可梦攻击
void attack(struct Pokemon *attacker, struct Pokemon *target) {
    sem_wait(&attacker->turnSemaphore);

    printf("%s attacks %s with damage \033[1;31m%d\033[0m\n", attacker->name, target->name, attacker->attack);
    target->health -= attacker->attack;

    if (target->health <= 0) {
        printf("%s failed!\n", target->name);
    } else {
        printf("%s's health: \033[1;32m%d\033[0m, %s's health: \033[1;32m%d\033[0m\n", target->name, target->health,attacker->name,attacker->health);
    }

    sem_post(&target->turnSemaphore);
}

// 函数：线程函数，模拟宝可梦对战
void *battle(void *args) {
    struct Pokemon *pikachu = (struct Pokemon *)args;
    struct Pokemon *snorlax = (struct Pokemon *)(args + sizeof(struct Pokemon));

    while (pikachu->health > 0 && snorlax->health > 0) {
        attack(pikachu, snorlax);
        sleep(1);  // 等待一段时间，模拟回合结束

        if (snorlax->health <= 0) {
            break;  // 如果 Snorlax 已经被击败，结束对战
        }

        attack(snorlax, pikachu);
        sleep(1);  // 等待一段时间，模拟回合结束
    }

    return NULL;
}

int main() {
    // 初始化宝可梦
    struct Pokemon pikachu = {"Pikachu", 30, 5};
    struct Pokemon snorlax = {"Snorlax", 50, 3};

    // 初始化信号量
    sem_init(&pikachu.turnSemaphore, 0, 1);  // 初始值为1表示皮卡丘先攻击
    sem_init(&snorlax.turnSemaphore, 0, 0);

    // 创建线程
    pthread_t pikachu_thread, snorlax_thread;
    pthread_create(&pikachu_thread, NULL, battle, &pikachu);
    pthread_create(&snorlax_thread, NULL, battle, &snorlax);

    // 等待线程结束
    pthread_join(pikachu_thread, NULL);
    pthread_join(snorlax_thread, NULL);

    // 判断哪只宝可梦赢得了对战
    if (pikachu.health <= 0) {
        printf("Snorlax wins!\n");
    } else {
        printf("Pikachu wins!\n");
    }

    // 销毁信号量
    sem_destroy(&pikachu.turnSemaphore);
    sem_destroy(&snorlax.turnSemaphore);

    return 0;
}

4.网络编程

Hello World

2023-11-05

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment