算法思想：穷举法

基本概念

穷举法思想，也称为暴力枚举法或遍历法，是一种简单直观解决问题的方法。它的基本思想是对所有可能的情况进行逐一测试，直至找到符合要求的解或确定无解为止。

穷举法思想主要涉及以下几个关键步骤：

确定问题空间：明确问题所有可能解构成的空间或集合。这个空间可以是一个数值范围、一个字符串集合、一个组合或排列的集合等。

逐一测试：程序按照某种顺序（如从小到大、从前往后等）遍历这个空间中的每一个元素或状态。对于每个元素或状态，程序会检查它是否满足问题的要求或条件。

检查条件：在遍历过程中，程序会根据问题的具体要求进行条件判断。如果当前元素或状态满足条件，则可能是一个解（或最优解），或者可能是进一步搜索的起点。如果不满足条件，则继续遍历下一个元素或状态。

记录结果：一旦找到满足条件的解，程序通常会记录这个解，并可能继续搜索以寻找更多的解或最优解。如果遍历完整个空间都没有找到解，则程序会输出无解的信息。

找出所有三位数中的水仙花数

问题描述

水仙花数（Narcissistic Number）也被称为阿姆斯特朗数（Armstrong Number），它是一个n位数，它的每个位上的数字的n次幂之和等于它本身。对于三位数来说，就是该数的每个位上的数字的立方和等于该数本身。

例如：153是一个水仙花数，因为 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153。
要求使用穷举法来找出所有的三位数中的水仙花数。

解题步骤

水仙花数的定义是一个n位数，它的每个位上的数字的n次幂之和等于它本身。对于三位数水仙花数，需要遍历所有三位数（即100到999之间的整数），然后对每个数的每一位进行提取，计算每一位数字的立方和，最后判断这个和是否等于原数。

C语言实现解题思路：

循环遍历所有三位数：使用一个for循环，从100遍历到999，包括这两个边界值，以覆盖所有三位数。

提取每一位数字：对于循环中的每一个数，需要提取它的百位、十位和个位数字。可以通过整除和取余操作实现。例如，对于数num，百位数字可以通过num / 100得到，十位数字可以通过(num % 100) / 10得到，个位数字可以通过num % 10得到。

计算每一位数字的立方和：对于提取出的每一位数字，计算其立方（即该数字自乘三次），然后将这三个立方值相加。

判断是否为水仙花数：比较计算出的立方和是否等于原数。如果相等，则原数是一个水仙花数。

输出结果：如果找到水仙花数，将其打印出来。

代码实现

#include <stdio.h>

int main() {
int i, num, originalNum, remainder, result = 0, temp;
printf("三位数中的水仙花数有：\n");

for (i = 100; i <= 999; i++) {
originalNum = i;
temp = i;
result = 0;

// 提取百位、十位和个位数字并计算立方和
while (temp != 0) {
remainder = temp % 10;
result += remainder * remainder * remainder;
temp /= 10;
}

// 判断是否为水仙花数
if (result == originalNum) {
printf("%d ", originalNum);
}
}

printf("\n");
return 0;
}

这段代码首先遍历所有三位数，然后对每个数进行位分离和计算立方和的操作，最后判断是否为水仙花数并输出结果。

 

算法分析

算法复杂性分析主要从时间复杂性和空间复杂性两个方面来考虑。

时间复杂性

程序使用了一个for循环来遍历所有三位数（从100到999），这是一个O(N)的操作，其中N是三位数的总数，即900。

在for循环内部，有一个while循环用于提取每个数的每一位并计算其立方和。这个while循环最多会执行三次（对于三位数），其时间复杂性是常数级的，即O(1)。

因此，整个算法的时间复杂性是O(N)，其中N=900，每个数内部的处理是常数时间的。

空间复杂性

空间复杂性关注的是算法执行过程中所需的辅助空间。在这个程序中，程序使用了几个整数变量（i, num, originalNum, remainder, result, temp）来存储中间结果和状态。这些变量的数量是固定的，不随输入规模的变化而变化，因此空间复杂性是O(1)。

程序没有使用任何动态分配的内存（如数组或链表），也没有使用递归调用栈来存储大量数据，因此空间需求是常数级的。

综上所述，该算法的时间复杂性是O(N)，其中N是三位数的总数；空间复杂性是O(1)。这意味着算法的运行时间随三位数的数量线性增长，而所需的辅助空间保持不变。对于这个问题规模来说，这是一个非常高效且实用的算法。

找出所有借书的方法

问题描述

假设小明有5本新书，要借给A、B、C三位小朋友，每个人每次只能借一本书，要求找出所有不同的有效借法。

解题步骤

这个问题可以通过穷举法来解决，具体步骤如下：
确定问题规模：有5本书和3个小朋友，需要找出所有可能的借书组合。
设计循环结构：使用三个嵌套的循环来代表A、B、C三位小朋友的选书过程。每个循环都从1遍历到5，代表5本书。
控制有效组合：在循环内部，需要确保每个小朋友选的书都是不同的，即没有重复。这可以通过比较每个循环的变量来实现。
输出结果：每当找到一个有效的借书组合时，就将其打印出来。

代码实现

#include <stdio.h>

int main() {
int i, j, k;
int count = 0; // 用于计数有效借法

printf("A、B、C三人所选的书号分别为:\n");
for (i = 1; i <= 5; i++) {
for (j = 1; j <= 5; j++) {
if (j == i) continue; // 确保B选的书和A不同
for (k = 1; k <= 5; k++) {
if (k == i || k == j) continue; // 确保C选的书和A、B都不同
printf("A:%d B:%d C:%d\n", i, j, k);
count++;
}
}
}
printf("共有%d种有效的借阅方法\n", count);
return 0;
}

代码通过三层循环遍历所有可能的借书组合，并使用continue语句来跳过那些不满足条件的组合（即存在重复书籍的组合）。最后输出所有有效的借书组合以及它们的总数。

算法分析

时间复杂度

代码中有三个嵌套的for循环，每个循环都遍历从1到5的整数，即它们各自执行5次。
第一个循环（由变量i控制）执行5次。
对于i的每一次迭代，第二个循环（由变量j控制）也执行5次，但由于if (j == i) continue;的存在，当j等于i时会跳过当前迭代，但这不影响循环的总次数，因为它仍然执行5次迭代。
对于i和j的每一次组合，第三个循环（由变量k控制）执行5次，但由于if (k == i || k == j) continue;的存在，当k等于i或j时会跳过当前迭代。然而，这同样不影响循环的总次数，它仍然执行5次迭代。

该算法整体的时间复杂度是三个循环的复杂度相乘，即O(5 * 5 * 5) = O(125)。由于这里的125是一个常数，这段代码的时间复杂度是O(1)，因为循环次数不随任何输入规模的变化而变化。

空间复杂度

代码使用了几个整数变量（i, j, k, count）和一些用于printf的临时变量（用于存储格式化字符串的参数）。
没有使用任何动态分配的内存（如数组或链表），也没有使用递归调用导致栈空间增长。
所有使用的变量都是局部变量，它们所占用的空间在函数执行期间是固定的，不随输入规模的变化而变化。

因此，这段代码的空间复杂度是O(1)，即常数空间复杂度，程序使用的内存空间不随输入规模的增大而增大。