Python | 习题

统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int CountX(LNode* HL,ElemType x){
  //定义一个计数器，初始为0
  int count = 0;
  //定义一个指针，指向单链表的第一个结点
  LNode* p = HL->next;
  //遍历单链表，直到遇到空指针为止
  while(p != NULL){
    //如果当前结点的值等于给定值x，那么计数器加一
    if(p->data == x){
      count++;
    }
    //指针后移，指向下一个结点
    p = p->next;
  }
  //返回计数器的值
  return count;
}

设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个c语言算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//假设线性表用数组a表示，长度为n，划分的关键字为Ki
void partition(int a[], int n, int Ki) {
  //定义两个指针i和j，分别指向数组的头和尾
  int i = 0;
  int j = n - 1;
  //循环直到i和j相遇
  while (i < j) 
  {
    //从左向右找到第一个大于等于Ki的元素
    while (i < j && a[i] < Ki) 
    {
      i++;
    }
    //从右向左找到第一个小于Ki的元素
    while (i < j && a[j] >= Ki) 
    {
      j--;
    }
    //如果找到了，交换两个元素的位置
    if (i < j) 
    {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  //最后，i指向的位置就是划分的界限
}

2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//假设链表的结点定义如下
typedef struct node {
  int data; //数据域
  struct node *next; //指针域
} node;

//生成集合C=A∩B的算法
node *intersection(node *A, node *B) {
  //创建一个空的链表C
  node *C = NULL;
  //创建一个指针p指向A的头结点
  node *p = A;
  //循环遍历A的每个结点
  while (p != NULL) {
    //判断p的数据是否在B中出现
    if (is_in(p->data, B)) {
      //如果是，将p的数据插入到C的尾部
      C = insert_tail(p->data, C);
    }
    //将p指向下一个结点
    p = p->next;
  }
  //返回C
  return C;
}

//判断一个元素是否在一个链表中出现的辅助函数
int is_in(int x, node *L) {
  //创建一个指针q指向L的头结点
  node *q = L;
  //循环遍历L的每个结点
  while (q != NULL) {
    //如果q的数据等于x，返回1（真）
    if (q->data == x) {
      return 1;
    }
    //将q指向下一个结点
    q = q->next;
  }
  //如果没有找到，返回0（假）
  return 0;
}

//将一个元素插入到一个链表的尾部的辅助函数
node *insert_tail(int x, node *L) {
  //创建一个新的结点s，将数据域赋值为x，指针域赋值为NULL
  node *s = (node *)malloc(sizeof(node));
  s->data = x;
  s->next = NULL;
  //如果L为空，直接返回s作为新的链表
  if (L == NULL) {
    return s;
  }
  //否则，创建一个指针r指向L的头结点
  node *r = L;
  //循环找到L的尾结点
  while (r->next != NULL) {
    r = r->next;
  }
  //将s链接到L的尾部
  r->next = s;
  //返回L
  return L;
}

水仙花数

1
2
3
4
5
6
for flower in range(100, 1000):
    a = flower // 100  # 百位数字是flower除以100，然后向下取整
    b = flower // 10 % 10  # 十位数字是flower除以10，向下取整然后再除以10取余
    c = flower % 10  # 个位数字是flower除以10再取余
    if flower == a ** 3 + b ** 3 + c ** 3:
        print(flower)

求和

1
2
3
4
5
6
sum1 = 0
i = 1
while(i <= 100):
    sum1 += i
    i += 1
print("sum1 = ", sum1)

斐波那契数列

1
2
3
4
5
6
7
x1, x2 = 0, 1
i = 1
print(x1, end=' ')
while i <= 20:
    print(x2, end=' ')
    x1, x2 = x2, x1 + x2
    i += 1

找质数更好的办法

1
2
3
4
5
num = []
for i in range(200, 301):
  if all(i % m != 0 for m in range(2, i)):
    num.append(i)
print(num)

最大公约数和最小公倍数

1
2
3
4
5
6
7
8
9
10
x, y = input("输入两个比较值，用逗号隔开").split(',')
Min = int(min(x, y))
Max = int(max(x, y))
Gys = 1
for i in range(1, Min + 1):
    if Max % i == 0 and Min % i == 0:
        Gys = i
print("最大公约数为：%d" % Gys)
Gbs = Min * Max / int(Gys)
print("最小公倍数为：%d", Gbs)

阶乘求和

1
2
3
4
5
6
7
8
n = int(input("请输入一个正整数："))
sum = 0
for i in range(1, n + 1):
  factorial = 1
  for j in range(1, i + 1):
    factorial *= j
  sum += factorial
print("阶乘求和为：", sum)

递归求1到100的和

1
2
3
4
5
6
7
8
def sumn(n):
    if n > 0:
        return n + sumn(n-1)
    else:
        return 0


print(sumn(100))

递归求回文数

1
2
3
4
5
6
7
8
9
10
11
def HuiWen(s):
    if len(s) < 2:
        return True
    if s[0] != s[-1]:
        return False
    return HuiWen(s[1:-1])


for i in range(1000, 2000):
    if HuiWen(str(i)):
        print(i, end=",")