首页 > 编程语言 >C语言第九周课——经典算法

C语言第九周课——经典算法

时间:2024-11-12 15:51:09浏览次数:3  
标签:arr 周课 元素 素数 C语言 算法 查找 数组 printf

目录

一、冒泡法排序

1.1原理

1.2代码实现(以升序排序为例) 

1.3逻辑 

1.4分析

二、二分法查找

2.1原理

2.2代码实现 

2.3逻辑

2.4算法效率分析

三、素数判断

3.1原理

3.2代码实现

3.3逻辑

3.4分析


一、冒泡法排序

1.1原理

  • 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
  • 这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端(升序排序的情况下),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。

1.2代码实现(以升序排序为例) 

#include<stdio.h>
// 定义数组长度
#define SIZE 3
int main()
{
    int arr[SIZE];
    int i;

    // 从控制台输入数字到数组
    printf("请输入%d个整数:\n", SIZE);
    for (i = 0; i < SIZE; i++)
    {
        scanf("%d", &arr[i]);
    }

	int n = SIZE;
	int h, j, temp;
    for (h = 0; h < n - 1; h++)
    {
        for (j = 0; j < n - h - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 交换元素
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    // 输出排序后的数组
    printf("排序后的数组为:\n");
    for (i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
	printf("\n");
    return 0;
}

1.3逻辑 

在这段代码中:

 
  • main函数里,首先通过循环和scanf函数从控制台接收用户输入的数字,并存储到数组arr中。
  • 然后通过两层循环来对输入的数组进行冒泡排序。
  • 最后再通过循环将排序后的数组元素输出到控制台。

1.4分析

  1. 时间复杂度分析
    • 最好情况:当输入的数组已经是有序的情况下,冒泡排序只需要进行一轮比较,没有元素交换操作。此时时间复杂度为,其中n是数组的长度。
    • 最坏情况:当输入的数组是逆序的情况下,需要进行n-1轮比较,每一轮比较的次数逐渐减少,总的比较次数是,时间复杂度为。
    • 平均情况:时间复杂度也是,因为在平均情况下,数组元素的无序程度介于最好情况和最坏情况之间。
  2. 空间复杂度分析
    • 冒泡排序是一种就地排序算法,它只需要一个额外的临时变量temp来交换元素的位置,所以空间复杂度为。这意味着它在排序过程中不需要额外的大量存储空间,只需要对原始数组进行操作即可。

二、二分法查找

2.1原理

二分查找(Binary Search),也叫折半查找,是一种在有序数组中查找特定元素的高效算法。它的基本思想是:

 
  • 每次比较中间元素与目标元素的值。
  • 如果中间元素的值等于目标元素的值,那么就找到了目标元素,查找结束。
  • 如果中间元素的值大于目标元素的值(因为是降序数组),则目标元素可能在数组的左半部分,所以下一次查找在左半部分继续进行。
  • 如果中间元素的值小于目标元素的值,则目标元素可能在数组的右半部分,下一次查找就在右半部分继续进行。
 

通过不断地将查找范围缩小一半,直到找到目标元素或者确定目标元素不存在为止。

2.2代码实现 

#include <stdio.h>
// 定义数组长度
#define SIZE 10
int main()
{
    int arr[SIZE] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int target;

    // 从控制台输入要查找的目标数字
    printf("请输入要查找的数字:\n");
    scanf("%d", &target);

    int left = 0;
    int right = SIZE - 1;
    int result = -1; // 先假设未找到,赋值为 -1

    while (left <= right)
    {
        // 计算中间元素的索引
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
        {
            result = mid;
            break; // 找到目标元素,退出循环
        }
        else if (arr[mid] < target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    if (result!= -1)
    {
        printf("目标数字 %d 在数组中的索引为 %d\n", target, result);
    }
    else
    {
        printf("未找到目标数字 %d\n", target);
    }

    return 0;
}

2.3逻辑

① 头文件包含

这行代码引入了标准输入输出头文件stdio.h,使得程序能够使用printfscanf等函数来进行控制台的输入输出操作。

②数组定义与初始化

  • 首先通过#define指令定义了一个常量SIZE来表示数组的长度,这里设置为10

  • main函数内部,定义并初始化了一个名为arr的整数数组,数组元素按照降序排列,从101。这个数组是后续进行二分查找的对象。

③目标数字输入

  • 定义了一个整型变量target,用于存储用户从控制台输入的要查找的目标数字。

  • 通过printf函数输出提示信息,引导用户输入数字,然后使用scanf函数从控制台读取用户输入的整数,并将其存储到target变量中。

④二分查找逻辑

  • 首先初始化了三个整型变量:

    • left:用于表示查找范围的左边界,初始化为0,即数组的起始索引。

    • right:表示查找范围的右边界,初始化为SIZE - 1,也就是数组的最后一个元素的索引。

    • result:用于存储最终查找结果的索引,初始化为-1,表示先假设目标数字未找到。

  • 然后进入一个while循环,只要left小于等于right,就说明查找范围还有效,继续进行查找操作:

    • 在每次循环中,先通过公式mid = left + (right - left) / 2计算出当前查找范围的中间元素的索引mid。这个公式的目的是为了避免整数溢出问题(相比于直接使用(left + right) / 2)。

    • 接着通过if - else if - else语句来比较中间元素arr[mid]与目标元素target的大小关系:

      • 如果arr[mid]等于target,说明找到了目标元素,将mid赋值给result,并通过break语句退出循环。

      • 如果arr[mid]小于target,由于数组是降序排列的,所以目标元素应该在当前中间元素的左边,因此将right更新为mid - 1,缩小查找范围到左半部分。

      • 如果arr[mid]大于target,则目标元素应该在当前中间元素的右边,所以将left更新为mid + 1,缩小查找范围到右半部分。

⑤查找结果输出

  • 根据result变量的值来判断是否找到目标数字。如果result不等于-1,说明找到了目标数字,通过printf函数输出目标数字及其在数组中的索引;如果result等于-1,则表示未找到目标数字,同样通过printf函数输出相应的提示信息。不过这里代码最后输出提示信息时有个小错误,printf("未找到目标数字 %d\n", darget);应该是printf("未找到目标数字 %d\n", target);,即把错误的darget修正为target

2.4算法效率分析

二分查找算法的时间复杂度为O(log n),其中n是数组的长度。在每次循环中,查找范围都会缩小一半,所以经过对数级别的次数就能找到目标元素(如果存在的话)或者确定其不存在。相比于简单的顺序查找(时间复杂度为),二分查找在处理大型有序数组时效率更高。

 

总体而言,这段代码实现了一个基本的二分查找功能,但需要注意修正输出提示信息时的拼写错误以确保代码的正确性。

三、素数判断

3.1原理

素数是指一个大于 1 且除了 1 和它自身外,不能被其他自然数整除的数。

①素数的定义及判断依据

根据素数的定义,要判断一个数n是否为素数,需要检查它是否能被 2 到n - 1之间的任何数整除。如果在这个范围内都不能被整除,那么n就是素数;反之,如果能被其中某个数整除,那么n就不是素数。

②程序实现思路

本程序通过两层循环来实现对 1 到 100 之内素数的判断:

  • 外层循环负责遍历 1 到 100 之间的每一个整数,从 2 开始(因为 1 不是素数),依次对每个数进行素数判断操作。

  • 对于外层循环遍历到的每一个整数,内层循环用于具体检查该数是否能被 2 到它自身减 1 之间的数整除。通过内层循环的检查结果来确定该数是否为素数。

3.2代码实现

#include <stdio.h>
int main()
{
    int i, j;

    printf("1到100之内的素数有:\n");

    // 遍历1到100的数字
    for (i = 2; i <= 100; i++)
    {
        // 假设当前数字i是素数
        int isPrime = 1;

        // 检查i是否能被2到i-1之间的数字整除
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                // 如果能被整除,说明不是素数,标记为0
                isPrime = 0;
                break;
            }
        }

        // 如果isPrime为1,说明是素数,输出该数字
        if (isPrime == 1)
        {
            printf("%d ", i);
        }
    }

    printf("\n");

    return 0;
}

3.3逻辑

在这个程序中:

  • main函数中,首先定义了两个整型变量ij,分别用于外层循环和内层循环的计数。
  • 通过printf函数输出提示信息,表示接下来要输出 1 到 100 之内的素数。
  • 然后是外层循环for (i = 2; i <= 100; i++),它会从 2 开始,每次递增 1,直到 100 为止,依次遍历这个范围内的每一个整数。对于每一个遍历到的整数i,都要进行是否为素数的判断。
 
  • 外层循环for (i = 2; i <= 100; i++)用于遍历从 2 到 100 的每一个整数。因为 1 不是素数,所以从 2 开始遍历。
  • 对于每一个要判断的整数i,首先在内层循环之前假设它是素数,通过设置isPrime = 1来表示。
  • 内层循环for (j = 2; j < i; j++)用于检查当前整数i是否能被 2 到i - 1之间的任何一个整数整除。如果能被整除(即i % j == 0),那么就说明i不是素数,此时将isPrime标记为 0,并通过break语句跳出内层循环,因为一旦确定不是素数就不需要再继续检查了。
  • 最后,当内层循环结束后,如果isPrime的值仍然为 1,就说明i是素数,通过printf函数输出该数字。

3.4分析

这种判断素数的方法虽然简单直观,但效率相对较低。对于每一个要判断的数n,都需要从 2 到n - 1进行遍历检查,其时间复杂度大致为O(n的2次方)(这里的n是要判断的数的范围,在本程序中是 100)。因为对于每个数都要进行n - 1次左右的除法运算来判断是否能被整除。

 

在实际应用中,如果要判断更大范围的数是否为素数,通常会采用更高效的算法,比如埃拉托斯特尼筛法等,这些算法可以大大提高判断素数的效率。

标签:arr,周课,元素,素数,C语言,算法,查找,数组,printf
From: https://blog.csdn.net/qq_58156721/article/details/143714930

相关文章

  • 初识C语言2
    选择语句如果你好好学习,校招时拿到一个好offer,走上人生巅峰。如果你不学习,毕业等于失业,回家卖红薯。这就是选择!循环语句有些事必须一直做,比如写csdn,比如大家每天都要吃饭、喝水三种循环语句:while语句,for语句,do-while语句(我后面写csdn会详细讲)函数函数的特点就是简......
  • PTA-C语言-数组-字符串转换成十进制整数
    题目:输入一个以#结束的字符串,本题要求滤去所有的非十六进制字符(不分大小写),组成一个新的表示十六进制数字的字符串,然后将其转换为十进制数后输出。如果在第一个十六进制字符之前存在字符“-”,则代表该数是负数。输入格式:输入在一行中给出一个以#结束的非空字符串。输出格式:......
  • C语言入门到精通(第六版)——第十四章
    14、文件    文件是一组相关数据的有序集合,是程序设计中的一个重要概念。通常情况下,使用计算机主要是在使用文件。要进行数据处理,往往也需要通过文件来完成。14.1、文件概述    文件是一组相关数据的有序集合,这个数据集有一个名称,叫做文件名。    ......
  • 代码随想录算法训练营第十一天|LeetCode150.逆波兰表达式求值、239.滑动窗口最大值、3
    前言打卡代码随想录算法训练营第49期第十一天 φ(゜▽゜*)♪首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目在学......
  • PTA-C语言-一维数组-出生年
    题目:以上是新浪微博中一奇葩贴:“我出生于1988年,直到25岁才遇到4个数字都不相同的年份。”也就是说,直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求,自动填充“我出生于y年,直到x岁才遇到n个数字都不相同的年份”这句话。输入格式:输入在一行中给出出生年份y和目......
  • 【24年新算法故障诊断】基于FVIM-DBN四向量优化深度置信网络的故障诊断(Matlab代码,评估
    本文采用四向量优化算法(FVIM,2024年新算法)优化深度置信网络DBN的超参数,形成FVIM-DBN故障诊断模型,以进一步提升其在数据分类任务中的性能。深度置信网络(DBN)是经典强大的深度神经网络,是一种具有多个隐藏层的前馈深度神经网络。它由若干堆叠的受限玻尔兹曼机(RestrictedBolt......
  • 排序算法 -堆排序
    文章目录1.堆排序(HeapSort)1.1简介1.2堆排序的步骤1.3堆排序C语言实现1.4时间复杂度1.5空间复杂度1.堆排序(HeapSort)1.1简介堆是一种特殊的完全二叉树,分为最大堆(MaxHeap)和最小堆(MinHeap)。在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个......
  • 用c语言来计算素数和
    #include<stdio.h>intisPrime(intnum){  if(num<2){    return0;//小于2的数不是素数  }  for(inti=2;i*i<=num;i++){    if(num%i==0){      return0;    }  }  return1;......
  • 基础数据结构【c语言版】之 “图” 详细讲述
    别忘了请点个赞+收藏+关注支持一下博主喵!!!1. 图的定义和术语1.1图的定义**图(Graph)**是由顶点(Vertex)和边(Edge)组成的一个集合,可以表示顶点之间的关系。通常,图可以表示为G=(V,E)G=(V,E)G=(V,E),其中:VVV是顶点集合,表示图中的所有顶点。EEE是边集合,表示图中顶点之间的连接......
  • 【HAProxy05】企业级反向代理HAProxy调度算法之静态算法与动态算法
    HAProxy调度算法HAProxy通过固定参数balance指明对后端服务器的调度算法,该参数可以配置在listen或backend选项中。HAProxy的调度算法分为静态和动态调度算法,但是有些算法可以根据不同的参数实现静态和动态算法相互转换。官方文档:http://cbonte.github.io/haproxy-dcon......