机试考点整理（3）——练习题

亦凉 2021-12-01 11:44 206阅读 0赞

> 斐波那契数列

#include <iostream>
    using namespace std;
    const int mod=1e9+7;
    int f[100005];
    int main()
    { 
    	int n;
    	cin>>n;
    	f[1]=1;
    	f[2]=1;
    	for(int i=3;i<=n;i++)
    	{ 
    		f[i]=(f[i-1]+f[i-2])% mod;
    	}
    	cout<<f[n]<<endl;
    	return 0;
    }

> 旋转矩阵

#include <iostream>
    using namespace std;
    int num[205][205];
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    	{ 
    		for(int j=0;j<m;j++)
    		{ cin>>num[i][j];}
    	}
    
    	for(int i=0; i<m;i++)
    	{ 
    		for(int j=0;j<n;j++)
    		{ 
    			if(j!=n-1)
    			{ 
    				cout<<num[n-1-j][i]<<" ";
    			}else{ 
    				cout<<num[n-1-j][i]<<endl;
    			}
    		}
    	}
    	return 0;
    }

> 最大子矩阵和

//暴力枚举
    #include <iostream>
    using namespace std;
    int A[55][55];
    int main()
    { 
    	int n,m,ans;
    	cin>>n>>m;
    	ans=-1005;
    	for(int i=0;i<n;i++)
    	{ 
    		for(int j=0;j<m;j++)
    		{ 
    			cin>>A[i][j];
    		}
    	}
    	for(int i=0;i<n;i++)
    	{ 
    		for(int j=i;j<n;j++)
    		{ 
    			for(int k=0;k<m;k++)
    			{ 
    				for(int l=k;l<m;l++)
    				{ 
    					int tmp=0;
    					for(int p=i;p<=j;p++)
    					{ 
    					for(int q=k;q<=l;q++)
    					{ 
    						tmp+=A[p][q];
    					}
    					}
    					if(tmp>ans)
    					{ 
    						ans=tmp;
    					}
    				}
    			}
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }

> 去重排序

#include <iostream>
    #include <algorithm>
    using namespace std;
    int num[105],ans[105];
    int main()
    { 
    	int n,m;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{ 
    		cin>>num[i];
    	}
    	sort(num,num+n);
    	m=0;
    	for(int i=0;i<n;i++)
    	{ 
    		if(i!=0&&num[i]!=num[i-1])
    		{ 
    			ans[m++]=num[i-1];
    		}
    	}
    	ans[m++]=num[n-1];
    	cout<<m<<endl;
    	for(int i=0;i<m;i++)
    	{ 
    		if(i !=m-1)
    		{ 
    			cout<<num[i]<< " ";
    		}else{ 
    			cout<<num[i]<<endl;
    		}
    	}
    	return 0;
    }

> 交叉排序

#include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    int A[100005];
    int main()
    { 
    	int N,l1,r1,l2,r2;
    	cin>>N>>l1>>r1>>l2>>r2;
    	for(int i=1;i<=N;i++)
    	{ 
    		cin>>A[i];
    	}
    	sort(A+l1,A+r1+1);
    	sort(A+l2,A+r2+1,greater<int>());
    	for(int i=1;i<=N;i++)
    	{ 
    		if(i!=N)
    		{ 
    			cout<<A[i]<<" ";
    		}else{ 
    			cout<<A[i]<<endl;
    		}
    	}
    }

> 10进制转成R进制

/* R进制 10<=R<=16 A B C D E F 分别表示 10-15 */
    #include <iostream>
    using namespace std;
    char ans[105];
    int main()
    { 
    	int N, R,m,now;
    	cin>>N>>R;
    	if(N<0){ 
    	 cout<<"-";
    	 N=-N;
    	}
    	m=0;
    	while(N)
    	{ 
    		now=N%R;
    		if(now<=9)
    		{ 
    			ans[m++]='0'+now;
    		}else{ 
    			ans[m++]='A'+now-10;
    		}
    		N/=R;
    	}
    	if(m==0)
    	{ 
    		cout<<0;
    	}
    	for(int i=m-1;i>=0;i--)
    	{ 
    		cout<<ans[i];
    	}
    	cout<<endl;
    	while(1)
    	getchar();
    }

> 回文数

#include <iostream>
    using namespace std;
    int num[1005];
    int digit[1005];
    bool judge(int x)
    { 
    	int cnt=0;
    	while(x)
    	{ 
    		digit[cnt++]=x%10;
    		x/=10;
    	}
    	for(int i=0;i<cnt/2;i++)
    	{ 
    		if(digit[i]!=digit[cnt-1-i])
    			return false;
    	}
    	return true;
    }
    int rev(int x)
    { 
    	int ret=0;
    	while(x)
    	{ 
    		ret=ret*10+x%10;
    		x/=10;
    	}
    	return ret;
    }
    int main()
    { 
    	int n,m;
    	cin>>n;
    	m=0;
    	num[m++]=n;
    	while(!judge(n))
    	{ 
    		n+=rev(n);
    		num[m++]=n;
    	}
    	cout<<m-1<<endl;
    	for(int i=0;i<m;i++)
    	{ 
    		if(i !=m-1)
    		{ 
    			cout<<num[i]<<"--->";
    		}else{ 
    			cout<<num[i]<<endl;
    		}
    	}
    	while(1)
    	getchar();
    }

> 机器人转向走路

//注意不是向哪走，而是在当前情况下转体然后再走
    #include <iostream>
    using namespace std;
    int dx[4]={ 0,-1,0,1};//上左下右
    int dy[4]={ 1,0,-1,0};//题目是坐标系/数组不一样的
    char op[15];
    int main()
    { 
    	int n,d,t,nowx,nowy;
    	cin>>n;
    	d=3;
    	nowx=0;
    	nowy=0;
    	for(int i=0;i<n;i++)
    	{ 
    		cin>>op>>t;
    		if(op[0]=='b')
    		{ 
    		 d=(d+2)%4;
    		}else if(op[0]=='l')
    		{ 
    			d=(d+1)%4;
    		}else if(op[0]=='r')
    		{ 
    			d=(d+3)%4;
    		}
    		nowx+=dx[d]*t;
    		nowy+=dy[d]*t;
    		
    	}
    	cout<<nowx<<" "<<nowy<<endl;
    	while(1)
    	getchar();
    	return 0;
    }