任务一 算法的定义及特性
一、算法是什么
定义：
- 算法是计算机解决问题的过程。
- 算法是解决特定问题的有效、系统的计算过程
- 算法是解决问题的步骤或方法。
- 算法是解决特定问题的一系列明确步骤和规则。
比喻：就像菜谱告诉你如何做菜一样，算法告诉计算机如何处理数据。
特点：
- 步骤是有限的
- 有效的
- 明确的
- 系统的
二、算法示例
题目：计算1到n的整数和
using System;
using System.Diagnostics;
namespace LearnCSharp
{
internal class Program
{
// 算法1：直接累加法
static int SumByLoop(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++)
{
sum += i;
}
return sum;
}
// 算法2：数学公式法
static int SumByFormula(int n)
{
return n * (n + 1) / 2;
}
// 算法3：递归法
static int SumByRecursion(int n)
{
if (n <= 0) return 0;
return n + SumByRecursion(n - 1);
}
// 主程序入口
public static void Main(string[] args)
{
Console.WriteLine("算法示例：计算1到n的整数和\n");
// 只测试一个值
int n = 1000;
Console.WriteLine($"测试值: n = {n}\n");
// 显示所有算法的计算结果
Console.WriteLine("计算结果：");
Console.WriteLine($"1. 循环累加法: {SumByLoop(n)}");
Console.WriteLine($"2. 数学公式法: {SumByFormula(n)}");
Console.WriteLine($"3. 递归法: {SumByRecursion(n)}");
// 简单的性能对比
Console.WriteLine("\n性能对比（执行时间）：");
var stopwatch = new Stopwatch();
stopwatch.Start();
SumByLoop(n);
stopwatch.Stop();
Console.WriteLine($"循环法: {stopwatch.ElapsedTicks} ticks");
stopwatch.Restart();
SumByFormula(n);
stopwatch.Stop();
Console.WriteLine($"公式法: {stopwatch.ElapsedTicks} ticks");
stopwatch.Restart();
SumByRecursion(n);
stopwatch.Stop();
Console.WriteLine($"递归法: {stopwatch.ElapsedTicks} ticks");
Console.WriteLine("\n算法特点总结：");
Console.WriteLine("1. 循环累加法 - 直观易懂，但效率随n增大而降低");
Console.WriteLine("2. 数学公式法 - 最高效，无论n多大都只需一步计算");
Console.WriteLine("3. 递归法 - 代码简洁，但有栈溢出风险（n太大时）");
Console.WriteLine("\n按任意键退出...");
Console.ReadKey();
}
}
}
三、算法总结
不同算法的特点对比
| 算法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 循环累加 | O(n) | O(1) | 直观，易理解 | n很大时较慢 |
| 数学公式 | O(1) | O(1) | 效率最高 | 需要数学知识 |
| 递归 | O(n) | O(n) | 代码简洁 | 可能栈溢出 |
| LINQ | O(n) | O(1) | 代码易读 | 性能开销 |
关键要点
- 同一问题，多种解法：不同算法都能得到正确结果
- 效率差异：数学公式法最优，循环法次之
- 适用场景：
- 小数据：任何方法都可
- 大数据：优先公式法
- 教学：循环法最直观
算法就是解决问题的具体步骤和策略，选择哪种算法取决于：
- 问题规模
- 性能要求
- 代码可读性
- 资源限制
四、算法的分类
算法可按功能、执行方式等维度分类，结合C#应用场景常见分类如下：
- 按功能分类：
-
排序算法：冒泡排序、快速排序（C#中可用于数组/List排序）；
-
查找算法：线性查找、二分查找（适用于有序集合）；
-
数值计算算法：求阶乘、斐波那契数列（常用于数学运算场景）；
-
图算法：深度优先搜索（DFS）、广度优先搜索（BFS）（适用于图数据结构）。
- 按执行方式分类：
- 迭代算法：通过循环重复执行步骤（如for/while循环）；
- 递归算法：方法自身调用（需设置终止条件，避免栈溢出）。
C#递归算法示例（求n的阶乘）：
public static int Factorial(int n)
{
// 终止条件（避免无限递归）
if (n == 0 || n == 1) return 1;
// 递归调用：自身调用+缩小问题规模
return n * Factorial(n - 1);
}
五、算法的三要素
简单来说，一个完整的算法就像一道做菜的菜谱，它由操作（你要切菜、翻炒这些动作）、控制结构（先切菜还是先放油的顺序）、数据结构（你处理的是蔬菜、肉类这些食材）三部分组成。
算法由操作、控制结构、数据结构三部分组成，三者协同构成完整算法，C#中需通过语法对应实现：
using System;
namespace LearnCSharp
{
internal class Program
{
// 示例1：计算数组元素平均值 - 展示算法的三要素
public static double CalculateAverage(int[] scores) // 数据结构：数组 int[]
{
// 操作：变量声明和初始化
int sum = 0;
// 控制结构：循环结构（for循环）
for (int i = 0; i < scores.Length; i++)
{
// 操作：算术运算（加法）和赋值
sum += scores[i];
}
// 控制结构：条件判断（隐式）和返回
// 操作：算术运算（除法）和类型转换
return (double)sum / scores.Length;
}
// 示例2：查找数组中的最大值 - 另一种算法展示三要素
public static int FindMaxValue(int[] numbers) // 数据结构：数组
{
if (numbers.Length == 0) // 控制结构：条件判断
{
throw new ArgumentException("数组不能为空");
}
int max = numbers[0]; // 操作：变量初始化和数组访问
// 控制结构：循环结构（foreach循环）
foreach (int number in numbers)
{
// 控制结构：条件判断（if语句）
if (number > max) // 操作：比较运算
{
max = number; // 操作：赋值
}
}
return max; // 操作：返回值
}
// 示例3：简单的排序算法 - 展示更复杂的三要素组合
public static void BubbleSort(int[] array) // 数据结构：数组
{
// 控制结构：嵌套循环（外层循环）
for (int i = 0; i < array.Length - 1; i++)
{
// 控制结构：嵌套循环（内层循环）
for (int j = 0; j < array.Length - i - 1; j++)
{
// 控制结构：条件判断
if (array[j] > array[j + 1]) // 操作：比较运算
{
// 操作：交换两个元素（涉及多个步骤）
int temp = array[j]; // 1. 临时存储
array[j] = array[j + 1]; // 2. 赋值操作
array[j + 1] = temp; // 3. 赋值操作
}
}
}
}
// 示例4：判断数字是否为质数 - 展示算法的逻辑设计
public static bool IsPrime(int number) // 数据结构：整数
{
// 控制结构：条件判断
if (number <= 1) return false;
if (number == 2) return true;
// 控制结构：循环结构
for (int i = 2; i <= Math.Sqrt(number); i++)
{
// 操作：算术运算（取余）和比较运算
if (number % i == 0)
{
return false; // 控制结构：提前返回
}
}
return true; // 操作：返回值
}
// 主程序入口 - 测试所有示例
public static void Main(string[] args)
{
Console.WriteLine("算法三要素示例\n");
// 测试示例1：计算平均值
Console.WriteLine("1. 计算数组平均值（展示三要素）：");
int[] scores = { 85, 92, 78, 95, 88 };
double average = CalculateAverage(scores);
Console.WriteLine($"数组: [{string.Join(", ", scores)}]");
Console.WriteLine($"平均值: {average:F2}\n");
// 测试示例2：查找最大值
Console.WriteLine("2. 查找数组最大值：");
int max = FindMaxValue(scores);
Console.WriteLine($"最大值: {max}\n");
// 测试示例3：冒泡排序
Console.WriteLine("3. 冒泡排序算法：");
int[] numbersToSort = { 64, 34, 25, 12, 22, 11, 90 };
Console.WriteLine($"排序前: [{string.Join(", ", numbersToSort)}]");
BubbleSort(numbersToSort);
Console.WriteLine($"排序后: [{string.Join(", ", numbersToSort)}]\n");
// 测试示例4：判断质数
Console.WriteLine("4. 判断数字是否为质数：");
int[] testNumbers = { 2, 7, 15, 17, 23, 29, 31 };
foreach (int num in testNumbers)
{
bool isPrime = IsPrime(num);
Console.WriteLine($"{num} 是质数吗？ {(isPrime ? "是" : "否")}");
}
Console.WriteLine();
// 展示算法的三要素总结
Console.WriteLine("【算法三要素总结】");
Console.WriteLine("=====================");
Console.WriteLine("1. 操作 - 算法的基本步骤（如 +, -, =, 比较等）");
Console.WriteLine(" 示例: sum += scores[i], number > max");
Console.WriteLine();
Console.WriteLine("2. 控制结构 - 控制算法流程（顺序、分支、循环）");
Console.WriteLine(" 示例: if判断、for循环、while循环");
Console.WriteLine();
Console.WriteLine("3. 数据结构 - 算法操作的对象（数据组织形式）");
Console.WriteLine(" 示例: 数组、变量、整数、布尔值");
Console.WriteLine();
// 用计算平均值的算法具体解释三要素
Console.WriteLine("【以计算平均值算法为例】");
Console.WriteLine("数据结构: int[] scores (数组，存储成绩)");
Console.WriteLine("操作: sum += scores[i] (加法运算和赋值)");
Console.WriteLine("控制结构: for循环 (控制遍历所有元素)");
Console.WriteLine("return语句 (返回计算结果)");
Console.WriteLine("\n按任意键退出...");
Console.ReadKey();
}
}
}
六、操作是什么
操作是算法的基础执行单元，指对数据的具体处理动作，C#中支持的核心操作对应语法如下：
-
算术运算：
+、-、*、/、%（取余）等； -
关系比较：
>、<、==、!=、>=、<=（返回bool值）； -
逻辑运算：
&&（与）、||（或）、!（非）（用于条件判断）； -
数据传送：输入（接收参数、Console.ReadLine()）、输出（Console.WriteLine()）、赋值（=）。
C#操作示例：
// 数据传送：输入（接收参数）+ 赋值
public static void CheckNumber(int num)
{
// 关系比较 + 逻辑运算（判断num是否在1-100之间）
bool isInRange = num > 0 && num <= 100;
// 数据传送：输出
Console.WriteLine($"数字是否在1-100之间：{isInRange}");
}
操作:操作就是算法里最基础的“动作”，不管用什么编程语言，这些基础动作都是相通的。
-
算术运算：加、减、乘、除 (比如计算
2 + 3，10 / 2。) -
关系比较：
>、<、=、≠ (比如判断5 > 3（结果为真），4 == 6（结果为假）。) -
逻辑运算：与（and）、或（or）、非（not）(比如判断“今天下雨 且 我带伞”（与），“周末去逛街 或 看电影”（或）。)
-
数据传送：输入、输出、赋值 (比如让用户输入年龄（输入），在屏幕上显示结果（输出），把
x = 10存到变量里（赋值）。)
示例： 计算圆的面积时，
- 输入圆的半径
r（数据传送-输入） - 计算
area = π * r * r（算术运算 + 赋值） - 输出面积
area（数据传送-输出）
七、控制结构是什么
控制结构：控制结构决定了这些 “操作” 的执行顺序，就像菜谱里的 “步骤顺序”。
-
顺序结构：按代码书写顺序依次执行（默认结构）；。 比如先淘米，再煮饭，最后盛饭。
-
选择结构：按条件分支执行，C#中通过if-else、switch实现； 比如“如果下雨，就带伞；否则，不带伞”。
-
循环结构：重复执行指定步骤，C#中通过for、while、do-while实现； 比如“把1到10的数字都加一遍”，需要循环10次。
示例：
判断一个数 n 是否为正数：
# 输出
八、数据结构是什么
数据结构：数据结构是算法处理的“对象”和这些对象的组织方式。比如你要处理的是单个数字、一串字符，还是一个列表，这些都属于数据结构。
数据结构是数据的组织、存储和关联方式，决定算法处理数据的效率，C#中提供内置数据结构（基础类型、集合）和自定义数据结构（类、结构体）：
-
简单数据结构：int（整数）、double（浮点数）、string（字符串）、bool（布尔值）；
-
复杂数据结构（C#集合）：List
<T>（动态数组）、Dictionary<K,V>（键值对）、Queue<T>（队列）、Stack<T>（栈）； -
自定义数据结构：通过class、struct定义（如链表节点、树节点）。
C#自定义数据结构示例（链表节点）：
// 自定义链表节点结构（存储int数据）
public class ListNode
{
public int Value { get; set; } // 数据域
public ListNode Next { get; set; } // 指针域（关联下一个节点）
// 构造函数（初始化节点）
public ListNode(int value)
{
Value = value;
Next = null;
}
}
九、算法的基本性质
算法需满足5个基本性质，确保其有效性和可行性，结合C#语法验证如下：
-
目的性：有明确目标（如“计算平均值”“排序数组”），C#中通过方法返回值/输出体现；
-
分步性：拆解为计算机可执行的最小步骤（如C#中单个运算、赋值语句），不可模糊；
-
有序性：步骤顺序固定，C#中通过控制结构保障（如顺序执行、分支优先级）；
-
有限性：步骤数量有限，需避免无限循环/递归（如递归必须设终止条件，循环需有退出逻辑）；
-
操作性：对数据进行具体操作并改变其状态（如C#中修改变量值、更新集合元素）。
反例（违背有限性的无效算法）：
// 无效算法：无限循环（无退出条件，违背有限性）
public static void InfiniteLoop()
{
while (true) // 条件恒为真，永远执行
{
Console.WriteLine("无限执行");
}
}
这些性质保证了算法是“有效、可行”的，不会是模糊或无限的。
- 目的性：算法必须有明确的目标 → 比如“计算圆面积”就是一个明确的目的。
- 分步性：算法要拆成计算机能执行的小步骤 → 不能只说“做饭”，而要拆成“买菜→洗菜→切菜→炒菜”。
- 有序性：步骤不能乱序 → 不能先炒菜再洗菜。
- 有限性：算法的步骤必须是有限的 → 不能无限循环下去，比如“计算1到无穷大的和”就不是有效算法。
- 操作性：算法要对具体对象进行操作并改变其状态 → 比如把变量
sum从0加到55，就是改变了sum的状态。
简易版：
-
目的性：有明确的功能目标
-
分步性：拆解为计算机可执行的具体步骤
-
有序性：步骤执行顺序固定，不可随意调换
-
有限性：步骤数量有限，不会无限执行
-
操作性：对数据对象进行操作并改变其状态