目录
- 零、说明
- 一、程序设计经典编程题(C语言实现)
- T1 求1~100的奇数
- T2 求n!
- T3 求1!+2!+3!+...+10!
- T4 在一个`有序数组`中查找具体的某个数字n(二分查找)
- T5 编写代码，演示多个字符从两端移动，向中间汇聚
- T6 模拟用户登录(三次机会)
- T7 输入三个数 并从大到小输出
- T8 打印100~200的素数(质数)
- T9 打印1000~2000之间的闰年
- T10 求最大公约数(含递归)
- 补充:辗转相除法的证明
- T11 求最小公倍数
- 二、力扣
- 面试题 17.04. 消失的数字
- 三、牛客网
- BC49 判断两个数的大小关系
- OR62 倒置字符串
- BC84 计算y的值
- BC101 班级成绩输入输出
- BC23 时间转换
- BC50 计算单位阶跃函数
零、说明
第一部分 是平时学习 做真题 做参考书练习 群友提问等等渠道获取到的个人认为比较有价值的题目第二部分和第三部分 是根据真题+题目热度挑选的题目- 本文的难度仅针对普通院校自命题的编程题!
- 如果一道题确实有两种不同的解法(主要体现在时空复杂度确实有改善 或者思路不一样 比如迭代法和递归法) 本文会分为
解法1 解法2进行介绍 - 一般情况下
最多能写到力扣官方题解的第一或者第二层大概可以应付考研的编程题 而力扣官方题解更高级的 甚至站在数学角度上去思考 我也无能为力用代码或图片讲述清楚!
- 必要的时候我会写题目描述;
- 不同的解法思路 我会写上对应的思路+我的错因+我的参考代码 仅供参考
- 如果有 还会写本题的总结和一些反思
一、程序设计经典编程题(C语言实现)
T1 求1~100的奇数
解法1 暴力求解:
解法2: 思考思考 只要知道第一个奇数 后面的+2+2+2不就行了?
总结:
解法1 循环一百次 判断一百次解法2 循环五十次 不需要判断- 初步领略一下算法的魅力 要多思考
- 类似的 下面这道题就可以从3开始打印 每次+3+3+3 而不需要遍历 判断 再打印了
- 还有一种思路:
T2 求n!
- 本题很简单 就是累乘
- 但是我眼睛瞎起来就把ret定义为0 答案恒为0了
参考代码:
int n = 5;
int i = 0;
int ret = 1;//别写成0了
for (i = 1; i <= n; i++)
ret *= i;
printf("%d\n", ret);
T3 求1!+2!+3!+…+10!
解法1:
- 思路:两层循环 第一层循环产生1~10的数据 第二层循环求出1! 2! 3!..并累加
- 注意这种写法
每次求单独求阶乘的时候 ret一定要置为1
- 这种解法不够好
因为有大量的重复计算将在解法2改进
int n = 3;//求1! + 2! + 3!
int i = 0;
int j = 0;
int ret = 1;//每次求单独的阶乘的时候就用它
int sum = 0;
for (int j = 1; j <= n; j++)
{
ret = 1;//所以要记得置为1啊!! 要不然第求下一次阶乘的时候 ret就不是从1开始乘的了
for (i = 1; i <= j; i++)
ret *= i;
sum += ret;
}
printf("%d", sum);
解法2:
- 思路:其实在计算10!的时候 已经出现了1! 2! 3! … 9! 既然如此
就可以一边计算 一边累加 避免了重复计算- 解法2更好 是经过思考的
int main()
{
int n = 10;
int i = 0;//控制循环
int ret = 1;//用于产生1! 2! 3!...10!
int sum = 0;
for (i = 1; i <= n; i++)
{
ret *= i;//在产生10!的过程中 其实已经产生了1! 2! 3!...
sum += ret;//边乘边加
}
printf("%d ", sum);
return 0;
}
T4 在一个有序数组中查找具体的某个数字n(二分查找)
解法1 直接暴力求解:
解法2 二分查找:
- 前提是:
有序所以不能乱给测试数组- right = mid-1; left = mid+1;
我一开始没有+-1 会导致死循环- int right = len - 1;
-1别忘记了 right是下标- 出循环之后有两种写法 可以利用flag 也可以直接判断
写法一:
#include<stdio.h>
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,11 };//测试数组 一定是有序的
int len = sizeof(arr) / sizeof(int);//数组元素个数
int k = 11;//查找目标
int flag = 0;//假设一开始默认找不到k 找到了就把第flag置为1
int left = 0;
int right = len - 1;
int mid = 0;
// = 也是可以取的 当left=right的时候 肯定还要进去判断一次
while (left <= right)
{
//每次进循环 都要算出一个新的mid进行判断
mid = (left + right) / 2;
if (arr[mid] < k)
//说明k在mid的右边
{
left = mid + 1;
}
else if (arr[mid] > k)
//说明k在mid的左边
{
right = mid - 1;
}
else
{
//这里已经可以输出mid的信息了 但是我放在下面打印
//把提示信息统一都放在循环外处理
flag = 1;
break;
}
}
//程序执行到这 有两种可能
//1.while全都判断完 自然结束 也就是最终没找到k 此时flag = 0
//2.flag = 1之后 break到这里来
if (flag)
printf("找到了下标是:%d\n", mid);
else
printf("没找到");
return 0;
}
写法二: 主要差异在于出循环之后 我怎么输入"没找到"比较合适
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10};
int num = 0;
while (2)
{
printf("输入你要查到的数字:\n");
scanf("%d", &num);
int left = 0;
int right = (sizeof(arr) / sizeof(int))-1;
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] > num)
right = mid-1;
else if (arr[mid] < num)
left = mid+1;
else
{
printf("找到了 下标是%d\n", mid);
break;
}
}
//走到这里 有两种情况 1.找到了break出来 2.没找到 但是left不<=right 循环结束了
//我直接判断一下此时mid对应的元素是不是num就能确定找没找到了 不需要flag也行
if (arr[mid] != num)
printf("没找到\n");
}
return 0;
}
T5 编写代码，演示多个字符从两端移动，向中间汇聚
题目描述:
打印hello world!
############
h##########!
he########d!
hel######ld!
hell###r#ld!
hello##orld!
hello world!
解法1:
- 双"指针" 一左一右 开始打印有效字符
- 每次肯定都是打印十个字符 打印几次由while来决定
- left和right把10个要打印的字符分成三部分 [0,left]打印对应的有效字符 [right,len-1]打印对应的有效字符 剩余部分打印#
- 相较于思路2 更节省空间
错因:
- 打印#的判断条件写错了 左右不分??!!
开区间(left,right)范围打印#- 每一次for循环结束
不要忘记++和-- 也不要忘记换行
#include<stdio.h>
#include<windows.h>
#include<string.h>
int main()
{
char ch[] = "hello world!";
int len = strlen(ch);//12
int left = 0;
int right = len - 1;
int i = 0;
while (left<=right)
{
for (i = 0; i < len; i++)
{
if (i > left && i < right) //易错
printf("#");
else
printf("%c", ch[i]);
}
printf("\n");
Sleep(1000);
left++;
right--;
}
return 0;
}
解法2:
- 给出两个数组 一个是字符 一个是# 注意#和字符的个数肯定都是一样的
- 然后也是用了两个指针 一左一右依次把字符赋给放#的那个数组
- 打印的时候 用%s专门只打印#的那个数组即可
错因:
- len–>求的是元素个数 也就是字符个数
故下标最大值是len-1判断部分是<=当左右指针指向同一个元素的时候 也要进入循环的
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>
#include<string.h>
int main()
{
char ch1[] = "zhuchenyang66dds6!";
char ch2[] = "******************";
int len = strlen(ch1);
int left = 0;
int right = len - 1;
for (left = 0, right = len - 1; left <= right; left++, right--)
{
ch2[left] = ch1[left];
ch2[right] = ch1[right];
printf("%s\n", ch2);
Sleep(100);
}
return 0;
}
或者写成while循环 都是一样Sleep()的头文件是windows.hsystem()的头文件是stdlib.h
T6 模拟用户登录(三次机会)
题目描述:
编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码则提示登录成，如果三次均输入错误，则退出程序。
解法1 利用strcmp函数:
- 定义要输入的密码 正确密码
count是还剩下几次机会- 只要count还没==0 就可以进去输入密码
我的错因:
- 一开始用的是下图这种定义方式 这样定义的话 其实数组大小是确定的 数组里放了一个空格 一个\n
元素个数(strlen)是1 大小(sizeof)是2字节下面输入密码肯定会越界的
2. 比较字符串是否相等不能用== 要用strcmp()函数 第一个参数比第二个参数大 就返回>0 相等的话返回0
#include<stdio.h>
#include<string.h>
int main()
{
char pswd[100] = " ";
char answer[100] = "zhukefu123";
int count = 3;
while (count>0)
{
printf("您还有%d次机会,请输入密码:\n",count);
scanf("%s", pswd);
if (strcmp(pswd, answer) != 0)
{
printf("密码错误!\n");
count--;
continue;
}
else
{
printf("密码正确!\n");
break;
}
}
if (count == 0)
printf("您没有机会了!!\n");
return 0;
}
解法2 直接暴力求解 相当于模拟实现了strcmp:
- 这里我犯了一个离谱的错误
多打了一个; 也就是这个if 啥也不干! 然后继续往下执行!
- 下图这部分写错了 左闭右开的话
右边就是循环次数也就是字符串长度是不需要-1的 -1会导致少判断最后一个字符也就是zcygst667也被算成密码正确了
- char ch[10] = " "; 10给的太小了!!! 要么限定用户只能输入多少的字符(一般交给前端限制) 要么给大点 否则
如果我测试的时候输入了一个zcysdshjadhshkd 会有栈溢出err- 这个错误算是值得注意的点 我要是用flag这种写法的话
每次给你一次新机会输入密码的时候 flag都应该重置为1!!!!否则在以下情况会出现问题: 当我第一次输入zcygst667 进入for的时候 把flag置为0 如果我后面输入了正确密码zcygst666 虽然不会执行flag=0 但是for循环出来走到if (flag == 1)的时候 发现flag上次已经给他置为0了 所以不进入if 直接继续下一次循环了 仿佛跳过了这次正确的输入- 主要就三个点的错误(下图已经修正)
int main()
{
int total = 8;
int i = 0;
char ch[1000];
char real[1000] = "zcygst666";
int flag = 1;
while (total > 0)
{
flag = 1;
scanf("%s", ch);
if (strlen(real) == strlen(ch))
{
for (i = 0; i < strlen(ch); i++)
{
if (ch[i] != real[i])
{
printf("错误\n");
total--;
flag = 0;
printf("还剩%d次机会\n", total);
break;
}
}
//程序走到这这里
//1.break出来的 flag已经是0
//2.判断发现全相等 循环自然结束 flag仍然是1
if (flag == 1)
{
printf("正确\n");
break;
}
}
else
{
printf("两个字符串长度都不一样!!错误\n");
total--;
printf("还剩%d次机会\n", total);
}
}
return 0;
}
- 其实我想说的是 针对解法2那个flag置为1的错误 还是要具体问题具体分析的 具体看自己的思路是什么 灵活编写代码
- 比如下面的代码(一开始给flag初始化的是0 密码正确再改为1) 就不需要每次都置为1
所以要多写多练多反思 该置为1的时候 我自己心里有数就行
int main()
{
int i = 10;
char real[20] = "zcygst";
char input[20];
int flag = 0;
while (i > 0)
{
scanf("%s", input);
if (strcmp(real, input) != 0)
{
//密码错误 那就不要动flag 本身就是0!
i--;
printf("err还剩%d次机会\n", i);
}
else
{
//输对了才改为1
flag = 1;
printf("yes\n");
break;
}
}
//1.要么是break到这里的时候 此时flag为1
//2.要么就是一次都没输对 不满足i>0跳到这里来 此时flag一直保持是0
if (flag == 0)
printf("你没机会了\n");
return 0;
}
T7 输入三个数 并从大到小输出
思路:
确定三个数了 用排序似乎有点小题大做了
其实比较三次即可 保证a放的最大 c放的最小 然后打印abc即可
而且三次比较都要交换 不如封装成一个函数 但是注意这个函数就必须要传地址了
#include<stdio.h>
void swap(int* x,int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int main()
{
int a = 1;
int b = 1;
int c = 1;
printf("请输入三个数:>\n");
scanf("%d %d %d", &a, &b, &c);
//目标:让a里放最大 b其次 c最小
//前两个if可以保证a最大 第三个if让c最小
if (a < b)
swap(&a, &b);
if (a < c)
swap(&a, &c);
if (c > b)
swap(&b, &c);
//从大到小输出
printf("%d %d %d", a, b, c);
return 0;
}
T8 打印100~200的素数(质数)
思路:
- 素数只能被1和本身整除 如果能找到一个非1非本身的因数 就可以判断不是素数
- 判断i是不是素数的时候
可以从闭区间[2,i-1]试除优化1:只要试除[2,根号i]比如16 如果有因数 一定是成对出现的 比如1-16 2-8 4-4 如果只看一半的话 肯定是不会大于根号16的(≤)- 优化2:
偶数肯定不是素数直接从101开始 每次i+2从奇数里面找素数
- double sqrt (double x);需要math.h的头文件 不放心的话循环里也可以强转成int
- 以上的方法
都叫"试除法"推荐博文:<<素数求解的N种境界>>
#include<stdio.h>
#include<math.h>
int main()
{
int i = 0;
int j = 0;
int flag = 1;
//产生100-200的素数
for (i = 100; i <= 200; i++)
{
//每次产生的i 开始都先认为他是个素数
flag = 1;
//这里是<=啊 写<的话 49也被判断成素数了
for (j = 2; j <= (int)sqrt(i); j++)
{
if (i % j == 0)
{
flag = 0;//那就不是素数
break;//只要有一次能进来 就直接break了
}
}
//走到这儿来 可能是
//1.break到这儿来 此时flag=0
//2.循环条件结束 此时flag仍未1 也就是i%j一次都不等于0 没机会把flag置为0 说明是素数
if (flag)
printf("%d ", i);
}
return 0;
}
T9 打印1000~2000之间的闰年
1. 能被4整除 但是不能被100整除的 是闰年2. 能被400整除 也是闰年
3. 其实可以i+=4 从1.2.的规则来看 闰年肯定能被4整除
int i = 0;
for (i = 1000; i <= 2000; i++)
{
if ((i % 400 == 0) || ((i % 4 == 0) && (i % 100 != 0)))
printf("%d ", i);
}
注意了 如果要用if来写的话
就是俩个if(并列关系 都需要判断的)
而不能是else if(非此即彼 只有一个入口)了
如果写的是else if 2000本身是闰年 但是判断他不是 因为只能进去第一个if
