【刷题系列】 分支循环

简介: 分支循环必刷题
1.二分/折半查找

🎈题目描述

用二分查找法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值,若找到key则输出其在数组中对应的下标,否则输出找不到。

🎈代码实现

//二分查找||折半查找
//前提:需要查询的数组为有序数组
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main() {
    
    int arr[] = { 1,2,3,4,5,6,7,8,9};
    
    int sz = sizeof(arr) / sizeof(arr[0]);
    int mid = 0, a = 0;
    scanf("%d", &a);
    int left = 0, right = sz - 1;
    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] < a) 
        {
            left = mid + 1;
        }
        else 
        {
        if (arr[mid] > a) 
        {
            right = mid - 1;
        }else
        {
            printf("找到了,元素的所在的下标为:%d\n", mid);
            break;
            }
        }
    }
    if(left > right)
    {
        printf("数组中不包含此元素\n");
    }
    return 0;
}     

利用函数half_search实现折半查找

#include <stdio.h>

int binary_search(int arr[], int a, int sz)    //将数组 要查找的数 数组大小传入
{
    int left = 0;        //左右下标均在函数内定义
    int right = sz-1;   //字符串以 '\0' 结束,减去一位。
    while(left<=right)
    {
        int mid = left+(right-left)/2;      //定义mid  
        if(arr[mid] < a)       用mid对应的元素与a比较
        {
            left = mid+1;
        }
        else if(arr[mid] > a)
        {
            right = mid-1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int a= 0;
    scanf("%d",&a);
    int sz = sizeof(arr)/sizeof(arr[0]);
    int ret = binary_search(arr, a, sz);
    if(ret == -1)
    {
        printf("找不到\n");
    }
    else
    {
        printf("找到了, 下标是:%d\n", ret);
    }
    
    return 0;
}

📌代码剖析

二分查找法(Binary Search)算法,也叫折半查找算法。二分查找要求数组数据必须采用顺序存储结构有序排列。查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0,时间复杂度为O(logn)。

过程:

二分查找有两个限制条件:

  1. 查找的数量只能是一个,不能是多个
  2. 查找的对象在逻辑上必须是有序的

为了防止left和right的整型值过大而导致溢出,引起位数丢失,可以将mid写为:

mid = left +(right-left)/2;
2.判断素数;

🎈题目描述

输出100-200之间所有的素数,并输出100-200之间素数的个数.

🎈代码实现

//判断是否是素数
#include<stdio.h>
int main()
{
    int i = 0,count=0;
    for (i = 101; i <= 200; i++)
    {
        int j = 0;
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                break;
            }
        }
        if (j == i)
        {
            printf("%d\n", i);
            count++;
        }
    }
    printf("count  = %d ",count);
}

利用函数实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int judge(int i){
    int j = 0;
    for (j = 2; j <= sqrt(i); j++) {
        if (i % j == 0) {
            return 0;
        }
    }    
  return 1;    
}
int main() {
    int i = 0;
    int count = 0;
    for (i = 101; i <= 200; i++) {
        if (judge(i)) {
            printf("%d\n", i);
            count++;
        }
    }
    printf("count = %d\n", count);
}

🎈代码剖析:

素数又称质数。所谓素数是指除了 1 和它本身以外,不能被任何整数整除的数,例如17就是素数,因为它不能被 2~16 的任一整数整除。

📌思路1):因此判断一个整数m是否是素数,只需把 m 被 2 ~ m-1 之间的每一个整数去除,如果都不能被整除,那么 m 就是一个素数。

📌思路2):判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除,只需被 2 ~ sqrt(i)之间的每一个整数去除就可以了。如果 m 不能被 2 ~ sqrt(i)任一整数整除,m 必定是素数。

例如判断 17 是是否为素数,只需使 17 被 2~4 之间的每一个整数去除,由于都不能整除,可以判定 17 是素数。

所以 只需要使i逐个除以sqrt(i),如果存在可以整除的数,则直接跳出,如果不存在,则为素数

3.打印n*n乘法表

🎈题目描述

输入一个数字n,打印n*n的乘法口诀表

🎈代码实现

