算法思想:穷举法
- 算法
- 2024-06-05
- 970热度
- 0评论
基本概念
穷举法思想,也称为暴力枚举法或遍历法,是一种简单直观解决问题的方法。它的基本思想是对所有可能的情况进行逐一测试,直至找到符合要求的解或确定无解为止。
穷举法思想主要涉及以下几个关键步骤:
确定问题空间:
明确问题所有可能解构成的空间或集合。这个空间可以是一个数值范围、一个字符串集合、一个组合或排列的集合等。
逐一测试:
程序按照某种顺序(如从小到大、从前往后等)遍历这个空间中的每一个元素或状态。对于每个元素或状态,程序会检查它是否满足问题的要求或条件。
检查条件:
在遍历过程中,程序会根据问题的具体要求进行条件判断。如果当前元素或状态满足条件,则可能是一个解(或最优解),或者可能是进一步搜索的起点。如果不满足条件,则继续遍历下一个元素或状态。
记录结果:
一旦找到满足条件的解,程序通常会记录这个解,并可能继续搜索以寻找更多的解或最优解。如果遍历完整个空间都没有找到解,则程序会输出无解的信息。
找出所有三位数中的水仙花数
问题描述
水仙花数(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),即常数空间复杂度,程序使用的内存空间不随输入规模的增大而增大。