二分查找以及循环练习

2023-07-17 45

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二分查找以及循环练习

1 在一个有序数组中查找每个具体的某个数字n（二分查找）

常规方法：(缺点：如果要找的数字在最后一位，则需要遍历整个数组，浪费时间）

1. #include <stdio.h>
2. int main()
3. {
4.  int i = 0;
5.  int k = 7;
6.  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
7.  for (i = 0; i < 10; i++)
8.  {
9.    if (arr[i] == k)
10.     {
11.       printf("找到了，下表为%d", i);
12.       break;
13.     }
14.   }
15.   if (i == 10)
16.   {
17.     printf("没有");
18.   }
19.   return 0;
20. }

二分查找法（折半查找法):（比较，缩小范围）

arr[]={1,2,3,4,5,6,7,8,9,10},在这里还是找数字k=7，

首先用1的下标0(left1）,和10的下标9（right1），相加除于2等于4（mid1）余1，用下标为4（mid1）的数字5和7比较，7显然在5的右边；

然后用下标5（mid1+1)(left2)和10的下标9(right2)相加除于2等于7（mid2），用下标为7的数字8和7比较，7在8的右边；

然后用下标6（mid2-1)(right3)和left2（left3）相加除于2等于5（mid3），用下标为5的数字6和7比较，7在6的右边

最后用下标6(mid3+1)和结尾3相加除于2等于6，刚好等于7。

代码展示：

1. #include <stdio.h>
2. int main()
3. {
4.  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
5.  int k = 7;
6.  int a = sizeof(arr) / sizeof(arr[0]);
7.  int left = 0;
8.  int right = a - 1;
9.  while (left <= right)
10.   {
11.     int mid = (right + left) / 2;
12.     if (arr[mid] < k)
13.     {
14.       left = mid + 1;
15.     }
16.     else if (arr[mid] > k)
17.     {
18.       right = mid - 1;
19.     }
20.     else
21.     {
22.       printf("找到了，下标是%d", mid);
23.       break;
24.     }
25.   }
26.   if (left > right)
27.   {
28.     printf("找不到");
29.   }
30.   return 0;
31. }

2 编写代码，演示多个代码从两端移动，向中间汇聚

举例说明： “#######” “a#####g” “ab###fg” “abc#efg” “abcdefg” ，就这样一步一步展示出来的就是多个代码从两端移动，向中间汇聚。

代码展示：

1. #include <stdio.h>
2. #include <windows.h>
3. int main()
4. {
5.  char arr1[] = "abcdefg";
6.  char arr2[] = "#######";
7.  int left = 0;
8.  int right = strlen(arr1) - 1;
9.  while (left <= right)
10.   {
11.     arr2[left] = arr1[left];
12.     arr2[right] = arr1[right];
13.     printf("%s\n", arr2);
14.     Sleep(1000);
15.     system("cls");
16.     left++;
17.     right--;
18.   }
19.   printf("%s", arr2);
20.   return 0;
21. }

代码理解

代码1展示：

1. #include <stdio.h>
2. #include <windows.h>
3. int main()
4. {
5.  char arr1[] = "abcdefg";
6.  char arr2[] = "#######";
7.  int left = 0;
8.  int right = strlen(arr1) - 1;
9.  while (left <= right)
10.   {
11.     arr2[left] = arr1[left];
12.     arr2[right] = arr1[right];
13.     printf("%s\n", arr2);
14.     left++;
15.     right--;
16.   }
17.   return 0;
18. }

新知识：Sleep()函数，括号内放置数字，单位为毫秒（一秒=1000毫秒=1000 000微秒=1000 000 000纳秒），需要时调用的头文件是#include <windows.h> 。

例如：

Sleep(1000),若是上面的代码块中printf()的后面一行插入（代码2展示），编码时，结果会每隔一秒出现一行。就是第一次出现a#####g，一秒后出现a#####g，又一秒后出现a#####g，一秒后出现a#####g

ab###fg ab###fg ab###fg

abc#efg abc#efg

abcdefg

代码2展示：

1. #include <stdio.h>
2. #include <windows.h>
3. int main()
4. {
5.  char arr1[] = "abcdefg";
6.  char arr2[] = "#######";
7.  int left = 0;
8.  int right = strlen(arr1) - 1;
9.  while (left <= right)
10.   {
11.     arr2[left] = arr1[left];
12.     arr2[right] = arr1[right];
13.     printf("%s\n", arr2);
14.     Sleep(1000);
15.     left++;
16.     right--;
17.   }
18.   return 0;
19. }

