C# .NET面试系列九：常见的算法

1. 求质数

// 判断一个数是否为质数的方法
public static bool IsPrime(int number)
{
    if (number < 2)
    {
        return false;
    }

    for (int i = 2; i <= Math.Sqrt(number); i++)
    {
        if (number % i == 0)
        {
            return false;
        }
    }

    return true;
}

class Program
{
    static void Main()
    {
        Console.Write("请输入一个正整数作为范围的上限：");
        int upperLimit;
        // 输入上限，并确保输入为正整数
        while (!int.TryParse(Console.ReadLine(), out upperLimit) || upperLimit <= 0)
        {
            Console.Write("请输入有效的正整数：");
        }
        Console.WriteLine($"在 1 到 {upperLimit} 的范围内的质数有：");
        // 查找并输出范围内的质数
        for (int number = 2; number <= upperLimit; number++)
        {
            if (Util.IsPrime(number))
            {
                Console.Write($"{number} ");
            }
        }
        Console.ReadLine();
    }
}

以上是一个简单的 C# 程序，用于找到一定范围内的质数（素数）。

这个程序首先要求用户输入一个正整数作为查找质数的范围上限，然后使用 IsPrime 方法判断每个数是否为质数，并输出在指定范围内的所有质数。 IsPrime 方法使用了试除法，检查一个数是否有除了 1 和自身以外的因子。

2. 有一列数1，1，2，3，5，…求第30个数.

在斐波那契数列中，通常是第一个和第二个数是1，后续的每个数是前两个数之和。因此，第30个数可以通过递归或循环方式计算。

public static long Fibonacci(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (n == 1 || n == 2)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}
class Program
{
    static void Main()
    {
        int n = 30;
        long result = Fibonacci(n);

        Console.WriteLine($"第 {n} 个数是：{result}");
        Console.ReadLine();
    }
}

请注意，递归方法在计算大数时可能会变得很慢，因为它重复计算相同的子问题。在实际应用中，为了提高效率，可以使用迭代或其他优化方法来计算斐波那契数列。

3. 冒泡排序

冒泡排序是一种简单的排序算法，其基本思想是通过多次交换相邻的元素，将较大的元素逐步移动到数组的末尾，实现排序。以下是 C# 中冒泡排序的实现：

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            // 如果前一个元素大于后一个元素，则交换它们
            if (arr[j] > arr[j + 1])
            {
                Swap(ref arr[j], ref arr[j + 1]);
            }
        }
    }
}

public static void Swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}

public static void PrintArray(int[] arr)
{
    foreach (int num in arr)
    {
        Console.Write(num + " ");
    }
    Console.WriteLine();
}

class Program
{
    static void Main()
    {
        int[] array = { 5, 2, 9, 1, 5, 6 };
        Console.WriteLine("排序前的数组：");
        PrintArray(array);

        BubbleSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);

        Console.ReadLine();
    }
}

在这个示例中，BubbleSort 方法执行冒泡排序，Swap 方法用于交换数组中两个元素的位置。程序首先输出未排序的数组，然后执行冒泡排序，最后输出排序后的数组。

4. 请编写一个函数，能够计算10以内数的阶乘，尽量采用递归算法。（10!=3628800）。

以下是一个使用递归算法计算10以内数的阶乘的 C# 函数：

public static long CalculateFactorial(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return n * CalculateFactorial(n - 1);
    }
}

class Program
{
    static void Main()
    {
        int n = 10;
        long factorial = CalculateFactorial(n);

        Console.WriteLine($"{n} 的阶乘是：{factorial}");
        Console.ReadLine();
    }
}

这个程序中的 CalculateFactorial 函数使用递归算法计算阶乘。递归基线是当输入为0或1时，返回1（0! 和 1! 都等于1）。否则，递归地调用函数，将输入减一，然后与原来的输入相乘。这样递归地进行下去，直到达到基线情况。

5. 请编程实现此方法。将输入的整型数组，合并转换为逗号分隔的字符串。

例如输入参数为整型数组{9，7，2}，那么输出结果为字符串"9,7,2"。

public static string MergeAndConvertToString(int[] array)
{
    // 使用 string.Join 方法将整型数组中的元素连接成一个字符串，以逗号分隔
    string result = string.Join(", ", array);
    return result;
}

class Program
{
    static void Main()
    {
        int[] numbers = { 1, 2, 3, 4, 5 };
        string result = MergeAndConvertToString(numbers);
        Console.WriteLine("合并后的字符串：" + result);
        Console.ReadLine();
    }
}

在这个示例中，MergeAndConvertToString 方法使用 string.Join 方法，该方法接受一个分隔符（逗号和空格）和一个整型数组，并返回将数组中的元素连接成的字符串。最后，该字符串被输出到控制台。

