前记
今天有人问了我几道C语言的题，说实话很久没碰过C了，这里仅做一个记录分享出来。
比较字符串大小
忽略大小写，比较字符串大小，并从大小输出
#include<stdio.h>
//忽略大小写，比较字符串大小，并从大小输出
#define MAX 100
void compare(char *a,char *b);
int main(){
char a[MAX];
char b[MAX];
gets(a),
gets(b);
printf("待比较字符串 %s %s \n" ,a,b);
compare(a,b);
return 0;
}
void compare(char *a,char *b){
char* m=a;
char* n=b;
while((*m==*n || *m==*n-32 || *m==*n+32) && *m!='\0'){
m++;
n++;
}
if(*m>=*n){
printf("比较后的字符串: %s %s\n",a,b);
}else printf("比较后的字符串: %s %s\n",b,a);拆分链表
将一个链表A拆分成两个，序号是奇数留在链表A中，序号是偶数保存在链表B中
#include<stdio.h>
#include<stdlib.h>
//将一个链表拆分成两个，奇数留在链表A中，偶数保存在链表B中
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
LinkList List_HeadInsert(LinkList &L);
LinkList DisCreat(LinkList &A);
void printLinkList(LinkList &L);
int main(){
LinkList A,B;
// LNode *p,*q;
A = List_HeadInsert(A);
printf("拆分前的链表A：");
printLinkList(A);
printf("\n");
B = DisCreat(A);
printf("拆分后的链表A：");
printLinkList(A);
printf("\n");
printf("拆分后的链表B：");
printLinkList(B);
}
LinkList DisCreat(LinkList &A){
//将表A中结点按序号的奇偶性分解到表A和表B中
LinkList B;
int i=0; //记录A中的结点序号
B=(LinkList)malloc(sizeof(LNode)) ; //创建B表表头
B->next=NULL; //B表的初始化
LNode *ra=A,*rb=B,*p;
p=A->next; //p为链表工作指针，指向带分解点
A->next=NULL;
while(p){
i++;
if(i%2==0) {
//序号为偶数
rb->next=p;
rb=p;
}else{
//序号为奇数
ra->next=p;
ra=p;
}
p=p->next;
}
ra->next=NULL;
rb->next=NULL;
return B;
}
LinkList List_HeadInsert(LinkList &L){
//头插法创建单链表
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL;
scanf("%d",&x);
while(x!=-1){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
void printLinkList(LinkList &L) {
LNode *p;
p=L->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
}
螺旋矩阵
#include<stdio.h>
#define MAX 100
int main(){
int a[MAX][MAX];
int i,j,t,n;
t=0;
scanf("%d",&n);
//初始化螺旋方阵
for(i=0;i<(n+1)/2;i++){
for(j=i;j<n-i;j++) //从左往右走
a[i][j]=++t;
for(j=i+1;j<n-i;j++) //从上往下走 （走到最后一行）
a[j][n-i-1]=++t;
for(j=n-i-2;j>=i;j--) //从右往左走 （从倒数第二列往左走，走到第i行）
a[n-i-1][j]=++t;
for(j=n-i-2;j>i;j--) //从下往上走
a[j][i]=++t;
}
//打印矩阵
for(i=0;i<n;i++){
for(j=0;j<n;j++)printf("%-5d",a[i][j]) ;
printf("\n");
}
return 0;
}#include<stdio.h>
#define MAX 10
int main(){
int a[MAX][MAX]={0};
int i,j,t,n,N;
t=1;
scanf("%d",&N);
//初始化螺旋方阵
for(n=0;n<=N/2;n++){
for(j=n;j<=N-n-1;j++) //从左往右走
a[n][j]=t++;
for(i=n+1;i<N-n-1;i++) //从上往下走 （走到倒数第二行）
a[i][N-n-1]=t++;
for(j=N-n-1;j>n;j--) //从右往左走 （从最后一列往左走，走到第n+1列）
a[N-n-1][j]=t++;
for(i=N-n-1;i>n;i--) //从下往上走
a[i][n]=t++;
}
//打印矩
for(i=0;i<N;i++){
for(j=0;j<N;j++)printf("%-5d",a[i][j]) ;
printf("\n");
}
return 0;
}
按顺时针方向输出m*n阶矩阵
#include<stdio.h>
//螺旋矩阵， 按层模拟，用了递归的思想
int main(){
int rows , columns,num;
scanf("%d %d\n" , &rows,&columns);
int matrix[rows][columns];
int *returnSize;
int order[rows*columns];
//定义指针没给指向 不能直接赋值
int a=0;
returnSize= &a;
if (rows == 0 || columns == 0) {
printf("NULL\n");
return 0;
}
for(int i=0;i<rows;i++)
for(int j=0;j<columns;j++){
scanf("%d" , &num);
matrix[i][j]=num;
}
for(int i=0;i<rows;i++){
for(int j=0;j<columns;j++){
printf("%-4d",matrix[i][j]);
}
printf("\n");
}
int i,j;
for(i=0;i<(columns+1)/2;i++){
for(j=i;j<columns;j++) //从左向右
order[(*returnSize)++] = matrix[i][j];
for(j=i+1;j<rows;j++) //从上到下
order[(*returnSize)++] = matrix[j][columns-i-1];
for(j=columns-i-2;j>=i;j--) //从右到左
order[(*returnSize)++] = matrix[rows-i-1][j];
for(j=rows-i-2;j>i;j--) //从下到上
order[(*returnSize)++] = matrix[j][i];
}
for(int i=0;i<*returnSize;i++) printf("%-4d",order[i]);
return 0;
}标准头文件结构
#ifndef __LIST_HEAD__
#define __LIST_HEAD__
#include "node.h"
typedef struct _list{
Node* head;
Node* tail;
}List;
#endif输入输出格式
6会填充到*号处，表示截图为6
弦截法 求方程的 近似根
#include<stdio.h>
#include<math.h>
//用弦截法求方程近似根
void secantMethod(double x1,double x2);
double fun(double x) ;
int main(){
double x1,x2;
x1=1;
x2=3;
secantMethod(x1,x2);
return 0;
}
double fun(double x) {
double f ;
f = 2*x*x*x-4*x*x+3*x-6;
return f;
}
void secantMethod(double x1,double x2){
double x,f;
do{
x=1.0*(x1*fun(x2)-x2*fun(x1))/(fun(x2)-fun(x1));
f=fun(x);
if(f*fun(x1)>0){
x1=x;
}else x2=x;
}while(fabs(f)>=1e-5);
printf("2*x*x*x-4*x*x+3*x-6=0的根：%f\n",x);
}汉诺塔问题
一．起源
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二．抽象为数学问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
解：（1）n == 1
第1次 1号盘 A—->C sum = 1 次
(2) n == 2
第1次 1号盘 A—->B
第2次 2号盘 A—->C
第3次 1号盘 B—->C sum = 3 次
（3）n == 3
第1次 1号盘 A—->C
第2次 2号盘 A—->B
第3次 1号盘 C—->B
第4次 3号盘 A—->C
第5次 1号盘 B—->A
第6次 2号盘 B—->C
第7次 1号盘 A—->C sum = 7 次
不难发现规律：1个圆盘的次数 2的1次方减1
2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
。 。 。 。 。
n个圆盘的次数 2的n次方减1
故：移动次数为：2^n – 1
三．调用方法的栈机制
特点：先进后出
从主线程开始调用方法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。
四．算法分析（递归算法）
我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法可以简单分为三个步骤：
（1） 把n-1个盘子由A 移到 B；
（2） 把第n个盘子由 A移到 C；
（3） 把n-1个盘子由B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
（1）中间的一步是把最大的一个盘子由A移到C上去；
（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上
#include<stdio.h>
//汉诺塔问题
//递归(递归出口n=0)、栈
int move(int n,char a,char b,char c); //将n个圆盘从A移动到C
int main(){
int n;
scanf("%d",&n);
printf("移动n个圆盘所需要的次数:%d\n",move(n,'A','B','C'));
return 0;
}
int move(int n,char a,char b,char c){
int cnt;
if(n==0){
cnt = 0;
}else if(n==1){
cnt = 1;
printf("%c->%c\n",a,c);
}else{
cnt = move(n-1,a,c,b); //将n-1个圆盘从A移动到B
printf("%c->%c\n",a,c); //将最大的圆盘从A移动到C
cnt++;
cnt =cnt + move(n-1,b,a,c); //将n-1个圆盘从B移动到C
}
return cnt;
}
字符串交换问题
字符串交换问题：字符串以A开头和以K结尾的单词进行交换
strtok
分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符（如果传入字符串，则传入的字符串中每个字符均为分割符）。首次调用时，s指向要分解的字符串，之后再次调用要把s设成NULL。每次调用成功则返回指向被分割出片段的指针。
如果s为空值NULL，则函数保存的指针SAVE_PTR在下一次调用中将作为起始位置。
如：Before： I AM A OK BOY VERY OK
After： I OK OK A BOY VERY AM
#include<stdio.h>
#include<string.h>
#define N 60
int main(){
char orginal[]="I AM A OK BOY VERY OK";
char *p,*delim=" ",*r[N]={0};
int k=0,i,j,len;
printf("\nOrginal:\n");
p=strtok(orginal,delim); //第一次调用p指向 ‘I’
printf("%s\t",p);
r[k++]=p; //*r[]指针数组，每一个数组元素是一个指针
//将分割出来的单词保存在*r[]这个指针数组中
while(p=strtok(NULL,delim)){
printf("%s\t",p);
r[k++]=p;
}
// 交换
i=0;
j=k-1;
while(i<=j){
len=strlen(r[j]);
if(r[i][0]!='A')
i++;
if(r[j][len-1]!='K')
j--;
if((r[i][0]=='A')&&(r[j][len-1]=='K')){
p=r[i];
r[i]=r[j];
r[j]=p;
i++;
j--;
}
}
printf("\nResult:\n");
for(i=0;i<k;i++){
printf("%s\t",r[i]);
}
printf("\n");
return 0;
}
三天打鱼两天晒网
某人从1990年1月1日起开始“三天打鱼两天晒网”，问这个人在以后的每一天是打鱼还是晒网
算法分析
- 计算从1990年1月1日开始到指定日期有多少天（如：1990年1月2日到1990年1月1日有2天）另：要计算闰年
- 打鱼晒网的周期为5天，所以计算的天数用5去除
- 用余数判断是打鱼还是晒网
- 余数为1 打鱼
- 余数为2 打鱼
- 余数为3 打鱼
- 余数为4 晒网
- 余数为0 晒网
#include<stdio.h>
#define Year 1990
int isLeap(int year);
int main(){
int year ,month,day,i,n=0;
int num[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
printf("请输入年月日(如1990-3-3但是要大于90年的1月1日)\n:");
scanf("%d-%d-%d-",&year,&month,&day);
if(isLeap(year)) num[2] +=1;
for(i=Year;i<year;i++){
if(isLeap(i))
n = n + 366;
else
n = n + 365;
}
for(i=1;i<month;i++){
n = n + num[i];
}
n += day;
printf("\n从%d年1月1日起到%d年%d月%d日共经过了%d天\n\n",Year,year,month,day,n);
if(n%5==0||n%5==4){
printf("%d年%d月%d日他在晒网\n\n",year,month,day);
}else
printf("%d年%d月%d日他在打鱼\n\n",year,month,day);
return 0;
}
int isLeap(int year){
int flag=0;
if((year%4==0&&year%100!=0)||(year%400)==0){
flag=1;
}
return flag;
}
判断是否闰年
判断任意年份是否为闰年，需要满足以下条件中的任意一个：
① 该年份能被 4 整除同时不能被 100 整除；
② 该年份能被400整除。
#include<stdio.h>
int main(){
//判断是否是闰年
//① 该年份能被 4 整除同时不能被 100 整除；
//② 该年份能被400整除。
//①②中满足一个即可
int n;
scanf("%d",&n);
if((n%4==0&&n%100!=0)||(n%400)==0){
printf("%d是闰年",n);
}else printf("%d不是闰年",n);
return 0;
}字符串插入问题
编写自定义程序段，实现在字符串Str1的r位置插入字符串str2
#include<stdio.h>
#include<string.h>
#define MAX 100
//编写自定义程序段，实现在字符串Str1的r位置插入字符
//r从0数起
串str2
int main(){
char str1[MAX];
char str2[MAX];
int len1=0,len2=0,r,i,j;
scanf("%s",str1);
scanf("%s",str2);
scanf("%d",&r);
len1=strlen(str1);
len2=strlen(str2);
for(i=len1-1;i>=r;i--){
str1[i+len2]=str1[i];
}
for(i=r,j=0;j<len2;j++){
str1[i++]=str2[j];
}
printf("%s\n",str1);
return 0;
}
计算正整数各个位之和
计算正整数各个位之和（如:153 各个位数之和位1+5+3=9），并放在数组a 中
#include<stdio.h>
//输入数值个数n,输入正整数，用程序实现输入每个正整数数位数字之和存放在数组a中
int sum(int num);
int main(){
int i,n,num;
printf("输入数值个数n=");
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++){
scanf("%d",&num);
a[i]=sum(num);
}
//打印
printf("输出数组a\n");
int j=1;
for(i=0;i<n;i++){
printf("a[%d]=%d",i,a[i]);
if(j<5){
printf(" ");
j++;
}else{
printf("\n");
j=1;
}
}
return 0;
}
int sum(int num){
int sum=0;
do{
sum += num%10;
num /= 10;
}while(num>0);
return sum;
}
输入十进制变二进制
#include<stdio.h>
//写子程序和程序，实现输入数值转变为二进制，结果存放在a[32]数组中
int main(){
int a[32],num,r,i=0;
printf("请输入十进制数：");
scanf("%d",&num);
printf("%d的二进制数为：",num);
while(num>0){
r=num%2;
a[i++]=r;
num /= 2;
}
while(i--) printf("%d" ,a[i]);
return 0;
}
strcpy 安全拷贝
#include<stdio.h>
#include<string.h>
#define N 4
//功能：将原字符串拷贝到目标字符串，且防止目标字符串溢出
//Dest: 目标字符串 Size：目标字符串缓冲区大小
//Src:原字符串
int my_strcpy_s(char *Dest,int Size,const char *Src){
int i;
//将Src的Size个字符复制到Dest中
for(i=0;i<Size;i++){
Dest[i]=Src[i];
}
return strcmp(Dest,Src); //比较两个字符串相等就返回0，不相等返回其他
}
int main(){
int m;
char str1[N],str2[]="abcfe";
m=my_strcpy_s(str1,N,str2);
printf("%d",m);
return 0;
}结果是0表示没有溢出，结果-1表示溢出
2020复试题3 超车问题
第3题
假设有一条单向通行的隧道，有一天有m辆编号为1到m的小轿车从这条隧道入口进入然后从出口驶出。每辆车只会经过这个隧道一次。全部的车都以恒定的速度经过隧道。
隧道的入口和出口处均设置有交通执法摄像头。从这两个交通执法摄像头，我们可以很清楚地知道每辆车进入和驶出隧道的顺序。没有两辆车会同时进入隧道，并且也没有两辆车会同时驶出隧道。
交通法规禁止车辆在隧道中超车。如果车辆i在隧道中超了车辆j，那么车辆i的车主就会面临罚款。每辆车的车主最多被罚款一次，即使他在隧道中超车多次。
我们对车辆i超车辆j的定义如下：如果车辆i晚于车辆j进入隧道，并且车辆i早于车辆j驶出隧道，那么车辆i就视为超车了车辆j。
给出车辆按时间顺序进入隧道的顺序和驶出隧道的顺序，请你编程计算有多少个车主会被罚款。
（程序运行要求，时间：2sec/空间：256MB）
输入
第一行一个整数m，表示车辆的个数。
第二行m个整数，表示按时间递增的顺序进入隧道的车辆的编号。每个整数满足大小在1到m之间并且互不相同。
第三行m个整数，表示按时间递增的顺序驶出隧道的车辆的编号。每个整数满足大小在1到m之间并且互不相同。
输出
一个整数，表示被罚款的车主的个数。
样例1
输入
3
1 2 3
1 2 3
输出
0
样例2
输入
4
1 3 2 4
4 3 2 1
输出
3
完成要求：
1.分析题意，说明涵盖的知识点和算法。预设所需解题时间。（10分）
答：考察的知识点有数组，和for()循环，if条件判断，break跳出当前循环。
要使用数组保存驶入车辆编号和驶出车辆编号，以及驶入车辆驶出顺序。if条件判断，break用于找出驶入车辆驶出顺序和被罚车主个数。算法时间复杂度为O(m*m)2.给出解题思路，绘出算法流程。（15分）
答：1、记录驶入车俩的驶出顺序，并保存在数组a中
2、第一辆驶入的车不存在超车问题，后驶入的车辆比前驶入的车辆先驶出即记为超车，即a[i]<a[j](j<i)时有超车发生。
流程图3.给出解题代码，注意代码规范并给以适当注释。（40分）
4.给出功能调试过程，说明出现的情况。（15分）
5.分析总结该类问题的其它解决方案。（10分）
6.在此基础上进行问题拓展，说明拓展问题的解决思路。（10分）
答：
1、
2、
- 将驶入车辆的驶出次序保存在数组a[]中；
- 第一辆车不存在超车问题，后驶入的车超前驶入的车记超车
#include<stdio.h>
int main(){
int m,i,k,j,cnt=0;
scanf("%d",&m);
int In[m],Out[m],a[m];
//输入驶入车辆编号
for(i=0;i<m;i++){
scanf("%d",&k);
In[i]=k;
}
//输入驶出车辆编号
for(i=0;i<m;i++){
scanf("%d",&k);
Out[i]=k;
}
//将驶入车辆驶出顺序保存在数组a中
for(i=0;i<m;i++)
for (j=0;j<m;j++){
if(In[i]==Out[j]){
a[i]=j;
break;
}
}
//计算被罚款车主个数
for(i=1;i<m;i++){
for(j=i-1;j>=0;j--){
if(a[i]<a[j]){
cnt++;
break;
}
}
}
printf("%d",cnt);
}
2020复试题1 机器人走路问题
第1题
有一个机器人站在一排长度为m+2的格子上，从左往右依次标号为0, 1, 2, 3, …, m + 1。它现在位于第0个格子。第1个到第m个的每个格子上都分布着一个指令，要么为’L’，要么为’R’。’L’表示如果机器人在这个格子，它只能选择向左跳跃；’R’表示如果机器人在这个格子，它只能选择向右跳跃。机器人在格子0只能选择向右跳跃。
这个机器人想到达格子m+1。机器人在开始跳跃之前，会选择一个正整数d并且每次跳跃最多跳跃d个格子，最少跳跃1个格子。一旦开始跳跃，这个正整数d就无法改变了。这意味着，假设机器人当前位于第i个格子，如果这个格子的指令是’L’，那么机器人可以跳跃到的下一个格子的范围是[max(0, i – d),i-1]；如果这个格子的指令是’R’，那么机器人可以跳跃到的下一个格子的范围是[i+1, min(m+1, i+d)]。
由于机器人的能量是有限的，它每次并不想跳得太远。所以它希望选择一个最小的值d，能够让他从第0个格子经过若干次的跳跃之后到达第m+1个格子。跳跃的次数是没有限制的，只要机器人最终能到达第m+1个格子。而且指令的分布保证了一定可以找到至少一个满足条件的d值。
指令的输入格式为一个字符串s，长度为m。
你需要对t个不同的字符串s，输入满足条件的最小的d值。
编程实现上述问题。
（程序运行要求，时间：2sec/空间：256MB）
输入：
第一行一个整数t(1<= t <=)。
接下来t行，每行一个字符串s(1 <= |s| <= )，只包含’L’和’R’。
数据保证所有s的长度的和不超过)。
输出：
共t行，每行一个正整数d。
样例
输入：
4
R
RRRR
LLR
输出：
1
1
3
完成要求：
1.分析题意，说明涵盖的知识点和算法。预设所需解题时间。（10分）
答：本题涵盖二位数组和指针数组，for 循环的知识2.给出解题思路，绘出算法流程。（15分）
答：3.给出解题代码，注意代码规范并给以适当注释。（40分）
4.给出功能调试过程，说明出现的情况。（15分）
5.分析总结该类问题的其它解决方案。（10分）
6.在此基础上进行问题拓展，说明拓展问题的解决思路。（10分）
#include<stdio.h>
#include<string.h>
#define N 10000
//机器人的最小就是最大的连续的L的个数加1
int main(){
int t ,i,cnt,max=0;
scanf("%d",&t);
char *a[t],str[t][N];
char *p;
for(i=0;i<t;i++)
a[i]=str[i]; //将第i个字符串的首地址赋予指针数组a的第i个元素 ，即对指针数组初始化，不进行初始化程序会报错
for(i=0;i<t;i++)
scanf("%s",a[i]);
for(i=0;i<t;i++){
cnt=0;
max=0;
for(p=a[i];*p!='\0';p++){
if(*p=='L'){
cnt++;
if(cnt>max) max=cnt;
}else{
cnt=0;
}
}
printf("%d\n",max+1);
}
return 0;
}
2020 复试5 上课记忆最多的公式
第5题
你和小军正在上一堂微积分的课。这堂课会持续m分钟，并且在第i分钟之内教授会讲授个公式。
小军虽然对微积分很感兴趣，但是由于他昨晚没有睡好，所以偶尔会打瞌睡。给出一个长度为m的数组t，如果为1，表示小军在第i分钟之内是清醒的；如果为0，表示小军在第i分钟之内是睡着的。当小军是清醒的时候，他会记下这分钟内教授讲授的所有公式；但是他睡着了就是睡着了，什么事情也不会干。
你有一个技巧，可以让小军连续k分钟都保持清醒。但是这个技巧你只能使用一次，你可以在第1到第m-k+1的任意一分钟的开始时刻使用这个技巧。如果你在某一分钟如第i分钟的开始时刻使用了这个技巧，那么小军将会在第j分钟内保持清醒并且记下所有的公式，j满足(i <= j <= i + k – 1)。
你的任务是在合适的时候使用这个技巧，使得小军可以记最多的公式，请你编程帮他计算出最多能记下多少公式。
（程序运行要求，时间：2sec/空间：256MB）
输入
第一行两个整数m和k，含义如题。
第二行m个整数，表示教授每分钟教授的公式的数量。
第三行m个整数，表示小军每分钟的状态，为1是清醒的，为0则睡着了。
满足1 <= k <= m <= )。
输出
一个整数，表示小军记下的最多的公式的数量。
样例
输入
6 3
2 3 5 2 5 3
1 1 0 1 0 0
输出
17
完成要求：
1.分析题意，说明涵盖的知识点和算法。预设所需解题时间。（10分）
答：使用的知识点有一维数组，for循环，if的分支结构2.给出解题思路，绘出算法流程。（15分）
答：解题思路
1、小军同学能记下的公式就是清醒的时刻记下的加上使用技巧后小军多记下的公式的
2、使用技巧后能多清醒的分钟的可能情况有0，1，2，3...k
3、 数组a中保存教授每分钟教授的公式的数量，将数组a的值赋给数组b，并将数组b中小军清醒时刻 的值设为0
4、遍历数组b，计算使用技巧后多记住的公式，并记录最大值
5、记住最多的公式就是清醒时刻记住的公式加上使用技巧后记录的最大值3.给出解题代码，注意代码规范并给以适当注释。（40分）
答：答案如下4.给出功能调试过程，说明出现的情况。（15分）
答：见截图5.分析总结该类问题的其它解决方案。（10分）
答：第一种方法时间复杂度O(m*k)，空间复杂度O(m）
第二种解法思路如下：
1、求清醒时刻记录的的公式和
2、第一次使用技巧位置为i=0；记录下使用魔法（技巧）后多记住的公式
3、下一次 使用技巧的位置为i+1，i位置就不在使用技巧的范围内，如此刻睡着就减去此刻记住的公式，6.在此基础上进行问题拓展，说明拓展问题的解决思路。（10分）
#include<stdio.h>
#include<string.h>
int main(){
int m,k;
int i,j,n,max=0,sum0=0,sum1=0;
scanf("%d %d",&m,&k);
int a[m],b[m],t[m];
//输入教授每分钟教授的公式的数量
for(i=0;i<m;i++)
scanf("%d",&a[i]);
// 输入小军每分钟的状态，为1是清醒的，为0则睡着了
for(i=0;i<m;i++)
scanf("%d",&t[i]);
//辅助数组b 保存小军在睡着的状态下老师教授的公式，清醒状态下记得公式计为0
for(i=0;i<m;i++){
if(t[i]==1){
b[i]=0;
sum0 += a[i];
}else b[i]=a[i];
}
for(i=0;i<m-k+1;i++) {
sum1=0;
for(j=0;j<k;j++)
sum1 += b[i+j];
if(max<sum1) max=sum1;
}
printf("%d\n",sum0+max);
return 0;
}#include<stdio.h>
int main(){
int m,k;
int i,j,max=0,sum0=0,sum1=0;
scanf("%d %d",&m,&k);
int a[m],t[m];
//输入教授每分钟教授的公式的数量
for(i=0;i<m;i++)
scanf("%d",&a[i]);
// 输入小军每分钟的状态，为1是清醒的，为0则睡着了
for(i=0;i<m;i++)
scanf("%d",&t[i]);
//第一次使用魔法，
for(i=0;i<k;i++){
if(t[i]==0)
sum1 += a[i];
}
max=sum1;
//清醒时刻学的公式求和
for(i=0;i<m;i++){
if(t[i]==1)
sum0 += a[i];
}
//一次遍历，从i=1 开始 ，记录每次使用魔法后多记的魔法个数
//滑动数组求解
for(i=k;i<m;i++){
if(t[i-k]==0)
sum1 -= a[i-k];
if(t[i]==0)
sum1 += a[i];
if(sum1>max)
max=sum1;
}
printf("%d\n",sum0+max);
return 0;
}不同路径（有障碍物）
思路和算法
我们用 f(i, j)f(i,j) 来表示从坐标 (0, 0)(0,0) 到坐标 (i, j)(i,j) 的路径总数，u(i, j)u(i,j) 表示坐标 (i, j)(i,j) 是否可行，如果坐标 (i, j)(i,j) 有障碍物，u(i, j) = 0u(i,j)=0，否则 u(i, j) = 1u(i,j)=1。
因为「机器人每次只能向下或者向右移动一步」，所以从坐标 (0, 0)(0,0) 到坐标 (i, j)(i,j) 的路径总数的值只取决于从坐标 (0, 0)(0,0) 到坐标 (i – 1, j)(i−1,j) 的路径总数和从坐标 (0, 0)(0,0) 到坐标 (i, j – 1)(i,j−1) 的路径总数，即 f(i, j)f(i,j) 只能通过 f(i – 1, j)f(i−1,j) 和 f(i, j – 1)f(i,j−1) 转移得到。当坐标 (i, j)(i,j) 本身有障碍的时候，任何路径都到到不了 f(i, j)f(i,j)，此时 f(i, j) = 0f(i,j)=0；下面我们来讨论坐标 (i, j)(i,j) 没有障碍的情况：如果坐标 (i – 1, j)(i−1,j) 没有障碍，那么就意味着从坐标 (i – 1, j)(i−1,j) 可以走到 (i, j)(i,j)，即 (i – 1, j)(i−1,j) 位置对 f(i, j)f(i,j) 的贡献为 f(i – 1, j)f(i−1,j)，同理，当坐标 (i, j – 1)(i,j−1) 没有障碍的时候，(i, j – 1)(i,j−1) 位置对 f(i, j)f(i,j) 的贡献为 f(i, j – 1)f(i,j−1)。综上所述，我们可以得到这样的动态规划转移方程：
f(i, j) = \left { \begin{aligned} 0 & , & u(i, j) = 0 \ f(i – 1, j) + f(i, j – 1) & , & u(i, j) \neq 0 \end{aligned} \right.
f(i,j)={
0
f(i−1,j)+f(i,j−1)
,
,
u(i,j)=0
u(i,j)
=0
很显然我们可以给出一个时间复杂度 O(nm)O(nm) 并且空间复杂度也是 O(nm)O(nm) 的实现，由于这里 f(i, j)f(i,j) 只与 f(i – 1, j)f(i−1,j) 和 f(i, j – 1)f(i,j−1) 相关，我们可以运用「滚动数组思想」把空间复杂度优化称 O(m)O(m)。「滚动数组思想」是一种常见的动态规划优化方法，在我们的题目中已经多次使用到，例如「剑指 Offer 46. 把数字翻译成字符串」、「70. 爬楼梯」等，当我们定义的状态在动态规划的转移方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度「降维」。如果你还不知道什么是「滚动数组思想」，一定要查阅相关资料进行学习哦。
代码中给出了使用「滚动数组思想」优化后的实现。
回顾这道题，其实这类动态规划的题目在题库中也出现过多次，例如「221. 最大正方形」、「1162. 地图分析」等。他们都以二维坐标作为状态，大多数都可以使用滚动数组进行优化。如果我们熟悉这类问题，可以一眼看出这是一个动态规划问题。当我们不熟悉的时候，怎么想到用动态规划来解决这个问题呢？我们需要从问题本身出发，寻找一些有用的信息，例如本题中：
(i, j)(i,j) 位置只能从 (i – 1, j)(i−1,j) 和 (i, j – 1)(i,j−1) 走到，这样的条件就是在告诉我们这里转移是 「无后效性」 的，f(i, j)f(i,j) 和任何的 f(i’, j’)(i’ > i, j’ > j)f(i ′,j ′)(i ′>i,j ′>j) 无关。
动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int m,n;
scanf("%d %d" ,&m,&n);
int i,j;
int a[n][m];
for(i=0;i<n;i++)
for(j=0;j<m;j++){
scanf("%d",&a[i][j]);
}
int f[m];
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%4d",a[i][j]);
}
printf("\n");
}
memset(f, 0, sizeof(f));
f[0] = (a[0][0] == 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 1) {
f[j] = 0;
printf("%4d",f[j]);
continue;
}
if (j - 1 >= 0 && a[i][j - 1] == 0) {
f[j] += f[j - 1];
}
printf("%4d",f[j]);
}
printf("\n");
}
// for(int i=0;i<m;i++)printf("%d",f[i]);
return 0;
}滑动数组的思想是用f[m]代替f[n][m]，数组f[m]的值会更新n次，如
第一次 f1[m]={1,1,1}
第二次更新时f[0]不变，f2[0]=f1[0]，f2[1]=f2[0]+f1[1]
f[j] = f[j - 1] + f[j] 对于此公式由于f[j]之前的数据已经更新过，
即 f[j]之前数组保存的是第 j 次更新的数据（第 j 行的数据，从1开始数）。
f[j]以及其之后的数据都是没更新过的，即数组保存的是第 j -1次更新的数据（第 j-1 行的数据，从1开始数）。
故f[j] = f[j - 1] + f[j] 就是f[i][j]=f[i][j-1]+f[i-1][j]
算法时间复杂度为O(mn)，空间复杂度为O(m)
请登录后发表评论
注册