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)。
过程：
二分查找有两个限制条件：
- 查找的数量只能是一个，不能是多个
- 查找的对象在逻辑上必须是有序的
为了防止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;
}
