1. 编程号首页

南京理工-机试真题

编程小号 • • 未分类

南京理工-机试真题20161.求阶乘答案：普通求阶乘的题目，但是需要注意的是int可最大表示12！但题目要求1《=n<=13所以建议long类型packaget2016;publicclassq1{ //因

 

2016

1. 求阶乘

南京理工-机试真题

答案：

普通求阶乘的题目，但是需要注意的是 int 可最大表示 12！ 但题目要求 1《=n<=13 所以建议long类型
 

package t2016;

public class q1 {

	// 因为n《=13，注意溢出，所以用long
	public static long fact(int n) {
		long ret = 1;
		if(n<=1) {
			return 1;
		}
		while(n>=2) {
			ret = ret * n;
			n--;
		}
		return ret;
	}
	
	
	public static void main(String[] args) {
		System.out.println(fact(13));
	}
}

2. 括号匹配

南京理工-机试真题

答案：

通过栈来检测，有如下几种情况

1）错误：栈非空，栈顶内容与右侧不匹配

2）错误：遍历完毕，栈非空，如<<<

3）错误：栈空时，遇到右侧，如>

4）正确：遍历完毕，没有遇到错误，且栈为空；

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */


bool isOk(string str)
{
	stack<char> st;
	for(int i=0; i<str.length(); i++)
	{
		char p = str[i];
		if(p=='[' || p=='{' || p=='(' || p=='<')
		{
			st.push(p);
		}
		else
		{
			// 遇到右侧，且栈空 
			if(st.empty())	return false;
			else
			{
				char temp = st.top();
				// 括号匹配, 退栈 
				if((p==']'&&temp=='[') || 
				(p=='}'&&temp=='{') || 
				(p==')'&&temp=='(') || 
				(p=='>'&&temp=='<'))
				{
					st.pop();
				}
			}
		}
	}
	
	if(st.empty())	return true;
	else	return false;
}


int main(int argc, char** argv) {
	string str;
	string  ret[6];
	int loop = 1;
	for(int i=0; i<loop; i++)
	{
		cin>>str;
		if(isOk(str))	ret[i] = "yes";
		else	ret[i] = "no";
	}
	
	for(int i=0; i<loop; i++)
	{
		cout<< ret[i] << endl;
	}	

	return 0;
}

 

3. 架线方案 图Prim算法

南京理工-机试真题

 

4. 搬箱子 动态规划

南京理工-机试真题

 

答案：

dp[i]表示以i结尾的子序列中LIS的长度。然后我用dp[j](0<=j<i)来表示在i之前的LIS的长度。然后我们可以看到，只有当a[i]>a[j]的时候，我们需要进行判断，是否将a[i]加入到dp[j]当中。为了保证我们每次加入都是得到一个最优的LIS，有两点需要注意：第一，每一次，a[i]都应当加入最大的那个dp[j]，保证局部性质最优，也就是我们需要找到max(dp[j](0<=j<i))；第二，每一次加入之后，我们都应当更新dp[j]的值，显然，dp[i]=dp[j]+1。 如果写成递推公式，我们可以得到

if(dp[i] >= dp[j]) dp[i] = max{dp[i], dp[j]+1}

else  dp[i] = dp[i]。

于是我们就能够得到O(n^2)的动态规划方法的实现：

测试用例：

输入：

7

1 7 3 5 9 4 8

输出：4

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int LIS(int n, int A[]);



//Longest Increasing Subsequence）最长上升子序列
int LIS(int n, int A[])
{
    int dp[n], temp;
    dp[0] = 1;
    for(int i=0; i<n; i++)
    {
        dp[i] = 1;   // 初值
        for(int j=0; j<i; j++)
        {
            // 递推关系式 dp[i]=max{ dp[i], dp[j](0<=j<i))+(a[i]>a[j]?1:0 }
            if(A[i] > A[j])
            {
                temp = dp[j] + 1;
                dp[i] = max(dp[i], temp);
            }
        }
    }
    return dp[n-1];
}



int main() {
    int n, ret, A[1000];
    cin>> n;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &A[i]);
    }
    ret = LIS(n, A);
    cout<< ret << endl;
	return 0;
}

 

5. 树的高度 图的遍历

南京理工-机试真题

 

答案：

即是图的邻接矩阵，DFS即可

注意，问的是距离根节点最远的距离，所以是树的高度h-1

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void initGraph(int n);
int DFS(int n, int root, bool visit[]);

/* 输入样例， output：3
5 5
1 2
1 4
1 5
2 3
*/