#include<stdio.h>
int main() {
    int i, j;
    int result = 0;
    int n = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            result = j * i;
            printf("%d * %d = %d   ", i, j, result);
            //printf("%d * %d = %-2d   ", i, j, result);
            //表示为左对齐且限制result为两位数
        }
        printf("\n");
    }
    return 0;
}

🎈代码剖析;

使用内外循环,i控制行,j控制列,内循环实现乘法公式的输出,而且保持j <= i,外循环最后一步输出换行实现表的输出.

📌代码优化: 利用%2d使=后边保持两位数字,不够则补零,利用-%2d使结果左对齐,使输出结果规范

4.字符串替换

🎈题目描述

编写代码,演示多个字符从两端移动,向中间汇聚,实现字符串的替换

🎈代码实现

#include<stdio.h>
int main() {
    char arr1[] = "welcome to bit!!!!";//!空格也算一个元素
    char arr2[] = "##################";
    int left = 0;
    int right = strlen(arr1) - 1;//sizeof(arr1)/sizeof(arr1[0]) - 2;
    printf("%s\n", arr2);
    while (left <= right){
     Sleep(1000);//表示暂停1000ms
     System("cls");
     arr2[left] = arr1[left];
     arr2[right] = arr1[right];
     left++;
     right--;
     printf("%s\n", arr2);
    }
    return 0;
}

🎈代码剖析:

要想实现arr1和arrr2的交换,先定义lefth和right,使arr1[left]和arr2[left]进行交换,arr1[right]和arr2[right]进行交换,然后使left自加一,right自减一,直到left>=right即可.

📌代码优化:

使用Sleep(1000)指令可以使程序暂停1000ms,可以更加清楚展现替换的过程.

使用system库函数,执行指令"cls",使程序没输出一次就清空屏幕输出下一次

5.数字9的个数

🎈题目描述

编写程序数一下 1到 100 的所有整数中出现多少个数字9

🎈代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main() {
    int i = 0;
    int count = 0;
    for (i = 1; i <= 100; i++) {
        if (i % 10 == 9) {
            count++;
        }
        if (i / 10 == 9) {
            count++;
        }
    }
    //9 19 29 39 49 59 69 79 89 99 90 -98
    printf("1-100以内出现了%d次数字9",count);
}

🎈代码剖析

如果i对10取余等于9,则count自加,如果i除以10等于9,则count自加,其中99同时满足以上两个条件则count++了执行两次.

利用for循环对1-100之间所有的数进行测试,满足条件则count++,即可得出答案.

6.打印菱形

用C语言在屏幕上输出以下菱形

实现

#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int i = 0;
        for (i = 0; i < n; i++) {
            int j = 0;
            for (j = 0; j < n - 1 - i; j++) {
                printf(" ");
            }
            for (j = 0; j < 2 * i + 1; j++) {
                printf("*");
            }
            printf("\n");
        }
        for (i = 0; i < n - 1; i++) {
            int j = 0;
            for (j = 0; j <= i; j++) {
                printf(" ");
            }
            for (j = 0; j < 2 * (n - i - 1) - 1; j++) {
                printf("*");
            }
            printf("\n");
        }
    }
    return 0;
}
相关文章
|
29天前
|
C语言
分支与循环讲解
分支与循环讲解
|
3月前
|
程序员 编译器 C语言
分支和循环(一)
分支和循环(一)
|
3月前
|
C语言
分支和循环(二)
分支和循环(二)
|
3月前
质数类判断方法(蓝桥杯,循环分支题型)
质数类判断方法(蓝桥杯,循环分支题型)
|
4月前
|
C语言
分支和循环(2)
分支和循环(2)
45 3
|
4月前
|
C语言
分支和循环(1)
分支和循环(1)
27 0
|
4月前
循环与分支——猜数字游戏(下)
循环与分支——猜数字游戏(下)
25 0
|
4月前
|
算法 编译器 C语言
循环与分支——猜数字游戏实现(上)
循环与分支——猜数字游戏实现(上)
30 0
|
编译器 C语言
分支与循环(1)
分支与循环(1)
分支与循环(1)
|
10月前
|
算法 C语言 数据安全/隐私保护
【C语言刷题】分支与循环系列
【C语言刷题】分支与循环系列
83 1