6. 产生一个int数组，长度为100，并向其中随机插入1-100，并且不能重复。

public static int[] GenerateRandomArray(int length)
{
    int[] array = new int[length];
    Random random = new Random();
    for (int i = 0; i < length; i++)
    {
        int randomNumber;
        do
        {
            // 生成不重复的随机数
            randomNumber = random.Next(1, 101);
        } while (Array.Exists(array, element => element == randomNumber));
        array[i] = randomNumber;
    }
    return array;
}

class Program
{
    static void Main()
    {
        int[] randomArray = Util.GenerateRandomArray(100);
        Console.WriteLine("生成的随机数组：");
        Util.PrintArray(randomArray);
        Console.ReadLine();
    }
}

在这个示例中，GenerateRandomArray 方法使用 Random 类生成不重复的随机数，并将它们插入到数组中。Array.Exists 方法用于检查数组中是否已经存在当前生成的随机数。最后，程序输出生成的随机数组。

7. 请将字符串"I am a student"按单词逆序输出 如"student a am I"

public static string ReverseWords(string input)
{
    // 将字符串按空格分割成单词数组
    string[] words = input.Split(' ');
    // 使用 Array.Reverse 方法逆序数组
    Array.Reverse(words);
    // 使用 string.Join 方法将逆序后的单词数组连接成字符串
    string reversedString = string.Join(" ", words);
    return reversedString;
}

class Program
{
    static void Main()
    {
        string inputString = "I am a student";
        string reversedString = Util.ReverseWords(inputString);
        Console.WriteLine("原始字符串：" + inputString);
        Console.WriteLine("逆序输出：" + reversedString);
        Console.ReadLine();
    }
}

在这个示例中，ReverseWords 方法首先使用 Split 方法将输入字符串按空格分割成单词数组，然后使用 Array.Reverse 方法逆序数组，最后使用 string.Join 方法将逆序后的单词数组连接成字符串。程序输出原始字符串和逆序输出的结果。

8. C# 取两个数组的相同元素

摘要: 以往我们都是肯定绞尽脑汁，肯定什么循环，元素大小，什么因素都考虑进去。但是现在采用Linq可以很好的解决这个问题。找出两个或多个数组的相同项。代码如下：

public static int[] GetCommonElements(int[] array1, int[] array2)
{
    // 使用 LINQ 的 Intersect 方法获取两个数组的交集
    int[] commonElements = array1.Intersect(array2).ToArray();
    return commonElements;
}

class Program
{
    static void Main()
    {
        int[] array1 = { 1, 2, 3, 4, 5 };
        int[] array2 = { 3, 4, 5, 6, 7 };
        int[] commonElements = Util.GetCommonElements(array1, array2);
        Console.WriteLine("数组1：" + string.Join(", ", array1));
        Console.WriteLine("数组2：" + string.Join(", ", array2));
        Console.WriteLine("相同元素：" + string.Join(", ", commonElements));
        Console.ReadLine();
    }
}

在这个示例中，GetCommonElements 方法使用 LINQ 的 Intersect 方法获取两个数组的交集。程序输出两个数组和它们的相同元素。请注意，使用 LINQ 的方法需要确保项目引用了 System.Linq 命名空间。

9. 有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

public static void GenerateThreeDigitNumbers()
{
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            for (int k = 1; k <= 4; k++)
            {
                // 确保三个数字互不相同
                if (i != j && i != k && j != k)
                {
                    int number = i * 100 + j * 10 + k;
                    Console.Write(number + " ");
                }
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Console.WriteLine("能组成的互不相同且无重复数字的三位数有：");
        Util.GenerateThreeDigitNumbers();
        Console.ReadLine();
    }
}

在这个程序中，使用三个嵌套的循环遍历数字1、2、3、4，通过组合的方式生成所有可能的三位数，并在组合过程中确保这三个数字互不相同。程序输出所有满足条件的三位数。

10. 用C#写一段选择排序算法，要求用自己的编程风格。

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;

        for (int j = i + 1; j < n; j++)
        {
            // 找到最小元素的索引
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }

        // 将最小元素与当前位置交换
        Swap(ref arr[i], ref arr[minIndex]);
    }
}

class Program
{
    static void Main()
    {
        int[] array = { 64, 25, 12, 22, 11 };
        Console.WriteLine("排序前的数组：");
        Util.PrintArray(array);
        Util.SelectionSort(array);
        Console.WriteLine("\n排序后的数组：");
        Util.PrintArray(array);
        Console.ReadLine();
    }
}

在这个示例中，SelectionSort 方法实现了选择排序算法。程序首先输出排序前的数组，然后进行选择排序，最后输出排序后的数组。 Swap 方法用于交换数组中两个元素的位置，PrintArray 方法用于输出数组。

