数据结构进阶实训课程笔记和算法练习

查看源码


题目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 运行情况截图