数据结构进阶实训一 位运算，优化算法

Data structure advanced training course notes and algorithm exercises
数据结构进阶实训课程笔记和算法练习

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

---

---

题目1

对于一个字节（8bit)的无符号整型变量
求其二进制表示中“1”的个数。要求算法的执行效率尽可能高。

1.1 算法设计思想

用户直接输入一个8位无符号整型常数，并进行用户输入的校验，如果不满足条件，提示用户重新输入，直到输入正确；

将十进制转换为二进制；

持续下面循环8次：

将二进制数模2，结果为1，计数器加1，然后二进制数右移一位；

循环结束，1的个数为计数器值。

1.2 源代码

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>

void main(){
    printf("Please enter an 8-bit unsigned integer constant:");
    char array[8];
    scanf("%s", array);
    int len = strlen(array);
    // 判断用户输入是否是8位无符号整型常量
    // 并判断用户输入是否为二进制
    // 如果长度不为8,或不是二进制数,则重新输入
    while(len!=8 || strspn(array, "01")!=len){
        printf("Your input does not meet the conditions!\n \
        Please enter an 8-bit unsigned integer constant as required:");
        scanf("%s", array);
        len = strlen(array);
    }
    int arrayToInt = strtol(array, NULL, 2);

    //十进制转二进制函数的声明
    int transfer(int x);
    int i=0, num=0;
    for(i; i<len; i++){
        if(transfer(arrayToInt)%2 == 1)
            num++;
        arrayToInt=arrayToInt>>1;
    }
    printf("The number of \"1\" in its binary representation is: %d.\n", num);

    printf("The program will continue to run, press any key to close it.");
    getch();
}

int transfer(int x){
    int i=0;
    int binary = 0b0;
    for(i ; i<x ; i++){
        binary++;
    }
    return binary;
}

1.3 运行情况截图

---

---

题目2

给定一个整数N，N！末尾会有多少个0呢？编写算法计算给定的N！末尾有多少个0？

2.1 算法设计思想

一个数的阶乘末尾有多少0，即判断这个数除以10的余数是否为0，如果为0，则末尾是0。

2.2 源代码

while(factorial>0){
  if(factorial%10==0)
    numOfZero++;
  else
    break;
  factorial = factorial / 10;
}

2.3 运行情况截图

---

---

题目3

求N!的二进制表示中最低位的1的位置。

3.1 算法设计思想

初始化计数器为0；

先把n!化为二进制表示的形式，再把其二进制形式模2，如果结果为0，将其二进制形式右移一位，并且计数器加1；

循环上面的操作，直到模2结果为1，结束循环，计数器即为最后结果。

3.2 源代码

int convert(int x){  // 十进制转二进制
  int binary=0b0, i=0;
  for(i; i<x; i++){
    binary++;
  }
  return binary;
}

void main(){
  int n,factorial=1, i=1, numOfZero=0;
  printf("Please enter an integer and the program will calculate its factorial:");
  scanf("%d", &n);
  for(i ; i<=n; i++){   // 求阶乘
    factorial *= i;
  }
  printf("The factorial of n is %d\n", factorial);
  int binary = convert(factorial);
  while(1){   // 求位置
    numOfZero++;
    if(binary%2==1)
      break;
    binary = binary>>1;
  }
  printf("When representing n! In binary, \
  the position of the lowest bit 1 is (from right to left): %d\n", numOfZero);
}

3.3 运行情况截图

---

---

题目4

对于一个由N个整数组成的数组，设计算法（程序），求出该数组中的最大值和最小值。

4.1 算法设计思想

先判断数组的前两个值，将小的赋给min，将大的赋给max；

循环从数组的下标2开始，将数组下标为2的值记为num，如果num小于min，则将num赋值给min，反之则不变；

如果num大于max，则将num赋值给max，反之则不变；

直到循环结束，max则为最大值，min为最小值。

4.2 源代码

void main(){
  int random, num[20], i=0, max, min;
  printf("Give an array of 20 integers:\n");
  for(i; i<20; i++){    // 使用随机数初始化数组
    random = rand()%100;
    num[i] = random;
    printf("%d  ", num[i]);
  }
  if(num[0]<num[1]){
    max=num[1];
    min=num[0];
  }
  else{
    max=num[0];
    min=num[1];
  }
  i=2;    // 从2开始比较
  for(i; i<20; i++){
    if(num[i]>max)
      max=num[i];
    if(num[i]<min)
      min=num[i];
  }
  printf("\nThe maximum value of the array is: %d", max);
  printf("\nThe minimum value of the array is: %d\n", min);
  system("pause");
}

4.3 运行情况截图

---

---

题目5

快速找出一个数组中所有满足条件的的两个数。（条件：这两个数的和等于一个给定的值sum.）。

5.1 算法设计思想

从第1个数开始循环与后面的数相加，判断结果如果等于给定值sum就输出这两个值；

然后从第2个数开始循环与后面的数相加，以此循环直到把数组遍历完。

5.2 源代码

void main(){
  int sum=100
  int num[20]={41, 67, 34, 0, 69, 24, 78, 58, 62, 64, 5, 45, 81, 27, 61, 91, 95, 42, 27, 36};
  printf("Give an array of 20 integers:\n");
  int i=0, j;
  for(i; i<20; i++){
    printf("%d  ", num[i]);
  }
  printf("\n");
  i=0;
  for(i; i<20; i++){
    int add=num[i];
    j= i+1;
    for(j; j<20; j++){
      if(add+num[j]==sum){
        printf("The sum of the two numbers found is 100, which are: %d and %d.\n", add, num[j]);
      }
    }
  }
  system("pause");
}

5.3 运行情况截图

---