#include<stdio.h>
double QH(int n) {
double s = 0;
double k = 1;
double m = 1;
for (int i = 1; i <= n; i++) {
k*= i;
m*= (2 * i + 1);
s += k/m;
}
return s+1;
}
int main(void)
{
int n;
scanf("%d", &n);
printf("%.10lf\n", QH(n));
return 0;
}
第4关：阶乘数列
#include<stdio.h>
//编写函数
/*********Begin*********/
/*********End**********/
int main()
{
int a,b,x;
scanf("%d",&x);
long long jiecheng=1, sum=0;
for (a=1;a<=x;a++)
{
for (b = 1;b <= a;b++)
{
jiecheng*= b;
}
sum+=jiecheng;
jiecheng = 1;
}
printf("%lld",sum);
}
第5关：亲密数
#include <stdio.h>
int main()
{
int a, i, b, n;
for (a = 1; a < 3000; a++)
{
for (b = 0, i = 1; i <= a / 2; i++ )
{
if(! (a % i))
b += i;
}
for (n = 0, i = 1; i <= b/2; i++)
{
if(! (b % i))
n += i;
}
if(n == a && a < b)
printf("(%d,%d)", a, b);
}
return 0;
}
第6关：公约公倍数
#include<stdio.h>
int main()
{
long x, y, z, m, n;
scanf("%ld%ld", &x, &y);
m = x, n = y;
if(x>0&&y>0)
{
while (y != 0)
{
z = x%y;
x = y;
y = z;
}
printf("%ld ", x);
printf("%ld", m*n / x);}
else
printf("Input Error");
}
程序设计部分 指针（一）
第1关：指针的使用
#include <iostream>
using namespace std;
void Max(int *a, int *b, int *c)
{
/********** Begin **********/
// 比较a和b的值，如果a大于b，则交换它们的值
if (*a > *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 比较a和c的值，如果a大于c，则交换它们的值
if (*a > *c) {
int temp = *a;
*a = *c;
*c = temp;
}
// 比较b和c的值，如果b大于c，则交换它们的值
if (*b > *c) {
int temp = *b;
*b = *c;
*c = temp;
}
/********** End **********/
}
第2关：指针运算
#include <iostream>
using namespace std;
void Reverse(int *start,int *end)
{
/********** Begin **********/
while (start < end) // 当start指针小于end指针时继续交换
{
// 交换start和end指向的值
int temp = *start;
*start = *end;
*end = temp;
// 移动指针
start++; // start指针向右移动
end--; // end指针向左移动
}
/********** End **********/
}
第3关：指针与数组
#include <iostream>
using namespace std;
void Split(int *arr,int len)
{
/********** Begin **********/
int left = 0; // 用于记录0应该放置的位置
for (int i = 0; i < len; i++) // 遍历数组
{
if (arr[i] == 0) // 如果当前元素是0
{
// 交换arr[i]和arr[left]的值
int temp = arr[i];
arr[i] = arr[left];
arr[left] = temp;
left++; // 移动left指针
}
}
/********** End **********/
}
程序设计部分 指针（二）
第1关：字符串与指针
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
void Shift(char *str,int k);
char m[100];
int len=0;
void Shift(char *str, int k) {
int len = strlen(str);
if (len == 0) return;
k = k % len;
char temp[len + 1];
strcpy(temp, str + k);
strcpy(temp + len - k, str);
temp[len] = '\0';
cout << temp << endl;
}
第2关：指针与二维数组
#include <iostream>
using namespace std;
void Add()
{
/********** Begin **********/
int rows, cols;
cin >> rows >> cols; // 读取矩阵的行数和列数
int matrix1[rows][cols];
int matrix2[rows][cols];
int result[rows][cols];
// 读取第一个矩阵的内容
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cin >> matrix1[i][j];
}
}
// 读取第二个矩阵的内容
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cin >> matrix2[i][j];
}
}
// 使用指针遍历两个矩阵并逐元素相加
int *p1 = &matrix1[0][0];
int *p2 = &matrix2[0][0];
int *pResult = &result[0][0];
for (int i = 0; i < rows * cols; i++) {
*pResult = *p1 + *p2; // 计算对应元素的和
p1++; // 移动指针到下一个元素
p2++;
pResult++;
}
// 输出结果矩阵
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
/********** End **********/
}
程序设计部分 指针（三）
第1关：指针作为函数参数
#include <iostream>
using namespace std;
void Sum(const int *arr,int len)
{
/********** Begin **********/
if (len == 0) {
cout << 0 << endl; // 如果数组长度为0，直接输出0
return;
}
int max_value = arr[0]; // 假设第一个元素是最大值
int sum = 0; // 初始化总和为0
// 遍历数组，找到最大值
for (int i = 0; i < len; i++) {
if (arr[i] > max_value) {
max_value = arr[i];
}
}
// 遍历数组，累加所有元素的值，但排除最大值
for (int i = 0; i < len; i++) {
if (arr[i] != max_value) {
sum += arr[i];
}
}
// 输出结果
cout << sum << endl;
/********** End **********/
}
第2关：指针作为函数返回值
#include <iostream>
using namespace std;
/********** Begin **********/
int* Read(int *len)
{
// 读取数组长度
cin >> *len;
// 动态分配数组
int *arr = new int[*len];
// 读取数组内容
for (int i = 0; i < *len; i++) {
cin >> arr[i];
}
// 返回数组指针
return arr;
}
/********** End **********/
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
typedef int tid_t;
typedef unsigned char uint8_t;
typedef void thread_action_func (struct thread *t, void *aux);
typedef bool list_less_func (const struct list_elem *a,
const struct list_elem *b,
void *aux);
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))
enum thread_status
{
THREAD_RUNNING, /* Running thread. */
THREAD_READY, /* Not running but ready to run. */
THREAD_BLOCKED, /* Waiting for an event to trigger. */
THREAD_DYING /* About to be destroyed. */
};
struct list_elem
{
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
};
struct list
{
struct list_elem head; /* List head. */
struct list_elem tail; /* List tail. */
};
struct list mylist;
/* Inserts ELEM just before BEFORE, which may be either an
interior element or a tail. The latter case is equivalent to
list_push_back(). */
void
list_insert (struct list_elem *before, struct list_elem *elem)
{
elem->prev = before->prev;
elem->next = before;
before->prev->next = elem;
before->prev = elem;
}
/* Returns the beginning of LIST. */
struct list_elem *
list_begin (struct list *list)
{
return list->head.next;
}
/* Returns LIST's tail.
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
struct list_elem *
list_end (struct list *list)
{
return &list->tail;
}
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
struct list_elem *
list_next (struct list_elem *elem)
{
return elem->next;
}
/* Initializes LIST as an empty list. */
void
list_init (struct list *list)
{
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}
/* Inserts ELEM at the end of LIST, so that it becomes the
back in LIST. */
void
list_push_back (struct list *list, struct list_elem *elem)
{
list_insert (list_end (list), elem);
}
struct thread
{
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
uint8_t *stack; /* Saved stack pointer. */
int priority; /* Priority. */
struct list_elem allelem; /* List element for all threads list. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
//此处为后添加的链表元素
struct list_elem myelem; /* List element. */
/* Owned by thread.c. */
unsigned magic; /* Detects stack overflow. */
};
/*
创建 5 个 thread 结构体，为每个结构体的 tid 字段依次赋值为第二个参数数组 mytid 中的对应数值，并依次将其插入到第一个参数list 中，插入过程中要求使用自定义的字段 myelem 作为链表元素挂载到 list 中。
*/
void myinsert(struct list *list,tid_t mytid[5])
{
list_init(list);
for(int i=0;i<5;i++)
{
/***begin 补全以下代码***/
struct thread *new_thread; // 定义一个指向 thread 结构体的指针
new_thread = (struct thread *)malloc(sizeof(struct thread)); // 使用 malloc 分配内存
if (new_thread == NULL) {
printf("Memory allocation failed\n");
exit(1); // 如果分配失败，退出程序
}
new_thread->tid = mytid[i]; // 为 tid 字段赋值
list_push_back(list, &new_thread->myelem); // 将新创建的 thread 结构体的 myelem 字段插入到链表中
/**end**/
}
}
第2关：通用链表的首地址计算
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
typedef int tid_t;
typedef unsigned char uint8_t;
typedef void thread_action_func (struct thread *t, void *aux);
typedef bool list_less_func (const struct list_elem *a,
const struct list_elem *b,
void *aux);
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))
enum thread_status
{
THREAD_RUNNING, /* Running thread. */
THREAD_READY, /* Not running but ready to run. */
THREAD_BLOCKED, /* Waiting for an event to trigger. */
THREAD_DYING /* About to be destroyed. */
};
struct list_elem
{
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
};
struct list
{
struct list_elem head; /* List head. */
struct list_elem tail; /* List tail. */
};
struct list mylist;
/* Inserts ELEM just before BEFORE, which may be either an
interior element or a tail. The latter case is equivalent to
list_push_back(). */
void
list_insert (struct list_elem *before, struct list_elem *elem)
{
elem->prev = before->prev;
elem->next = before;
before->prev->next = elem;
before->prev = elem;
}
/* Returns the beginning of LIST. */
struct list_elem *
list_begin (struct list *list)
{
return list->head.next;
}
/* Returns LIST's tail.
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
struct list_elem *
list_end (struct list *list)
{
return &list->tail;
}
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
struct list_elem *
list_next (struct list_elem *elem)
{
return elem->next;
}
/* Initializes LIST as an empty list. */
void
list_init (struct list *list)
{
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}
/* Inserts ELEM at the end of LIST, so that it becomes the
back in LIST. */
void
list_push_back (struct list *list, struct list_elem *elem)
{
list_insert (list_end (list), elem);
}
struct thread
{
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
uint8_t *stack; /* Saved stack pointer. */
int priority; /* Priority. */
struct list_elem allelem; /* List element for all threads list. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
//此处为后添加的链表元素
struct list_elem myelem; /* List element. */
/* Owned by thread.c. */
unsigned magic; /* Detects stack overflow. */
};
void
thread_foreach(thread_action_func *func, void *aux)
{
struct list_elem *e;
for (e = list_begin (&mylist); e != list_end (&mylist);
e = list_next (e))
{
struct thread *t ;
/**** BEGIN 补全以下代码*****/
t = list_entry(e, struct thread, myelem); // 使用 list_entry 宏获取 thread 结构体的首地址
/**** END *****/
func (t, aux);
}
}
第3关：基于函数指针的通用链表操作
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
typedef int tid_t;
typedef unsigned char uint8_t;
typedef void thread_action_func (struct thread *t, void *aux);
typedef bool list_less_func (const struct list_elem *a,
const struct list_elem *b,
void *aux);
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))
enum thread_status
{
THREAD_RUNNING, /* Running thread. */
THREAD_READY, /* Not running but ready to run. */
THREAD_BLOCKED, /* Waiting for an event to trigger. */
THREAD_DYING /* About to be destroyed. */
};
struct list_elem
{
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
};
struct list
{
struct list_elem head; /* List head. */
struct list_elem tail; /* List tail. */
};
struct list mylist;
/* Inserts ELEM just before BEFORE, which may be either an
interior element or a tail. The latter case is equivalent to
list_push_back(). */
void
list_insert (struct list_elem *before, struct list_elem *elem)
{
elem->prev = before->prev;
elem->next = before;
before->prev->next = elem;
before->prev = elem;
}
/* Returns the beginning of LIST. */
struct list_elem *
list_begin (struct list *list)
{
return list->head.next;
}
/* Returns LIST's tail.
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
struct list_elem *
list_end (struct list *list)
{
return &list->tail;
}
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
struct list_elem *
list_next (struct list_elem *elem)
{
return elem->next;
}
/* Initializes LIST as an empty list. */
void
list_init (struct list *list)
{
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}
/* Inserts ELEM at the end of LIST, so that it becomes the
back in LIST. */
void
list_push_back (struct list *list, struct list_elem *elem)
{
list_insert (list_end (list), elem);
}
/* Inserts ELEM in the proper position in LIST, which must be
sorted according to LESS given auxiliary data AUX.
Runs in O(n) average case in the number of elements in LIST. */
void
list_insert_ordered (struct list *list, struct list_elem *elem,
list_less_func *less, void *aux)
{
struct list_elem *e;
for (e = list_begin (list); e != list_end (list); e = list_next (e))
if (less (elem, e, aux))
break;
return list_insert (e, elem);
}
struct thread
{
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
uint8_t *stack; /* Saved stack pointer. */
int priority; /* Priority. */
struct list_elem allelem; /* List element for all threads list. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
//此处为后添加的链表元素
struct list_elem myelem; /* List element. */
/* Owned by thread.c. */
unsigned magic; /* Detects stack overflow. */
};
/* 自定义比较函数 */
bool
mycompare(const struct list_elem *a, const struct list_elem *b, void *aux)
{
/***begin 补全以下代码***/
struct thread *ta = list_entry(a, struct thread, myelem);
struct thread *tb = list_entry(b, struct thread, myelem);
return ta->tid < tb->tid;
/***end***/
}
/*
创建 5 个 tcb 结构体，为每个结构体的 tid 字段赋值为第二个参数数组 mytid 中的数值，并【按序】将其插入到第一个参数list 中，插入过程中要求使用自定义的字段 myelem 作为链表元素挂载到 list 中。
*/
void myinsert(struct list *list,tid_t mytid[5])
{
list_init(list);
for(int i=0;i<5;i++)
{
/***begin 补全以下代码***/
struct thread *t = malloc(sizeof(struct thread));
t->tid = mytid[i];
list_insert_ordered(list, &t->myelem, mycompare, NULL);
/***end***/
}
}