#define MAX 999
int G[MAX][MAX];

void initGraph(int n)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)  G[i][j]=0;
    }

}

int DFS(int n, int root, bool visit[])
{
    visit[root] = true;
    int maxSubH = 0, subH;
    for(int i=1; i<n; i++)
    {
        if(G[root][i]==1 && visit[i]==false)
        {
            subH = DFS(n, i, visit);
            if(subH > maxSubH)  maxSubH = subH;
        }
    }
    return maxSubH+1;
}


int main() {
    int N,n, root, x, y, h, dist;
    cin>> N>> root;
    n = N + 1;
    initGraph(n);
    // 还有N-1行
    for(int i=0; i<N-1; i++)
    {
        cin>> x>> y;
        G[x][y] = 1;
        G[y][x] = 1;
    }
    bool visit[n] = {false};
    // h是树的高度，但求的是最远的距离，所以要-1
    h = DFS(n, root, visit);
    dist = h-1;
    cout<< dist<<endl;
	return 0;
}

 

6. 女士优先 字符串替换

南京理工-机试真题

答案：

字符串替代问题，每次检查字符串是否含有“MF”，若有，则将字符串所有的 MF 更新为
FM 即可。

注意：string的库用<string.h>，cpp的库容易出问题

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//int detect()

void mySwap(string str, int p1, int p2)
{
    char temp;
    temp = str[p1];
    str[p1] = str[p2];
    str[p2] = temp;
}


int main() {
    char str[20];
    int p1, p2, loop=0;
    bool flag;
    cin >> str;
    cout << str<< endl;

    int length=strlen(str);
    while(true)
    {
        p1 = 0;
        p2 = 1;
        flag=false;
        while(p2<length)
        {
            if (str[p1]=='M' && str[p2]=='F')
            {
                char temp=str[p1];
                str[p1]=str[p2];
                str[p2]=temp;
                flag=true;
            }
            p1++;
            p2++;
        }

        loop++;
        if(flag == false)   break;
    }
    cout<< loop<< endl;
    cout<<str<<endl;
	return 0;
}

 

 

2015

1. 提取数字位数

输入一个十进制正整数，输出其十进制各位数的和。

例如，输入3，输出3,；输入23，输出5

 

答案：

迭代各个位数，提取结果

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
    int n, sum=0, rest;
    cin >>n;
    rest = n;
    while(rest != 0)
    {
        sum += rest%10;
        rest = rest / 10;
    }
    cout<< sum;
	return 0;
}

2. 母牛生产问题  easy

母牛生产问题，第一年有一头小母牛，3年之后每头母牛每年都生一只小母牛，假设都不死。第n（n>=1）年之后一共有多少头母牛？输出n从1-20的母牛数量

 

答案：

即每隔3年，数量翻倍一次

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
    int sum = 1, i=1;
    for(; i<=20; i++)
    {
        if(i!=1 && (i-1)%3==0)  sum*=2;
        cout<<i<<"年: "<< sum<< endl;
    }
	return 0;
}

 

3. 运动员

南京理工-机试真题

 

答案：

因为N<100，所以最多分13组；用grp表示组数，用A[]数组存储每个组的人数，rest表示余数；即只要前rest个组每个组人数+1，则正好满足；

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
    int A[13];
    int N, grp, m, rest;
    cin>> N;
    grp = N/8+(N%8==0?0:1);
    m = N / grp;
    rest = N % grp;
    for(int i=0; i<grp; i++)
    {
        A[i] = m;
        if(i<rest)  A[i]++;
        // output
        printf("%d ", A[i]);
    }
}

 

4. 十进制数各个位数

南京理工-机试真题

答案：

IDE：devc；就是各个位数，循环

#include <iostream>
#include <stdio.h> 
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */


int main(int argc, char** argv) {
	int temp = 0, sum = 0, a, n;
	cin>> a>> n;
	for(int i=0; i<n; i++)
	{
		temp = 10*temp + a;
		sum += temp;
	}
	cout<<sum<<endl;
	
	return 0;
}

 

5. 素数

南京理工-机试真题

答案：

1. for循环，遍历2-100，给所有数标记是否是素数，存于A[]数组

2. for循环如果A[i]和A[i+2]是素数，即为孪生素数对，输出并count++

3. 检测是否为素数的算法为从2到i*i<n；

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
bool isPrime(int n);



