2020校招4399游戏开发岗笔试编程题题解

序号四

题目描述：
有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

输入描述：
一行，一个正整数n（1<=n<=1000000）。

输出描述：
输出答案

输入样例：
5
输出样例：
4

解题思路：
可以使用链表中的循环链表依次遍历进行模拟来求解，但是这样稍显笨重，所以这里是使用普通一维数组来完成，可以发现如果想完成循环效果，即下标始终在0到最后一位循环，即index=(index+1)%数组长度，这样就可以保证在求出答案前一直循环遍历数组

//ac代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int a[maxn];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) a[i] = 1;
	int numIn = n;
	int index = 0;
	int numThree = 0;
	while(numIn>1){
		if(a[index] == 1){
			++numThree;
			if(numThree == 3){
				numThree = 0;
				a[index] = -1;
				--numIn;
			}
		}
		index = (index+1)%n;
	}
	for(int i=0;i<n;i++) if(a[i] == 1) cout<<i+1<<endl;
	return 0;
}

---

第三题

小陆每天要写一份工作日报，日报标题含有日期。几年后，他翻开以前的日报，想知道两份日报的日期是否同为星期几，请编程帮助他判断。

本题有些问题，这里只记录如果判断闰年，与根据给出的两个年月日算出相隔时间

#include<bits/stdc++.h>
using namespace std;
int m[13]={365,31,28,31,30,31,30,31,31,30,31,30,31};
int rm[13]={366,31,29,31,30,31,30,31,31,30,31,30,31};

bool isR(int year){
	if(( year % 4 == 0 && year % 100 != 0 ) || year % 400 == 0) return true;
	else return false;
}

int Day(int y1,int m1,int d1,int y2,int m2,int d2){
	//保证始终小的时间在前便于计算
		if(y1>y2){
			int tempm=m1,tempd=d1,tempy=y1;
			m1=m2,d1=d2,y1=y2;
			m2=tempm,d2=tempd,y2=tempy;
		}
		else if(y1==y2&&m1>m2){
			int tempm=m1,tempd=d1;
			m1=m2,d1=d2;
			m2=tempm,d2=tempd;
		}else if(y1==y2&&m1==m2&&d1>d2){
			int temp=d1;
			d1=d2;
			d2=temp;
		}
		//开始计算前后时间的相差天数
		int count=0;
		//先将年份加到目标年前一年 
		while(y1+1<y2){
			if(isR(y1)) count+=rm[0];
			else count+=m[0];
			++y1;
		}
		//再加到目标前一年的12月31日 
		for(int i=m1;i<12;i++){
			if(isR(y1)) count+=rm[i];
			else count+=m[i];
		}
		count+=31-d1;
		//cout<<count<<endl;
		for(int i=1;i<m2;i++){
			if(isR(y2)) count+=rm[i];
			else count+=m[i];
		}
		count+=d2;
		return count;
} 

int main(){
	cout<<Day(1970,1,2,2020,2,7)<<endl;//18298
	return 0;
} 

---

第四题–斐波那契数列变形题

段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？

这个题目如果自己计算出n=1.2.3.4时的结果，会发现他们的结果的规律与斐波那契数列类似，皆是f(n)=f(n-2)+f(n-3)这种类似的，所以可以通过for循环或者递归求解

//ac代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
//int a[maxn];
int main()
{
	int n;
	cin>>n;
	int a1,a2,a3,a4;
	int res1=0,res2=0,res3=0;
	if(n<4){
		if(n==1) cout<<"1 1 0"<<endl;
		else if(n==2) cout<<"2 2 1"<<endl;
		else if(n==3) cout<<"3 4 1"<<endl;
		return 0;
	}
	//只能跳1,2级时
	a1=1;
	a2=2;
	for(int i=3;i<=n;i++){
		a3=a1+a2;
		a1=a2;
		a2=a3;
	}
	res1=a3;
	//只能跳1,2,3 
	a1=1;
	a2=2;
	a3=4; 
	for(int i=4;i<=n;i++){
		a4=a1+a2+a3;
		a1=a2;
		a2=a3;
		a3=a4;
	} 
	res2=a4;
	//只能跳2,3
	a1=0;
	a2=1;
	a3=1;
	for(int i=4;i<=n;i++){
		a4=a1+a2;
		a1=a2;
		a2=a3;
		a3=a4;
	} 
	res3=a4;
	cout<<res1<<" "<<res2<<" "<<res3<<endl;
	return 0;
}