创新工厂
- 格式：doc
- 大小：70.00 KB
- 文档页数：10
【一】三道题程序题，要求一个小时做完，而且提前交卷有加分。
题目1：把一串英文句子按单词反序输出。
如："good moring" -> "moring good"。
题目2：输入一个正整数N，输出大于N且最接近这个数的素数。
题目3：用数组实现排序二叉树。
【出处】/user/longt/Article_1790【一解】题目1：我的想法是把句子的每个字符遍历一遍，找到每个单词首字母的位置，然后再倒过来访问。
存放单词首字母序号的结点定义struct Node{Node(int n, Node * p = NULL) {i = n; next = p;}int i; // 存放单词首字母序号Node * next;};句子反序输出char * reverse (char * sentence){int i = 0;Node * first = NULL;if (sentence != NULL && sentence[0] != '\0'){first = new Node(0, NULL); // 判断内存是否申请成功语句此处略去}// 遍历寻找每个单词首字母while (sentence[i] != '\0'){if (sentence[i] == ' ')// 前端插入first = new Node(i+1, first); // 判断内存是否申请成功语句此处略去 i++;}char * r = new char[i+1];Node * p = first;int n = 0;while (p != NULL){for (int j=p->i; j<i; j++,n++){r[n] = sentence[j];}r[n++] = ' ';i = p->i - 1;p = p->next;}r[n-1] = '\0'; // 字符串结束符return r;}题目2：我的想法是写一个质数判断函数，然后从N+1往后开始寻找。
感觉应该有更佳的方法。
判断一个数是否是质数#include <cmath>using namespace std;// 判断一个数是否是质数bool IsPrimeNumber(int n){if (n == 2)return true;if (n % 2 == 0 || n < 3)return false;int end = (int)sqrt((float)n); // 不写在for循环判断中，提高效率for (int i=3; i<=end; i=i+2){if (n % i == 0)return false;}return true;}寻找比N大的最小质数int SearchPN(int n){while (IsPrimeNumber(n+1) == false)n++;return n+1;}题目3：我不知道用数组实现“排序二叉树”和“实现二叉树”有什么区别。
我觉得如果是用数组实现二叉树的话还是很简单的，就是开一个数组，数组中每个元素存放一个树结点，每个树结点包含有“parent”、“leftchild”和“rightchild”三个int。
以下摘自原文作者：“思路：一颗树中每个结点只有唯一一个父亲，而数组中每个元素只能存一个值，所以把这个值存为父亲结点，根节点值定-1就好。
但是要求实现排序二叉树，所以还需要记录每个结点，因此用个pair<T,T>，最后通过数组pair<T,T> tree[] 来实现。
”【二】请问下面这个程序输出是什么？#include <stdio.h>union A{int i;char c[2];};int main(){A a;a.c[0] = 10;a.c[1] = 1;printf("%d", a.i);return0;}【出处】/u/20101012/21/3aa793bb-c8e5-49c7-b72f-ca985b0d5c4e.html?3 2141【二解】union A开辟了一个4字节的空间，如果是x86的电脑，那么是按小端格式(Little-endian)存储数据的，那么A.c[0]指向的就是i的最后一个字节。
举列来说：如果我给A.i赋值为10，那么实际内存中是这么存储的：（关于何为小端格式，请参见/passingcloudss/archive/2011/05/03/2035273.html）地址0 1 2 3数据0x0A 0x00 0x00 0x00c[0]=0x0A，c[1]=0x00，c[2]=0x00，c[3]=0x00；对于未赋值的字节块，编译器在调试版本（DEBUG）会自动填充0xCC，因此本题涉及的内存实际上是这样的：地址0 1 2 3数据0x0A 0x01 0xCC 0xCC最终输出结果应该是0xCCCC010A=-859045622。
这里再重申一下，该结果是在x86电脑的DEBUG模式下的输出！一个诡异的发现，如果把程序改为：#include <stdio.h>union{int i;char c[2];}A;void main(){A.c[0]=10;A.c[1]=1;printf("%d", A.i);}输出结果是0x0000010A=266！引申：通过这道题的方法，我们可以判断CPU是小端格式还是大端格式！【三】笔试题量很小，答题时间1个小时。
1道填空题，9道左右选择题，最后一道编程题。
题目1：对于int a = 65536 + 1024 + 8 + 1；int b = f(a)；执行后b等于多少？int f(int x){int c = 0;while(x != 0){x = x & (x-1);c++;}return c;}题目2：5个骰子，六个面分别标有1~6，现在将五个同时随机投掷，五个点数之和为下面哪个点的概率最大？(A)14 (B)15 (C)17 (D)20题目3：请问c等于多少？unsigned long c = 0;char a = 0x48;char b = 0x52;c = b<<8 | a;题目4：编程题A、B两个量杯，容量分别为M升、N升，现在要用A和B给另一个量杯C盛水K升，C量杯足够大，备用水无限。
编程输出每一个步骤三个杯子中的水量。
比如：输出(0,0,0), (M,0,0)等。
【出处】/blog/769423【三解】题目1：这个程序就是求二进制数中1的个数，所以答案是4。
题目2：思路一：先算每个骰子掷出点数的期望值。
每面的概率都是1/6，单个骰子的期望为1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6 = 3.55个骰子相互独立，期望就是3.5*5=17.5，17或18为最接近的点数，选（C）。
思路二：掷出的点数最小为5，即1+1+1+1+1只有一种可能；掷出的点数最大为30，即6+6+6+6+6也只有一种可能。
点数的分布应该是中间大、两头小，并且应该是左右对称的，所以最可能的点数应该是(5+30)/2=17.5，选（C）。
题目3：b<<8是把b向左位移8位，相当于把b乘以2的8次方，得到0x5200；再和a位或，由于0x5200的后8位是0，位或运算等效于加法运算，得到c=0x5248=21064。
引申：如果c不是定义成unsigned long，而是一个小字节的类型，比如c定义成char型，那么c=0x48。
题目4：这道题比较复杂，我们先来分析一下思路。
首先，不失一般性，不妨设M>N，如果我们能实现 K1=K%N 升，那么只需再用B量杯给C量杯加上 (int)K/N 杯即可。
设M和N的最大公约数为L，于是，不管我们对M和N进行几次和运算或差运算，得到的数仍是L的倍数。
也就是说，不管怎样操作，使用A量杯和B量杯，我们只能得到“L的倍数”升。
注意，这只是说，能实现的一定是L的倍数，但不一定每个L的倍数都能实现。
另一方面，根据数论中的Bezout等式，存在整数a和b，使得aM+bN=L成立。
事实上，假如我们找到了一组满足a0*M+b0*N=L的(a0,b0)，那么对于任意整数t，a=a0+t*N/L，b=b0-t*M/L都能满足aM+bN=L。
所以，我们一定能找到一组a>0、b<0，使aM+bN=L，那么我们只需往C量杯中倒入a杯A量杯的水，再倒走(-b)杯B量杯的水，C量杯中就能得到L升水！结合上面两方面，我们得到，C量杯能实现K升水当且仅当 K1是L的自然数倍。
具体实现的思路如下：先求出M和N的最大公约数L，判断K1是否能够整除L；然后不断给C倒入M升水（中途如果C水量超过N，就倒走N升水），直到C水量为K1；最后再给C中倒入若干次N升水即可。
具体代码如下：打印每次操作void Show(int &i, int A, int B, int C) // i记录操作的次数{cout << i << ".(" << A << "," << B << "," << C << ")" << endl; i++;}辗转相除法求最大公约数int GCD(int M, int N) // 辗转相除法求最大公约数{if (M >= N){if (M%N == 0)return N;elsereturn GCD(M%N, N);}else{if (N%M == 0)return M;elsereturn GCD(M, N%M);}}解法主函数bool Solution(int M, int N, int K){// M, N, K是三个容器的容量// A, B, C是三个容器目前的水量int A=0, B=0, C=0, i=1;int K1 = K % N;int L = GCD(M, N);if (K1%L != 0) // 不可能实现return false;while (C != K1){// A中盛满水倒给CA = M;Show(i, A, B, C);C += A; A = 0;Show(i, A, B, C);// 如果C水量超过N，就倒走Nwhile (C > N){B = N;C -= N;Show(i, A, B, C);B = 0;Show(i, A, B, C);}}// 给C倒上若干杯B中的水while (C != K){B = N;Show(i, A, B, C);B = 0;C += N;Show(i, A, B, C);}return true;}事实上，这个实现方法不是很完美，比如M=5,N=4,K=10，本来只需用2杯A量杯的水即可；但是按照上述算法，是倒入一杯A量杯的水，随后立即倒走一杯B量杯的水，如此往复10次，得到10升，这显然是不明智的。
