欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

17年微软笔试题

程序员文章站 2024-01-10 10:42:52
...
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;

/*
* 儿子在父亲后面跟父亲一起跑步
* 父亲的起点在x,儿子的起点在y
* 父亲速度为每步x米
* 父亲总共跑了 n steps
* 求儿子的跑步速度(m/step)
* 使得儿子在跑步过程中与父亲重合的
* 步子是最多的
* 儿子第一步必须踩在父亲的脚印上
* 输出 最多重合步数和 儿子的速度
* 思路: 儿子第一步必须踩在父亲的脚印上
* 因此,儿子第一步有n 个选择,决定了n 种速度
* 对每一种速度 计算和父亲重合的步数
**/
vector<int> followTheFootStep(int positionOfFather,int positionOfSon,int speed,int steps){
 		
 		vector<int> fpoint;
 		int samepoint = 0,maxpoint = 0;
 		int velocity = 0,maxv = 0;
 		/* 终点 位置 */
 		int fend = positionOfFather + speed * steps;
 		cout<<fend<<endl;
 		// 父亲的每一个脚印
 		for(int i = 0; i <= steps; i++){
 			fpoint.push_back(positionOfFather+i*speed);
 		}
 		for(int i = 0; i <= steps; i++){
 			int sstep = fpoint[i] - positionOfSon;
 			int spos = positionOfSon;
 			samepoint = 0;
 			velocity = 0;
 			for(int i = 1; spos <= fend; i++){
 				spos = spos +sstep;
 				if(find(fpoint.begin(),fpoint.end(),spos) != fpoint.end()){
 					samepoint++;
 					velocity = sstep;
 				}
 				if (samepoint >= maxpoint){
 						maxpoint = samepoint;
 						maxv = velocity;
 					}
 				if (spos >= fend){
 					break;
 					
 				}
 			}
 		}
 		vector<int> res;
 		res.push_back(maxpoint);
 		res.push_back(maxv);
 		return res;
 	}

int main(){
	cout<<followTheFootStep(13,5,9,4)[0]<<endl;
}

相关标签: 微软笔试