从C到Capable-----寻找肇事车牌(一次循环)
🌧(day43:C2)
目录
📝题目:
🚩题目分析:
💡解题思路:
🌟解法一:
🌈代码实现
✏代码注释
🌟解法二:
🌈代码实现
✏代码注释
📝题目:
一辆卡车违反交通规则,撞人后逃跑。现场共有三个目击者,但都没有记住车号,只记下车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前两位不同;丙是个数学家,他说:4位车号刚好是一个整数的平方。请根据以上线索帮助警方找到车号。
🚩题目分析:
现在已知条件有
- 车牌有4个数字
- 车牌前两个数字相同
- 车牌后两个数字相同
- 车牌4位数为一个数的平方
💡解题思路:
由限制条件车牌只有4个数字,那么我们可以使用枚举的方法找到满足上述条件的数。
由条件:车牌4位数为一个数的平方
我们以此枚举出一个个整数,当这个整数的平方满足剩下的三个条件时,这个整数的平方就是要找的车牌。
再枚举前我们可以先做一个初步的判断,判断从那个数开始枚举。
当然我们可以直接从1开始枚举,直到10000,不过1^2 = 1显然不符合4位数字的要求。
那么考虑到,31x31 = 961,32x32 = 1024, 99x99 = 9810, 100x100 = 10000
我们的枚举便缩小了枚举范围,从32到99
🌟解法一:
由于我们需要判断前后两位车牌数字,也就是判断4位数中的千位,百位和十位,个位。
那么我们可以使用以下方法将千位,百位,十位,个位分离出来判断。
a1,a2,a3,a4分别表示千位数,百位数,十位数,个位数
a1 = n / 1000;
a2 = (n - a1*1000) / 100;
a3 = (n - a1*1000 - a2*100) / 10;
a4 = n - a1*1000 - a2*100 - a3*10;
🌈代码实现
# include # include main(){int a1, a2, a3, a4, n, i;for (i = 32; i <= 99; i++){n = pow(i, 2);a1 = n / 1000;a2 = (n - a1*1000) / 100;a3 = (n - a1*1000 - a2*100) / 10;a4 = n - a1*1000 - a2*100 - a3*10;if ((a1 == a2 && a3 == a4) && (a1 != a3))printf("该车牌号为:%d\n", n);}}
✏代码注释
# include # include main(){// a1,a2,a3,a4分别表示千位数,百位数,十位数,个位数int a1, a2, a3, a4, n, i;for (i = 32; i <= 99; i++){n = pow(i, 2);a1 = n / 1000; // 利用整除求千位数a2 = (n - a1*1000) / 100; // 先将千位数去除(减去)后计算百位数a3 = (n - a1*1000 - a2*100) / 10;a4 = n - a1*1000 - a2*100 - a3*10;if ((a1 == a2 && a3 == a4) && (a1 != a3)) // 带入条件1,2判断printf("该车牌号为:%d\n", n);}}
方法一只含有一次循环,时间复杂度为O(n)。仅使用有限变量储存数字,空间复杂度为O(1)
还不清楚什么是时间复杂度,空间复杂度的同学点这里:一个小故事带你了解大O表示法
🌟解法二:
解法二和解法一的不同之处在于解法二先构造出AABB型的车牌,再根据条件四选出最终车牌。
🌈代码实现
# include # include main(){ int i, j, k, n; for (i = 0; i <= 9; i++) { for(j = 0; j <= 9; j++) { if (i != j) { n = i*1000 + i*100 + j*10 + j; for ( k = 32; k < 95; k++) { if ( k*k == n) { printf("车牌号是:%d。", k*k); } } } } }}
✏代码注释
# include # include main(){ int i, j, k, n; for (i = 0; i <= 9; i++) //枚举前两位 { for(j = 0; j <= 9; j++) //枚举后两位 { if (i != j) //如果满足前两位于后两位不相等的条件 { n = i*1000 + i*100 + j*10 + j; //构造 iijj 型4位数的车牌号 for ( k = 32; k < 95; k++) { if ( k*k == n) //将枚举数平方后与iijj型4位数比较,判断是否为正确车牌 { printf("车牌号是:%d。", k*k); } } } } }}
解法二的时间复杂度较高,如果数据很多,运行起来会很慢。解法二使用三重循环时间复杂度为O(n^3),仅使用有限变量储存数字,空间复杂度为O(1)
今天就到这,明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