C#程序设计.唐大仕.05.基础类及常用算法

Posted on 2021-10-15 Edited on 2021-10-20 In csharp.tds Views:

DotNet 基本类库、类型转换、库函数（Math、String、Random、DateTime）、集合、泛型、排序、基本算法（遍试、迭代、递归）

中国大学慕课

基础类及常用算法

1. DotNet 基本类库

统一的编程 API：NET Framework 类库

具体

2. 类型转换

任何事物都是对象

任何事物都是 object 类的子类
一个函数如果需要object参数，则可以代入任意参数
任何对象都有以下方法

ToString();
Equals();
GetType();
GetHashCode();
// MemberwiseClone(); // 没找到?
// ...

常量也是对象

1 2	3.ToString(); "Hello".Length;

表达式中的类型转换

当有不同种类的混合运算时:
- int \(\to\) long \(\to\) float \(\to\) double

整型提升

在计算的时候，所有的 byte、short、char 等转为 int

强制类型转换

在表达式前面用（类型）来表示

1
2
3

double a = 3.14;
int b = (int)a;
float c = (float)(d+1.25);

类型转换函数

System.Convert 类有以下 static 方法
- 每个函数有对应参数类型的各种重载函数

ToInt16();
ToInt32();
ToInt64();
ToSbyte();

会抛出异常

基本类型

关键字含有等价的类

int：System.Int32

静态属性或方法

int a = 0;
a = int.MaxValue;
a = int.MinValue;

double b = 0.0;
b = double.NaN;
b = double.NegativeInfinity;
b = double.PositiveInfinity;

Parse 和 TryParse

TryParse 不抛出异常

Parse 抛出异常

ToString()

更具体的查看文档

internal class Program {
    private static void W(string s) {
        Console.WriteLine(s);
    }

    private static void Main(string[] args) {
        string specifier;
        CultureInfo culture;
        double a = 314.15326;

        W(a.ToString());
        // 314.15326

        specifier = "G";
        culture = CultureInfo.CreateSpecificCulture("eu-ES");
        W(a.ToString(a.ToString(specifier, culture)));
        // 31415326

        W(a.ToString(specifier, CultureInfo.InvariantCulture));
        // 314.15326

        W(a.ToString("#0.00"));
        // 314.15

        Console.ReadKey();
        return;
    }
}

3. 数学、文字、日期

Math 类

Abs();
Sin();
Cos();
Tan();
Round();
Exp();
Log();
Pow();
// ...

Random 类

1 2	Next(100); // [0, 100) NextDouble(); // [0, 1)

Random 得到的是伪随机数
如果要用更强的随机数，可以使用如下方法

using System.Security.Cryptography;

RNGCryptoServiceProvider rdm = new RNGCryptoServiceProvider();
byte[] a = new byte[100];
rdm.GetBytes(a);

DateTime 类

using System.Threading;

W(DateTime.Now.ToString());
// 2021/10/16 16:25:45

Thread.Sleep(1000);

W(DateTime.Now.ToString());
// 2021/10/16 16:25:46

DateTime 是值类型

new DateTime(y,m,d,h,m,s);
// 属性与方法
Now;
Year;
Month;
Day;
Date;

ToString("yyyy-MM-dd HH:mm:ss"); // H(24小时),h(12小时),MM(月份),mm(分钟)
AddMinutes(5);

TimeSpan
- 两个日期相减，可以得到一个TimeSpan

String 类

==;
+;
[];

Length;
IndexOf();
LastIndexOf();
StartsWith();
EndsWith();
Substring(idx, len); // 注意第二个参数
Trim();
TrimEnd();
PadLeft();
Insert();
Remove();
Split(';');
string.Join()

StringBuilder

不可变的 String 与可变的 StringBuilder

Append();
Remove();
Replace();
Length();
ToString();

性能测试
- 在头部 Insert，StringBuilder 不一定会更快
  - 可以设置初始容量
- 尾部 append，StringBuilder 更快

4. 数组、集合、泛型

数组

// 声明
int[] a;  // 一维数组
int[,] b; // 二维数组

// 分配空间
a = new int[10];
b = new int[4,5];

集合类

1	using System.Collections;

数组列表 ArrayList
- 相当于动态数组,实现 IList
哈希表 Hashtable
- 相当于键/值的集合，实现 IDictionary
- 用 [] 进行访问，表示获取、增加、删除、修改
- 提示：用于查询时，比线性搜索的效率要高，可用于程序的优化
栈和队列 Stack/Queue

foreach

foreach(var a in listA) {
    // ...
    Console.WriteLine(a);
}

1
2
3

foreach(类型 变量 in xxxx) {
    // ...
}