11. 有一个10个数的数组，计算其中不重复数字的个数。{3,5,9,8,10,5,3},用HashSet。

public static int CountUniqueNumbers(int[] arr)
{
    // 使用 HashSet 来存储不重复的数字
    HashSet<int> uniqueNumbers = new HashSet<int>(arr);

    return uniqueNumbers.Count;
}

class Program
{
    static void Main()
    {
        int[] numbers = { 3, 5, 9, 8, 10, 5, 3 };
        int uniqueCount = Util.CountUniqueNumbers(numbers);
        Console.WriteLine("数组中不重复数字的个数：" + uniqueCount);
        Console.ReadLine();
    }
}

在这个示例中，CountUniqueNumbers 方法接受一个整型数组，并使用 HashSet 来存储不重复的数字。最后，通过 Count 属性获取 HashSet 中不重复数字的个数。程序输出数组中不重复数字的个数。

12. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些人参加了竞赛：

（１）Ａ参加时，Ｂ也参加；

（２）Ｂ和Ｃ只有一个人参加；

（３）Ｃ和Ｄ或者都参加，或者都不参加；

（４）Ｄ和Ｅ中至少有一个人参加；

（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。

/// <summary>
/// 数组遍历
/// </summary>
public static void CheckCombinations()
{
    char[] students = { 'A', 'B', 'C', 'D', 'E' };

    // 遍历所有可能的组合
    for (int a = 0; a <= 1; a++)
    {
        for (int b = 0; b <= 1; b++)
        {
            for (int c = 0; c <= 1; c++)
            {
                for (int d = 0; d <= 1; d++)
                {
                    for (int e = 0; e <= 1; e++)
                    {
                        // 检查满足条件的组合
                        if (Condition1(a, b) &&
                            Condition2(b, c) &&
                            Condition3(c, d) &&
                            Condition4(d, e) &&
                            Condition5(e, a, d))
                        {
                            // 输出符合条件的组合
                            Console.Write($"A{(a == 1 ? "参加" : "不参加")} ");
                            Console.Write($"B{(b == 1 ? "参加" : "不参加")} ");
                            Console.Write($"C{(c == 1 ? "参加" : "不参加")} ");
                            Console.Write($"D{(d == 1 ? "参加" : "不参加")} ");
                            Console.Write($"E{(e == 1 ? "参加" : "不参加")}\n");
                        }
                    }
                }
            }
        }
    }
}
static bool Condition1(int a, int b)
{
    return a == 0 || b == 1;
}

static bool Condition2(int b, int c)
{
    return (b == 1 && c == 0) || (b == 0 && c == 1);
}

static bool Condition3(int c, int d)
{
    return c == 1 || d == 1 || (c == 0 && d == 0);
}

static bool Condition4(int d, int e)
{
    return d == 1 || e == 1;
}

static bool Condition5(int e, int a, int d)
{
    return e == 0 || (a == 1 && d == 1);
}
class Program
{
    static void Main()
    {
        Console.WriteLine("可能参加计算机竞赛的学生组合：");
        Util.CheckCombinations();
        Console.ReadLine();
    }
}

在这个示例中，我们使用嵌套循环遍历所有可能的组合，然后根据条件进行检查，满足条件的组合会被输出。这样我们就找到了符合给定条件的学生参加计算机竞赛的可能组合。

13. 程序设计：猫大叫一声，所有的老鼠都开始逃跑，主人被惊醒。

class Cat
{
    public void Shout()
    {
        Console.WriteLine("猫大叫一声！");
    }
}

class Mouse
{
    private int number;

    public Mouse(int number)
    {
        this.number = number;
    }

    public void RunAway()
    {
        Console.WriteLine($"老鼠 {number} 逃跑了！");
    }
}

class Owner
{
    public void WakeUp()
    {
        Console.WriteLine("主人被惊醒了！");
    }
}
class Program
{
    static void Main()
    {
        Console.WriteLine("猫大叫一声...");
        Cat cat = new Cat();
        Mouse[] mice = new Mouse[5];
        for (int i = 0; i < mice.Length; i++)
        {
            mice[i] = new Mouse(i + 1);
        }
        Owner owner = new Owner();
        // 猫叫一声，老鼠逃跑，主人被惊醒
        cat.Shout();
        foreach (Mouse mouse in mice)
        {
            mouse.RunAway();
        }
        owner.WakeUp();
        Console.ReadLine();
    }
}

在这个示例中，我们定义了 Cat 类、Mouse 类和 Owner 类，分别表示猫、老鼠和主人。程序模拟了猫叫一声后，老鼠逃跑，主人被惊醒的情景。

本系列文章题目摘自网络，答案重新梳理