手写C语言之分支循环语句-二分查找算法实现（08）
【摘要】
目录
前言计算 n 的阶乘计算 1!+2!+3!+……+10!在一个有序数组中查找具体的某个数字n（二分查找）编写代码，演示多个字符从两端移动，向中间汇聚编写代码实现，模拟用户登录情景，并且只能登...
前言
前面我们学习判断循环，下面将我们所学的知识进行实际的应用！
- 计算 n的阶乘。
- 计算 1!+2!+3!+……+10!
- 在一个有序数组中查找具体的某个数字n。（二分查找）
- 编写代码，演示多个字符从两端移动，向中间汇聚。
- 编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码正确则提示登录成，如果三次均输入错误，则退出程序
计算 n 的阶乘
#include <stdio.h>
int main() {
int i = 0;
int tep = 1;
for (int i = 1; i <= 10; i++) {
tep *= i;
}
printf("%d", tep);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
这里是求得10的阶乘！那么要计算n的阶乘，那么只需要将10换成n即可！
计算 1!+2!+3!+……+10!
首先需要弄懂这个算法逻辑是什么？到底应该如何去设计，前面一道题说了，计算阶乘，那么这里只是一个将阶乘求和一下就OK了。
#include <stdio.h>
int main() {
int n = 0;
scanf("%d", &n);
int result = 0;
for (int i = 1; i <= n; i++) {
int temp = 1;
for (int j = 1; j <= i; j++) {
temp *= j;
}
result += temp;
}
printf("%d", result);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
有人觉得上面的时间复杂度很高，那么如何改进呢？因为代码中用到了两处循环，如果循环次数单个是n的话，那么一共就是n的平方！所以如果我们能够把多重循环降低的话，那么可以很快的节省我们的额时间！
#include <stdio.h>
int main() {
int ret = 1;
int reslut = 0;
for (int n = 1; n <= 10; n++) {
ret *= n;
reslut += ret;
}
printf("%d", reslut);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
这里只用到了一次循环，时间复杂度就已经降低了，我们可以测试一下二者的时间！
#include <stdio.h>
#include <time.h>
int main() {
int ret = 1;
int resluts = 0;
clock_t start_time, end_time;
int result = 0;
start_time = clock();
for (int i = 1; i <= 10000; i++) {
int temp = 1;
for (int j = 1; j <= i; j++) {
temp *= j;
}
result += temp;
}
end_time = clock();
printf("%d", result);
printf("传统的双重嵌套循环用时： %lfs\n", (double)(end_time - start_time) / CLOCKS_PER_SEC);
clock_t start_time1, end_time1;
start_time1 = clock();
for (int n = 1; n <= 10000; n++) {
ret *= n;
resluts += ret;
}
end_time1 = clock();
printf("%d", resluts);
printf("修改后的程序用时 : %lfs\n", (double)(end_time1 - start_time1) / CLOCKS_PER_SEC);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
我们可以发现时间对比，第二个明显比第一个要快很多！
在一个有序数组中查找具体的某个数字n（二分查找）
什么叫有序数组，就是已经排好序了
传统的解决方法就是从前往后遍历，但是这样的效果太低了，速度很慢，如果成千上万的数组，那么我们查找起来就非常的麻烦！有没有什么办法呢？这里我们就需要介绍一个关于数据结构的二分查找，又叫折半法。
二分查找升级版（自定义起始值和结束值序列，并且输入查找数即可查找！）
这里运用到数组的语法，注意我们在产生有从长度的数组的时候，需要指定长度，不然会编译报错！
#include <stdio.h>
int main() {
int num1 = 0;
int num2 = 0;
int k = 0;
printf("请输入需要产生的有序序列数组的起始值：");
scanf("%d",&num1);
printf("请输入需要产生的有序序列数组的结束值：");
scanf("%d", &num2);
int arr[100] = { 0 };
printf("请输入你要查找的数：");
scanf("%d",&k);
//产生0-num2个数值
for (int i = 0; i < num2-num1+1; i++) {
arr[i] = num1+i;
}
for (int j = 0; j < num2 - num1; j++)
printf("%d", arr[j]);
printf("\n");
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz;
while (left <=right) {
int mid = (left + right) / 2;
if (arr[mid] < k) {
left = mid + 1;
}
else if (arr[mid] > k) {
right = mid - 1;
}
else {
printf("找到了！下标为：%d\n", mid);
break;
}
}
if (left > right) {
printf("找不到！停止程序！\n");
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
核心算法代码
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz;
while (left <=right) {
int mid = (left + right) / 2;
if (arr[mid] < k) {
left = mid + 1;
}
else if (arr[mid] > k) {
right = mid - 1;
}
else {
printf("找到了！下标为：%d\n", mid);
break;
}
}
if (left > right) {
printf("找不到！停止程序！\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
二分查找函数
int bin_search(int arr[], int left, int right, int key)
{
int mid = 0;
while(left<=right)
{
mid = (left+right)>>1;
if(arr[mid]>key)
{
right = mid-1;
}
else if(arr[mid] < key)
{
left = mid+1;
}
else
return mid;//找到了，返回下标
}
return -1;//找不到
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
编写代码，演示多个字符从两端移动，向中间汇聚
#include <stdio.h>
int main()
{
char arr1[] = "welcome to bit...";
char arr2[] = "#################";
int left = 0;
int right = strlen(arr1) - 1;
printf("%s\n", arr2);
//while循环实现
while (left <= right)
{
Sleep(1000);
arr2[left] = arr1[left];
arr2[right] = arr1[right];
left++;
right--;
printf("%s\n", arr2);
}
//for循环实现
for (left = 0, right = strlen(src) - 1;
left <= right;
left++, right--)
{
Sleep(1000);
arr2[left] = arr1[left];
arr2[right] = arr1[right];
printf("%s\n", target);
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码正确则提示登录成，如果三次均输入错误，则退出程序
#include <stdio.h>
int main()
{
char psw[10] = "";
int i = 0;
int j = 0;
for (i = 0; i < 3; ++i)
{
printf("密码错误，请重新输入:");
scanf("%s", psw);
if (strcmp(psw, "123") == 0)
break;
}
if (i == 3)
printf("密码三次错误！已锁定！请明日再试！\n");
else
printf("登陆成功！\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
这里用到了字符串的比较函数，strcmp（）。基本形式为strcmp(str1,str2)，若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。这个函数是用于比较字符串中字符值的大小的、从第一个字符开始比较！
每文一语
加油！
文章来源: wxw-123.blog.csdn.net，作者：王小王-123，版权归原作者所有，如需转载，请联系作者。
原文链接：wxw-123.blog.csdn.net/article/details/124544247
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）