理论说明 该问题解决的是如何快速的求得a的b次方。一般做***是使用了一个循环次数为b的for循环，并在每次循环时都累乘a,这样在b次循环结束时就能获得a的b次方。但是显然这种方法并不是最优的。按照这个策略，当我们循环到第i次时，此时的累乘的结果即为2的i次。那么当我们完成了前16次循环时，我们就得到了a的16次的数字，思考要获得a的32次我们还需要继续完成后续的16次循环吗？答案是否定的，当我们已经获得了a的16次时，我们只需将a的16次对应的数字求平方，我们即可计算出a的32次方，这样后16次乘法运算我们只用了一次平方就就完成了。既然a的32次可以由a的16次求平方取到，那么a的16次呢？...

题目来源和说明 本题来源于2007年清华大学计算机研究生机考真题。 题目描述 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。 输入描述 可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。 输出描述 对于每组数据，输出N的质因数的个数。 样例 输入： 120 输出： 5   简要分析 我们利用上篇博客中所讲的素数筛选法预先筛选出所有可能在题目所给定数据范围内称为素因数的素数。并在程序输入待处理数字n时，依次遍历所有小于n的素数，判断死否为n的因素。若确定某素数为n的因数，则通过试除确定其对应的幂指...

题目来源和说明 题目来源于2009年哈尔滨工业大学计算机研究生机考真题 题目描述 给定一个数字n,要求判断是否是素数（0,1,负数字都是非素数） 样例 输入 13 1 输出 yes no   简要分析 素数判断，从2-sqrt(n)找是否能够整除的因子即可。 C++ 代码 #include<iostream> #include<math.h> using namespace std; bool judge(int x) { if(x<=1) return false; //前计算出来，能够保证sqrt仅算一次 int bound=(int)sqrt(x)+1; /...

题目来源和说明 2011年哈尔滨工业大学计算机研究生机试真题 题目描述 输入两个正整数，求其最小公倍数 样例 输入 10 14 输出 70   简要分析 最小公倍数：两个数字的乘积再除以最大公约数。最大公约数的方法已经再第13记录了。具体的代码如下：  C++ 代码 #include<iostream> using namespace std; int gcd(int a,int b) { //求最大公约数 return b!=0 ? gcd(b,a%b):a; } int main() { int a,b; while(scanf("%d%d",&a,&b)!=E...

题目来源和说明 2011年哈尔滨工业大学计算机研究生机试真题 题目描述 输入两个正整数，求其最大公约数 样例 输入 49 14 输出 7   简要分析 要求a和b的最大公约数： （1）如果a和b全为0，则他们的最大公约数不存在 （2）如果a和b其中之一为0，则他们的最大公约数为a、b中非零的那个； （3）如果a和b都不为0，则使新a=b，新b=a%b，然后重复该过程。 C++ 代码 递归形式： #include<iostream> using namespace std; int gcd(int a,int b) { if(b==0) return a; else return g...

题目来源和说明 题目来源于2008年浙江大学计算机及软件工程研究生机试真题。 题目描述 输入两个不超过整型定义的非负10进制整数A和B(<=2^31-1)，输出A+B的m (1 < m <10)进制数。 样例 输入 8 1300 48 2 1 7 0 输出 2504 1000   简要分析 这个题目是最普通的进制转换，我们只需要求得两数得和并将其转换为m进制输出即可。 C++ 代码 #include<iostream> using namespace std; int ans[50]; int main() { long long a,b; int m; whil...

题目来源和说明 题目来源于王道考研，题目链接如下： https://www.nowcoder.com/questionTerminal/8c3c5dae2c4a4266ba04f993a18e286b 题目描述 读入两个小于10000的正整数A和B，计算A+B。需要注意的是：如果A和B的末尾K（不超过8）位数字相同，请直接输出-1。 样例 输入 1 2 1 11 21 1 108 8 2 36 64 3 0 0 1 输出 3 -1 -1 100   简要分析 这个题目我们依次取出倒数第K个数字即可，如果不相等，则直接退出不再进行判断，返回a+b就行 C++ 代码 #include<ios...

题目来源和说明 本题来源于2005年华中科技大学计算机保研机试真题，试通过本次专题梳理和总结二叉排序树的问题。 题目描述 输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。 样例 输入： 5 1 6 5 9 8 输出： 1 6 5 9 8 1 5 6 8 9 5 8 9 6 1   简要分析 这个程序的主要代码，是节点x插入树T中，保持二叉排序树的性质，即Insert(Node* T,int x)函数。这个主要是递归的思想。如果x<T.c，即插入左子树；如果x>T.c，即插入右子树。还需要特判一下，T是否为空。因为如果不处理T.c就会出问题。T为空，就直接创建一个节点赋值...

题目来源和说明 2006年清华大学计算机研究生机试真题，本题设计二叉树的建立、由二叉树的两种遍历还原二叉树、二叉树的遍历等多种知识点。希望通过本题梳理和总结二叉树的各种知识点~ 题目描述 根据先序和中序遍历，还原二叉树，并后续遍历树，打印结果 样例 输入： ABC BAC FDXEAG XDEFAG 输出： BCA XEDGAF   C++ 代码 #include<iostream> #include<string.h> using namespace std; struct Node { Node *l; Node *r; char c; }Tree[50]; int...

题目来源和说明 2010年北京邮电大学计算机研究生机试真题，我们以这个题为例梳理和总结哈夫曼树的应用。 题目链接：https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=1&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking 题目描述 哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需...

题目来源和说明 该题目来源自王道考研机试，希望通过该题目梳理总结机试中栈的应用问题。 题目描述 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定任何一个左括号都从内到外与它右边最靠近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在写一行标出不能匹配的括号。不能匹配的左括号用“$”标注，不能匹配的右括号用“?”标注。 样例 输入： )(rttyy())sss)( 输出： )(rttyy())sss)( ? ?$   C++ 代码 #include<iostream> #include<stack> using namespa...

题目来源和说明 题目来源自王道考研！在这一节中主要梳理的四贪心的思想，即总是选择“当前最好的选择”。希望通过本节内容掌握贪心的一些基本思想。 题目描述 FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i]...

题目来源和说明 题目是2010年哈尔滨工业大学计算机研究生机试真题，像通过本次例题梳理和掌握简单的查找算法，后续可能会更一期其他难度更大的查找算法 题目描述 输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1） 样例 输入： 2 1 3 0 输出： -1   简要分析 水题不解释啦，看代码吧，相信都能看懂~ C++ 代码 #include<iostream> using namespace std; int buf[200]; int main() { int n; while(scanf("%d",&n)...

题目来源和说明 2001年清华大学计算机研究生机试真题 题目描述 输入一个高度h，输出一个高为h，上底边为h的梯形。 样例 输入：5 输出： ***** ******* ********* *********** *************   简要分析 这道题主要是观察每一行空格和数字的个数。 先看*：第一行h个，第h行则h+(h-1)*2 再看空格：第一行：(h-1)*2个，最后一行0个 分析到这应该for循环就出来了。 C++ 代码 #include<iostream> using namespace std; int main() { int h; while(scanf(...