【www.gbppp.com--题目解答】
2011 各大IT公司笔试面试题目
分类: C++ 语法知识2012-02-12 11:05 563人阅读 评论(1) 收藏 举报
2011.10.17百度面试题
1、进程切换需要注意哪些问题?
保存处理器PC寄存器的值到被中止进程的私有堆栈; 保存处理器PSW寄存器的值到被中止进程的私有堆栈; 保存处理器SP寄存器的值到被中止进程的进程控制块;
保存处理器其他寄存器的值到被中止进程的私有堆栈; 自侍运行进程的进程控制块取SP值并存入处理器的寄存器SP; 自侍运行进程的私有堆栈恢复处理器各寄存器的值;
自侍运行进程的私有堆栈中弹出PSW值并送入处理器的PSW; 自侍运行进程的私有堆栈中弹出PC值并送入处理器的PC。
2、输入一个升序数组,然后在数组中快速寻找两个数字,其和等于一个给定的值。
这个编程之美上面有这个题目的,很简单的,用两个指针一个指向数组前面,一个指向数组的后面,遍历一遍就可以了。
3、有一个名人和很多平民在一块,平民都认识这个名人,但是这个名人不认识任何一个平民,任意两个平民之间是否认识是未知的,请设计一个算法,快速找出这些人中的那个名人。 已知已经实现了一个函数 bool know(int a,int b) 这个函数返回true的时候,表明a认识b,返回false的时候表明a不认识b。
思路:首先将n个人分为n/2组,每一组有2个人,然后每个组的两个人调用这个know函数,假设为know(a,b),返回true的时候说明a认识b,则a肯定不是名人,a可以排除掉了,依次类推,每个组都调用这个函数依次,那么n个人中就有n/2个人被排除掉了,数据规模将为n/2。同理在剩下的n/2个人中在使用这个方法,那么规模就会将为n/4,这样所有的遍历次数为n/2+n/4+n/8+........ 这个一个等比数列,时间复杂度为o(n)。
4、判断一个自然数是否是某个数的平方。当然不能使用开方运算。
方法1:
遍历从1到N的数字,求取平方并和N进行比较。
如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。
复杂度为O(n^0.5)。
方法2:
使用二分查找法,对1到N之间的数字进行判断。
复杂度为O(log n)。
方法3:
由于
(n+1)^2
=n^2 + 2n + 1,
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到这些项构成了等差数列(每项之间相差2)。
所以我们可以比较 N-1, N - 1 - 3, N - 1 - 3 - 5 ... 和0的关系。
如果大于0,则继续减;如果等于0,则成功退出;如果小于 0,则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些。
例如:3^2 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 5
4^2 = 16 = 1 + 2*1 + 1 + 2*2+1 + 2*3+1
view plain
1.
2.
3.
4.
5.
6.
7.
8.
9. int square(int n) { int i = 1; n = n - i; while( n > 0 ) { i += 2; n -= i; }
10. if( n == 0 ) //是某个数的平方
11. return 1;
12. else //不是某个数的平方
13. return 0;
14. }
百度2011.10.16校园招聘会笔试题
一、算法设计
1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。
思路:这个使用数学中的极坐标来解决,先调用[s1,t1]随机产生一个数r,归一化后乘以半径,得到R*(r-s1)/(t1-s1),然后在调用
[s2,t2]随机产生一个数a,归一化后得到角度:360*(a-s2)/(t2-s2)
2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。
思路:如果用户查询的数量小于m,那么直接就存起来。如果用户查询的数量大于m,假设为m+i,那么在1-----m+i之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i),如果选择的是后面i条记录中的查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i),当查询记录量很大的时候,m/(m+i)== (m-1)/(m+i),所以每个query被抽中的概率是相等的。
3、C++ STL中vector的相关问题:
(1)、调用push_back时,其内部的内存分配是如何进行的?
(2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作?
vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的时候,这块空间会让某种方式扩展,但是你删除数据的时候,它却不会缩小。
vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据了,未清内存,因为vector的capacity容量未变化,系统维护一个的默认值。
有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}
事实上,vector根本就不管内存,它只是负责向内存管理框架acquire/release内存,内存管理框架如果发现内存不够了,就malloc,但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存,因为内存分配在stl的底层:stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存),所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off
一般的STL内存管理器allocator都是用内存池来管理内存的,所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量,而不是真的把内存归还给系统。这样做一是为了避免内存碎片,二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端,服务端需做一个异常客户端行为的过滤系统,设服务器在某一刻收到客户端A的一个请求,则1分钟内的客户端任何其它请求都需要被过滤,现知每一客户端都有一个IPv6地址可作为其ID,客户端个数太多,以至于无法全部放到单台服务器的内存hash表中,现需简单设计一个系统,使用支持高效的过滤,可使用多台机器,但要求使用的机器越少越好,请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数:
如p([1,2,3])输出:
[123]、[132]、[213]、[231]、[321]、[323]
求一个组合函数
如p([1,2,3])输出:
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
这两问可以用伪代码。
网易游戏2011.10.15校园招聘会笔试题
1、对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。
2、如果X大于0并小于65536,用移位法计算X乘以255的值为: (X<<8)-X
X<<8-X是不对的,因为移位运算符的优先级没有减号的优先级高,首先计算8-X为0,X左移0位还是8。
3、一个包含n个节点的四叉树,每个节点都有四个指向孩子节点的指针,这4n个指针中有 3n+1 个空指针。
4、以下两个语句的区别是:第一个动态申请的空间里面的值是随机值,第二个进行了初始化,里面的值为0
1.
2. int *p1 = new int[10]; int *p2 = new int[10]();
5、计算机在内存中存储数据时使用了大、小端模式,请分别写出A=0X123456在不同情况下的首字节是,大端模式:0X12 小端模式:0X56 X86结构的计算机使用 小端 模式。
一般来说,大部分用户的操作系统(如windows, FreeBsd,Linux)是小端模式的。少部分,如MAC OS,是大端模式 的。
6、在游戏设计中,经常会根据不同的游戏状态调用不同的函数,我们可以通过函数指针来实现这一功能,请声明一个参数为int *,返回值为int的函数指针:
int (*fun)(int *)
7、下面程序运行后的结果为:to test something
1.
2. char str[] = "glad to test something"; char *p = str;
3.
4.
5.
6.
7. p++; int *p1 = static_cast<int *>(p); p1++; p = static_cast<char *>(p1); printf("result is %s\n",p); 8、在一冒险游戏里,你见到一个宝箱,身上有N把钥匙,其中一把可以打开宝箱,假如没有任何提示,随机尝试,问:
(1)恰好第K次(1=<K<=N)打开宝箱的概率是多少。 (1-1/n)*(1-1/(n-1))*(1-1/(n-2))***(1/(n-k+1)) = 1/n
(2)平均需要尝试多少次。
这个就是求期望值 由于每次打开宝箱的概率都是1/n,则期望值为: 1*(1/n)+2*(1/n)+3*(1/n)+......+n*(1/n) = (n+1)/2
亚信联创2011.9.17招聘会笔试题
1、对于如下程序: 1.
2.
3.
4.
5.
6.
7.
8.
9. #include <iostream> using namespace std; class A { public: A() { cout<<"A"<<endl; }
10. }; 11.
12. int main(void)
13. {
14. A a[4], b,*p;
15. }
会输出多少个A?( C )
A、2 B、3 C、5 D、6
p只是一个对象指针,并没有指向一个对象的内存空间,所以没有调用构造函数。
2、头文件中的 ifndef/define/endif 有什么作用?
答:防止该头文件被重复引用,避免变量、类型等被重新定义 。
3、const 有什么用途?(请至少说明两种)
答:(1)可以定义 const 常量。
(2)const可以修饰函数的参数、返回值,甚至函数的定义体。被const修饰的东西都受到强制保护,可以预防意外的变动,能提高程序的健壮性。
4、如下的字符串函数,用于生存一个字符串 ”连接号码异常” ,并返回它的指针
1.
2.
3. char* strfun() { char str[20];
4.
5.
6.
7.
8.
9. strcpy(str, “连接号码异常”); printf(“%s \n”, str); //printf语句1 return str; } void main() {
10. char *pstr = strfun();
11. printf("%s \n", pstr); //printf语句2
12. }
问题1 : printf语句1和printf语句2哪个能在屏幕上正在打印出来?
问题2 : 如果不能正常在屏幕上打印出字符串,请说明原因。
问题3 : 如果不修改strfun的声明,请问该如何修改上述程序的错误。
答:
问题1:语句1可以正常打印,语句2不能正常打印;
问题2:语句2使用的指针所指向的内存空间str[20],在函数strfun返回时已经被释放了;
问题3:可以将函数strfun中的语句char str[20];改为char *str = new char[20];
5、下面是交换两个double型数据的函数, 1.
2.
3.
4.
5.
6.
7.
8.
9. void swap( double* p1, double* p2 ) { double *p; *p = *p1; *p1 = *p2; *p2 = *p; } void main() {
10. double a = 0.1;
11. double b = 0.2;
12. swap( &a, &b );
13. }
请找出上述代码的错误,指出错误的原因,并改正。
答:函数swap中混淆了double型指针与double型变量的差别,对于一个未初始化的指针访问其内存空间是非常危险的。对swap函数修改如下:
1.
2.
3.
4.
5.
6.
7. void swap( double* p1, double* p2 ) { double p; p = *p1; *p1 = *p2; *p2 =p; }
各大互联网公司前端笔试面试题–JavaScript篇
1.JavaScript是一门什么样的语言,它有哪些特点?
没有标准答案。
2.JavaScript的数据类型都有什么?
基本数据类型:String,boolean,Number,Undefined, Null
引用数据类型:Object(Array,Date,RegExp,Function)
那么问题来了,如何判断某变量是否为数组数据类型?
方法一.判断其是否具有“数组性质”,如slice()方法。可自己给该变量定义slice方法,故有时会失效
方法二.objinstanceof Array 在某些IE版本中不正确
方法三.方法一二皆有漏洞,在ECMA Script5中定义了新方法Array.isArray(), 保证其兼容性,最好的方法如下:
3.已知ID的Input输入框,希望获取这个输入框的输入值,怎么做?(不使用第三方框架)
4.希望获取到页面中所有的checkbox怎么做?(不使用第三方框架)
5.设置一个已知ID的DIV的html内容为xxxx,字体颜色设置为黑色(不使用第三方框架)
6.当一个DOM节点被点击时候,我们希望能够执行一个函数,应该怎么做? 直接在DOM里绑定事件:<div onclick=”test()”></div>
在JS里通过onclick绑定:xxx.onclick = test
通过事件添加进行绑定:addEventListener(xxx, „click‟, test) 【大型公司笔试面试】
那么问题来了,Javascript的事件流模型都有什么?
“事件冒泡”:事件开始由最具体的元素接受,然后逐级向上传播
“事件捕捉”:事件由最不具体的节点先接收,然后逐级向下,一直到最具体的
“DOM事件流”:三个阶段:事件捕捉,目标阶段,事件冒泡
7.什么是Ajax和JSON,它们的优缺点。
Ajax是异步JavaScript和XML,用于在Web页面中实现异步数据交互。 优点:
可以使得页面不重载全部内容的情况下加载局部内容,降低数据传输量 避免用户不断刷新或者跳转页面,提高用户体验
缺点:
对搜索引擎不友好(
要实现ajax下的前后退功能成本较大
可能造成请求数的增加
跨域问题限制
JSON是一种轻量级的数据交换格式,ECMA的一个子集
优点:轻量级、易于人的阅读和编写,便于机器(JavaScript)解析,支持复合数据类型(数组、对象、字符串、数字)
8.看下列代码输出为何?解释原因。
解释:Undefined是一个只有一个值的数据类型,这个值就是“undefined”,在使用var声明变量但并未对其赋值进行初始化时,这个变量的值就是undefined。而b由于未声明将报错。注意未申明的变量和声明了未赋值的是不一样的。
9.看下列代码,输出什么?解释原因。
解释:null是一个只有一个值的数据类型,这个值就是null。表示一个空指针对象,所以用typeof检测会返回”object”。
10.看下列代码,输出什么?解释原因。
undefined与null相等,但不恒等(===)
一个是number一个是string时,会尝试将string转换为number
尝试将boolean转换为number,0或1
尝试将Object转换成number或string,取决于另外一个对比量的类型
所以,对于0、空字符串的判断,建议使用 “===” 。“===”会先判断两边的值类型,类型不匹配时为false。
那么问题来了,看下面的代码,输出什么,foo的类型为什么?
执行完后foo的值为111,foo的类型为Number。
执行完后foo的值为113,foo的类型为String。
11.看代码给答案。
Java试题 1. 选择题
1) 定义如下数组,操作正确的是(D)
int[] numArray = {1,2,3};
A) numArray [3] = 300 B) numArray[0].length C) numArray++ D) numArray.length 2) 定义如下二维数组,操作错误的是(D)
int[][] numArray = {{1,2},{3}}
A) numArray[0][1]=200 B) numArray[0].length C) numArray.length D) numArray[1][1]=100 3) 以下程序代码错误的是(D)
abstract class Parent{} class ChildA extends Parent{} abstract class ChildB extends Parent{} A)Parent p = new ChildA();
B)Parent p = new Parent(){void sysHello(){}};
C)ChildA a = new ChildA(); D)Parent p = new ChildB(); 4) 设 int x = 1;int y = 2;float z = 2;则表达式值 x/y;x/z分别是(D)
A )0.5 0.5 B) 0 0 C) 0.5 0 D) 0 0.5 5) 设 int x = 1;int y = 2;int z = 3;则表达式 y+=z--/x++的值是(D)
A) 3 B) 3.5 C) 4 D) 5 6) 下列语句执行后,c的值是(D)
int a = 10; int b = 18; int c = 30; switch(b-a){
case 8: c++; case 9:c+=2 case 10:c+=3; default : c/b;
}
A) 31 B) 32 C) 33 D) 2
2. 程序分析题
1) 计算随机生成整数数组奇数与偶数的比例(程序填空)【大型公司笔试面试】
/**
* 计算随机生成整数数组奇数与偶数的比例 * */
public class CalOddRate { /** * 生成给定数量的0 到10000随机整数,并把存储到数组中 * @param count 生成随机整数的数量 * @return 生成的随机数组 */ int[] generateArray(int count){ int[] numArray = for(int i=0;i<count;i++){ numArray[i] = (int)(Math.random()); System.out.println("numArray["+i+"]="+numArray[i]); } return numArray; } /** * 计算给定数组的奇数与偶数的比例 * @param numArray 要计算奇数与偶数比例的数组 * @return 奇数的比例 */ public double calOddRate(int[] numArray){ int count = numArray.length; oddNum = 0; for(){ if){ //判断是否为奇数 oddNum++; } } return oddNum/count; } public static void main(String[] args) { CalOddRate calOddRate = new CalOddRate(); int[] numArray = calOddRate.generateArray(4); double oddRate = calOddRate.calOddRate(numArray); System.out.println("奇数的比例为:"+oddRate*100+"%");
}
}
2) 请写出程序运行结果
class Parent{ static{ System.out.println("A"); } public Parent(){ System.out.println("B"); } public Parent(String name){ System.out.println("C"); } }
class Child extends Parent{ public Child(){ System.out.println("D"); } public Child(String name){ this(); System.out.println("E"); } }
public class Test { public void printTest(String name){ try{ if("tester".equals(name) || 1/0 == 1){ new Child(name); }else{ new Child(); } }catch(Exception ex){ System.out.println("F"); }finally{ System.out.println("G"); } } public static void main(String[] args) { Test test = new Test(); test.printTest("tester");
} }
输出结果:
A B D E G F G
数据库试题
1. 如下有学生表(Student)、课程表(Course)和成绩表(Grade),根据要求写出
相关SQL
(Student)
(Course)
(Grade)
1) 写出每门课程都大于等于85分的学生信息:S_ID(学生编号)、S_NAME
(学生姓名)
或
2) 计算出每位学生的平均成绩,输出:S_NAME(学生姓名),平均成绩
3) 查询出每位学生成绩最高的课程,输出:S_NAME(学生姓名)、C_NAME(课
程名称)、G_SCORE(分数)
或
算法笔试题
1、将一整数逆序后放入一数组中(要求递归实现) void convert(int *result, int n) { if(n>=10)
convert(result+1, n/10); *result = n%10;
}
int main(int argc, char* argv[]) {
int n = 123456789, result[20] = {}; convert(result, n); printf("%d:", n); for(int i=0; i<9; i++)
printf("%d", result[i]); }
2、求高于平均分的学生学号及成绩(学号和成绩人工输入)double find(int total, int n) { int number, score, average; scanf("%d", &number); if(number != 0) { scanf("%d", &score);
average = find(total + score, n+1); if(score >= average)
printf("%d:%d\n", number, score);
return average; } else { printf("Average = %d\n", total/n); return total/n; }
}
int main(int argc, char* argv[]) { find(0, 0); }
3、递归实现回文判断(如:abcdedbca就是回文,判断一个面
试者对递归理解的简单程序) int find(char *str, int n) { if(n <= 1)
return 1;
else if(str[0] == str[n-1])
return find(str+1, n-2); else
return 0;
}
int main(int argc, char* argv[]) {
char *str = "abcdedcba";
printf("%s: %s\n", str, find(str, strlen(str)) ?
"Yes" : "No");
}
4、组合问题(从M个不同字符中任取N个字符的所有组合) void find(char *source, char *result, int n) { if(n == 1) { while(*source)
printf("%s%c\n", result, *source++);
} else { int i, j;
for(i=0; source[i] != 0; i++); for(j=0; result[j] != 0; j++); for(; i >= n; i--) { result[j] = *source++; result[j+1] = '\0'; find(source, result, n-1); }
}
}
int main(int argc, char* argv[]) { int const n = 3;
char *source = "ABCDE", result[n+1] = {0}; if(n>0 && strlen(source)>0 && n<=strlen(source))
find(source, result, 3); }
5、分解成质因数(如435234=251*17*17*3*2,据说是华为笔试题)
void prim(int m, int n) { if(m > n) { while(m%n != 0)
n++; m /= n; prim(m, n); printf("%d*", n);
}
}
int main(int argc, char* argv[]) { int n = 435234; printf("%d=", n); prim(n, 2); }
6、寻找迷宫的一条出路,o:通路; X:障碍。(大家经常谈到的一个小算法题) #define MAX_SIZE 8 int H[4] = { 0, 1, 0, -1 }; int V[4] = { -1, 0, 1, 0 }; char Maze[MAX_SIZE][MAX_SIZE] = {
{'X','X','X','X','X','X','X','X'}, {'o','o','o','o','o','X','X','X'}, {'X','o','X','X','o','o','o','X'}, {'X','o','X','X','o','X','X','o'}, {'X','o','X','X','X','X','X','X'}, {'X','o','X','X','o','o','o','X'}, {'X','o','o','o','o','X','o','o'}, {'X','X','X','X','X','X','X','X'} };
void FindPath(int X, int Y) {
if(X == MAX_SIZE || Y == MAX_SIZE) {
for(int i = 0; i < MAX_SIZE; i++)
for(int j = 0; j < MAX_SIZE; j++)
printf("%c%c", Maze[i][j], j <
MAX_SIZE-1 ? ' ' : '\n');
}
else
for(int k = 0; k < 4; k++)
if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE
&& 'o' == Maze[X][Y]) {
Maze[X][Y] = ' ';
FindPath(X+V[k], Y+H[k]); Maze[X][Y] = 'o';
}
}
int main(int argc, char* argv[]) {
FindPath(1,0); }
7、随机分配座位,共50个学生,使学号相邻的同学座位不能相邻(早些时候用C#写的,没有用C改写)。 static void Main(string[] args) { int Tmp = 0, Count = 50; int[] Seats = new int[Count]; bool[] Students = new bool[Count];
System.Random RandStudent=new System.Random();
Students[Seats[0]=RandStudent.Next(0,Count)]
= true;
for(int i = 1; i < Count; ) {
Tmp = (int)RandStudent.Next(0, Count); if((!Students[Tmp]) && (Seats[i-1]-Tmp!=1) &&
(Seats[i-1] - Tmp) != -1) { Seats[i++] = Tmp; Students[Tmp] = true;
}
}
foreach(int Student in Seats)
System.Console.Write(Student + " "); System.Console.Read();
}
8、求网格中的黑点分布。现有6*7的网格,在某些格子中有黑点,已知各行与各列中有黑点的点数之和,请在这张网格中画出黑点的位置。(这是一网友提出的题目,说是他笔试时遇到算法题) #define ROWS 6 #define COLS 7 // 各行黑点数和的情况
int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0}; // 各列黑点数和的情况
int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1};
int iCount, iFound;
int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS]; int Set(int iRowNo) {
if(iRowNo == ROWS) {
for(int iColNo=0; iColNo < COLS && iSumC[iColNo]
==iPointsC[iColNo]; iColNo++) if(iColNo == COLS-1) {
printf("\nNo.%d:\n", ++iCount); for(int i=0; i < ROWS; i++) for(int j=0; j < COLS; j++) printf("%d%c", Grid[i][j],
(j+1) % COLS ? ' ' : '\n');
iFound = 1; // iFound = 1,有解
} } else {
for(int iColNo = 0; iColNo < COLS; iColNo++) {
if(iPointsR[iRowNo] == 0) {
Set(iRowNo + 1); }
else if(Grid[iRowNo][iColNo] == 0) {
Grid[iRowNo][iColNo] = 1; iSumR[iRowNo]++; iSumC[iColNo]++;
if(iSumR[iRowNo] < iPointsR[iRowNo] &&
iSumC[iColNo] <= iPointsC[iColNo]) Set(iRowNo); else if(iSumR[iRowNo] ==
iPointsR[iRowNo] && iRowNo < ROWS)
Set(iRowNo + 1);
Grid[iRowNo][iColNo] = 0; iSumR[iRowNo]--; iSumC[iColNo]--;
}
}
}
return iFound; // 用于判断是否有解
}
int main(int argc, char* argv[]) {
if(!Set(0))
printf("Failure!");
} 9、有4种面值的邮票很多枚,这4种邮票面值分别1, 4, 12, 21,现从多张中最多任取5张进行组合,求取出这些邮票的最大连续组合值。(据说是华为2003年校园招聘笔试题) #define N 5 #define M 5
int k, Found, Flag[N];
int Stamp[M] = {0, 1, 4, 12, 21}; // 在剩余张数n中组合出面值和Value int Combine(int n, int Value) {
if(n >= 0 && Value == 0) { Found = 1; int Sum = 0;
for(int i = 0; i < N && Flag[i] != 0; i++) { Sum += Stamp[Flag[i]];
printf("%d ", Stamp[Flag[i]]);
}
printf("\tSum=%d\n\n", Sum);
} else for(int i=1; i<M && !Found && n>0; i++)
if(Value-Stamp[i] >= 0) { Flag[k++] = i;
Combine(n-1, Value-Stamp[i]); Flag[--k] = 0;
}
return Found;
}
int main(int argc, char* argv[]) { for(int i=1; Combine(N, i); i++, Found=0);
}
10、大整数数相乘的问题。(这是2002年在一考研班上遇到的算法题)
void Multiple(char A[], char B[], char C[]) {
int TMP, In=0, LenA = -1, LenB = -1; while(A[++LenA] != '\0')
;
while(B[++LenB] != '\0')
;
int Index, Start = LenA + LenB - 1;
for(int i=LenB-1; i>=0; i--) {
Index = Start--; if(B[i] != '0') {
for(int In = 0, j = LenA-1; j>=0; j--) {
TMP = (C[Index]-'0') + (A[j]-'0') *
(B[i] - '0') + In;
C[Index--] = TMP % 10 + '0'; In = TMP / 10; }
C[Index] = In + '0'; } } }
int main(int argc, char* argv[]) {
char A[] = "21839244444444448880088888889"; char B[] = "38888888888899999999999999988"; char C[sizeof(A) + sizeof(B) - 1];
for(int k=0; k<sizeof(C); k++)
C[k] = '0'; C[sizeof(C)-1] = '\0';
Multiple(A, B, C);
for(int i=0; C[i] != '\0'; i++)
printf("%c", C[i]);
本文来源:http://www.gbppp.com/jy/407925/
推荐访问:担保公司笔试和面试 面试笔试题库