system("cls")清除调试台的内容。

代码3展示：

1. #include <stdio.h>
2. #include <windows.h>
3. int main()
4. {
5.  char arr1[] = "abcdefg";
6.  char arr2[] = "#######";
7.  int left = 0;
8.  int right = strlen(arr1) - 1;
9.  while (left <= right)
10.   {
11.     arr2[left] = arr1[left];
12.     arr2[right] = arr1[right];
13.     printf("%s\n", arr2);
14.     Sleep(1000);
15.     system("cls");
16.     left++;
17.     right--;
18.   }
19.   printf("%s", arr2);
20.   return 0;
21. }

复习知识点：打印字符串用%s,打印字符用%c.

知识点总结：（1）整数类型数组，求最大下标是多少:a=sizeof(arr[])/sizeof(arrr[0])-1

(2)字符类型：strlen(arr)-1 sizeof(arr[])-2(因为/0也算一个字节）

3 编写代码实现，模拟用户登录情景，并且只能登陆三次（只允许输入三次密码，如果密码正确则提示登陆成功，如果三次均输入错误，则退出程序）

代码展示：

1. #include <stdio.h>
2. #include <string.h>
3. int main()
4. {
5.  int i = 0;
6.  char password[20] = "";
7.  for (i = 0; i < 3; i++)
8.  {
9.    printf("请输入密码");
10.     scanf("%s", password);
11.     if ((strcmp(password, "123456")) == 0)
12.     {
13.       printf("登陆成功\n");
14.       break;
15.     }
16.     else
17.     {
18.       printf("密码错误\n");
19.     }
20.   }
21.   if (i == 3)
22.   {
23.     printf("密码三次均输入错误，退出程序");
24.   }
25.   return 0;
26. }

知识点：

（1）scanf("%d",password) 为什么不是 scanf("%d",&password) 因为password是数组名，数组名本来就是地址，所以不需要取地址符号。

（2）strcmp（）函数是string compare（字符串比较）的缩写，比较字符串返回整数。（头文件是string.h）

strcmp（str1，str2)，str1=str2，返回0:；str1<str2，返回负数；str1>str2，返回正数。

4 猜数字游戏

电脑随机产生一个数字，玩家猜。

代码展示：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
4. void menu()
5. {
6.  printf("**************************\n");
7.  printf("****    1.play   *********\n");
8.  printf("****    0.exit   *********\n");
9.  printf("**************************\n");
10. }
11. void game()
12. {
13.   int guess = 0;
14.   int r = rand()%100 + 1;
15.   while (1)
16.   {
17.     printf("请输入猜测的数字：");
18.     scanf("%d", &guess);
19.     if (guess < r)
20.     {
21.       printf("猜小了\n");
22.     }
23.     else if (guess > r)
24.     {
25.       printf("猜大了\n");
26.     }
27.     else
28.     {
29.       printf("猜测正确");
30.       break;
31.     }
32.   }
33. }
34. 
35. int main()
36. {
37.   int input = 0;
38.   srand((unsigned int)time(NULL));
39.   do
40.   {
41.     menu();
42.     printf("请选择：");
43.     scanf("%d", &input);
44.     switch (input)
45.     {
46.     case 1:
47.       game();
48.       break;
49.     case 0:
50.       printf("退出游戏");
51.       break;
52.     default:
53.       printf("请重新输入");
54.       break;
55.     }
56.   } while(input);
57.   return 0;
58. }

代码新知识：

该代码中，#include <stdlib.h> #include <time.h> 是产生随机数的头文件（记好）

%100 产生的是（0-99）

C语言中随机产生数字的是rand函数（产生的都是整数）(0-32767)，库文件是<stdlib.h>。

二分查找以及循环练习

1 在一个有序数组中查找每个具体的某个数字n（二分查找）

2 编写代码，演示多个代码从两端移动，向中间汇聚

3 编写代码实现，模拟用户登录情景，并且只能登陆三次（只允许输入三次密码，如果密码正确则提示登陆成功，如果三次均输入错误，则退出程序）

4 猜数字游戏

热门文章

最新文章

相关电子书