其中 xxxx 必须是实现了实现 IEnumerable 接口或含有 GetEnumerator() 方法的类型
这个方法的原型是 IEnumerator GetEnumerator();
返回的是一个接口 IEnumerator
- Current 属性
- MoveNext() 及 Reset() 方法

二分查找

1	Array.BinarySearch();

泛型

泛型具有更好的类型检查及性能

1	using System.Collections.Generic;

列表
- List
- LinkedList
- SortedList
字典
- Dictionary
- SortedDictionary
集合
- HashSet
- SortedSet
栈、队列
- Stack, Queu

一些代码

List 的遍历
foreach 的内部实现

private static void PrintValues2(IList<string> myList) {
    // foreach 遍历方式
    foreach (string item in myList) {
        Console.Write("{0}\n", item);
    }
}

private static void PrintValues3(IEnumerable<string> myList) {
    // foreach 的内部实现
    IEnumerator<string> myEnumerator = myList.GetEnumerator();
    while (myEnumerator.MoveNext()) {
        Console.Write("{0}\n", myEnumerator.Current);
    }
    Console.WriteLine();
}

HashTable 的遍历

排序

自己写排序程序
使用 SortedXXXX 类
使用 Array.Sort() 方法

1	Array.Sort(arr, (a, b) => a.Length - b.Length);

总结

5. 常用算法

算法

指令的有限序列
特点
- 有穷性
- 确定性
- 可行性
- 输入、输出

遍试算法

枚举、穷尽

例子

百鸡问题：100元钱买100只鸡，如何买？已知条件：鸡母每只3元，鸡公每只1元，鸡仔每3只1元。
鸡兔同笼问题：鸡兔在同一笼子中，共有头30只，共有脚100只，问鸡兔又有几只？
百分币问题：要给人100分币有多少种方案。已知分币的种类有1分、2分、5分、10分、50分共5种。
佩尔方程：某将领的军队有29个方阵（人数为平方），如果他也参与其中，则可以排成一个大方阵，请问他有多少军队？
韩信点兵
水仙花数：\(1^3+5^3+3^3=153\)
完全数：\(28=1+2+4+7+14\)（因数）
相亲数
验证哥德巴赫猜想

迭代算法

求平方根（不动点迭代）
- 牛顿法
数字平方和
Mandelbrot 集
Julia 集

倍边法求 Pi

使用正多边形的周长 \(C_1\) 近似圆周长 \(C_2\)，令 \(r=1\)

\[ \pi=\dfrac{C}{2r}=\dfrac{C_1}{2} \]

\(a_n=b_{m},m=3\cdot{2^{n+1}}\) 表示正 \(m\) 边形的周长
- \(a_0=1\)：正六边形
- 橙色线段：\(a_n\)
- 红色线段：\(a_{n+1}\)

\[ \sqrt{1-\left(\dfrac{a_n}{2}\right)^{2}}+\sqrt{\left(a_{n+1}\right)^2-\left(\dfrac{a_n}{2}\right)^2}=1 \]

\[ a_{n+1}=\sqrt{2-2\sqrt{1-\dfrac{a_n^4}{4}}} \]

using System;
class TestDebugPi {
    public static void Main() {
        double a = 1;
        for (int n = 1; n <= 10; n++) {
            a = Math.Sqrt(2 - Math.Sqrt(4 - a * a));
            double pi = a * 3 * Math.Pow(2, n);
            Console.WriteLine(pi);
        }
        Console.WriteLine(Math.PI);
        // 如果n<=100,如何?
        // 精度问题, 出错
    }
}

递归算法

阶乘
走台阶问题（一步一级或两级）
斐波那契数列
绘制树
- 加入随机因素

6. 程序的调试

程序错误

语法错误、运行错误、逻辑错误

语法错误

常见的语法错误
- 如括号不配对、多了或少了分号
- 字母写错、变量未定义、控件命名写错
- 函数少传了一个参数
语法错：编译器可以发现（在编辑、编译时）
对编程者：养成良好的编程习惯
- 命名、空行、注释

运行时错误

运行时错误（Runtime Error）多数发生在不可预期的异常
- 文件打不开、网络打不开、内存不足
- 整数除法的除数为零，数组下标走越界、变量初始化为null
解决办法
- 使用 try{}catch{}
- 使用 if 语句进行判断处理

逻辑错误

逻辑错误（Logic Error）是指程序所完成的任务与预想的任务不匹配
- 小于s.Length写成<=s.Length
- 1到加100,却只加到99
- 算法的错误
解决逻辑错误
- 分析清楚需求、理清算法、在程序中进行调试
- 特别注意边界条件、特殊值