bool isPrime(int n)
{
	if(n==2)	return true;
	bool flag = true;
	for(int i=2; i*i<=n; i++)
	{
		if(n%i==0)	
		{
			flag = false;
			break;
		}
	}
	return flag;
}


int main() {
	bool A[101];
	int count = 0;
	for(int i=2; i<101; i++)
	{
		A[i] = isPrime(i);
	} 
	
	for(int i=2; i<101; i++)
	{
		if(A[i] && A[i+2])
		{
			printf("%d-%d\n", i, i+2);
			count++;
		}
	}
	printf("sum = %d", count);
}

 

6. 分数化为小数 手动除法

南京理工-机试真题

答案：

结果存放到A[], 每次的余数放到rest[]，每次计算得到余数之后，把它和rest数组的每一位进行比价，若存在相同，则说明循环到达了尽头；

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */





int main() {
	int val, M, N, begin, end=100;
	int  A[100], rest[100];
	bool flag = false;
	cin>> M>> N;
	
	rest[0] = M;
	for(int i=0; i<100; i++)
	{
		val = rest[i] * 10;
		A[i] = val/N;
		rest[i+1] = val % N;
		for(int j=0; j<=i; j++)
		{
			// 此时为循环点 
			if(rest[j]==rest[i+1])
			{
				begin = j;
				end = i;
				flag = true;
				break;
			}
		}
		if(flag==true)	break;
	}
	
	//output
	printf("0."); 
	for(int i=0; i<=end; i++){
		
		printf("%d", A[i]);
	}
	printf("    ,start from %d\n", begin+1);
	printf("end = %d", end);
	return 0;
}

 

7. 桶的用法，包括排序，计数

南京理工-机试真题

 

答案：

先把数据存入input[]数组，是便于通过scanf和空格读入数据；

注意：前几行scanf中的%d后面不允许空格，否则无法读入数据；

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

/*
3 1 4 2 1 4 3 4 -1
*/

int main() {
	int bucket[100]={0}, A[30], B[30],input[30], countA=0, countB=0, n, num=0;
	// 输入
	 for(int i=0; i<30; i++)
	 {
	 	scanf("%d", &input[i]);  //注意此处%d后面不允许空格
	 	num++;
	 	if(input[i]==-1)	break;
	 }
	
	//test
//	for(int i=0; i<num; i++)
//	{
//		printf("%d\n", input[i]);
//	}
	
	// 输入，装入桶bucket 
	for(int i=0; i<num; i++)
	{
		n = input[i];
		if(n==-1)	break;
		
		// 首次出现 ,存入B 
		if(bucket[n] == 0)
		{
			B[countB] = n;
			countB++;
		}
		bucket[n]++;
	}
	
	// 输出B
	for(int i=0; i<countB; i++)
	{
		printf("%d:%d   ", B[i], bucket[B[i]]);
	 } 
	 printf("\n");
	// A按降序存放 
	for(int i=99; i>=0; i--)
	{
		if(bucket[i]!=0)
		{
			A[countA] = i;
			countA++;
		}
	 } 
	//输出A 
	for(int i=0; i<countA; i++)
	{
		printf("%d:%d   ", A[i], bucket[A[i]]);
	 } 

	return 0;
}

 

 

2014

1.输入一个整数转换成二进制输出

如输入3，输出11；输入6，输出110

答案：

采用递归法；

递归基：n=0时，return；

递归策略：每次对n/2调用函数，

末尾：输出 n%2;

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */


void toBinary(int n);


// 递归方法 
void toBinary(int n)
{
	if(n==0)	return;
	toBinary(n/2);
	printf("%d", n%2);
}


int main() {
	int n;
	cin>>n;
	toBinary(n);
	return 0;
}

 

 

2. int型和double型的比较

试想32位整型数据所能表示的最大数阶乘。假设y=x!，在32位整型内，x最大为多少y不溢出，输出x和y的值。

答案：

用MAX_INT表示最大int型数，将其转为double，再将其为double类型的

#include <iostream>
#include <vector>
#include <stack>

#include <string.h>
#include <stdio.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */


void toBinary(int n);


double jie(int num)
{
	if(num==0)
		return 1;
	else
		return num*jie(num-1);
}


int main() {
	int maxint=INT_MAX;
	int num=0;
	while(jie(num)<=maxint)
	{
		num++;
	}
	cout<<"保证阶乘不溢出的整型数据最大为\n"<<num-1<<"\n其阶乘为：\n"<<maxint<<endl;

	return 0;
}

 

今天的文章南京理工-机试真题分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/60525.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注